Thursday, June 12, 2008

/dev/random (literally and figuratively)

1. So I'm trying to figure out a way to construct an extractor (in the sense of Barak and Halevi; I'm still unclear in exactly what way this is related to the usual definition of an extractor) from a block cipher.

A construction like this should work pretty well: Determine an m-bit key K from a long string with high min-entropy. Then, use block cipher B with that key to encrypt the all-0 block; then, take consecutive substrings A_i of length m (padding the last if necessary) and compute a sequence defined by E_(i+1) = B(K, E_i xor A_i). The last term of this sequence is the output of the extractor.

Assuming the key is chosen from some distribution with reasonably high min-entropy, then E_i and A_i should be mostly independent. If E_i is "near uniform" (i.e. has min-entropy close to the Shannon entropy) and small, and A_i and E_i are uncorrelated, then the min-entropy is almost additive. The problem is, it's not obvious how to make this rigorous, or even under what conditions it actually holds.

What does this have to do with /dev/random? Well, it's well-known how to build a pseudo-random generator from a block cipher in counter mode. So if we can also construct an extractor from a secure block cipher, we can obtain a robust, secure random generator which has the added bonuses of being 1) small and 2) fast. Which makes it a perfect candidate for replacing/supplementing /dev/random, CryptGenRandom, etc.

2. Anyone know a good resource for learning about expanders? (Other than Luca Trevisan's blog, of course; his series on the subject is pretty much just epic. I need an introduction to the topic, though, which is shallower and broader).

3. How on earth do four Supreme Court justices believe that Gitmo detainees aren't entitled to challenge their detention in civil court? If Scalia and Thomas are such "strict constructionists," why don't they note that the relevant clause of the Constitution reads:
The privilege of the writ of habeas corpus shall not be suspended, unless when in cases of rebellion or invasion, the public safety may require it.
Which, you might notice, says nothing at all about "enemy combatants," or "acceptable alternatives to habeas corpus." Unless they personally amended the Constitution themselves?