Abstract
We describe a modification of an interactive identification scheme of Schnorr intended for use by smart cards. Schnorr’s original scheme had its security based on the difficulty of computing discrete logarithms. The modification that we present here will remain secure if either of two computational problems is infeasible, namely factoring a large integer and computing a discrete logarithm. For this enhanced security we require somewhat more communication and computational power, but the requirements remain quite modest, so that the scheme is well suited for use in smart cards.
This work was performed under U. S. Department of Energy contract number DE-AC04-76DP00789
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
Thomas Beth, “Efficient zero-knowledge identification scheme for smart cards,” Advances in Cryptology (Proceedings of Eurocrypt’ 88), Lecture Notes in Computer Science 330 (1989), 77–84.
David Chaum, Jan-Hendrik Evertse, Jeroen van de Graaf, and René Peralta, “Demonstrating possession of a discrete logarithm without revealing it,” Advances in Cryptology (Proceedings of Eurocrypt’ 86) Lecture Notes in Computer Science 263 (1987), 200–212.
David Chaum, Jan-Hendrik Evertse, and Jeroen van de Graaf, “An improved protocol for demonstrating possession of discrete logarithms and some generalizations,” Advances in Cryptology (Proceedings of Eurocrypt’ 87) Lecture Notes in Computer Science 304 (1988), 127–141.
Yvo Desmedt, Claude Goutier, and Samy Bengio, “Special uses and abuses of the Fiat-Shamir passport protocol,” Advances in Cryptology (Proceedings of Crypto’ 87) Lecture Notes in Computer Science 293 (1988), 21–39.
A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, and J. M. Pollard, “The Number Field Sieve”, Proceedings of the 22nd ACM Symposium on Theory of Computing, Association for Computing Machinery, New York, 1990, 564–572.
Arjen K. Lenstra and Mark S. Manasse, Factoring by Electronic Mail, Proceedings of Eurocrypt’ 89, Lecture Notes in Computer Science, to appear.
Kevin S. McCurley, A Key Distribution System Equivalent to Factoring, Journal of Cryptology 1 (1988), 95–105.
J. M. Pollard, “Monte Carlo Methods for Index Computation mod p,” Mathematics of Computation 32 (1978), 918–924.
C.P. Schnorr, Efficient Identification and Signatures for Smart Cards, Proceedings of Crypto’ 89, Lecture Notes in Computer Science, to appear.
Samuel S. Wagstaff, Jr., Greatest of the Least Primes in Arithmetic Progressions Having a Given Modulus, Mathematics of Computation 33 (1979), 1073–1080.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1991 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Brickell, E.F., McCurley, K.S. (1991). An Interactive Identification Scheme Based on Discrete Logarithms and Factoring. In: Damgård, I.B. (eds) Advances in Cryptology — EUROCRYPT ’90. EUROCRYPT 1990. Lecture Notes in Computer Science, vol 473. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46877-3_6
Download citation
DOI: https://doi.org/10.1007/3-540-46877-3_6
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-53587-4
Online ISBN: 978-3-540-46877-6
eBook Packages: Springer Book Archive