Dual Construction of Stern-based Signature Scheme

Authors: Pierre-Louis Cayrel, Sidi Mohamed El Yousfi Alaoui

Abstract:

In this paper, we propose a dual version of the first threshold ring signature scheme based on error-correcting code proposed by Aguilar et. al in [1]. Our scheme uses an improvement of Véron zero-knowledge identification scheme, which provide smaller public and private key sizes and better computation complexity than the Stern one. This scheme is secure in the random oracle model.

Keywords: Stern algorithm, Véron algorithm, threshold ring signature, post-quantum cryptography.

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

References:

[1] Carlos Aguilar Melchor, Pierre-Louis Cayrel, and Philippe Gaborit. A new efficient threshold ring signature scheme based on coding theory. In PQCrypto -08: Proceedings of the 2nd International Workshop on Post- Quantum Cryptography, pages 1-16, Berlin, Heidelberg, 2008. Springer- Verlag.
[2] 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.
[3] Emmanuel Bresson, Jacques Stern, and Michael Szydlo. Threshold ring signatures and applications to ad-hoc groups. In CRYPTO -02: Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, pages 465-480. Springer-Verlag, 2002.
[4] N. Courtois, M. Finiasz, and N. Sendrier. How to achieve a McEliecebased digital signature scheme. In Advances in Cryptology - Asiacrypt- 2001, volume 2248 of Lecture Notes in Computer Science, pages 157-174, Gold Coast, Australia, 2001. Springer.
[5] Amos Fiat and Adi Shamir. How to prove yourself: practical solutions to identification and signature problems. In Proceedings on Advances in cryptologyÔÇöCRYPTO -86, pages 186-194. Springer-Verlag, 1987.
[6] U. Fiege, A. Fiat, and A. Shamir. Zero knowledge proofs of identity. In STOC -87: Proceedings of the nineteenth annual ACM symposium on Theory of computing, pages 210-217, 1987.
[7] Matthieu Finiasz and Nicolas Sendrier. Security bounds for the design of code-based cryptosystems. Cryptology ePrint Archive, Report 2009/414, 2009. http://eprint.iacr.org/.
[8] F. J. MacWilliams and N. J. A. Sloane. The theory of error-correcting codes, volume 16. North-Holland Mathematical Library, 1977.
[9] R. McEliece. A public-key cryptosystem based on algebraic coding theory. The Deep Space Network Progress Report, DSN PR 42-44, 1978. http://ipnpr.jpl.nasa.gov/progressreport2/42-44/44N.PDF.
[10] R. Misoczki and P. S. L. M. Barreto. Compact mceliece keys from goppa codes. Preprint, 2009. http://eprint.iacr.org/2009/187.pdf.
[11] H. Niederreiter. Knapsack-type cryptosystems and algebraic coding theory. Problems of Control and Information Theory, 15(2):159-166, 1986.
[12] J. N. Pierce. Limit distribution of the minimum distance of random linear codes. In IEEE Trans. Inf. Theory, pages 595-599, Vol. IT-13 (1967).
[13] Ronald L. Rivest, Adi Shamir, and Yael Tauman. How to leak a secret: Theory and applications of ring signatures. In Essays in Memory of Shimon Even, pages 164-186, 2006.
[14] Jacques Stern. A new identification scheme based on syndrome decoding. In CRYPTO -93: Proceedings of the 13th annual international cryptology conference on Advances in cryptology, pages 13-21. Springer-Verlag, 1994.
[15] Pascal Véron. Probleme sd, opérateur trace, schemas dt-identification et codes de goppa. PhD thesis, Université de Toulon et du Var, 1995.
[16] Pascal Véron. Improved identification schemes based on error-correcting codes. Appl. Algebra Eng. Commun. Comput., 8(1):57-69, 1996.