[11286] in cryptography@c2.net mail archive
Re: building a true RNG
daemon@ATHENA.MIT.EDU (Paul Crowley)
Fri Aug 2 14:14:44 2002
To: "John S. Denker" <jsd@monmouth.com>
Cc: David Wagner <daw@cs.berkeley.edu>,
cryptography@wasabisystems.com, Barney Wolff <barney@tp.databus.com>
From: Paul Crowley <paul@ciphergoth.org>
Date: 02 Aug 2002 12:51:34 +0100
In-Reply-To: "John S. Denker"'s message of "Fri, 02 Aug 2002 07:27:45 -0400"
"John S. Denker" <jsd@monmouth.com> writes:
> David Wagner <daw@cs.berkeley.edu> writes:
> >>> I don't know of any good cryptographic hash function
> >>> that comes with a proof that all outputs are possible.
>
> What about the scheme
> Pad -> Encipher -> Contract
> described at
> http://www.monmouth.com/~jsd/turbid/paper/turbid.htm#sec-uniform-hash
It's not hard to understand why it isn't easy to solve this problem
using symmetric primitives. Any solution must come with a proof that
for any image, there is a preimage. With symmetric primitives, that
proof usually constitutes a recipe for generating the preimage given
the image.
In this case, I don't see a proof that this proposal can generate any
output. I tried to construct one myself but fell over on the padding
issue. I suspect that if you were to solve that you would also have
shown that it was not preimage resistant.
If you allow a keyed hash function then it's much easier to specify
the properties it must have to be useful for entropy distillation, but
of course that gives you a chicken-and-egg problem. Maybe you can do
something with some sort of idea of "computable distributions" to
overcome the specification problem David Wagner outlines?
--
__ Paul Crowley
\/ o\ sig@paul.ciphergoth.org
/\__/ http://www.ciphergoth.org/
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@wasabisystems.com
