Modern Computational Cryptography

Imagine an encryption scheme that can be broken, but the fastest possible attack requires a trillion years of computation. You probably wouldn't worry about such an attack because there is no meaningful difference between a task that takes a trillion years and a task that is simply impossible. But our style of security definitions is completely agnostic to an attack's running time. If there is a calling program that can distinguish two libraries after a trillion years of computation, then those libraries are deemed not interchangeable. An encryption scheme that allows this kind of attack would be deemed insecure.

Now imagine an encryption scheme that can be broken, but the best possible attack is guaranteed to succeed only with extremely low probability. In fact, the probability that the attack succeeds is smaller than the probability of winning the lottery a hundred times in a row. Again, you probably wouldn't worry about this attack because there is no meaningful difference between an event that happens with such a tiny probability and an event that is simply impossible. But our style of security definitions is completely agnostic to an attack's success probability. If there is a calling program that can distinguish two libraries, with output probabilities that are different by the tiniest nonzero amount, then those libraries are deemed not interchangeable. An encryption scheme that allows this kind of attack would be deemed insecure.

The modern approach to provable security builds on the vocabulary that we developed in chapter 2 but dismisses attacks with astronomically high computational cost or astronomically tiny success probability. Instead of proving statements like: No attack against this scheme can succeed at all, not even in principle, we will prove statements like: Every attack against this scheme has either astronomically high computational cost or astronomically small success probability.

We'll start by clarifying precisely what is meant by “astronomically” high costs or low probabilities.

4.1. The concrete approach to provable security

In the concrete approach to provable security, our goal is to be as quantitative as possible about security claims. We rarely say definitively that a cryptographic algorithm “is secure,” as we did when discussing OTP. Instead, we say things like, “any attack that expends at most $2^{80}$ effort can succeed with probability no better than $2^{-64}$.” It is up to the user to judge whether this quantitative level of security is acceptable, based on their use-case and risk tolerance.

4.1.1. Huge numbers

The concrete approach requires good intuition about huge numbers (like $2^{128}$) and tiny numbers (like $2^{-128}$). Here are some examples to help put huge computations into perspective:

These two examples provide different monetary estimates because Bitcoin mining happens exclusively on special-purpose hardware (ASICs), which can perform Bitcoin mining and do nothing else. Cloud computing services offer general-purpose CPUs, which are orders of magnitude slower and less energy efficient, hence more expensive.

4.1.2. Tiny numbers

Next are some examples to help put tiny probabilities into perspective:

I encourage you to explore your own ways of understanding extreme numbers.

The last point about probability deserves some clarification.

• Events with probability $2^{-80}$ happen all the time. Every time you shuffle a deck of fifty-two cards, the probability of getting that particular ordering of the cards is approximately $2^{-225}$. The event that I describe as effectively impossible is that you have a specific ordering in mind before you shuffle, and then observe that ordering after shuffling. In cryptography we are always talking about specific events that are defined a priori. These are effectively impossible if their probability is $2^{-80}$.

• You must take care to consider the probability of the correct event. There may be an encryption scheme that fails catastrophically (i.e., perhaps it completely leaks the secret key) with probability $2^{-80}$ each time the $\Enc$ algorithm is called. However, some attack scenarios might allow the $\Enc$ algorithm to be invoked many times, giving an adversary many chances to trigger this catastrophic event. Of course, the adversary will be satisfied if any one of those chances succeed, so that is the event whose probability is most important. If an adversary causes $\Enc$ to be called $2^{50}$ times, then the event that really matters happens not with probability $2^{-80}$ but more like $2^{50}/2^{80} = 2^{-30}$, which is “only” one in a billion.

It is often useful to think about a trade-off between an attack's running time and its success probability:

Typical cryptographic standards are designed to target at least 128 bits of security.

4.2. The asymptotic approach to provable security

The concrete approach is helpful for answering practical questions like, how large should my keys be to achieve a comfortable security level? But with that level of precision comes the responsibility of managing more tedious quantitative details during a security proof.

