8
$\begingroup$

If entropy is the measure of surprise, and a given PRNG has a uniform distribution, then the entropy would be high. So the Mersenne Twister(MT) has high entropy.

But the MT is also predictable. You can retrieve its past bits and predict its future bits.

What's the relationship between entropy and predictability?

$\endgroup$
  • $\begingroup$ If it's predictable, how can it be surprising? $\endgroup$ – Ella Rose Jan 16 at 16:30
  • $\begingroup$ @fgrieu You're right, thanks. Made it more general. $\endgroup$ – Bastien Jan 16 at 17:53
  • 2
    $\begingroup$ @EllaRose I'm trying to draw a clear line between entropy and predictability as they apply to random number generators. $\endgroup$ – Bastien Jan 16 at 18:10
5
$\begingroup$

entropy is the measure of surprise

That's informal, short and non-quantitative, but correct within that. In the case of a Random Number Generator, we must make that: entropy is the measure of surprise in the outputs of the RNG, for one skilled person (with arbitrarily large computing power) knowing the RNG design including any parameter (for MT: the Mersenne prime used, and a few others). That's for unknown seed (if any) assumed uniformly random but arbitrarily large computing power of the skilled person (unless otherwise stated).

The entropy considered here is a property of the generator, not that of one particular bitstring that it outputs.

Entropy further can be defined for the total output of a generator, or per output bit. In cryptography we measure the entropy in bit, so that it is 1 bit per output bit for an ideal uniform True RNG.

For any Pseudo RNG, the whole output is predictable from design, parameters and seed, hence the entropy in the whole output is limited to the entropy in what generates its seed, which is finite. And the entropy per output bit decreases to zero as the output size increase towards infinity.

the Mersenne Twister(MT) has high entropy.

No, because it is a PRNG (see above).

the MT is also predictable.

Yes, with enough output, and little computing power.


What's the relationship between entropy and predictability?

If a bitstring generator has the property that it's full output is predictable from a finite length prefix (as is the case for MT), then this generator has finite total entropy (bounded by said finite length in bits for Shannon entropy in bits), and vanishingly small entropy per output bit.

The converse is false for practical definition of (un)predictable. In particular, there exist practical Cryptographically Secure PRNGs (thus of finite total entropy) that are practically unpredictable.


To make things quantitative: consider a generator $G$ of arbitrarily long bitstrings. Note $G_b$ that generator restricted to its first $b$ bits. $G_b$ is susceptible to generate $2^b$ different $b$-bit bitstrings $B$ with respective probability $p_B$ (possibly $0$ for some $B$), with $1=\sum p_B$ (the sum being over $2^b$ terms $B$). $G_b$ has Shannon entropy in bits $$H(G_b)=\sum_{B\text{ with }p_B\ne0}p_B\,\log_2\left(\frac1{p_B}\right)$$ and its average entropy per bit is $H(G_b)/b$.

For an ideal TRNG (which output is uniformly random independent bits), and any $b$, all $b$-bit bitstrings are equiprobable with $p_B=2^{-b}$ and it comes $H(G_b)=b$.

For any PRNGs with $s$-bit seed (per any distribution), $H(G_b)\le \max(b,s)$. The entropy of the generator's whole output is $H(G)=\displaystyle\lim_{b\to\infty}H(G_b)$. That is maximal with $H(G)=s$ when all seeds generate different outputs and the seed is uniformly random.

$\endgroup$
  • $\begingroup$ If as you say H(any bit string) = 0, and you wanted to transmit that string to the Martians without loss in one attempt, what determines the minimum transmission length? $\endgroup$ – Paul Uszak Jan 16 at 22:01
  • $\begingroup$ Ok, I'll repeat this back to you to see if I understand it. PRNGs have relatively low entropy because, while they may start with some high entropy bits from some source as the seed, the way the PRNG then generates subsequent bits is linear and predictable such that all the effective entropy is in the seed only. A CSPRNG in contrast generates bits in a non-linear fashion such that, even though it's still deterministic, the effective (practical) entropy remains high because it's infeasible to predict the next bit. Is that right? $\endgroup$ – Bastien Jan 16 at 23:15
  • $\begingroup$ @Bastien: yes that's correct, if we replace your "PRNGs" with linear PRNGs. That's necessary because, for standard definitions, some PRNGs (including all CSPRNGs) are not practically predictable; and some of the practically predictable PRNGs are not linear (including most PRNGs built from a CSPRNG by restricting the seed, and many others). $\endgroup$ – fgrieu Jan 17 at 7:58
1
$\begingroup$

For the entropy of a bit string to be meaningful, it must have been chosen in some particular random or partially-random process which had a certain probability of producing that exact string, and a certain probability of producing something else. The entropy of a string is then, roughly(*), the negative log of the probability that the process that produced the string, would have done so. Thus, if some process generates a string which has 8 bits of entropy, that means that the process would have had a 1 in 256 chance of generating that particular string.

