Orsdxy

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.

So is it fair to say that entropy does not imply predictability? And that predictability is something else entirely?

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.

No, entropy can imply predictability and sometimes they can be used interchangeably. Although not generally for cryptography.

If you reduce the notion of entropy to that of simple information, it becomes clearer. So the paradigm is entropy = information, and that's the standard computer science definition. Consider the Wikipedia entry:-

Information entropy is the average rate at which information is produced by a stochastic source of data.

The sometimes confusing issue though is who is surprised, at what point and what is the source? I now think of it as known entropy (high predictability) and unknown entropy (low predictability). The a priori /a posteriori experience is crucial. Three examples of sources:-

1. Shakespeare. He produced about 8 Mbits of information in his complete works, which accrued at approximately 1.5 bits per scratchy character. So H(Shakespeare) = 1.5 bits/byte, yet we know all his work. Therefore and simultaneously, we can also say that H(Shakespeare) = 0 if we were to use it for cryptography. So no surprisal.


2. AES CTR. A simple AES PRNG with a 128 bit key can produce $2^{128}$ unique streams of data. You would say that H(AES-PRNG) = 128 bits for any length of stream, yet to store that stream (simply or sans key) you would consider a H(AES-PRNG) of 8 bits/byte.


3. True random number generator. There may be no key of any sort, and the source is a physical device. Surprise is maximal for anyone reading the output with H(TRNG) = 8 bits/byte. Everyone is therefore surprised at all points and there is no known entropy. It's all unpredictable.

In the case of entropy, like pornography, Justice Potter Stewart said that you'll know it when you see it. Unless you're designing TRNG's, it's common to just assume that in cryptography entropy is the key/seed or the device that created the key/seed. And that it's a complete surprise to an attacker.