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