The asymptotic approach is an alternative that lets us make more qualitative, all-or-nothing statements, at the cost of losing some quantitative precision. “Asymptotic” means considering the behavior of an algorithm in the limit—that is, as the key size approaches infinity. You are probably familiar with asymptotic analysis using big-$O$ notation. Focusing only on asymptotic behavior allows us to hide many tedious quantitative details. For example, you don't need to carefully calculate that a certain operation takes exactly $16n^2 + 24n + 74$ steps; you can stop as soon as you realize it takes $O(n^2)$ steps.

4.2.1. Polynomial running time

In the asymptotic approach, we only consider adversaries that run in polynomial time.

Polynomial-time algorithms are closed under composition: A polynomial-time program that calls a polynomial-time subroutine can be combined into a monolithic algorithm whose overall running time is also polynomial. Without this composition property, many aspects of the theory would be problematic or incoherent.

4.2.2. Negligible probabilities

You've seen asymptotic analysis (big-$O$) to categorize functions that approach infinity as their input grows, like the running time of an algorithm. Asymptotic analysis tells us how fast a function zooms off toward infinity.

In cryptography we also use asymptotic analysis to describe probabilities that approach zero as the input gets larger. We are interested in how fast these probability functions approach zero. If the probability of some event approaches zero fast enough, we can classify that event as effectively impossible.

Suppose a cryptographic algorithm fails catastrophically with probability $1/\secpar^2$. This probability clearly approaches zero as $\secpar$ grows, but does it approach zero fast enough? There may be attack scenarios in which an adversary could have $\secpar^2$ chances to trigger the catastrophic event, because $\secpar^2$ is a polynomial, and we consider adversaries that have polynomial running time. With so many chances, the catastrophic event actually has a very good probability of happening in at least one of the attempts. Hence, $1/\secpar^2$ does not seem to approach zero fast enough to ignore.

On the other hand, suppose the catastrophic failure happens with probability $1/2^\secpar$. If an adversary gets two chances to trigger the catastrophic event, it happens with probability at most $2/2^\secpar$; if the adversary gets $\secpar^2$ chances, the probability is at most $\secpar^2/2^\secpar$. A polynomial-time adversary can get at most a polynomial number of chances to trigger the catastrophic event, but no matter what polynomial we place in the numerator, the denominator $2^\secpar$ always “wins,” sending the overall probability to zero in the limit. Hence, $1/2^\secpar$ approaches zero fast enough to be robust for polynomial-time situations.

In the asymptotic approach to cryptography, we require an adversary's success probability to approach zero faster than any reciprocal-polynomial. Formally:

Nearly every appearance of a negligible probability in this book will be easy to identify, usually having the form $\frac{q(\secpar)}{2^\secpar}$, where $q$ is some polynomial.

4.2.3. Comparing concrete vs asymptotic

In this book, we mostly stick to the asymptotic approach. The asymptotic style leads to simpler, cut-and-dry security statements like “every polynomial-time adversary succeeds with only negligible probability," whereas the concrete style demands that we carefully account for an adversary's advantage.

For example, a security theorem in the asymptotic style might read like this:

It's not important right now to understand what “secure PRF” or “CPA-secure” means; these serve as merely an illustration here. The same theorem in the concrete style might read more like this:

Both the concrete and asymptotic approaches have clear merit, and both are common in the research literature. And it's important to acknowledge that everything we prove in this book in the asymptotic style could also be proven in a concrete style. Our fundamental approach of defining security in terms of libraries and distinguishers is compatible with both styles.

The concrete approach is necessary when determining proper key sizes. A security theorem in the asymptotic approach tells you only about a system's eventual behavior, in the limit as key sizes approach infinity. It tells you very little about its behavior for any specific key size.

Another important distinction between the concrete and asymptotic approaches is what happens if P = NP. For almost any cryptographic primitive, the problem of breaking it (asymptotically) is in the complexity class NP. So if P = NP, almost all of cryptography can be broken in polynomial time; asymptotic security is doomed in this case, but concrete security may still be viable.

