Insider Forgery Cryptanalysis of Two Post-Quantum Multi-Signature Schemes

Abstract:

In 2010, M. Meziani and P.-L. Cayrel presented two post-quantum multi-signature schemes based on the syndrome decoding hard problem and error correcting codes. In this paper, we propose the insider forgery cryptanalysis of M. Meziani et al.s post-quantum multi-signature schemes. In M. Meziani et al.s schemes, the verifier only verifies the final multi-signature and does not check the validity of the partial signatures generated by other signers. Thus the malicious last signer can forge a valid multi-signature by himself/herself on behalf of the group of signers, which can pass the verification of the verifier. Therefore, M. Meziani et al.s post-quantum multi-signature schemes do not meet the security requirements of multi-signature schemes.

• Periodical: Applied Mechanics and Materials (Volume 437)
• Pages: 876-879
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.437.876
• Online since: October 2013
• Authors: Fan Yu Kong*, Lu Hong Diao, Jia Yu, Ya Li Jiang, Da Shui Zhou
• Keywords: Digital Signature, Error Correcting Codes, Multi-Signature Scheme, Post-Quantum Cryptography

References

[1] P. W. Shor: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Journal on Computing, Vol. 26(5) (1997), pp.1484-1509.

DOI: 10.1137/s0097539795293172

[2] M. Ajtai: Generating hard instances of lattice problems (extended abstract), In ACM Symp. on Theory of Computing - STOC (1996), pp.99-108.

DOI: 10.1145/237814.237838

[3] O. Regev: On lattices, learning with errors, random linear codes, and cryptography, In Proc. 37th ACM Symp. on Theory of Computing – STOC (2005), pp.84-93.

DOI: 10.1145/1060590.1060603

[4] C. Peikert and B. Waters: Lossy trapdoor functions and their applications, In Proc. 40th ACM Symp. on Theory of Computing – STOC (2008), pp.187-196.

DOI: 10.1145/1374376.1374406

[5] C. Gentry, C. Peikert, and V. Vaikuntanathan: Trapdoors for hard lattices and new cryptographic constructions, In Proc. 40th ACM Symp. on Theory of Computing – STOC (2008), pp.197-206.

DOI: 10.1145/1374376.1374407

[6] D. Cash, D. Hofheinz, E. Kiltz and C. Peikert: Bonsai Trees, or How to Delegate a Lattice Basis, In Proceedings 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques - Eurocrypt 2010, LNCS 6110, Springer-Verlag (2010).

DOI: 10.1007/978-3-642-13190-5_27

[7] Pierre-Louis Cayrel, Mohammed Meziani: Post-quantum cryptography: code-based signatures, Proceedings of the 2010 international conference on Advances in computer science and information technology, LNCS 6059, Springer-Verlag (2010), pp.82-99.

DOI: 10.1007/978-3-642-13577-4_8

[8] R.J. McEliece: A public-key cryptosystem based on algebraic coding theory, DSN progress report, No. 42-44 (1978), pp.114-116.

[9] M. Finiasz and N. Sendrier: Security bounds for the design of code-based cryptosystems, Advances in Cryptology – Asiacrypt 2009, LNCS 5912, Springer-Verlag (2009), pp.88-105.

DOI: 10.1007/978-3-642-10366-7_6

[10] G. Kabatianskii, E. Krouk, and B. J. M. Smeets: A digital signature scheme based on random error-correcting codes, IMA Int. Conf., LNCS 1355, Springer-Verlag (1997), p.161–167.

DOI: 10.1007/bfb0024461

[11] N. Courtois, M. Finiasz, and N. Sendrier: How to achieve a McEliece-based digital signature scheme, Advances in Cryptology – Asiacrypt 2001, LNCS 2248, Springer-Verlag (2001), pp.157-174.

DOI: 10.1007/3-540-45682-1_10

[12] S. J. Aboud: Two efficient digital multi-signature schemes, Int. J. Soft. Computing. Vol. 2 (2007), pp.113-117.

[13] M. Bellare and G. Neven: Multi-signatures in the plain public-key model and a general forking lemma, In Proc. 13th ACM conference on Computer and Communications Security ACM Press, New York (2006), pp.390-399.

DOI: 10.1145/1180405.1180453

[14] R. D. Díaz, L. H. Encinas and J. M. Masqué: A Multi-signature Scheme Based on the SDLP and on the IFP, In proceedings of the 4th international conference on computational intelligence in security for information systems - CISIS (2011).

DOI: 10.1007/978-3-642-21323-6_17

[15] Mohammed Meziani and Pierre-Louis Cayrel: A Multi-Signature Scheme based on Coding Theory, World Academy of Science, Engineering and Technology, Vol. 63 (2010), pp.244-250.