A Multi-Signature Scheme based on Coding Theory

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].

Authors:

• Mohammed Meziani
• Pierre-Louis Cayrel

Keywords:

• Post-quantum cryptography
• Coding-based cryptography
• Digital signature
• Multisignature scheme.

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.