Modulo based hash functions [was: The Pure Crypto Project's Hash Function]

[Anton Stiglic]

A bit belated, but might be useful to someone...

I was reviewing some parts of Stinson's book and was
reminded of some schemes I had forgotten about.

One hash function is described in one of the exercises, it is 
basically the same thing that Ron Rivest described in his
post to this tread.  It consists of an exponentiation operation, 
with the base being a fixed generator of largest order, the exponent
being the value to be hashed, and the modulo being an RSA integer
(assume factorization is unknown).
Stinson references the following paper for this scheme:

J.K. Gibson.  Discrete logarithm hash function that is collision
free and one way.  IEE Proceedings-E, 138 (1991), 407-410

Another hash function described in detail (with a detailed proof
of security and an example) in Stinson's book is due to Chaum, 
van Heijst and Pfitzmann.
You have a large prime p with q = (p-1)/2 also prime.  a and b
are two primitive elements of Z_p, you assume that the value of 
log_a (b) is not publicly known (and that it is difficult to compute).
The hash function is defined as
    H(x1, x2) = a^x1 * b^x2 mod p,
where x1 and x2 are values in the range  [0, q-1].

You can extend this hash function (or any other finite domain hash
function where the length in bits of the input is greater than that of
the output), to a hash function with infinite domain using the well 
known techniques due to Damgard and Merkle.

The reference given for this scheme is the following:
D. Chaum, E. van Heijst and B. Pfitzmann.  Cryptographically 
strong undeniable signatures, unconditaionally secure for the 
signer.  Lecutre Notes in Compute Science, 576 (1992), 
470-484.  (Advances in Cryptology - CRYPTO '91).

If you want some kind of provable security, have someone you
trust to generate the public parameters, and don't mind your
hash functions being slow, these are both good options.

--Anton

P.S.  Damgard and Merkle references are:

I.B.Damgard.  A design principle for hash functions.  Lecutre
Notes in Computer Science, 435 (1990), 416-427.  (Advances
in Cryptology - CRYPTO '89).

R.C.Merkle.  One way hash functions and DES.  Lecutre Notes
in Computer Science, 435 (1990), 428-446.  (Advances in Cryptology
- CRYPTO '89).

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com