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
    If I understand Wikipedia correctly (which is admittely quite difficult), min entropy is always $\leq$ than shannon entropy. – SEJPM Nov 8 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.)

  • 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:-

graph

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.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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