Extracting uniform randomness from noisy source

[David Wagner]

Amir Herzberg  wrote:
>Also, I didn't mention another simple secure solution, which is to use 
>universal hash function h_k(noise), where again k is a random key (again, 
>such a key is necessary, but can be `burned into` the hardware). Universal 
>hash functions are easy to implement and very efficient (much more than 
>crypto hash functions).

Yes, it's true.  However, this construction has a significant
disadvantage.  If you look carefully at the proof of security for this
approach (it's usually called the Leftover Hashing Lemma), you'll find
that the approach is wasteful of entropy.  If you want a 2^80 level of
security, you need at least 240 bits of true randomness.  That's because
the theorem requires a factor of three more bits of entropy than you
might think.  SHA1 doesn't have this problem.  As entropy is hard enough
to come by as it is, I think such wastefulness is best avoided, and I
would prefer SHA1 over 2-universal hashing in any practical system.

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