zbMATH — the first resource for mathematics

Necessary and sufficient conditions for collision-free hashing. (English) Zbl 0817.94014
Brickell, Ernest F. (ed.), Advances in cryptology - CRYPTO ’92. 12th annual international cryptology conference, Santa Barbara, CA, USA, August 16-20, 1992. Proceedings. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 740, 433-441 (1993).
Summary: This paper determines an exact relationship between collision-free hash functions [I. Damgård, Advances in cryptology – Eurocrypt ‘87, Lect. Notes Comput. Sci. 304, 203-216 (1988; Zbl 0647.94011)] 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\).
For the entire collection see [Zbl 0803.00037].

94A60 Cryptography