This has always been possible, but it sounds like they've lowered the minimum entropy needed in the source streams to produce a high-quality output.
> The academics’ latest work hurdles those restrictions allowing the use of sequences that are only weakly random
What does "weakly random" mean, if not a PRNG? Just low pure entropy per bit of sequence data? What's the threshold then between strong random and weak random -- wouldn't it be a continuum of entropy?
Minor nitpick: Also, how can a deterministic PRNG have less entropy (0) than that of its seed?
A deterministic PRNG's sequence has exactly the entropy of it's seed, actually, but it has 0 bits of entropy per symbol, because its sequence is infinite.
The thing most people get confused about with entropy is in thinking that entropy is a property of some single object, like a bit string. Really, entropy is always a measurement about a probability distribution, just like mean or variance is. In the usual case with random streams, the distribution is P(x_i | x_i-1 ... x_0) for bits x_i in the stream, i.e. the distribution remaining for the current bit even if we know all previous bits. For a deterministic PRNG, once we can extract the key from the history (given unlimited compute power) that distribution becomes deterministic, so the entropy is 0.
The one case where they coincide (sort of) is if you believe your random sequence is generated by a randomly chosen Turing machine, which I've only really seen in philosophical settings.
A uniformly chosen 64-bit integer still has exactly 64 bits of entropy, regardless of how much Kolmogorov complexity the actual bits you generate have.
If there's any way two seeds can eventually lead to identical internal states would be one example.
weakly random:
let X a random variable over {0,1}^n. That is, X is a distribution over bit sequences of length n. Distribution means I assign each of the 2^n bit sequences a nonnegative probability that sums to 1.
If X were uniform (true random), then each sequence in the 2^n such possible sequences would have probability 2^-n. Unfortunately, we have no such sequence generators, or life would be easy.
Let the min entropy of X be the largest natural k such that P[X=x] <= 2^-k for every x. ie roughly how likely are such sequences to take their most likely value. Or how biased is our RV.
eg: uniform random over sequences of length n would have min-entropy n.
Again, the problem is we have no uniform random sequences available to us. Instead, we have biased sequences. So there is a long history of asking how can we take a biased random sequence and turn it into a random sequence. You do this with an extractor.
For example, suppose we had a sequence which produced independent bits 1 with probability p and 0 with probability q=1-p. However, we don't know p. What we could do (an extractor!) is use two sequence bits to produce one output bit, as so: sequence 0,1 has probability p x q, and sequence 1,0 has probability q x p. Map 0,1 to 0 and 1,0 to 1, and ignore 0,0 and 1,1. Now we can produce 0 with probability 1/2 and 1 with probability 1/2, ie we have uniform random from an input sequence of unknown bias (but perfectly uncorrelated, which also doesn't exist in nature. Life is hard.)
We measure the quality of extractors by calculating how bad (lower entropy) a sequence they can take and how close (statistical distance, which has a technical definition) they can output a distribution close to uniform.
Anyway, I got distracted, but in general weakly random means distributions or sequences which are biased. The less biased they are the more they're called "almost random." In general, you want to build extractors that run on sequences with unknown bias.
hth
Tuesday morning I ssh into the box. How much high quality entropy do you think I got from the nearly deterministic network and disc traffic on this machine? Maybe a few bits.
What I'm hoping comes of this is that we can find a better set of inputs for several/random, and that we can use more conservative estimates of entropy from the sources that are already used. Also I hope we find a way to treat intel's hardware RNG as a low quality input (currently it's a no quality input.)