Collision Free Hash Functions and Public Key Signature Schemes

The ability of a hash function to improve security and speed of a signature scheme is discussed: for example, it 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.

Abstract

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·O (log2(k)), while the signature checking process will be faster by a factor of O (log2(k)).