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

[Ralf Senderek]

On Wed, 14 May 2003, Anton Stiglic wrote:

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

Thank you for the references.

Anton describes two proposals for hash functions based on modular
arithmetic (with some conditions on g, p, q, a, b and the inputs xi):

A (Shamir, Rivest) :    hash-A(x) = g^x (mod p*q)

B (Chaum, van Heijst :  hash-B(x1,x2) = a^x1 * b^x2 (mod p)
   Pfitzmann)


> 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

I am not concerned about speed unless it is going to make the hash
unusable, but with factoring of p*q being infeasible we have at least
2048 bit hash values, expanding the size of signatures by a factor of 13,
compared to sha1.

And proposal A is clearly not multiplication free, so you will be
able to find Z, X and Y with hash(X)*hash(Y) (mod p*q) = hash(Z).
As the hash shall create signatures with RSA, one needs multiplication
freedom, and (AFAIK) cannot process the whole message in one step.

The prove of collision resistance, Ronald Rivest has given in an earlier
posting, might be ruined if a Davies-Meyer-like feed forward process is
wrapped around the exponentiation.  hash(i) = something(xi) XOR hash(i-1)
The second proposal is subject to the same dilemma.


Is it possible to have both, a prove of collision resistance and
multiplication freedom?

Ralf.

*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*
* Ralf Senderek  <ralf at senderek.de> http://senderek.de  * What is privacy *
* Sandstr. 60   D-41849 Wassenberg  +49 2432-3960       *     without     *
* PGP: AB 2C 85 AB DB D3 10 E7  CD A4 F8 AC 52 FC A9 ED *   Pure Crypto?  *
*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*


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