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?
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.
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).
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
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.
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.
The entropy of a random string is the number of bits you need to describe the full string this appears to be the definition of kolmogorov complexity, rather than entropy.
$\endgroup$
– Ella Rose♦
Jan 16 at 16:32
...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.
