[electrograv]

Thanks for the explanation, that makes sense. I think this quote threw me off:

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

[njohnson41]

Right, the amount of entropy per bit of sequence is always between 0 (deterministic) and 1 (every bit is independent and 50/50) (... or between 0 and log2(k) in general if the element varies over a set of k things). These "weak" sources just have low entropy per bit. They could be biased (more 0s than 1s) or correlated (long runs of 0s/1s or periodicity), or just have some other pattern that sometimes holds.

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.

[dietrichepp]

The entropy of a single object is a meaningful concept. It is usually called Kolmogorov complexity.

[njohnson41]

Kolmogorov complexity is definitely meaningful, but it's not (Shannon) entropy, just conceptually similar. Many people think of something like Kolmogorov-complex sequences when they think of "random" sequences, which is (IMO) why they have trouble thinking of entropy as being about a probability distribution.

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.

[x0x0]

I'm not sure if I know the precise definition, but I think I remember how it's used.

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

[Sophistifunk]

> how can a deterministic PRNG have less entropy (0) than that of its seed

If there's any way two seeds can eventually lead to identical internal states would be one example.

[hinkley]

Let's say I have a machine that runs one cron job. It looks for work, writes a few files if it finds some. Over a three day holiday weekend, no work is queued so the machine hardly does anything. And it's on a vlan so there's little to no broadcast traffic hitting it.

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