4.3. Indistinguishability

In chapter 2, we said that two libraries were interchangeable if they induce identical output probabilities, for all adversaries. In the modern (asymptotic) approach, we say that two libraries are indistinguishable if they induce negligibly close output probabilities, for all polynomial-time adversaries:

Below are some facts about indistinguishability that are useful in security proofs:

4.3.1. Hybrid proofs using indistinguishability

Indistinguishability is transitive, but there is an important subtlety: The negligible advantages “pile up.” Suppose $\L_{0} \indist \L_{2} \indist \cdots \indist \L_{q}$, and suppose $\L_{i-1}$ can't be distinguished from $\L_{i}$ with advantage better than $\epsilon_i(\secpar)$, as a function of the security parameter $\secpar$. Then, the advantage when distinguishing $\L_{0}$ from $\L_{q}$ could be as high as $\epsilon_1(\secpar) + \cdots + \epsilon_q(\secpar)$.

In simple security proofs like the ones we've seen so far, the number of hybrids $q$ does not depend on the security parameter, and everything works out as you might expect. The sum of a constant number of negligible functions is also negligible, and thus $\L_{0} \indist \L_{q}$ in the example above.

However, we will soon see proofs in which the number of hybrids $q$ depends on the security parameter. For example, in some upcoming proofs $q$ is the number of times the adversary calls the library. Since the adversary is assumed to run in polynomial time, $q$ is some unspecified polynomial function of the security parameter. These situations are more delicate, because the sum of a non-constant number of negligible functions might not be negligible (see exercise 4.3). Despite this, it is still possible to prove something like the following:

Claim 4.3.3 is a simplification of the truth, but it captures the intuition needed to understand proofs later in this book: It is generally safe to write a proof with a polynomial number of hybrids.

You can safely stop at the informal statement of claim 4.3.3 if you prefer, but here are the gory details for those of you who are interested. It's not enough that $\L_{i-1} \indist \L_i$ (for all $i$), because this condition involves first fixing $i$ and then considering the libraries' asymptotic behavior as the security parameter approaches infinity. Instead, we must demand that $\L_{i-1} \indist \L_i$, even against an adversary who can choose $i$, because this new scenario allows $i$ to depend on the security parameter.

Every security proof in this book is compatible with the conditions of claim 4.3.4. But for the sake of simplicity, we won't write proofs in terms of this precise language and will instead use the more informal style of claim 4.3.3—that is, we will say things like “$\L_0 \indist \L_1 \indist \cdots \indist \L_q \equiv \L^*$, and $q$ is a polynomial in the security parameter, so therefore $\L_0 \indist \L^*$.”

4.4. The bad-event technique

In this section we will introduce a new technique that can be used to prove indistinguishability:

The lemma is a bit abstract, so before proving it, let's see an example where it applies:

The proof of the bad-event lemma uses conditional probabilities, which are briefly reviewed below. But don't worry! Once we prove the lemma, we never need to deal directly with conditional probabilities again.

We now prove lemma 4.4.1:

More strategies for the bad-event technique: The previous example featured a bad event whose probability is relatively easy to understand and bound. We are not always so lucky. Bad events often involve values chosen by the adversary, so we can't assume anything about how they are distributed. In particular, we can't assume independence, which is often important.

For example, consider the difference between the following two libraries:

In both libraries, the guess subroutine returns $R ==X$, and in both libraries $R$ is sampled uniformly. We might be tempted to say that $\PR{ R == X } = 1/2^\secpar$ in both libraries. However, this probability is correct only when $R$ is independent of $X$! This is the case in $\lib{1}$ but not (necessarily) in $\lib{2}$. In $\lib{1}$, $R$ is chosen after $X$. In $\lib{2}$, the adversary can call cheat to learn $R$ and then call guess with $R=X$. Clearly this strategy leads to an $X$ that is not independent of $R$.

