building a true RNG

Helger Lipmaa helger at tcs.hut.fi
Mon Jul 29 16:23:51 EDT 2002


On Mon, 29 Jul 2002, David Wagner wrote:

> I don't know of any good cryptographic hash function that comes with
> a proof that all outputs are possible.  However, it might not be too
> hard to come up with plausible examples.  For example, if we apply the
> Luby-Rackoff construction (i.e., 3 rounds of a Feistel cipher), with
> ideal hash functions in each round, does this have the desired properties?
> It might.

If by good you just mean collision-resistant, then Chaum-van
Heijst-Pfitzmann is a collision-resistant hash function. Recall that CVP
works like that:

  H(x_1||x_2)=g_1^(x_1)g_2^(x_2) mod p

where p is a prime and g_1, g_2 are independently and randomly chosen
generators. (in particular, their mutual discrete logs are unknown)

For any y from Z_p, there exists an (x_1||x_2), st H(x_1||x_2)=y: just
take x_1 to be the discrete log of y on basis g_1, and set x_2=0. It's
just hard to find x_1, if we assume that the DLP is hard. The same
assumption makes CVP one-way and also collision-resistant.

Furthermore, you can extend CVP to arbitrary inputs by using some standard
mechanisms.

Helger



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



More information about the cryptography mailing list