(*) There are a variety of ways of measuring entropy, but for most purposes they're close to each other that a simple approximation can be reasonably close to all of them.

If a process does not generate strings with equal probability, it's often appropriate to regard the entropy produced by the process as being that of the highest-probability string. So if a process has a 50% chance of generating the 16-bit string of zeroes, and a one in 131,070 chance of generating any other 16-bit string, it would generally be appropriate to regard the process as yielding one bit of entropy even one could filter the output to yield more (e.g. generating bit strings until one gets one that isn't all zeroes would yield 15.999978 bits of entropy while requiring, on average, only twice as long as generating one bit).

$\endgroup$
  • $\begingroup$ OK, I've seen the negative log calculation before. So if a random process has a uniform distribution, we can say its entropy is high, correct? So what I'm trying to understand is the relationship between entropy and predictability. Because from what I'm reading, something with high entropy doesn't automatically make it unpredictable. So you can have a PRNG with high entropy that still wouldn't be suited for cryptography purposes. $\endgroup$ – Bastien Jan 16 at 18:02
  • $\begingroup$ @EllaRose Yeah, so if a random process has a uniform distribution, we can say its entropy is high is a vacuously true in that case. You would have to show a random process with low entropy. The lowest would be a random bit, but in general if you randomly sample from a uniform distribution, the entropy will be maximized for that domain. Hashing an incrementing counter would not count as a random sample since it gives the same results each run. $\endgroup$ – PyRulez Jan 16 at 18:48
  • $\begingroup$ Ah, I see where I went wrong, using a deterministic process to try and prove a point about a random one. (Apologies to supercat for blowing up their notifications) $\endgroup$ – Ella Rose Jan 16 at 18:51
  • $\begingroup$ @fgrieu: The entropy of a bit string in a particular context is measured relative to the probability that the process that produced it could have alternative bitstrings instead, and is meaningful only in contexts where that can be measured or estimated. $\endgroup$ – supercat Jan 16 at 19:31
  • $\begingroup$ @supercat: you are right about the possible definition of entropy of a particular bitstring. I should have read more carefully. However I think that the question uses entropy for that of the generator, not of a bitstring. $\endgroup$ – fgrieu Jan 16 at 20:16
1
$\begingroup$

PRNG would have a pseudo-uniform distribution, so to speak. There is actually a correlation between its outputs. So its entropy is limited to that of the seed.

Having (really) low entropy makes something predictable, since you can just bruteforce the seed. The converse is not true, however. A poorly designed PRNG will leak entropy in a way an adversary can take advantage of (unless the PRNG is not meant to be resistant to adversaries, like a video game). When a good PRNG leaks entropy, on the other hand, its computationally infeasible to take advantage of, so it effectively never decreases in entropy for practical purposes.

$\endgroup$
0
$\begingroup$

The entropy of a random string is the number of bits you need to describe the full string, there is no computational aspect there. But if MT is predictable, it means with "few" bits, you can retrieve the full chain, then it could not have high entropy.

In fact an efficient PRNG could not have too much "high" entropy (because the seed/secret key should not be too long), but it doesn't mean there is an efficient attack to retrieve the full string.

$\endgroup$
-3
$\begingroup$

...a given PRNG has a uniform distribution, then the entropy would be high.

In cryptography, it is common to consider the entropy of a generator as the unknown input to that generator. It would be equivalent to the seed or key for a RNG. So for a common AES-128 counter based CSPRNG, the entropy would be 128 bits. The output distribution is irrelevant where cryptographic entropy is concerned, although most RNGs in their original forms do produce uniform output. They would be difficult to use for encryption otherwise.

So the Mersenne Twister(MT) has high entropy.

Ish. It starts out high with an entropy of 19,937 bits for the common 32 bit implementation. However MT is invertable and the state can be discovered by looking at sufficient output. Observing 624 output words from MT allows the internal state to be discovered. Consequently the entropy reduces by 32 bits per output word, reaching zero after 624 outputs. Any subsequent output is entirely predictable. The leftover hash lemma applies to MT outputs less than 624 words, when it would be acting as a very inefficient randomness extractor.

What's the relationship between entropy and predictability?

In cryptography generally, entropy = unpredictability = surprisal. That is necessary for seeding RNGs and creating keys. A cryptographer strives for unpredictable RNG sequences and unknown keys. A CSPRNG cannot be inverted, the seed/key cannot be recovered and thus the entropy, unpredictability and surprisal of output is preserved no matter the length of said output.

$\endgroup$
  • 1
    $\begingroup$ "although most RNGs in their original forms do produce uniform output" They certainly do not, as that would be information theoretically impossible. What they do is produce an output distribution that is computationally indistinguishable from a uniform distribution. $\endgroup$ – Maeher Jan 17 at 10:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.