building a true RNG

[Paul Crowley]

"John S. Denker" <jsd at monmouth.com> writes:

> David Wagner <daw at 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 at paul.ciphergoth.org
/\__/ http://www.ciphergoth.org/

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