This section describes some strategies to deal with bad events involving adversarially chosen values. The strategies rely on two important facts about the bad-event technique:

• Lemma 4.4.1 is symmetric with respect to $\lib{1}$ and $\lib{2}$. When using the bad-event technique to show that $\lib{1} \indist \lib{2}$, we can calculate the bad-event probability in either $\lib{1}$ or $\lib{2}$, whichever is more convenient for the analysis.

• The only thing that matters for the bad-event technique is the probability that the bad event is eventually triggered. It doesn't matter when the bad event is triggered. In other words, we could modify a library so that the bad event is triggered at a different time—potentially making our probability analysis easier—but with the same eventual probability.

The following example takes advantage of these facts and demonstrates the strategy:

This example illustrates an important strategy for the bad-event technique:

Finally, remember that the goal of the bad-event technique is to show that the bad event is triggered with negligible probability. We don't need to calculate the probability exactly; it's enough to prove a negligible upper bound.

4.5. Birthday probabilities

Many randomized cryptographic algorithms will fail in some way (i.e., lose their security) if two executions of that algorithm happen to sample the same random choices. Thus, it is important to understand the probability of such an event.

A more general form of the question is:

Let us give a name to this probability:

It is possible to write an exact formula for this probability:

Asymptotic bounds: The exact formula for $\Birthday(q,N)$ is cumbersome. It is much more convenient to use the following approximations:

We can express the birthday bound using libraries, which makes it convenient to use in a security proof:

In some security proofs we can use lemma 4.5.7 to avoid explicitly reasoning about bad events. However, bad events cannot always be avoided, especially when they involve values chosen by the adversary.

Exercises

1. Suppose that $f$ and $g$ are negligible functions. Prove that $f+g$ and $f\cdot g$ are negligible.

2. Suppose $f$ is a negligible function and $p$ is a polynomial. Prove that $f\cdot p$ is negligible.

3. For any integer $i$, define the function

   $f_i(n) = \begin{cases} 1 & \text{ if } n \le i \\ 0 & \text{ if } n > i \end{cases}.$

   1. Prove that for each $i$, $f_i$ is a negligible function.

   2. Consider the sum of many $f_i$'s, where the number of terms in the sum depends on $\secpar$:

      $g(\secpar) = \sum_{i=1}^{\hl{\secpar}} f_i (\secpar)$

      Show that $g$ is not negligible.

   3. Our convention is that all libraries have access to the security parameter $\secpar$ as a global variable. For every integer $i$, define the following library:

      $\L_i$

      $\subname{query}(\,)$:

      if $\secpar \le i$:

      return $\bit0^\secpar$

      else

      $R \gets \bits^\secpar$

      return $R$

      Prove that for all integers $i$, we have $\L_{i-1} \indist \L_i$. Remember, we are fixing $i$ and the considering the asymptotic behavior of of $\L_i$, as $\secpar$ approaches infinity.

   4. With $\L_i$ defined as above, is $\L_0 \indist \L_\secpar$? In this question, the parameter $i$ is growing along with the security parameter $\secpar$.

4. Prove that the following two libraries are indistinguishable:

   $\lib{1}$

   $\subname{a}(A)$:

   if $A \in \mathcal{A}$:

   return $\mytrue$

   else:

   $\mathcal{A} := \mathcal{A} \cup \{A\}$

   return $\myfalse$

   $\subname{b}(B)$:

   if $B \in \mathcal{B}$:

   return $\mytrue$

   else:

   $\mathcal{B} := \mathcal{B} \cup \{B\}$

   return $\myfalse$

   $\indist$

   $\lib{2}$

   $\key \gets \bits^\secpar$

   $\subname{a}(A)$:

   if $A \in \mathcal{X}$:

   return $\mytrue$

   else:

   $\mathcal{X} := \mathcal{X} \cup \{A\}$

   return $\myfalse$

   $\subname{b}(B)$:

   if $B \oplus \key \in \mathcal{X}$:

   return $\mytrue$

   else:

   $\mathcal{X} := \mathcal{X} \cup \{B \oplus \key\}$

   return $\myfalse$

   Let's call arguments to a “$A$-values” and arguments to b “$B$-values.” Library $\lib{1}$ checks for repeats among the $A$-values and repeats among the $B$-values. Library $\lib{2}$ checks whether there is any repeat among any combination of $A$-values and values of the form $B \oplus \key$, where $\key$ is a global secret.

