Relation between entropy and min-entropy

I understand that the entropy is the number of bits that can encode a set of messages. However, I don't understand what the min-entropy is and how it is related to entropy.

Let's describe a simple password case: if a password is 100 random bits, is the min-entropy also 100?

• If I understand Wikipedia correctly (which is admittely quite difficult), min entropy is always $\leq$ than shannon entropy. – SEJPM Nov 8 at 15:14

2 Answers

There is min-entropy, Shannon entropy, and max entropy. (Plus a few more definitions, but let's only focus on these.) All of these measures are greatest, for a given number of outcomes, when each outcome occurs with equal probability. (In such case all three are equal.)

$$\text{min-entropy} \leq \text{Shannon entropy} \leq \text{max-entropy}$$

Min-entropy describes the unpredictability of an outcome determined solely by the probability of the most likely result. This is a conservative measure. It's good for describing passwords and other non-uniform distributions of secrets.

$$\text{min-entropy} = -\log_2{(p_{\text{max}})}$$

Say you have an algorithm which produces 8 digit numeric password. If the number 00000000 occurs 50% of the time and the remaining $$10^8 - 1$$ passwords occur with equal probability. The Shannon entropy would be about $$14.3$$ bits, but the min-entropy is precisely $$1$$.

Min-entropy can be associated with the best chance of success in predicting a person's password in one guess.

Shannon entropy is defined to equal $$\sum_{i=0}^n{-p_i\log_2(p_i)}$$ for a probability distribution $$p$$ with $$n$$ posisble outcomes. Shannon entropy describes the average unpredictability of the outcomes of a system.

It also measures how much information is in a system (on average). Shannon entropy is the smallest possible average file size for a compression algorithm designed specifically with the distribution $$p$$ in mind.

Max-entropy is defined solely on the number of possible outcomes. It is equal to $$-\log_2(n)$$. It's not particularly useful in cryptography or passwords. It's a measure of the number of bits you would need to have to designate one bit pattern for every possible outcome.

The three quantities are always the same for a uniform distribution. This is because $$p_i = p_\text{max} = \frac{1}{n}$$.

$$-\log_2(p_\text{max}) = -\log_2 (\frac{1}{n}) = \log_2 (n)$$

$$\sum_{i=0}^n{-p_i\log_2(p_i)} = n(\frac{1}{n} \log_2 (\frac{1}{n})) = -\log_2 (\frac{1}{n}) = \log_2 (n)$$

This is why passwords picked from a uniform distribution (using a secure RNG) are said to be stronger than human generated passwords. Humans are biased in which password they choose. (Their password distribution is non-uniform.)

• measure are greatest or equal? – kelalaka Nov 8 at 16:47
• @kelalaka Regarding the third sentence? Greatest (maximized) AND equal (to each other). – Future Security Nov 8 at 16:49
• Yes, the third sentence – kelalaka Nov 8 at 16:50

Entropy is a measure of fundamental information within a system, and comes in various degrees of conservatism as far as cryptography is concerned. But there is a very important threshold entropy measure called Shannon entropy.

You hint at it in your question, in that no entropy measure lower than Shannon entropy can completely describe a system. So Shannon entropy can fully describe a system without any information loss, and forms the lower bound for any compression algorithm. Min. entropy as $$-log(p_{max})$$ tends to be used in cryptographic circumstances as it's the most conservative. But it cannot fully describe a system. It is a lossy measure of information. By analogy, min. entropy is to information as a JPEG is to an image. Shannon entropy would be a PNG or GIF.

And no, a password of 100 random independent bits would not have a min. entropy of 100 if you measure it empirically. A real sample of 100 random bits might easily result in 60 ones and 40 zeros. That would give a min. entropy of $$-log_2(0.6)*100$$ which is 74 bits. That's why it is called min.

The following shows this min. effect on a histogram of bits from /dev/urandom:-

Empirical min.entropy in this case is 0.9913 bits/bit of the sampled 1MB of data, whereas you might theoretically expect 1.0 bits/bit.