Advertisement

On the length of cryptographic hash-values used in identification schemes

  • Marc Girault
  • Jacques Stern
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 839)

Abstract

Many interactive identification schemes based on the zero-knowledge concept use cryptographic hash-values, either in their basic design or in specific variants. In this paper, we first show that 64-bit hash-values, a length often suggested, definitely decrease the level of the security of all these schemes. (Of course, this does not compromise the security of the schemes by themselves). Then we prove that collision-resistance is a sufficient condition to achieve the claimed level of security. Finally, by using a weaker notion of collision-resistance, we present interesting variants of some of these schemes (in particular the Schnorr and the Guillou-Quisquater schemes) which minimize the number of communication bits for a given level of security.

References

  1. [Fe68]
    W. Feller, An introduction to probability theory and its applications, J. Wiley & Sons, 1968.Google Scholar
  2. [FFS88]
    U. Feige, A. Fiat and A. Shamir, Zero-knowledge proofs of identity, Journal of Cryptology, Vol. 1, No2, 1988, pp. 77–94.zbMATHCrossRefMathSciNetGoogle Scholar
  3. [FS86]
    A. Fiat and A. Shamir, How to prove yourself: Practical solutions to identification and signature problems, Advances of Cryptology: Proceedings of CRYPTO’86, Lecture Notes in Computer Science, Vol. 263, Springer-Verlag, Berlin, 1987, pp. 186–194.Google Scholar
  4. [GMR85]
    S. Goldwasser, S. Micali and C. Rackoff, The knowledge of interactive proof-systems, Proceedings of 17th ACM Symposium on Theory of Computing, 1985, pp. 291–304.Google Scholar
  5. [GQ88]
    L.C. Guillou and J.J. Quisquater, A practical zero-knowledge protocol fitted to security microprocessors minimizing both transmission and memory, Advances of Cryptology: Proceedings of EUROCRYPT’88, Lecture Notes in Computer Science, Vol. 330, Springer-Verlag, Berlin, 1988, pp. 123–128.Google Scholar
  6. [PS87]
    J.M. Pollard and C.P. Schnorr, An efficient solution of the congruence x 2 + ky 2 = m (mod n), IEEE Transactions on Information Theory, Vol. IT-33, No5, 1987, pp. 702–709.CrossRefMathSciNetGoogle Scholar
  7. [Sc89]
    C.P. Schnorr, Efficient identification and signature for smart cards, Advances of Cryptology: Proceedings of CRYPTO’89, Lecture Notes in Computer Science, Vol. 435, Springer-Verlag, Berlin, 1987, pp. 239–252.CrossRefGoogle Scholar
  8. [Sh89]
    A. Shamir, An efficient identification scheme based on permuted kernels, Advances of Cryptology: Proceedings of CRYPTO’89, Lecture Notes in Computer Science, Vol. 435, Springer-Verlag, Berlin, 1987, pp. 606–609.CrossRefGoogle Scholar
  9. [St89]
    J. Stern, An alternative to the Fiat-Shamir protocol, Advances of Cryptology: Proceedings of EUROCRYPT’89, Lecture Notes in Computer Science, Vol. 434, Springer-Verlag, Berlin, 1990, pp. 173–180.Google Scholar
  10. [St93]
    J. Stern, A new identification scheme based on syndrome decoding, Advances of Cryptology: Proceedings of CRYPTO’93, to appear.Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 1994

Authors and Affiliations

  • Marc Girault
    • 1
  • Jacques Stern
    • 2
  1. 1.SEPTCaenFrance
  2. 2.Laboratoire d’InformatiqueEcole Normale SupérieureParisFrance

Personalised recommendations