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?

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

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

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

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.