building a true RNG

[Bart Preneel]

On 2 Aug 2002, Paul Crowley wrote:

> I meant to say, another example of a believed one-way function that is
> guaranteed to be able to produce any output is one based on the
> difficulty of discrete log:
>
> f:(x) = g^x mod p
>
> is bijective if the domain and range is 1..p-1, but finding preimages
> is the discrete log problem.  Of course this doesn't compress.  I
> don't know of any examples which compress and have collision resistance.

Choose a group of prime order.
Choose t random group elements g_i (1 <= i <= t) different from 1.
Write input x as x_1 || x_2 || ... || x_t
prepend a 1 bit to each x_i giving z_i

f:(x)= g_1^z_1 . g_2^z_2 . .... . g_t^z^t

For details:
M. Bellare, O. Goldreich, S. Goldwasser,
("Incremental cryptography: the case of hashing and signing," Crypto 94)
after earlier work by D. Chaum, E. van Heijst, B. Pfitzmann,
("Cryptographically strong undeniable signatures, unconditionally secure
for the signer," Crypto'91) and S. Brands.

--Bart


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