Abstract
In this paper we demonstrate that widely known identification systems, such as the public-file-based Feige-Fiat-Shamir scheme, can be insecure if proper care is not taken with their implementation. We suggest possible solutions. On the other hand, identity-based versions of the Feige-Fiat-Shamir scheme are conceptually more complicated than necessary.
Article PDF
Similar content being viewed by others
References
S. Bengio, G. Brassard, Y. G. Desmedt, C. Goutier, and J.-J. Quisquater, “Aspects and Importance of Secure Implementations of Identification Systems,” Manuscript M209, Philips Research Laboratory, Brussels, May 1987; revision available from the authors.
T. Beth and Y. Desmedt, “Identification tokensor: Solving the chess grandmaster problem,” Proceedings of Crypto '90, Santa Barbara, California, August 1990, Lecture Notes in Computer Science, Springer-Verlag, Berlin, to appear.
G. Brassard, “How to improve signature schemes,” Proceedings of Eurocrypt '89, Houthalen, Belgium, April 1989, Lecture Notes in Computer Science, Vol. 434, Springer-Verlag, Berlin, pp. 16–22.
M. V. D. Burmester and Y. G. Desmedt, “Remarks on the soundness of proofs,” Electronics Letters, 25(22) (1989), 1509–1511.
J. H. Conway, On Numbers and Games, Academic Press, London, 1976.
Y. Desmedt, “Major security problems with the ‘unforgeable’ (Feige-)Fiat-Shamir proofs of identity and how to overcome them,” Proceedings of Securicom 88, Paris, March 1988, pp. 147–159.
Y. Desmedt, C. Goutier, and S. Bengio, “Special uses and abuses of the Fiat-Shamir passport protocol,” Proceedings of Crypto '87, Santa Barbara, California, August 1987, Lecture Notes in Computer Science, Vol. 293, Springer-Verlag, Berlin, pp. 21–39.
Y. Desmedt and J.-J. Quisquater, “Public-key systems based on the difficulty of tampering (Is there a difference between DES and RSA?),” Proceedings of Crypto '86, Santa Barbara, California, August 1986, Lecture Notes in Computer Science, Vol. 263, Springer-Verlag, Berlin, pp. 111–117.
U. Feige, A. Fiat, and A. Shamir, “Zero knowledge proofs of identity,” Proceedings of 19th ACM Symposium on Theory of Computing, New York, May 1987, pp. 210–217.
U. Feige, A. Fiat, and A. Shamir, “Zero-knowledge proofs of identity,” Journal of Cryptology, 1(2) (1988), 77–94.
A. Fiat and A. Shamir, “How to prove yourself: Practical solutions to identification and signature problems,” Proceedings of Crypto '86, Santa Barbara, California, August 1986, Lecture Notes in Computer Science, Vol. 263, Springer-Verlag, Berlin, pp. 186–194.
A. Fiat and A. Shamir, “Unforgeable proofs of identity,” Proceedings of Securicom 87, Paris, March 1987, pp. 147–153.
J. Gleick, “A new approach to protecting secrets is discovered,” New York Times, pp. C1 and C3, February 18, 1987.
S. Goldwasser, S. Micali, and C. Rackoff, “The knowledge complexily of interactive proof systems,” SIAM Journal on Computing, 18 (1989), 186–208.
S. Goldwasser, S. Micali, and R. Rivest, “A digital signature scheme secure against adaptive chosen-message attacks,” SIAM Journal on Computing, 17(2) (1988), 77–94.
B. W. Lampson, “A note on the confinement problem,” Communications of the ACM, 16(10) (1973), 613–615.
P. D. Merillat, “Secure stand-along positive personnel identity verification system (SSA-PPIV),” Technical Report SAND79-0070, Sandia National Laboratories, March 1979.
M. O. Rabin, “Digital signatures and public-key functions as intractable as factorization,” Technical Report MIT/LCS/TR-212, Massachusetts Institute of Technology, 1979.
J. Saltzer, “On digital signalures,” ACM Operating Systems Review, 12(2) (1978), 12–14.
A. Shamir, “Interactive identification”, Presented at the Workshop on Algorithms, Randomness and Complexity, Centre International de Rencontres Mathématiques (CIRM), Luminy, Marseille, March 1986.
A. Shamir, “The search for provably secure identification schemes,” Proceedings of the International Congress of Mathematicians, ICM 86, Berkeley, California, August 1986, pp. 1488–1495.
G. J. Simmons, “The prisoners' problem and the subliminal channel,” Proceedings of Crypto '83, Santa Barbara, California, August 1983, Plenum, New York, pp. 51–67.
G. J. Simmons, “A system for verifying user identity and authorization at the point-of-sale or access,” Cryptologia, 8(1) (1984), 1–21.
Webster's Third New International Dictionary of the English Language (Unabridged), Merriam, Springfield, Massachusetts, 1971.
R. Zelazny, Unicorn Variations, The Amber Corporation, 1982, reprinted by Avon Books, New York, 1987.
Author information
Authors and Affiliations
Additional information
Gilles Brassard's research is supported in part by Canada's NSERC. A part of this research was done while Yvo Desmedt was sponsored by NFWO (the Belgian NSF). A later part was done while he was visiting professor at the Département IRO, Université de Montréal. A part of his research is now supported by NSF Grants NCR-9004879 and NCR-9106327. This research was done while Jean-Jacques Quisquater was at the late Philips Research Laboratory, Belgium. Parts of this research were presented at Crypto '86, Crypto '87, and Securicom '88.
Rights and permissions
About this article
Cite this article
Bengio, S., Brassard, G., Desmedt, Y.G. et al. Secure implementation of identification systems. J. Cryptology 4, 175–183 (1991). https://doi.org/10.1007/BF00196726
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF00196726