Extracting unifrom randomness from noisy source

[Amir Herzberg]

Hi all, I've looked into this a bit further, and here is summary. 

1. In order to extract randomness from an arbitrary noisy source, we
need to use some short, `seed` random string. We assume that the noise
is independent of this `seed`. (If we don't use a seed, then every
randomness extracting (deterministic) function has some distribution of
input (noise) for which the output is not uniformly distributed - e.g.
any distribution of inputs which map to one output...)

2. Of course, the `seed` requirement does not apply if we hash the noise
using a hash function, and analyse using the `random oracle` model i.e.
analyse security when the hash function is implemented by a randomly
choosen function. But clearly here the randomness is `hidden` in the
`choice` of the random function. Clearly this is not a good
justification for relying on any particular hash function (e.g. SHA1)!

3. I don't know of any attack showing a reasonable, natural source of
noise for which the output of some reasonable hash function is
non-uniformly distributed. However I'm also not aware of any
cryptoanalytical effort to demonstrate such an attack. While almost all
practical crypto is based on unproven assumptions and `proof of security
by failure of cryptoanalysis`, seems that simply relying on SHA1(noise)
to be uniform is hardly justifyable. 

4. There is substantial amount of research showing efficient randomness
extractors. Noam Nisan has a nice survey, available from his homepage,
N. Nisan. Extracting randomness: How and why (a survey). In Proceedings
of the 11th IEEE Conference on Computational Complexity, pages 44--58.
IEEE, New York, 1996. 

5. While the extractors described by Nisan (and others) are indeed very
efficient, I'm not aware of any available implementations. Implementors
may consider using therefore their favorite block cipher, e.g. AES,
using a random key. Notice that this random key should be selected
uniformly but could be part of the software, common to all deployments
and non-secret; security is only based on the independence of the
sampled noise in this key. Namely, 

pseudo-random = AES_k (noise) 

Security of this construction follows from the assumption that the block
cipher (e.g. AES) is a Pseudo-random function; notice that this is a
standard assumption for block ciphers (and therefore block ciphers are
cryptoanalysed to meet this assumption). 

6. Of course under the random oracle model, h(x,k) is also a
pseudo-random function... But why?

Regards, Amir Herzberg
See http://amir.herzberg.name/book.html  for lectures and draft-chapters
from book-in-progress, `Introduction to Cryptography, Secure
Communication and Commerce`; feedback appreciated!
 


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