[11243] in cryptography@c2.net mail archive
Re: building a true RNG
daemon@ATHENA.MIT.EDU (Helger Lipmaa)
Mon Jul 29 16:30:04 2002
Date: Mon, 29 Jul 2002 23:23:51 +0300 (EEST)
From: Helger Lipmaa <helger@tcs.hut.fi>
To: David Wagner <daw@cs.berkeley.edu>
Cc: "John S. Denker" <jsd@monmouth.com>,
David Wagner <daw@mozart.cs.berkeley.edu>,
cryptography@wasabisystems.com, Barney Wolff <barney@tp.databus.com>
In-Reply-To: <200207291745.g6THjdP10410@mozart.cs.berkeley.edu>
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@wasabisystems.com
