A Multi-Signature Scheme based on Coding Theory

Authors: Mohammed Meziani, Pierre-Louis Cayrel

Abstract:

In this paper we propose two first non-generic constructions of multisignature scheme based on coding theory. The first system make use of the CFS signature scheme and is secure in random oracle while the second scheme is based on the KKS construction and is a few times. The security of our construction relies on a difficult problems in coding theory: The Syndrome Decoding problem which has been proved NP-complete [4].

Keywords: Post-quantum cryptography, Coding-based cryptography, Digital signature, Multisignature scheme.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1060998

References:

[1] S. Barg. Some New NP-Complete Coding Problems. Probl. Peredachi Inf., 30:23-28, 1994.
[2] M. Bellare and G. Neven. Multi-signatures in the plain public-key model and a general forking lemma. In CCS -06: Proc. of the 13th ACM conference on Computer and communications security, pages 390-399. ACM, 2006.
[3] T. P. Berger, P.-L. Cayrel, P. Gaborit, and A. Otmani. Reducing key length of the McEliece cryptosystem. In Progress in Cryptology - Africacrypt-2009, LNCS, pages 77-97. Springer, 2009.
[4] E. Berlekamp, R. McEliece, and H. van Tilborg. On the inherent intractability of certain coding problems. IEEE Transactions on Information Theory, 24(3):384-386, 1978.
[5] D. J. Bernstein, T. Lange, and C. Peters. Attacking and defending the McEliece cryptosystem. Cryptology ePrint Archive, Report 2008/318, 2008. http://eprint.iacr.org/.
[6] D. Boneh and M. Franklin. Identity-based encryption from the weil pairing. In CRYPTO -01: Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, pages 213-229. Springer, 2001.
[7] D. Boneh, C. Gentry, B. Lynn, and H. Shacham. Aggregate and verifiably encrypted signatures from bilinear maps. In EUROCRYPT, pages 416-432. Springer, 2003.
[8] P.L. Cayrel, A. Otmani, and D. Vergnaud. On Kabatianskii-Krouk- Smeets Signatures. In Proceedings of the first International Workshop on the Arithmetic of Finite Fields (WAIFI 2007), Springer, pages 237-251, Madrid, Spain, June 21-22 2007.
[9] N. Courtois, M. Finiasz, and N. Sendrier. How to achieve a McEliecebased digital signature scheme. In Advances in Cryptology - Asiacrypt- 2001, volume 2248 of LNCS, pages 157-174, Gold Coast, Australia, 2001. Springer.
[10] L. Dallot. Towards a concrete security proof of courtois, finiasz and sendrier signature scheme. Proceedings of WEWoRC 2007, Bochum, GermanyÔÇ× 2007. http://users.info.unicaen.fr/~ldallot/download/articles/ CFSProof-dallot.pdf.
[11] M. Finiasz. Nouvelles constructions utilisant des codes correcteurs d-erreurs en cryptographie à clef publique. PhD thesis, INRIA-Ecole polytechnique, October 2004.
[12] M. Finiasz and N. Sendrier. Security bounds for the design of codebased cryptosystems. In to appear in Advances in Cryptology - Asiacrypt-2009, 2009. http://eprint.iacr.org/2009/414.pdf.
[13] T. Hardjono and Y. Zheng. A practical digital multisignature scheme based on discrete logarithms (extended abstract). In in AUSCRYPT-92, pages 122-132. Springer, 1993.
[14] L. Harn and T. Kiesler. Rsa blocking and multisignature schemes with no bit expansion. Electron Letters, 26(18):1490.1491, August 1990.
[15] L. Harn and T. Kiesler. New scheme for digital multisignature. Electron Letters, 25(15):1002.1003, July 1989.
[16] K. Itakura and K. Nakamura. New scheme for digital multisignature. NEC Research and Development, 71:1-8, October 1983.
[17] G. Kabatianskii, E.Krouk, and B. J. M. Smeets. A digital signature scheme based on random error-correcting codes. IMA Int. Conf., Springer LNCS 1355:161-167, 1997.
[18] K. Kawauchi and M. Tada. On the exact security of multi-signature schemes based on rsa. In ACISP 2003, volume 2727.
[19] K. Kawauchi and M. Tada. On the security and the efficiency of multisignature schemes based on a trapdoor one-way permutation. IEICE Trans. Fundam. Electron. Commun. Comput. Sci., E88-A(5):1274-1282, 2005.
[20] Y. Komano, K. Ohta, A. Shimbo, and S. Kawamura. Formal security model of multisignatures. In ISC, pages 146-160, 2006.
[21] E. Liberty and S. W. Zucker. The mailman algorithm: A note on matrixvector multiplication. Inf. Process. Lett., 109(3):179-182, 2009.
[22] R.J. McEliece. A public-key cryptosystem based on algebraic coding theory. Jpl dsn progress report 42-44 , pages 114-116, 1978.
[23] S. Micali, K. Ohta, and L. Reyzin. Accountable-subgroup multisignatures: extended abstract. In ACM Conference on Computer and Communications Security, pages 245-254, 2001.
[24] R. Misoczki and P. S. L. M. Barreto. Compact mceliece keys from goppa codes. Preprint, 2009. http://eprint.iacr.org/2009/187.pdf.
[25] S. Mitomi and A. Miyaji. A general model of multisignature schemes with message flexibility, order flexibility, and order verifiability. IEICE Trans. Fundam., E-84-A(5):2488-2499, 2001.
[26] T. Okamoto. A digital multisignature scheme using bijective public-key cryptosystems. ACM Trans. Comput. Syst., 6(4):432-441, 1988.
[27] O.Kazuo and O. Tatsuaki. A digital multisignature scheme based on the fiat-shamir scheme. In ASIACRYPT -91: Proc. of the International Conference on the Theory and Applications of Cryptology, pages 139- 148. Springer, 1993.
[28] A. Shamir. Identity-based cryptosystems and signature schemes. In Proceedings of CRYPTO 84 on Advances in cryptology, pages 47-53. Springer-Verlag., 1984.
[29] P. W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26:1484-1509, 1997.
[30] L. Wang, E. Okamoto, Y. Miao, T. Okamoto, and H. Doi. Id-based series-parallel multisignature schemes for multi-messages from bilinear maps. In WCC, pages 291-303, 2005.