Abstract
In 1986, Fiat and Shamir [2] exhibited zero-knowledge based identification and digital signature schemes. In these schemes, as well as in subsequent variants, both the prover and the verifier have to perform modular multiplications. This paper is an attempt to build identification protocols that use only very basic operations such as multiplication by a fixed matrix over the two-element field. Such a matrix can be viewed as the parity-check matrix of a linear binary error-correcting code. The idea of using error-correcting codes in this area is due to Harari [3] but the method that is described here is both simpler and more secure than his original design.
Research supported by the PRC mathématiques et informatique
Chapter PDF
Similar content being viewed by others
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.
A. Fiat and A. Shamir, How to prove yourself: Practical solutions to identification and signature problems, Proceedings of Crypto 86, Santa-Barbara (1986), 181–187.
S. Harari, Un algorithme d’authentification sans transfert d’information Proceedings, Trois journées sur le codage, Toulon (1988), to appear.
J.N. Pierce, Limit distributions of the minimum distance of random linear codes, IEEE Trans. Inform. Theory, (1967) 595–599.
J. Stern, A method for finding codewords of small weight, Proceedings, Trois journées sur le codage, Toulon (1988), to appear.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1990 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Stern, J. (1990). An alternative to the Fiat-Shamir protocol. In: Quisquater, JJ., Vandewalle, J. (eds) Advances in Cryptology — EUROCRYPT ’89. EUROCRYPT 1989. Lecture Notes in Computer Science, vol 434. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46885-4_19
Download citation
DOI: https://doi.org/10.1007/3-540-46885-4_19
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-53433-4
Online ISBN: 978-3-540-46885-1
eBook Packages: Springer Book Archive