Extracting uniform randomness from noisy source

[David Wagner]

Sandy Harris  wrote:
>Are Nystrom's "perfect" s-boxes a useful primitive here?

No.  At least, I don't see how they would change anything.

>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.

I don't believe it.  I earlier sketched a proof that no deterministic
scheme can achieve everything we'd like, if we assume nothing about the
input distribution other than that it has enough entropy.  I believe
the proof applies to all schemes, whether or not they use bent S-boxes
or other clever ideas.  I don't see how your approach evades this
fundamental barrier.  What am I missing?

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