Extracting uniform randomness from noisy source

[Sandy Harris]

John Kelsey wrote:

> The thing that struck me, thinking about this, is that the kind of security
> proof available for any of these primitives is a poor fit for the actual
> problem.  That's pretty-much a recipe for getting proposals that don't work
> in practice.
> 
> Would it make sense to differentiate the two different things we're trying
> to do, here?
> 
> a.  Map the entropy from one string sampled from a large set with only
> approximately-known distribution to a short string, in such a way that we
> have a strong expectation that the short string will have a uniform
> distribution.
> 
> b.  Output the result in a way that doesn't leak partial information about
> its inputs, and that (if full entropy was provided in the input) isn't
> distinguishable from a random value in practice.
> 
> Also, in a practical system, we're likely to want:
> 
> c.  Output the result in a way that is expected to be unconditionally
> secure (indistinguishable from random to unbounded attackers) if there was
> sufficient entropy in the input, and computationally secure (reducing to
> the strength of AES, HMAC-SHA1, etc.) if not.

Are Nystrom's "perfect" s-boxes a useful primitive here? With 2n bits in
and n out, you can construct an s-box such that all output columns are
bent boolean functions, and so are all linear combinations of columns.

It seems to me that some sort of S-P network built with Nystrom s-boxes
ought to give us what we need here. We need to compress a bunch of
low-entropy data into a high-entropy chunk, and each s-box gives 2-to-1
compression. We need provable properties for the network, and Nyberg's
proofs or the s-box properties give us a starting point.

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