Dual Construction of Stern-based Signature Scheme

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.

Authors:

• Pierre-Louis Cayrel
• Sidi Mohamed El Yousfi Alaoui

Keywords:

• Stern algorithm
• Véron algorithm
• threshold ring signature
• post-quantum cryptography.

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.