Adi Shamir's Discrete Logarithm Hash Function

During a discussion in the cryptography mailing forum a long forgotten proposal of a hash function based on modular arithmetic was mentioned by Ronald L. Rivest which perfectly fits into the project, I am working on, the Pure Crypto Project.
Years ago Adi Shamir invented this hash function, which has at least two important advantages compared to today's standard hash functions. First, it is based on a very intuitive concept of modular exponentiation. Once the message has been converted into a long integer x, the hash is simply

hash(x) = g x (mod p*q).

Second, Ronald Rivest showed in a clear way that Shamir's hash function is provably collision-resistant, as constructing a collision will require the ability to factor the modulus.
Thus the security of the discrete logarithm hash function (SDLH) is based on exactly the same foundation as the security of the RSA cryptosystem.

I have collected all information about SDLH which was available to me and put it into a paper "A Discrete Logarithm Hash Function for RSA Signatures" in which the capability of the SDLH to create signatures is analysed in detail. This paper also covers considerations about the choice of the public parameters and the reduction of the hash function's output length. Along with the SDLH a new concept is introduced into hashing, because the output does not only depend on the message to be hashed but also depends on the user's public key material which makes SDLH particulary useful to create signatures.

There is also an implementation of the hash function as a stand alone program using keyfiles containing the public parameters. Of course, applications intending to use SDLH will not only take care of the key material's integrity but will also check the minimum sizes of the public parameters to ensure the security of the hash's output.

It should be emphasized that using the new hash function today is risky because there has not been much peer review and testing yet, but due to the clear advantages of the hash I am convinced that it deserves a broader acceptance in future.

Finally in a personal communication Prof. Shamir has consented to use the SDLH in the Pure Crypto Project and he has expressed his wish to see the hash implemented. If you have information about other implementations, please send me a note so that I can create a link to this work as well.

Ralf Senderek, July 2003