Why is Min-entropy significant in cryptography?

Question

Let $H_{min}$ = Min-entropy and $H$ = Shannon entropy.

Unless you're gaming the system or deliberately trying to be obtuse, very rarely is $ \frac{H} {H_{min}} > 10$ from any conceivable physical source. To achieve a ratio of >10 in hardware/ real life would be quite a feat of engineering and tantamount to a joke/NSA conspiracy. For worldly context, lift engineering commonly uses a safety factor of 7. If the lift gear fails, real people die. Since arbitrarily, $ \frac{H}{100} << H_{min} $ in the overwhelming majority of cases, why is $H_{min}$ significant in cryptography?

---

I know the definitions.

Answer 1

In most cases, cryptography requires values to be uniformly random (in which case discussions of min-entropy are moot) or unpredictable (in which case min-entropy isn't sufficient --- though "conditional" min-entropy might be --- since in these contexts an adversary typically has multiple guesses).

The context where I see min-entropy play the greatest role is in randomness extraction. Since physical sources of randomness rarely produce uniformly random bits, we need a way to transform the output of some physical system (presumably containing some amount of entropy, however measured) into a uniformly random bit string. At that point, we can start to do cryptography.

The Leftover Hash Lemma tells us how to take an input $X$ and transform it into a value $f_S(X) \in \{0, 1\}^n$ that is "close" to uniform. In particular, it tells us how to construct $f$ such that $n \leq H_{\infty}(X) - 2 \log(1/\epsilon)$, where $\epsilon$ is the statistical distance between the uniform distribution and $f_S(X)$ (technically, the distance between $(S, f_S(X))$ and $(S, U)$, where $U$ and $S$ are uniform and $S$ is implicitly a fixed, public value).

We're not making any assumptions on $X$ except for it's min-entropy. This quite nice because in practice we can't precisely characterize the distributions used to provide inputs to RNGs (which vary from device to device in the case of HW RNGs, and are not known a priori in the case of, e.g., /dev/urandom). Of course, estimating $H_{\infty}(X)$ is its own bag of worms...

Answer 2

We're going to play a game of guess-what-number-I'm-thinking-of.

I will pick a number at random out of {0,1,2,3}. You don't know what the number is, but I will tell you what the probability distribution is. I want to put a bound on the probability that you win this game, no matter what strategy you use. Your strategy is a probability distribution on guesses. (You are not allowed to scream LOOK BEHIND YOU, A THREE-HEADED MONKEY—only number guesses are allowed.)

1. Suppose I use the following probability distribution:

   \begin{equation} \begin{array}{c|c} \text{number} & \text{probability} \\ \hline 0 & 1/4 \\ 1 & 1/4 \\ 2 & 1/4 \\ 3 & 1/4 \\ \end{array} \end{equation}

   The Shannon entropy of this distribution is $$H = -\sum_i p(i) \log p(i) = -4\cdot (1/4) \log(1/4) = -\log(1/4) = 2\,\mathrm{bits}.$$

   The min-entropy of this distribution is $$H_\infty = -\max_i \log p(i) = -\log(1/4) = 2\,\mathrm{bits}.$$

   • If you always guess 0, your success probability is 1/4.
   • If you always guess 1, your success probability is 1/4.
   • If you always guess 2, your success probability is 1/4.
   • If you always guess 3, your success probability is 1/4.
   • If you guess uniformly at random—the same distribution I gave here—then your success probability is 1/4.

   In fact, no matter what strategy you use, your success probability is always 1/4, which is also $2^{-H} = 2^{-H_\infty}$ in this case.

2. Suppose I use the following probability distribution instead:

   \begin{equation} \begin{array}{c|c} \text{number} & \text{probability} \\ \hline 0 & 1/2 \\ 1 & 1/4 \\ 2 & 1/8 \\ 3 & 1/8 \\ \end{array} \end{equation}

   The Shannon entropy of this distribution is

   \begin{align} H &= -\sum_i p(i) \log p(i) \\ &= -(1/2) \log (1/2) - (1/4) \log (1/4) \\ &\quad - (1/8) \log (1/8) - (1/8) \log (1/8) \\ &= (1/2) \log 2 + (1/4) \log 4 + 2\cdot (1/8) \log 8 \\ &= 1.75\,\mathrm{bits}. \end{align}

   The min-entropy of this distribution is \begin{align} H_\infty &= -\max_i \log p(i) = -\log(1/2) = 1\,\mathrm{bit}. \end{align}

   • If you always guess 0, your success probability is 1/2.
   • If you always guess 1, your success probability is 1/4.
   • If you always guess 2, your success probability is 1/8.
   • If you always guess 3, your success probability is 1/8.

   • If you guess uniformly at random, your success probability is is only 1/4. To compute this probability, let $N$ be a random variable for my number and $G$ for your guess. Your success probability is $\Pr[N = G]$. If we sum over all possible values of $N$ and $G$ and expand by the chain rule of probability theory, $$\sum_{n = 0}^3 \sum_{g = 0}^3 \Pr[n = g \mid N = n, G = g] \cdot \Pr[N = n, G = g],$$ note that the left-hand probability $\Pr[n = g \mid \cdots]$ is simply 1 or 0 because the indices $n$ and $g$ are not random variables, and the right-hand probability $\Pr[N = n, G = g]$ is $\Pr[N = n] \, \Pr[G = g]$ since my number $N$ and your guess $G$ are independent. Thus, your success probability is

     \begin{align} \sum_{i = 0}^3 \Pr[N = i] \cdot \Pr[G = i] &= (1/4)\cdot(1/2) + (1/4)\cdot(1/4) + 2\cdot(1/4)\cdot(1/8) \\ &= 1/4. \end{align}

   The best strategy is obviously to always guess 0: then you will win the game half the time. No other strategy can do better than this; indeed, no other strategy can even attain this success probability. This success probability is, in fact, $2^{-H_\infty}$.

‘But that's silly!’, you interject. ‘You just defined $H_\infty$ so it is $-\log_2$ of the highest possible success probability; the fact that it is called “min-entropy” in probability theory jargon is a coincidence!’ Well, yes. What is of interest in cryptography is setting bounds on the adversary's success probability, so that we have high confidence the adversary will not succeed. The coincidence means we can take advantage of theorems from probability theory relating notions of entropy and computing the entropy of various distributions we use to model the real world.

Shannon entropy is directly relevant to optimizing your telegram budget. If you want to send a stream of telegrams from San Francisco to Tokyo where each telegram is chosen randomly using the distribution in (2), you can save money by encoding the number 0 as the bit string 0, the number 1 as the bit string 10, and the numbers 2 and 3 respectively as 110 and 111, instead of using the usual binary encoding of integers as 00, 01, 10, and 11. This is not relevant to cryptography, so Shannon entropy is useful only when we can bound the distance from Shannon entropy to min-entropy of some distribution in question—in general, nothing can be said about that distance.

Answer 3

You have to be very careful, since the context in which the entropy is being used can make a big difference. A random variable $X$ on $\{0,1\}^{128},$ which has Shannon entropy $$H(X)=127$$ bits and Renyi entropy (of order $1/2$) $$H_{1/2}(X)= 127/5<25$$ bits can be guessed on average by $2^{25}$ guesses in a brute force attack. So the security parameter is $2^{\text{entropy}}$ and ist has been reduced by taking the fifth root, not by dividing by 5.

See discussion in the questions here and here.