Abstract
Zero-knowledge proofs were introduced in 1985, in a paper by Goldwasser, Micali and Rackoff ([6]). Their practical significance was soon demonstrated in the work of Fiat and Shamir ([4]), who turned zero-knowledge proofs of quadratic residuosity into efficient means of establishing user identities. Still, as is almost always the case in public-key cryptography, the Fiat-Shamir scheme relied on arithmetic operations on large numbers. In 1989, there were two attempts to build identification protocols that only use simple operations (see [11,10]). One appeared in the EUROCRYPT proceedings and relies on the intractability of some coding problems, the other was presented at the CRYPTO rump session and depends on the so-called Permuted Kernel problem (PKP). Unfortunately, the first of the schemes was not really practical. In the present paper, we propose a new identification scheme, based on error-correcting codes, which is zero-knowledge and is of practical value. Furthermore, we describe several variants, including one which has an identity based character. The security of our scheme depends on the hardness of decoding a word of given syndrome w.r.t. some binary linear error-correcting code.
PATENT CAUTION: This document may reveal patentable subject matter
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
E. R. Berlekamp, R. J. Mc Eliece and H. C. A. Van Tilborg. On the inherent intractability of certain coding problems, IEEE Trans. Inform. Theory, (1978) 384–386.
F. Chabaud, Asymptotic analysis of probabilistic algorithms for finding short codewords, Proceedings of EUROCODE 92, Lecture Notes in Computer Science, to appear.
M. J. Coster, A. Joux, B. A. LaMacchia, A. M. Odlyzko, C. P. Schnorr and J. Stern, Improved low-density subset sum algorithms, Computational Complexity, to appear.
A. Fiat and A. Shamir, How to prove yourself: Practical solutions to identification and signature problems, Proceedings of Crypto 86, Lecture Notes in Computer Science 263, 181–187.
U. Feige, A. Fiat and A. Shamir, Zero-knowledge proofs of identity, Proc, 19th ACM Symp. Theory of Computing, 210–217, (1987) and J. Cryptology, 1 (1988), 77–95.
S. Goldwasser, S. Micali and C. Rackoff, The knowledge complexity of interactive proof systems, Proc. 17th ACM Symp. Theory of Computing, 291–304, (1985).
J. S. Leon, A probabilistic algorithm for computing minimum weights of large error-correcting codes. IEEE Trans. Inform. Theory, IT-34(5): 1354–1359.
J. C. Lagarias and A. M. Odlyzko, Solving low-density subset sum problems, J. Assoc. Comp. Mach. 32 (1985), 229–246.
F. J. MacWilliams and N. J. A. Sloane, The theory of error-correcting codes, North-Holland, Amsterdam-New-York-Oxford (1977).
A. Shamir, An efficient identification scheme based on permuted kernels, Proceedings of Crypto 89, Lecture Notes in Computer Science 435, 606–609.
J. Stern, An alternative to the Fiat-Shamir protocol, Proceedings of Eurocrypt 89, Lecture Notes in Computer Science 434, 173–180.
J. Stern, A method for finding codewords of small weight, Coding Theory and Applications, Lecture Notes in Computer Science 388 (1989), 106–113.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Stern, J. (1994). A new identification scheme based on syndrome decoding. In: Stinson, D.R. (eds) Advances in Cryptology — CRYPTO’ 93. CRYPTO 1993. Lecture Notes in Computer Science, vol 773. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48329-2_2
Download citation
DOI: https://doi.org/10.1007/3-540-48329-2_2
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57766-9
Online ISBN: 978-3-540-48329-8
eBook Packages: Springer Book Archive