5. Prove that the following two libraries are indistinguishable:

   $\lib{1}$

   $R \gets \bits^\secpar$

   $\subname{guess}(X)$:

   if $L$ undefined or $L \oplus X \ne R$:

   $L := X$

   return $\myfalse$

   else: // $L \oplus X == R$

   $L := X$

   return $\mytrue$

   $\indist$

   $\lib{2}$

   $\subname{guess}(X)$:

   return $\myfalse$

   In $\lib{1}$, the $\subname{guess}$ subroutine returns $\mytrue$ if called twice on consecutive inputs that xor to $R$. It uses $L$ to store the previous input to $\subname{guess}$.

6. Prove that the following two libraries are indistinguishable:

   $\lib{1}$

   $\subname{samp}(X)$:

   $Y \gets \bits^\secpar$

   $\mathcal{X} := \mathcal{X} \cup \{X\}$

   $\mathcal{Y} := \mathcal{Y} \cup \{Y\}$

   if $X \in \mathcal{Y}$ or $Y \in \mathcal{X}$:

   return $\mytrue$

   else: return $\myfalse$

   $\indist$

   $\lib{2}$

   $\subname{samp}(X)$:

   return $\myfalse$

   In $\lib{1}$, each call to $\subname{samp}$ involves an $X$-value (chosen by the adversary) and a $Y$-value (uniformly sampled, and secret). It returns $\mytrue$ if any $X$-value matches any $Y$-value (possibly from different calls to $\subname{samp}$).

7. Prove that the following two libraries are indistinguishable:

   $\lib{1}$

   $\subname{a}(\,)$:

   $A \gets \bits^\secpar$

   return $A$

   $\subname{b}(\,)$:

   $B \gets \bits^\secpar$

   return $B$

   $\indist$

   $\lib{2}$

   $\subname{a}(\,)$:

   $A \gets \bits^\secpar \hl{\setminus \mathcal B}$

   $\A := \A \cup \{ A \}$

   return $A$

   $\subname{b}(\,)$:

   $B \gets \bits^\secpar \hl{\setminus \mathcal A}$

   $\mathcal{B} := \mathcal{B} \cup \{ B \}$

   return $B$

   In $\lib{2}$, the two subroutines will never output a common value, although each subroutine can repeat a value individually.

8. Prove that the following two libraries are indistinguishable:

   $\lib{1}$

   $\subname{samp}(M)$:

   $R \gets \bits^\secpar$

   return $R$

   $\indist$

   $\lib{2}$

   $\subname{samp}(M)$:

   do

   $R \gets \bits^\secpar$

   until $M \oplus R \not\in \mathcal{X}$

   $\mathcal{X} := \mathcal{X} \cup \{M \oplus R\}$

   return $R$

   Each call to $\subname{samp}$ takes $M$ as input and gives $R$ as output. In $\lib{2}$, it is guaranteed that $M \oplus R$ never repeats.

9. Prove that the following two libraries are indistinguishable:

   $\lib{1}$

   // $\mathcal{S}$ is a set of strings

   $\subname{samp}(\mathcal{S})$:

   $R \gets \bits^\secpar$

   return $R$

   $\indist$

   $\lib{2}$

   // $\mathcal{S}$ is a set of strings

   $\subname{samp}(\mathcal{S})$:

   $R \gets \bits^\secpar \setminus \mathcal{S}$

   return $R$

   Assume that the set $\mathcal{S}$ is passed as an explicit list. That is, if the calling program runs in polynomial time, then $\mathcal{S}$ can have only polynomially many items.