zbMATH — the first resource for mathematics

Collision free hash functions and public key signature schemes. (English) Zbl 0647.94011
Advances in cryptology - EUROCRYPT ’87, Proc. Workshop, Amsterdam/Neth. 1987, Lect. Notes Comput. Sci. 304, 203-216 (1988).
[For the entire collection see Zbl 0635.00022.]
In this paper, we present a construction of hash functions. These functions are collision free in the sense that under some cryptographic assumption, it is provably hard for an enemy to find collisions. Assumptions that would be sufficient are the hardness of factoring, of discrete log, or the (possibly) more general assumption about the existence of claw free sets of permutations. The ability of a hash function to improve security and speed of a signature scheme is discussed: for example, we can combine the RSA-system with a collision free hash function based on factoring to get a scheme which is more efficient and much more secure. Also, the effect of combining the Goldwasser-Micali-Rivest signature scheme with one of our functions is studied. In the factoring based implementation of the scheme using a k- bit modulus, the signing process can be speeded up by a factor roughly equal to \(k\cdot O(\log_ 2(k))\), while the signature checking process will be faster by a factor of \(O(\log_ 2(k))\).

94A60 Cryptography