Abstract
This paper determines an exact relationship between collision-free hash functions and other cryptographic primitives. Namely, it introduces a new concept, the pseudo-permutation, and shows that the existence of collision-free hash functions is equivalent to the existence of claw-free pairs of pseudo-permutations. When considered as one bit contractors (functions from k + 1 bits to k bits), the collision-free hash functions constructed are more efficient than those proposed originally, requiring a single (claw-free) function evaluation rather than k.
Supported by a NSF Graduate Fellowship
Chapter PDF
Similar content being viewed by others
References
Manual Blum and Silvio Micali. How to generate cryptographically strong sequences of pseudo-random bits. SIAM Journal of Computing, 13(4):850–864, November 1984.
Ivan Damgård. Collision free hash functions and public key signature schemes. In Proceedings of EUROCRYPT’ 87, volume 304 of Lecture Notes in Computer Science, pages 203–216, Berlin, 1988. Springer-Verlag.
Alfredo De Santis and Moti Yung. On the design of provably-secure cryptographic hash functions. In Proceedings of EUROCRYPT’ 90, volume 473 of Lecture Notes in Computer Science, pages 412–431, Berlin, 1990. Springer-Verlag.
Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How to construct random functions. Journal of the Association for Computing Machinery, 33(4):792–807, October 1986.
Shafi Goldwasser, Silvio Micali, and Ronald L. Rivest. A digital signature scheme secure against adaptive chosen-message attack. SIAM Journal of Computing, 17(2):281–308, April 1988.
J. Håstad. Pseudo-random generators under uniform assumptions. In Proceedings of the Twenty Second Annual ACM Symposium on Theory of Computing, pages 395–404. ACM, 1990.
Russell Impagliazzo, Leonid A. Levin, and Michael Luby. Pseudo-random generation from one-way functions. In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pages 12–24. ACM, 1989.
Toshiya Itoh. Personal communication, August 1992.
Leonid A. Levin. Average case complete problems. SIAM Journal on Computing, 15:285–286, 1986.
M. Naor and M. Yung. Universal one-way hash functions and their cryptographic applications. In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pages 33–43. ACM, 1989.
Wakaha Ogata and Kaoru Kurosawa. On claw free families. In Proceedings of ASIACRYPT’ 91, 1991.
John Rompel. One-way functions are necessary and sufficient for secure signatures. In Proceedings of the Twenty Second Annual ACM Symposium on Theory of Computing, pages 387–394. ACM, 1990.
A. Yao. Theory and applications of trapdoor functions. In Proceedings of the Twenty Third IEEE Symposium on Foundations of Computer Science, pages 80–91. IEEE, 1982.
Yuliang Zheng, Tsutomu Matsumoto, and Hideki Imai. Duality between two cryptographic primitives. In Proceedings of the Eighth International Conference on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, volume 508 of Lecture Notes in Computer Science, pages 379–390, Berlin, 1990. Springer-Verlag.
Yuliang Zheng, Tsutomu Matsumoto, and Hideki Imai. Structural properties of one-way hash functions. In Proceedings of CRYPTO’ 90, volume 537 of Lecture Notes in Computer Science, pages 285–302, Berlin, 1990. Springer-Verlag.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Russell, A. (1993). Necessary and Sufficient Conditions for Collision-Free Hashing. In: Brickell, E.F. (eds) Advances in Cryptology — CRYPTO’ 92. CRYPTO 1992. Lecture Notes in Computer Science, vol 740. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48071-4_30
Download citation
DOI: https://doi.org/10.1007/3-540-48071-4_30
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57340-1
Online ISBN: 978-3-540-48071-6
eBook Packages: Springer Book Archive