Unconditional Cryptography

Rudiments of Provable Security

2.1. Attack scenarios as libraries

In the previous chapter, we showed how to formalize an attack scenario in terms of an adversary calling a special subroutine. Later in this book, we will encounter attack scenarios that are not easy to describe with just a single subroutine.

In some attack scenarios, the victim can perform several different kinds of actions. For example, the adversary may compel the victim to encrypt one thing, then decrypt another. It is convenient to model fundamentally different actions as separate subroutines.
Many attack scenarios feature stateful victims. For example, a victim holds a long-term key that it uses to encrypt many plaintexts. We need a way to describe persistent values that are reused across different subroutine calls.

Instead of using a single subroutine, we can formalize attack scenarios as libraries:

Definition 2.1.1 (Libraries)

A library is simply a collection of subroutines. We specify libraries as concrete pseudocode, and we have some important conventions about the meaning of that code:

All variables are private to their own library's scope and cannot be accessed by the calling program.
All variables are global to the library and accessible to all subroutines in the same library.
Lines of code outside of any subroutine (always written at the top of the library) are executed at the beginning of time. Usually these lines initialize global variables.

Certain types of variables are initialized to a default value so that we don't need to explicitly write their initialization.

boolean variable	initialized to $\myfalse$
integer variable / counter	initialized to zero
set variable / collection	initialized to the empty set
associative array / dictionary	initialized to the empty map

Code comments begin with $\bit{//}$ .

Example 2.1.2

The following library has two subroutines and one global variable $D$ :

\lib{dice-guess}

D \gets \{1,2,3,4,5,6\}

\subname{guess}(G)

return

D == G

\subname{reroll}(\,)

D \gets \{1,2,3,4,5,6\}

// without an explicit return

// statement, returns

\mynull

This library models an attack scenario in which a victim holds a 6-sided die. The first line of the library (outside of any subroutine) represents what the victim does at the beginning of time: It rolls the die. Both subroutines access a global variable $D$ . The two subroutines represent actions that the adversary can cause, at any time: The adversary can make a guess about the current value of the die and learn whether the guess was correct. The adversary can also instruct the victim to (privately) re-roll the die, learning nothing about the result of that roll.

The adversary plays the role of a calling program that invokes the subroutines of a library. We need a way to write the act of combining a calling program with a library and executing the resulting combined program.

Definition 2.1.3 (Linking calling programs & libraries)

Suppose a program $\A$ makes calls to subroutines in a library $\L$ . Then we write $\A \hl{\link} \L$ to denote the result of linking $\A$ to $\L$ in the obvious way, resulting in a combined, self-contained program.

We write $\A \link \L \outputs b$ to denote the event that the combined program $\A \link \L$ outputs the value $b$ . If $\A$ or $\L$ are randomized, then the output of $\A$ is a random variable with an associated probability distribution. We usually care about calling programs that return a boolean output. We define $\PR{ \A \link \L \outputs \mytrue }$ to be the output probability of $\A$ linked to $\L$ .

Example 2.1.4 (Output probabilities)

Below is an example calling program $\A$ linked to the dice-rolling library $\lib{dice-guess}$ from example 2.1.2:

\A

\subname{guess}(6)

return

\mytrue

\subname{reroll}()

return

\subname{guess}(6)

\link

\lib{dice-guess}

D \gets \{1,2,3,4,5,6\}

\subname{guess}(G)

return

D == G

\subname{reroll}(\,)

D \gets \{1,2,3,4,5,6\}

return

\mynull

The combined program outputs $\mytrue$ if the victim rolls a 6 in either of its first two rolls. One way to calculate the resulting output probability is the following:

\begin{aligned} \PR{ \A \link \L \outputs \mytrue } &= 1 - \PR{ \A \link \L \outputs \myfalse } \\ &= 1 - \PR{ \text{first roll } \ne 6 } \PR{ \text{second roll } \ne 6 } \\ &= 1 - \frac 56 \cdot \frac 56 = 1 - \frac{25}{36} = \frac{11}{36}.\end{aligned}

When we reason about security properties, we write a lot of different libraries on the page. But remember, security is about what happens when an adversary is allowed to call the library's subroutines. We just can't write the adversary on the page, because adversaries are always unspecified and arbitrary. Whenever you see the code of a library, always remember to picture an adversary in the role of a calling program.

It is standard in cryptography to define security in terms of adversaries interacting with libraries that play the role of the victims, but the idea of calling them libraries is unique to this book. Elsewhere, you might see libraries called (security) games or (security) experiments.

2.2. Interchangeable libraries

In the previous chapter, we discussed the security of OTP by showing that the following two subroutines have the same behavior; on every input, they generate the same output distribution:

\subname{attack}(\ptxt)

\key \gets \bits^n

\ctxt := \key \oplus \ptxt

return

\ctxt

\subname{attack}(\ptxt)

R \gets \bits^n

return

R

Let's extend this idea from simple subroutines to more complicated libraries. What does it mean for two libraries to “produce the same output behavior,” especially if they have several subroutines, or persistent/static variables? We will say that two libraries $\lib{1}$ and $\lib{2}$ “have the same behavior” if they induce the same output probability in every calling program.

Definition 2.2.1 (Interchangeable libraries)

Suppose two libraries $\lib{1}$ and $\lib{2}$ have the same interface: identically named subroutines with identical argument types and return types. We say that $\lib{1}$ and $\lib{2}$ are interchangeable, and we write $\hl{\lib{1} \equiv \lib{2}}$ , if no calling program behaves differently when linked to either of the two libraries. More formally, $\lib{1} \equiv \lib{2}$ if, for every calling program $\A$ with boolean output,

\PR{ \A \link \lib{1} \outputs \mytrue } = \PR{ \A \link \lib{2} \outputs \mytrue }.

It might help to think of a calling program as a distinguisher whose goal is to determine whether it is linked to $\lib 1$ or to $\lib 2$ . The two libraries are interchangeable if no distinguisher can succeed, not even with the smallest change in its output probability.

It is important to understand exactly what information can pass between $\A$ and $\L$ in the combined program $\A \link \L$ . In short, the only thing that the calling program can learn about the library's operation is the return value of its subroutines. In particular:

The calling program cannot access the variables inside the library. This is what we mean when we say that the library's variables are privately scoped to the library. The calling program can learn about private variables only through what $\L$ 's subroutines are willing to provide as return values.
The calling program cannot measure how long (e.g., number of clock cycles) the library takes to compute the response. The calling program cannot detect cache hits/misses that might indicate whether the library accessed a certain region of memory. Remember, the point of all this is to formally prove things about security. Our calling programs and libraries are clean mathematical abstractions, not literal (messy) physical computers.

You can use the methods in this book to prove security guarantees that involve an adversary who can observe response times and/or CPU cache behaviors, and so on. You simply need to make these channels of information explicit in your libraries; they don't exist automatically like they do when programs are running together on the same physical computer.

It is also important to understand that definition 2.2.1 involves two completely independent program executions. We consider the output probability of $\A$ linked to $\L_1$ , then, separately, consider the output probability of the same $\A$ linked to $\L_2$ . We never consider any scenario in which $\A$ is linked to both libraries at once, or where one library is swapped for the other during an ongoing execution of $\A$ .

Claim 2.2.2 (Re-stating OTP security using libraries)

Claim 1.4.1 can be rephrased as follows: The following two libraries are interchangeable.

\lib{otp-real}

\otpenc(\ptxt)

\key \gets \bits^n

\ctxt := \key \oplus \ptxt

return

\ctxt

\equiv

\lib{otp-rand}

\otpenc(\ptxt)

R \gets \bits^n

return

R

In other words, no adversary can tell the difference between OTP ciphertexts and uniformly sampled strings, given the ability to arbitrarily choose the plaintexts, when OTP keys are sampled uniformly and used for only one encryption.

In the proof of claim 1.4.1 we showed that these two subroutines induce identical output distributions for every choice of input. Since the only information passed from library to calling program is this subroutine output, this implies that the libraries are interchangeable.

Finally, definition 2.2.1 puts absolutely no restriction on the calling program. The two libraries must induce identical output probabilities on all calling programs, even those whose running time is astronomical. Only in later chapters will we care about the running time of calling programs.

Ways to be interchangeable: You're probably familiar with many ways that two different programs can “have the same behavior.” Here are a few examples:

Example 2.2.3 (Interchangeable libraries)

Two libraries are interchangeable if:

Their only difference happens in unreachable lines of code.

$\subname{foo}(n)$ :

$\cdots$

$X \gets \{1, \ldots, n\}$

if $X < 0$ :

return $\bit 0^n$

$\cdots$

$\equiv$

$\subname{foo}(n)$ :

$\cdots$

$X \gets \{1, \ldots, n\}$

if $X < 0$ :

return $\bit 1^n$

$\cdots$
Their only difference is the value they assign to a variable that is never actually used.

$\subname{foo}(A,B)$ :

$\cdots$

$C := \subname{bar}(\hl{A})$

$\cdots$

$\subname{bar}(M)$ :

$X \gets \bits^n$

return $X$

$\equiv$

$\subname{foo}(A,B)$ :

$\cdots$

$C := \subname{bar}(\hl{B})$

$\cdots$

$\subname{bar}(M)$ :

$X \gets \bits^n$

return $X$
Their only difference is that one library unrolls a loop that occurs in the other library.

$\subname{foo}(n)$ :

if $n<1$ : return $\mynull$

for $i = 1$ to $n$ : $\subname{bar}(i)$

$\cdots$

$\equiv$

$\subname{foo}(n)$ :

if $n<1$ : return $\mynull$

for $i = 1$ to $n-1$ : $\subname{bar}(i)$

$\hl{\subname{bar}(n)}$

$\cdots$
Their only difference is that one library inlines a subroutine call that occurs in the other library.

$\subname{foo}(A)$ :

$\cdots$

$C := \subname{sample}()$

$\cdots$

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

$X \gets \bits^n$

return $X$

$\equiv$

$\subname{foo}(A)$ :

$\cdots$

$C \gets \bits^n$

$\cdots$

Hopefully it's quite clear why each of these pairs of libraries “have the same behavior.” Each example is extremely simple, yet each one appears somewhere in a proof later in this book.

Most attack scenarios involve randomized libraries, and these can be interchangeable in more interesting ways:

Example 2.2.4 (Interchangeable libraries involving randomness)

Concatenating two strings, which were sampled independently and uniformly, has the same effect as sampling from the uniform distribution over longer strings.

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

$X \gets \bits^n$

$Y \gets \bits^m$

// “ $\|$ ” denotes string concatenation:

return $X \| Y$

$\equiv$

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

$R \gets \bits^{n+m}$

return $R$
It does not matter when a value is sampled, as long as it is sampled before its first use. In the left library below, $S$ is sampled eagerly, at the beginning of time. In the right library, $S$ is sampled lazily, at the last possible instant before it is used.

$S \gets \bits^n$

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

return $S$

$\equiv$

// $S := \myundef$ by default

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

if $S$ undefined:

$S \gets \bits^n$

return $S$
If we sample uniformly, but re-sample whenever we get an “undesirable” value, this has the same effect as sampling uniformly from the set of “desirable” values. In the example below, values above 90 are “undesirable”:

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

do:

$A \gets \{1,\ldots,100\}$

while $A > 90$

return $A$

$\equiv$

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

$A \gets \{1,\ldots,90\}$

return $A$

Kerckhoffs's principle: How is Kerckhoffs's principle reflected in the idea of interchangeability? Two libraries must induce the same output probability in all calling programs, even calling programs whose source code depends arbitrarily on the source code of the libraries. In plain language, the calling program can “know” the source code of the two libraries that it tries to distinguish.

Remember: Even if its source code is public, a library can still have secrets. Knowing that the library executes the statement “ $\key \gets \bits^n$ ” doesn't help you know the specific of value $\key$ that was chosen at runtime.

2.3. How to distinguish two libraries

Every security definition in this book is phrased in terms of two interchangeable libraries. So when we need to demonstrate that something is insecure, we show that those two libraries are not interchangeable. To do this, it's enough to describe just one calling program that produces different output probabilities in the presence of the two libraries. There are usually many different ways to write such a calling program, making this a good outlet for expressing your creativity.

Demonstrating Insecurity / “Attacking” Insecure Schemes

When you are asked to show that something is insecure, you are being asked to show that two libraries are not interchangeable.

First, figure out which two libraries are involved.
Write down the code of a calling program. This program's goal is to behave differently in the presence of the two libraries.
Calculate the two relevant output probabilities. If they are different, then your attack has succeeded.

Let's see some examples of how to distinguish two libraries. Consider a victim who encrypts many OTP plaintexts (of the adversary's choice) using the same key. We want to show that the resulting ciphertexts will not appear uniformly distributed. We can do so by showing that the following two libraries are not interchangeable:

\lib{1}

\key \gets \bits^n

\otpenc(\ptxt)

\ctxt := \key \oplus \ptxt

return

\ctxt

\not\equiv

\lib{2}

\otpenc(\ptxt)

\ctxt \gets \bits^n

return

\ctxt

Library $\lib{1}$ describes an attack scenario in which the key $\key$ is chosen once at the beginning of time, and reused in each call to $\otpenc$ . Library $\lib{2}$ describes a scenario in which the adversary sees only “random junk.” Below are a few ways to think about a successful attack distinguishing these libraries:

Example 2.3.1 (Attacking OTP with a reused key, #1)

In OTP, it is possible to obtain the key by requesting an encryption of the all-zeros plaintext. In $\lib{1}$ , making multiple calls of the form $\otpenc(\bit 0^n)$ will result in the same response $\key$ every time. We wouldn't expect the same response every time from $\lib{2}$ . We formalize this idea by writing the following adversary program:

\A

\ctxt_1 := \otpenc(\bit 0^n)

\ctxt_2 := \otpenc(\bit 0^n)

return

\ctxt_1 == \ctxt_2

When $\A$ is linked to $\lib{1}$ , as we argued, $\ctxt_1 = \ctxt_2 = \key$ . Therefore, $\A \link \lib{1}$ outputs $\mytrue$ with probability 1.

However, when $\A$ is linked to $\lib{2}$ , the values $\ctxt_1$ and $\ctxt_2$ are distributed uniformly and independently. The probability that $\ctxt_1 = \ctxt_2$ is therefore only $1/2^n$ . Hence:

\begin{aligned} \PR{ \A \link \lib{1} \outputs \mytrue } &= 1, \\ \PR{ \A \link \lib{2} \outputs \mytrue } &= 1/2^n.\end{aligned}

The probabilities are different, so the two libraries are not interchangeable.

Example 2.3.2 (Attacking OTP with a reused key, #2)

Another observation we might make is that a plaintext $\ptxt$ is encrypted to the same ciphertext $\ctxt$ every time. If an adversary calls $\otpenc(\ptxt)$ multiple times with the same $\ptxt$ , then in $\lib{1}$ the responses will be the same, but in $\lib{2}$ the responses will be sampled independently.

We can formalize this idea by writing the following adversary program:

\A

\ptxt := {}

arbitrary element of

\bits^n

\ctxt_1 := \otpenc(\ptxt)

\ctxt_2 := \otpenc(\ptxt)

return

\ctxt_1 == \ctxt_2

Using almost identical reasoning as in the previous example, we can calculate:

\begin{aligned} \PR{ \A \link \lib{1} \outputs \mytrue } &= 1, \\ \PR{ \A \link \lib{2} \outputs \mytrue } &= 1/2^n.\end{aligned}

We reach the same conclusion: The two libraries are not interchangeable.

This attack generalizes the first example, which can be obtained by fixing $\ptxt = \bit0^n$ . In a sense, we have shown that there is nothing particularly special about the all-zeros plaintext.

Example 2.3.3 (Attacking OTP with a reused key, #3)

One useful strategy is to start with a “skeleton” adversary, with many details missing:

\A

\ctxt_1 := \otpenc(\ptxt_1 ={} ??)

\ctxt_2 := \otpenc(\ptxt_2 ={} ??)

\cdots

return

??

We haven't decided yet which $\ptxt_i$ values to use as inputs to the $\otpenc$ subroutine, or how many calls to make. But we know that in $\lib{1}$ the $i$ -th response will be $\ctxt_i = \key \oplus \ptxt_i$ . In particular, each expression $\ctxt_i = \key \oplus \ptxt_i$ includes the same term $\key$ . Using the algebraic properties of xor, we can therefore observe:

\begin{aligned} \ctxt_i \oplus \ctxt_j &= (\key \oplus \ptxt_i) \oplus (\key \oplus \ptxt_j) \\ &= \key \oplus \key \oplus \ptxt_i \oplus \ptxt_j \\ &= \bit0^n \oplus \ptxt_i \oplus \ptxt_j \\ &= \ptxt_i \oplus \ptxt_j .\end{aligned}

The adversary knows every term appearing in the condition $\ctxt_i \oplus \ctxt_j = \ptxt_i \oplus \ptxt_j$ , and can therefore check whether it holds. It indeed always holds in $\lib{1}$ , and we might also guess that it doesn't always hold in $\lib{2}$ . The specific choice of $\ptxt_i, \ptxt_j$ doesn't seem to be important, so we can write the details of our adversary as follows:

\A

\ptxt_1, \ptxt_2 := {}

arbitrary elements of

\bits^n

\ctxt_1 := \otpenc(\ptxt_1)

\ctxt_2 := \otpenc(\ptxt_2)

return

\ctxt_1 \oplus \ctxt_2 == \ptxt_1 \oplus \ptxt_2

As in the previous examples, it is possible to show that:

\begin{aligned} \PR{ \A \link \lib{1} \outputs \mytrue } &= 1, \\ \PR{ \A \link \lib{2} \outputs \mytrue } &= 1/2^n.\end{aligned}

We reach the same conclusion: The two libraries are not interchangeable.

Once again this attack generalizes the previous one, which can be obtained by fixing $\ptxt_1 = \ptxt_2$ . When that is the case, $\ptxt_1 \oplus \ptxt_2 = \bit0^n$ and the two conditions $\ctxt_1 == \ctxt_2$ (used in the previous attack) and $\ctxt_1 \oplus \ctxt_2 == \ptxt_1 \oplus \ptxt_2 = \bit0^n$ (used in this attack) are logically equivalent. Thus, there is nothing particularly special about calling $\otpenc$ with a repeated argument.

This final attack example also demonstrates a useful strategy that appears throughout the book:

The xor Cancellation Strategy

Express the values that the adversary would see, algebraically as xor expressions. If two expressions have a common term, then xor'ing the values will cause the common term to cancel out, and the result will often be useful in an attack.

2.4. How to prove that two libraries are interchangeable

In cryptography, as in life, you should always break down a complicated problem into small, manageable pieces. In a security proof, we must show that a certain pair of libraries are interchangeable. How can we break such a proof into smaller pieces? Since the $\equiv$ operator is transitive, we can use the following idea:

Hybrid Proof Technique

The hybrid proof technique is a way to prove $\lib{start} \equiv \lib{end}$ , by demonstrating:

\lib{start} \equiv \L_{1} \equiv \L_{2} \equiv \cdots \equiv \L_{n} \equiv \lib{end}.

The intermediate libraries $\L_1, \L_2, \ldots$ (called hybrid libraries) are chosen so that each individual step $\L_{i} \equiv \L_{i+1}$ is easy to justify.

The vast majority of security proofs in the book use this simple but powerful technique. Each individual step $\L_{i} \equiv \L_{i+1}$ in a hybrid proof can be extremely simple. Every situation listed in example 2.2.3 and example 2.2.4 is used in some hybrid proof in this book.

Another common step in a hybrid proof is based on the following observation:

Claim 2.4.1 (Chain rule)

If $\lib1 \equiv \lib2$ , then for all $\L^*$ , we have $\L^* \link \lib1 \equiv \L^* \link \lib2$ . Here we are interpreting $\L^* \link \lib{i}$ as a compound library.

Proof:

For every calling program $\A$ , we have:

\begin{aligned} \PR{ \A \link (\L^* \link \lib1) \outputs \mytrue } &\overset{(1)}= \PR{ (\A \link \L^*) \link \lib1 \outputs \mytrue }\\ &\overset{(2)}= \PR{ (\A \link \L^*) \link \lib2 \outputs \mytrue }\\ &\overset{(3)}= \PR{ \A \link (\L^* \link \lib2) \outputs \mytrue }.\end{aligned}

Steps (1) and (3) follow from the fact that the $\link$ operator is associative. Step (2) follows from the fact that $\lib1 \equiv \lib2$ : These two libraries have the same effect on all calling programs, and $(\A \link \L^*)$ is one such calling program.

An example hybrid proof: Let's look at the following example that nicely showcases several common kinds of steps that can be used in a hybrid proof, including claim 2.4.1. Incidentally, the following claim is one of the most useful tools in future security proofs throughout the book.

Claim 2.4.2 (A convenient property of xor)

The following two libraries are interchangeable:

\lib{xor-samp-1}

\subname{sample}(M)

X \gets \bits^n

Y := X \oplus M

return

(X,Y)

\equiv

\lib{xor-samp-2}

\subname{sample}(M)

Y \gets \bits^n

X := Y \oplus M

return

(X,Y)

A plain-English translation of this claim would be:

If you want two values whose xor is $M$ , you can either sample the first uniformly and solve for the second, or you can sample the second uniformly and solve for the first. Both methods induce the same distribution.

Proof:

The sequence of hybrid libraries is presented below; it contains five intermediate hybrids besides the starting and ending libraries. Later in the book, we will discuss more intuition and strategies for generating your own hybrid proofs. For now your goal should be to simply understand why each pair of consecutive hybrid libraries are interchangeable—that is, why each change has no effect on any calling program.

Hybrid Sequence:

[ [ ['12','remove','hidden'], ['16','add','hl'], ['16','remove','hidden'], ['3','add','hidden'], ['18','remove','slide-up'], ['8','add','slide-down'] ], [ ['16','remove','hl'], ['78','add','hl'], ['86','add','hl'], ['28','remove','slide-up'], ['18','add','slide-down'] ], [ ['22','remove','hidden'], ['79','add','hl'], ['79','remove','slide-left'], ['12','add','hidden'], ['78','remove','hl'], ['78','add','slide-right'], ['86','remove','hl'], ['86','add','slide-right'] ], [ ['79','remove','hl'], ['5','add','hl'], ['81','add','hl'], ['43','remove','slide-up'], ['28','add','slide-down'] ], [ ['32','remove','hidden'], ['82','add','hl'], ['82','remove','slide-left'], ['83-slide','remove','slide-left'], ['22','add','hidden'], ['5','remove','hl'], ['5','add','hidden'], ['81','remove','hl'], ['81','add','slide-right'] ], [ ['82','remove','hl'] ], [ ['83-flip','add','flipped'], ['57','remove','slide-up'], ['43','add','slide-down'] ], [ ['84','add','hl'], ['86','add','hl'], ['66','remove','slide-up'], ['57','add','slide-down'] ], [ ['61','remove','hidden'], ['85','add','hl'], ['85','remove','slide-right'], ['86','add','hl'], ['86','remove','slide-right'], ['32','add','hidden'], ['84','remove','hl'], ['84','add','slide-left'], ['86','remove','hl'], ['86','add','slide-left'], ['83-slide','add','slide-left'] ], [ ['85','remove','hl'], ['86','remove','hl'], ['16','add','hl'], ['79','add','hl'], ['75','remove','slide-up'], ['66','add','slide-down'] ], [ ['70','remove','hidden'], ['73','add','hl'], ['73','remove','hidden'], ['78','add','hl'], ['78','remove','slide-right'], ['86','add','hl'], ['86','remove','slide-left'], ['61','add','hidden'], ['16','remove','hl'], ['16','add','hidden'], ['79','remove','hl'], ['79','add','slide-right'] ], [ ['73','remove','hl'], ['78','remove','hl'], ['86','remove','hl'] ] ]

The starting point of the hybrid proof is library

\lib{xor-samp-1}

We first introduce a new variable

X'

, which is not used anywhere. This change has no effect on the calling program.

You can check for yourself (using the algebraic properties of xor) that

X

and

X'

always hold the same value. It therefore has no effect on the calling program to change a reference to

X

into a reference to

X'

We want to argue that

Y

is uniformly distributed, and we can do so by observing that

Y

looks like an OTP ciphertext with

X

as the key and

M

as the plaintext. To use this fact, we first “factor out” the computation of

Y

in terms of the

\lib{otp-real}

library from claim 2.2.2. Factoring out these statements leaves us with a compound library, but has no effect on the calling program.

Now we are in a situation where we can use claim 2.2.2 and the chain rule (claim 2.4.1). Replacing

\lib{otp-real}

with

\lib{otp-rand}

in this compound library (while keeping the other part

\lib{hyb-3-4}

the same) has no effect on any calling program.

It has no effect on the calling program to inline a subroutine call.

Finally, we globally rename variable

X'

X

. This change clearly has no effect on the calling program. The result is the library

\lib{xor-samp-2}

\lib{xor-samp-1}

sample(

M

X \gets \bits^n

Y

{}:= {}

X \oplus M

\otpenc(M)

{}\gets \bits^n

return

(X,Y)

(X',Y)

(X,Y)

\link

\lib{otp-real}

\otpenc

(

\ptxt

\key \gets \bits^n

\ctxt := \key \oplus \ptxt

return

\ctxt

\lib{otp-rand}

\otpenc

(

\ptxt

\ctxt \gets \bits^n

return

\ctxt

Through this sequence of small changes, we proved that the two libraries $\lib{xor-samp-1}$ and $\lib{xor-samp-2}$ are interchangeable.

There is one step the proof that may seem mysterious: We introduced a new variable $X'$ that always holds the same value as $X$ . To see why the new variable was necessary, let's focus on the following step in the proof:

\lib{hyb-2}

\subname{sample}(M)

X \gets \bits^n

Y := X \oplus M

X' := Y \oplus M

return

(X',Y)

\equiv

\lib{hyb-3-4}

\subname{sample}(M)

Y := \otpenc(M)

X' := Y \oplus M

return

(X',Y)

\link

\lib{otp-real}

\otpenc(\ptxt)

\key \gets \bits^n

\ctxt := \key \oplus \ptxt

return

\ctxt

This step works because we have essentially renamed the variable $X$ in $\lib{hyb-2}$ to the variable $\key$ in $\lib{otp-real}$ . If we had not introduced the new variable $X'$ , this step would have gone like this:

\subname{sample}(M)

X \gets \bits^n

Y := X \oplus M

X' := Y \oplus M

return

(\hl{X},Y)

\overset{!}{\not\equiv}

\subname{sample}(M)

Y := \otpenc(M)

return

(\hl{X^{??}},Y)

\link

\lib{otp-real}

\otpenc(\ptxt)

\key \gets \bits^n

\ctxt := \key \oplus \ptxt

return

\ctxt

If the goal of this step is to rename $X$ to $\key$ , then how do we handle the appearance of $X$ in the expression “return $(\hl{X},Y)$ ”? It's not possible to change this expression into “return $(\hl{\key},Y)$ ” because $\key$ is a private variable, scoped only to $\lib{otp-real}$ . We can, however, recompute $\key$ from outside $\lib{otp-real}$ , and that's exactly what the line “ $X' := Y \oplus \ptxt$ ” does.

2.4.1. The three-hop maneuver

Let's focus more closely on how we moved between the following two hybrids in the proof of claim 2.4.2:

\subname{sample}(M)

\hl{X \gets \bits^n}

Y \hl{:= X \oplus M}

X' := Y \oplus M

return

(X',Y)

\equiv \cdots \equiv

\subname{sample}(M)

Y \hl{\gets\bits^n}

X' := Y \oplus M

return

(X',Y)

There were three steps:

First, we factored out the highlighted lines from the library on the left so that a separate instance of the $\lib{otp-real}$ library appeared.
Then, we replaced $\lib{otp-real}$ with $\lib{otp-rand}$ , while keeping the “main” library intact, taking advantage of claim 2.4.1.
Finally, we inlined $\lib{otp-rand}$ into the main library.

The net effect of these three steps was to replace the two lines “ $X \gets \bits^n$ ; $Y := X \oplus \ptxt$ ” with “ $Y \gets \bits^n$ .”

This sequence of steps—factor out, swap sub-libraries, inline—are standard and appear in every security proof in this book, often several times. This idiom deserves a special name:

The Three-Hop Maneuver

The three-hop maneuver consists of the following steps:

\L_{1} ~~\equiv~~ \L_2 \link \lib{A} ~~\equiv~~ \L_2 \link \lib{B} ~~\equiv~~ \L_3.

$\L_1 \equiv \L_2 \link \lib{A}$ : Factor out some lines of $\L_1$ in terms of explicit subroutine calls to $\lib{A}$ . Other lines of code stay behind, as $\L_2$ .
$\L_2 \link \lib{A} \equiv \L_2 \link \lib{B}$ : Replace $\lib{A}$ with $\lib{B}$ , while keeping $\L_2$ unchanged.
$\L_2 \link \lib{B} \equiv \L_3$ : Inline $\lib{B}$ , resulting in a monolithic library $\L_3$ .

2.5. Abstract cryptographic primitives

Specific algorithms like OTP are important in cryptography, but OTP is just one instance of an encryption scheme, and it's also important that we can discuss encryption schemes and their security properties in the abstract. In cryptography, useful abstractions like “encryption scheme” are called primitives. Three things are important when defining a cryptographic primitive:

The syntax of a primitive specifies its basic raw interface. What are its algorithms? How many inputs and outputs are there, and what are their types?
Correctness properties are the basic functionality we expect from the primitive, that do not involve any adversary—things like “decryption should be the inverse of encryption.”
Security properties are guarantees that hold in a specific attack scenario, in the presence of an adversary.

Symmetric-key encryption is a primitive whose syntax is defined as follows:

Definition 2.5.1 (Syntax of symmetric-key encryption)

A symmetric-key encryption (SKE) scheme consists of the following algorithms:

$\Enc$ : a (possibly randomized) algorithm that takes a key $\key \in \K$ and plaintext $\ptxt \in \M$ as input, and outputs a ciphertext $\ctxt \in \C$ .
$\Dec$ : a deterministic algorithm that takes a key $\key \in \K$ and ciphertext $\ctxt \in \C$ as input, and outputs a plaintext $\ptxt \in \M$ .

The set $\K$ of possible keys is called the scheme's key space, and similarly $\M$ and $\C$ are called the plaintext space and ciphertext space, respectively. We sometimes use $\Sigma$ to refer to the encryption scheme as a whole, with $\Sigma.\Enc$ , $\Sigma.\Dec$ , $\Sigma.\K$ , etc., denoting its constituent algorithms and sets.

An encryption scheme should satisfy a correctness property:

Definition 2.5.2 (Correctness for SKE)

An SKE $\Sigma$ is correct if encryption and decryption are inverses, in the following sense:

\PR{ \Sigma.\Dec\bigl(\key,\Sigma.\Enc(\key,\ptxt)\bigr) = \ptxt } = 1,

for all $\ptxt \in \Sigma.\M$ and $\key \in \Sigma.\K$ . The definition involves a probability because $\Sigma.\Enc$ may be a randomized algorithm.

We will see several security goals for SKE, but the simplest is the one we have been considering for OTP:

Definition 2.5.3 (One-time secrecy)

An SKE scheme $\Sigma$ has one-time secrecy if the following two libraries are interchangeable:

\lib{ots-real}^\Sigma

\otsenc(\ptxt)

\key \gets \Sigma.\K

\ctxt := \Sigma.\Enc(\key,\ptxt)

return

\ctxt

\equiv

\lib{ots-rand}^\Sigma

\otsenc(\ptxt)

\ctxt \gets \Sigma.\C

return

\ctxt

We might translate this formal definition into plain language as:

An encryption scheme has one-time secrecy if its ciphertexts are uniformly distributed, when keys are sampled uniformly, kept secret, and used for only one encryption, and no matter how the plaintexts are chosen.

A security definition is a template meant to be filled in. If we have a particular encryption scheme $\Sigma$ in mind and want to prove (or disprove) its security, we populate the template with the scheme's key space $\K$ , encryption algorithm $\Enc$ , and ciphertext space $\C$ , then compare the resulting two libraries.

Example 2.5.4 (One-time secrecy of OTP)

One-time pad (OTP) is defined as follows:

\begin{aligned}\K &= \bits^n \\ \M &= \bits^n \\ \C &= \bits^n\end{aligned}

\qquad

\Enc(\key,\ptxt)

\ctxt := \key \oplus \ptxt

return

\ctxt

\qquad

\Dec(\key,\ctxt)

\ptxt := \key \oplus \ctxt

return

\ptxt

If we populate the template from definition 2.5.3 with these specifics of OTP, we obtain the following two libraries:

\lib{ots-real}

\otsenc(\ptxt)

\key \gets \hl{\bits^n}

\K

\ctxt := \hl{\key \oplus \ptxt}

\Enc(\key,\ptxt)

return

\ctxt

\lib{ots-rand}

\otsenc(\ptxt)

\ctxt \gets \hl{\bits^n}

\C

return

\ctxt

As we have already discussed, these two libraries are interchangeable, so we conclude that OTP has one-time secrecy.

Example 2.5.5 (Insecure OTP variant)

Let's revisit the OTP variant from example 1.7.1 that uses and instead of xor.

\begin{aligned}\K &= \bits^n \\ \M &= \bits^n \\ \C &= \bits^n\end{aligned}

\qquad

\Enc(\key,\ptxt)

\ctxt := \key \mathbin{\&} \ptxt

return

\ctxt

You may have already noticed that the scheme does not satisfy the correctness property! To see why, consider that the extreme case of the key $\key = \bit0^n$ encrypts every plaintext to the ciphertext $\bit0^n$ .

Regardless of whether the scheme satisfies correctness, we can ask whether it has one-time secrecy. We populate the template from definition 2.5.3 with this scheme's parameters and ask whether the resulting libraries are interchangeable:

\lib{ots-real}

\otsenc(\ptxt)

\key \gets \hl{\bits^n}

\K

\ctxt := \hl{\key \mathbin{\&} \ptxt}

\Enc(\key,\ptxt)

return

\ctxt

\quad

\lib{ots-rand}

\otsenc(\ptxt)

\ctxt \gets \hl{\bits^n}

\C

return

\ctxt

In this case, the libraries are not interchangeable, because the following adversary can distinguish them:

\A

\ptxt := \bit{0}^n

\ctxt := \otsenc(\ptxt)

return

\ctxt == \bit 0^n

When $\A$ is linked to $\lib{ots-real}$ , the ciphertext $\ctxt$ is always computed as $\key \mathbin{\&} \ptxt = \key \mathbin{\&} \bit 0^n = \bit 0^n$ . Therefore, $\A$ always outputs true: $\PR{ \A \link \lib{ots-real} \outputs \mytrue } = 1$ .
When $\A$ is linked to $\lib{ots-rand}$ , the value $\ctxt$ is chosen uniformly. The probability that $\ctxt = \bit 0^n$ is $1/2^n$ . Hence, $\PR{ \A \link \lib{ots-rand} \outputs \mytrue } = 1/2^n$ .

Since these two probabilities are different (for any $n$ ), the libraries are not interchangeable, and the encryption scheme does not have one-time secrecy.

There are many other strategies that can successfully distinguish these two libraries. Perhaps you can think of a few and write them formally as calling programs.

2.6. Modular cryptographic constructions

Cryptographic primitives are like building blocks, which we can use to build more complicated things in a modular way. We can use the security properties of the underlying primitives to prove security of the larger construction.

Let's see an example of such a modular construction. It involves a rather indirect approach to encryption. Suppose Alice wants to privately send some message $\ptxt$ to Bob, and they already share a secret key $\key$ . Alice can do the following:

Sample a new key $\key'$ , uniformly.
Use $\key$ to encrypt $\key'$ , resulting in ciphertext $\ctxt_1$ .
Use $\key'$ (not $\key$ !) to encrypt $\ptxt$ , resulting in $\ctxt_2$ .
Send both $\ctxt_1$ and $\ctxt_2$ to Bob.

Bob can decrypt in two steps:

Use $\key$ to decrypt $\ctxt_1$ , and learn $\key'$ .
Use $\key'$ to decrypt $\ctxt_2$ , and learn $\ptxt$ .

What I have just described is a recipe to construct a new (complicated) encryption scheme out of an existing (simpler) one. The recipe is modular; it doesn't specify exactly how Alice “uses $\key'$ to encrypt $\ptxt$ ” or how Bob “uses $\key$ to decrypt $\ctxt_1$ .” We can imagine plugging in any encryption scheme into this recipe, and maybe even different schemes for the two different encryption/decryption steps in the recipe! The recipe can be formalized as follows:

Construction 2.6.1 (A modular way to combine two encryption schemes)

Let $\Sigma_1$ and $\Sigma_2$ be encryption schemes for which $\Sigma_2.\K \subseteq \Sigma_1.\M$ (that is, $\Sigma_1$ can encrypt keys for $\Sigma_2$ ). Define a new scheme $\Sigma^*$ as follows:

\begin{aligned} \Sigma^*.\K &= \Sigma_1.\K \\ \Sigma^*.\M &= \Sigma_2.\M \\ \Sigma^*.\C &= \Sigma_1.\C \times \Sigma_2.\C \end{aligned}

\quad

\Sigma^*.\Enc( \key, \ptxt)

\key' \gets \Sigma_2.\K

\ctxt_1 := \Sigma_1.\Enc(\key, \key')

\ctxt_2 := \Sigma_2.\Enc(\key', \ptxt)

return

(\ctxt_1, \ctxt_2)

\quad

\Sigma^*.\Dec\bigl( \key, (\ctxt_1,\ctxt_2) \bigr)

\key' := \Sigma_1.\Dec(\key, \ctxt_1)

\ptxt := \Sigma_2.\Dec(\key', \ctxt_2)

return

\ptxt

Construction 2.6.1 is heavy on notation, exactly because it is so modular and refers to arbitrary/unspecified encryption schemes $\Sigma_1$ and $\Sigma_2$ . Be sure you understand the connection between the notation and the simple informal recipe described above. The new construction $\Sigma^*$ supports keys that are the same as $\Sigma_1$ 's keys, and plaintexts that are the same as $\Sigma_2$ 's plaintexts. The ciphertexts in $\Sigma^*$ consist of a pair of ciphertexts, one from each of $\Sigma_1$ and $\Sigma_2$ .

Construction 2.6.1 is also our first example of an encryption scheme whose $\Enc$ algorithm is randomized. The $\Enc$ algorithm samples a fresh $\key'$ each time it is called. Thus, encrypting the same plaintext, even under the same key (which is not advised for the encryption schemes we've seen so far) can produce different ciphertexts. Randomized encryption schemes will become important later in the book.

Staying in the realm of abstract, unspecified encryption schemes, we can ask whether the recipe always results in a secure encryption scheme.

Claim 2.6.2 (One-time secrecy of the construction)

If $\Sigma_1$ and $\Sigma_2$ both have one-time secrecy, then construction 2.6.1 also has one-time secrecy. In other words,

if:

\quad

\lib{ots-real}^{\Sigma_1}

\otsenc_1(\ptxt)

\key \gets \Sigma_1.\K

\ctxt := \Sigma_1.\Enc(\key,\ptxt)

return

\ctxt

\equiv

\lib{ots-rand}^{\Sigma_1}

\otsenc_1(\ptxt)

\ctxt \gets \Sigma_1.\C

return

\ctxt

\quad

(

\Sigma_1

secure)

and:

\quad

\lib{ots-real}^{\Sigma_2}

\otsenc_2(\ptxt)

\key \gets \Sigma_2.\K

\ctxt := \Sigma_2.\Enc(\key,\ptxt)

return

\ctxt

\equiv

\lib{ots-rand}^{\Sigma_2}

\otsenc_2(\ptxt)

\ctxt \gets \Sigma_2.\C

return

\ctxt

\quad

(

\Sigma_2

secure)

then:

\quad

\lib{ots-real}^{\Sigma^*}

\otsenc^*(\ptxt)

\key \gets \Sigma_1.\K

{} = \Sigma^*.\K

(\ctxt_1,\ctxt_2) := \Sigma^*.\Enc(\key,\ptxt)

\key' \gets \Sigma_2.\K

\ctxt_1 := \Sigma_1.\Enc(\key, \key')

\ctxt_2 := \Sigma_2.\Enc(\key', \ptxt)

return

(\ctxt_1, \ctxt_2)

\equiv

\lib{ots-rand}^{\Sigma^*}

\otsenc^*(\ptxt)

\ctxt \gets \Sigma^*.\C

\ctxt_1 \gets \Sigma_1.\C

\ctxt_2 \gets \Sigma_2.\C

return

(\ctxt_1,\ctxt_2)

\quad

(

\Sigma^*

secure)

The claim is fundamentally an if-then statement involving three separate instances of one-time secrecy. It therefore involves three different pairs of $\lib{ots-*}$ libraries. Since this is a source of potential confusion, I have changed subroutine names to $\otsenc_1, \otsenc_2, \otsenc^*$ to help keep track of which scheme's security we are talking about at any given point. Most future constructions and proofs won't be quite so confusing, since they involve security properties of different primitives, involving different-looking libraries.

Because the claim is so abstract/modular, it is less about any particular encryption scheme, and more about the implications of the one-time secrecy definition itself. “One-time secrecy is preserved under this way of combining two encryption schemes.”

Proof:

We use the hybrid technique to prove that $\lib{ots-real}^{\Sigma^*} \equiv \lib{ots-rand}^{\Sigma^*}$ , while assuming the hypotheses $\lib{ots-real}^{\Sigma_1} \equiv \lib{ots-rand}^{\Sigma_1}$ and $\lib{ots-real}^{\Sigma_2} \equiv \lib{ots-rand}^{\Sigma_2}$ .

Hybrid Sequence:

The starting point is

\lib{ots-real}^{\Sigma^*}

, and our goal is to make a sequence of interchangeable modifications until we eventually arrive at

\lib{ots-rand}^{\Sigma^*}

We can first apply the security of

\Sigma_1

with a three-hop maneuver. The three hops are: (1) factor out the operations involving

\Sigma_1

, so that an instance of its library

\lib{ots-real}^{\Sigma_1}

appears; (2) replace

\lib{ots-real}^{\Sigma_1}

with

\lib{ots-rand}^{\Sigma_1}

; (3) inline

\lib{ots-rand}^{\Sigma_1}

. These changes have no effect on the calling program.

We can now apply the security property of

\Sigma_2

in a similar three-step maneuver. The final result is

\lib{ots-rand}^{\Sigma^*}

, which completes the proof.

\lib{ots-real}^{\Sigma^*}

\otsenc^*

(

\ptxt

\key \gets \Sigma_1.\K

{} = \Sigma^*.\K

(\ctxt_1,\ctxt_2) := \Sigma^*.\Enc(\key,\ptxt)

\key' \gets \Sigma_2.\K

\ctxt_1

{}:= {}

\Sigma_1.\Enc(\key, \key')

\otsenc_1(\key')

{}\gets \Sigma_1.\C

\ctxt_2

{}:= {}

\Sigma_2.\Enc(\key', \ptxt)

\otsenc_2(\ptxt)

{}\gets \Sigma_2.\C

return

(\ctxt_1, \ctxt_2)

\link

\lib{ots-real}^{\Sigma_1}

\otsenc_1

(

\ptxt

\key \gets \Sigma_1.\K

\ctxt := \Sigma_1.\Enc(\key, \ptxt)

return

\ctxt

\lib{ots-rand}^{\Sigma_1}

\otsenc_1

(

\ptxt

\ctxt \gets \Sigma_1.\C

return

\ctxt

\link

\lib{ots-real}^{\Sigma_2}

\otsenc_2

(

\ptxt

\key \gets \Sigma_2.\K

\ctxt := \Sigma_2.\Enc(\key, \ptxt)

return

\ctxt

\lib{ots-rand}^{\Sigma_2}

\otsenc_2

(

\ptxt

\ctxt \gets \Sigma_2.\C

return

\ctxt

2.7. ☆ “Real-or-random” vs. “left-or-right”

Security definitions don't represent some timeless, universal truth, handed down to us from the Cryptography Gods. Rather, we (mere Cryptography Humans) do our best to model a reasonable attack scenario and say something precise about what can happen in that scenario. There could be more than one way to do this.

In this book, the default way to define security is the real-or-random paradigm: Something is “secure” if its outputs look like the uniform distribution. But that's not the only sensible way to define security, at least for encryption. In the left-or-right paradigm, we say that an encryption scheme is “secure” if encryptions of one plaintext look like encryptions of any other plaintext—but not necessarily like the uniform distribution. In the left-or-right paradigm, we formalize an attack scenario in which the adversary chooses two plaintexts but only one of them gets encrypted. The adversary should not be able to determine which of the two plaintexts is encrypted.

Definition 2.7.1 (Left-or-right formulation of one-time secrecy)

An SKE scheme $\Sigma$ satisfies left-or-right one-time secrecy (OTS) if the following two libraries are interchangeable:

\lib{ots-left}^\Sigma

\otsenc(\ptxt_L, \ptxt_R)

\key \gets \Sigma.\K

\ctxt := \Sigma.\Enc(\key,\hl{\ptxt_L})

return

\ctxt

\equiv

\lib{ots-right}^\Sigma

\otsenc(\ptxt_L, \ptxt_R)

\key \gets \Sigma.\K

\ctxt := \Sigma.\Enc(\key,\hl{\ptxt_R})

return

\ctxt

$\lib{ots-left}$ always encrypts the left plaintext, while $\lib{ots-right}$ always encrypts the right one.

We now have two definitions of security for encryption, and, perhaps unfortunately, they are not equivalent. One is a strictly stronger security requirement than the other. Any scheme that satisfies the real-or-random flavor of security also satisfies the left-or-right flavor (see exercise 2.24), but the converse is not true.

\begin{array}{rcl} & \Rightarrow & \\ \text{$\Sigma$ satisfies real-or-random security} & & \text{$\Sigma$ satisfies left-or-right security.} \\ & \underset{\substack{\text{not}\\\text{necessarily}}}{\not\Leftarrow} \end{array}

We must acknowledge the existence of an uncanny gap between the two definitions, containing schemes that are secure in the left-or-right sense but not the real-or-random sense. However, this gap is relatively insignificant in practice. The schemes that inhabit it are highly unnatural; they look like they were designed just to prove a philosophical point about security definitions—because almost all of them were! I know of only one exception to this rule, a truly natural encryption scheme that we will see later in section 14.5, which is secure in the left-or-right sense but not the real-or-random sense. Every other encryption scheme we actually care about satisfies both definitions.

So which is the “correct” way to define security of encryption? Neither paradigm is objectively “correct”; they simply demand different things from an encryption scheme. What's most important is to recognize that there is a choice to be made at all! Here are a few more philosophical and cultural differences between the real-or-random and left-or-right paradigms:

Left-or-right is the more “traditional” way to define security for encryption. You'll see it appear as the standard approach in most other references and in the research literature.
On the other hand, the real-or-random paradigm is the standard (and often, only sensible) way to define security for many other, non-encryption primitives.
I find that security definitions in the real-or-random paradigm are more intuitive and easier to use. The adversary provides just one plaintext at a time, not two.
Security proofs in the real-or-random paradigm are often half the length of comparable proofs in the left-or-right paradigm. To prove security in the left-or-right paradigm, you need a sequence of hybrids in which the only net change is to replace $\ptxt_L$ with $\ptxt_R$ . Usually there is a hybrid precisely in the middle of the proof in which ciphertexts are generated uniformly, and the hybrids on either side of this midpoint are like mirror images, with their only difference being $\ptxt_L$ vs. $\ptxt_R$ . A security proof of real-or-random security is already complete once it reaches that middle point.
Left-or-right security is a more minimal definition and fits better with many natural intuitions you probably have about security. Does a secure encryption scheme become suddenly insecure if you append zeros to every ciphertext? What if you repeat every bit in every ciphertext? What if you simply change the definition of the ciphertext space $\C$ ? It seems silly that such benign changes should have an impact on security.

And indeed, if we define security in the left-or-right paradigm, then all of these changes preserve security (see exercises 2.25 and 2.26). But they break security in the real-or-random sense.
When a scheme is insecure according to the left-or-right paradigm, the resulting attack is often easier to appreciate as a security problem. “I can tell whether your ciphertext contains this or that” just feels like more of an attack than “Your ciphertexts don't look uniformly chosen.”

Exercises

Show that the following two libraries are not interchangeable:

$\lib1$

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

$x \gets \Z_{10}$

return $x$

$\lib2$

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

$x \gets \Z_{10}$

return $2x \pct 10$
Show that the following two libraries are not interchangeable:

$\lib1$

$R \gets \bits^n$

$\subname{foo}(X)$ :

$R := R \oplus X$

return $R$

$\lib2$

$\subname{foo}(X)$ :

$Y \gets \bits^n$

return $Y$

Note that the variable $R$ in $\lib{1}$ is static/persistent, and is changed in each call to foo.
Give a convincing justification that $\PR{ \A \link \lib{2} \outputs \mytrue } = 1/2^n$ in example 2.3.3.
Let $\Sigma$ be the variant of OTP that uses boolean-and, and let $\lib{ots-real}^\Sigma$ and $\lib{ots-rand}^\Sigma$ be the libraries involved in one-time secrecy (shown in example 2.5.5). Let $\A$ be the following calling program:

$\A$

$\ptxt \gets \bits^n$

$\ctxt := \otsenc(\ptxt)$

return $\ctxt == \bit 0^n$

Calculate $\PR{ \A \link \lib{ots-real} \outputs \mytrue }$ and $\PR{ \A \link \lib{ots-rand} \outputs \mytrue }$ .
Prove formally that the $\equiv$ operator is transitive: If $\lib{1} \equiv \lib{2}$ and $\lib{2} \equiv \lib{3}$ , then $\lib{1} \equiv \lib{3}$ .
Prove that the following two libraries are interchangeable, for all $\nmod$ .

$\lib{mod-samp-1}$

$\subname{sample}(M)$ :

$X \gets \Z_\nmod$

$Y := (M - X) \pct \nmod$

return $(X,Y)$

$\equiv$

$\lib{mod-samp-2}$

$\subname{sample}(M)$ :

$Y \gets \Z_\nmod$

$X := (M - Y) \pct \nmod$

return $(X,Y)$

This exercise generalizes claim 2.4.2: Each library generates random $X$ and $Y$ whose sum mod $\nmod$ is $M$ .
h Prove that the following two libraries are interchangeable:

$\lib{left}$

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

$R \gets \bits^n$

return $\overline{R}$

$\equiv$

$\lib{right}$

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

$R \gets \bits^n$

return $R$

$\overline{R}$ denotes the bitwise complement of $R$ —that is, the result of flipping every bit in the string $R$ .

Write $\overline{R}$ in terms of xor.
Prove that the following two libraries are interchangeable:

$\lib{left}$

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

$A \gets \bits^n$

$B \gets \bits^n$

return $A \big\| (A\oplus B)$

$\equiv$

$\lib{right}$

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

$R \gets \bits^{2n}$

return $R$
Below are two pairs of libraries. One pair is interchangeable, one is not. Give a proof and a distinguishing attack:
1. $\lib{left}$
  
  $\subname{sample}(\,)$ :
  
  $A \gets \bits^n$
  
  $B \gets \bits^n$
  
  $C \gets \bits^n$
  
  return $(A \oplus B) \big\| (B\oplus C) \big\| \hl{(C \oplus A)}$
  
  $\quad$
  
  $\lib{right}$
  
  $\subname{sample}(\,)$ :
  
  $R \gets \bits^{3n}$
  
  return $R$
2. $\lib{left}$
  
  $\subname{sample}(\,)$ :
  
  $A \gets \bits^n$
  
  $B \gets \bits^n$
  
  $C \gets \bits^n$
  
  return $(A \oplus B) \big\| (B\oplus C) \big\| \hl{C}$
  
  $\quad$
  
  $\lib{right}$
  
  $\subname{sample}(\,)$ :
  
  $R \gets \bits^{3n}$
  
  return $R$
$\star$ In abstract algebra, a (finite) group is a finite set $\G$ of items together with an operator $\otimes$ that satisfies the following axioms:
- Closure: For all $a,b \in \G$ , we have $a \otimes b \in \G$ .
- Identity: There is a special identity element $e \in \G$ that satisfies $e \otimes a = a \otimes e = a$ for all $a \in \G$ .
- Associativity: For all $a,b,c \in \G$ , we have $(a \otimes b) \otimes c = a \otimes (b \otimes c)$ .
- Inverses: For all $a \in \G$ , there exists an inverse element called $\hl{a^{-1}} \in \G$ such that $a \otimes a^{-1} = a^{-1} \otimes a = e$ .
Define the following encryption scheme in terms of an arbitrary group $(\G, \otimes)$ :

$\begin{aligned} \K &= \G \\ \M &= \G \\ \C &= \G \end{aligned}$

$\quad$

$\Enc(\key,\ptxt)$ :

return $\key \otimes \ptxt$

$\quad$

$\Dec(\key,\ctxt)$ :

return ?? ${}$
1. Prove that $\bits^\secpar$ is a group with respect to the xor operator. What is the identity element, and what is the inverse of a value $X \in \bits^\secpar$ ?
2. Fill in the details of the $\Dec$ algorithm and prove (using the group axioms) that the scheme satisfies correctness.
3. Prove that the scheme satisfies one-time secrecy.
Write a different attack that distinguishes the libraries in example 2.5.5, and calculate the two output probabilities. Try to make your attack as different as possible from the one given in the example.
Why do you think I did not show the decryption algorithm for the variant of OTP that uses boolean-and, in example 2.5.5?
Prove that the following encryption scheme does not have one-time secrecy:

$\begin{aligned} \K &= \{1,\ldots,9\} \\ \M &= \{1,\ldots,9\} \\ \C &= \{0,\ldots,9\} \end{aligned}$

$\quad$

$\Enc(\key,\ptxt)$ :

return $(\key \times \ptxt) \pct 10$
h In this exercise you will show that an encryption scheme cannot achieve one-time secrecy if it has fewer keys than plaintexts. Let $\Sigma$ be an encryption scheme with $|\Sigma.\K| < |\Sigma.\M|$ .
1. Suppose we fix an arbitrary ciphertext $\ctxt \in \Sigma.\C$ , and run the following code:
  
  $\mathcal{S} := \emptyset$
  
  for each $\key \in \Sigma.\K$ :
  
  add $\Sigma.\Dec(\key,\ctxt)$ to the set $\mathcal{S}$
  
  $\ptxt \gets \Sigma.\M$
  
  if $\ptxt \in \mathcal{S}$ : return $\mytrue$
  
  else: return $\myfalse$
  
  Argue that this program outputs $\myfalse$ with some nonzero probability.
2. Show that the following program $\A$ can successfully distinguish $\lib{ots-real}^\Sigma$ and $\lib{ots-rand}^\Sigma$ (definition 2.5.3):
  
  $\A$
  
  $\ptxt \gets \Sigma.\M$
  
  $\ctxt := \otsenc(\ptxt)$
  
  $\mathcal{S} := \emptyset$
  
  for each $\key \in \Sigma.\K$ :
  
  add $\Sigma.\Dec(\key,\ctxt)$ to the set $\mathcal{S}$
  
  if $\ptxt \in \mathcal{S}$ : return $\mytrue$
  
  else: return $\myfalse$
  
  Calculate both relevant output probabilities.
In part (a), how does the size of the set $\mathcal{S}$ compare to $|\M|$ ? In part (b), show that $\A \link \lib{ots-rand}^\Sigma$ and the code from part (a) are interchangeable.
Let $\Sigma$ be an SKE scheme and define the following library:

$\lib{guess}^\Sigma$

$b \gets \{0,1\}$

$\otsenc(\ptxt)$ :

if $b == 0$ :

$\key \gets \Sigma.\K$

return $\Sigma.\Enc(\key,\ptxt)$

else: // $b == 1$

$\ctxt \gets \Sigma.\C$

return $\ctxt$
1. Suppose that $\Sigma$ has one-time secrecy. Prove that for all calling programs $\A$ , we have
  
  $\PR{ \A \link \lib{guess}^\Sigma \outputs b } = 1/2,$
  
  where $b$ is the global variable chosen at the beginning of time in $\lib{guess}$ .
2. Prove the converse of part (a). Namely, if $\Sigma$ does not have one-time secrecy then there is a calling program $\A$ for which $\PR{ \A \link \lib{guess}^\Sigma \outputs b } \ne 1/2.$
Let $\Pi_n$ denote the set of all permutations over $\{1, \ldots, n\}$ , which we write as functions $K : \{1,\ldots,n\} \to \{1,\ldots, n\}$ . Show that the following encryption scheme does not have one-time secrecy:

$\begin{aligned} \K &= \Pi_n \\ \M &= \bits^n \\ \C &= \bits^n \end{aligned}$

$\Enc(\key,\ptxt)$ :

for $i=1$ to $n$ :

// $i$ th bit of $\ctxt$ = $\key(i)$ 'th bit of $\ptxt$

$\ctxt[i] := \ptxt[ \key(i) ]$

return $\ctxt$

$\Dec(\key,\ctxt)$ :

for $i=1$ to $n$ :

// $\key(i)$ 'th bit of $\ptxt$ = $i$ th bit of $\ctxt$

$\ptxt[ \key(i) ] := \ctxt[i]$

return $\ptxt$
Show that construction 2.6.1 satisfies the correctness property for an SKE, if $\Sigma_1$ and $\Sigma_2$ both do.
The proof of claim 2.6.2 first applies the security of $\Sigma_1$ , then of $\Sigma_2$ , each in a three-hop maneuver. Explain why the proof doesn't work if these three-hop maneuvers are done in the opposite order.
Suppose we instantiate the scheme $\Sigma^*$ from claim 2.6.2 with $\Sigma_1 = \Sigma_2 ={}$ OTP. What happens when a victim repeats a key (to $\Sigma^*$ )? Show an attack analogous to the ones in section 2.3.
Construction 2.6.1 is a randomized encryption scheme. Suppose $\Sigma_2.\K = \bits^n$ and we make construction 2.6.1 deterministic with the following change:

$\Sigma^*.\Enc( \key, \ptxt)$ :

$\key' \hl{:= \bit0^n}$

$\ctxt_1 := \Sigma_1.\Enc(\key, \key')$

$\ctxt_2 := \Sigma_2.\Enc(\key', \ptxt)$

return $(\ctxt_1, \ctxt_2)$

Does the resulting $\Sigma^*$ still have one-time secrecy after this change? Give either a security proof or an attack.
Here is a modular construction that illustrates the intuitive idea that it is safe to encrypt the same plaintext twice, under two independent keys. In other words, perhaps for the sake of redundancy, if we always encrypt all plaintexts twice under independent keys, do we get a secure encryption scheme? (You may wonder why such an “obvious” statement requires proof, but later in the book we study security definitions for which it is not safe.)

Let $\Sigma$ be an SKE scheme. Define the following new scheme $\Sigma_2$ :

$\begin{aligned} \Sigma_2.\K & = \Sigma.\K \times \Sigma.\K \\ \Sigma_2.\M &= \Sigma.\M \\ \Sigma_2.\C &= \Sigma.\C \times \Sigma.\C \end{aligned}$

$\quad$

$\Sigma_2.\Enc\bigl( (\key_1,\key_2), \ptxt \bigr)$ :

$\ctxt_1 := \Sigma.\Enc(\key_1, \ptxt)$

$\ctxt_2 := \Sigma.\Enc(\key_2, \ptxt)$

return $(\ctxt_1, \ctxt_2)$

$\Sigma_2.\Dec\bigl( (\key_1,\key_2), (\ctxt_1, \ctxt_2) \bigr)$ :

$\ptxt_1 := \Sigma.\Dec(\key_1, \ctxt_1)$

$\ptxt_2 := \Sigma.\Dec(\key_2, \ctxt_2)$

if $\ptxt_1 \ne \ptxt_2$ : return $\myerr$

return $\ptxt_1$

Prove that $\Sigma_2$ has one-time secrecy if $\Sigma$ does.
Here is a modular construction that illustrates the intuitive idea that it is safe to encrypt a long plaintext by separately encrypting its two halves (under independent keys). (You may wonder why such an “obvious” statement requires proof, but later in the book we study security definitions for which it is not safe.)

Let $\Sigma$ be an SKE scheme. Define the following new scheme $\Sigma_2$ :

$\begin{aligned} \Sigma_2.\K & = \Sigma.\K \times \Sigma.\K \\ \Sigma_2.\M &= \Sigma.\M \times \Sigma.\M \\ \Sigma_2.\C &= \Sigma.\C \times \Sigma.\C \end{aligned}$

$\Sigma_2.\Enc\bigl( (\key_1,\key_2), (\ptxt_1, \ptxt_2) \bigr)$ :

$\ctxt_1 := \Sigma.\Enc(\key_1, \ptxt_1)$

$\ctxt_2 := \Sigma.\Enc(\key_2, \ptxt_2)$

return $(\ctxt_1, \ctxt_2)$

$\Sigma_2.\Dec\bigl( (\key_1,\key_2), (\ctxt_1, \ctxt_2) \bigr)$ :

$\ptxt_1 := \Sigma.\Dec(\key_1, \ctxt_1)$

$\ptxt_2 := \Sigma.\Dec(\key_2, \ctxt_2)$

return $(\ptxt_1, \ptxt_2)$

Prove that $\Sigma_2$ has one-time secrecy if $\Sigma$ does.
Let $\Sigma$ be an SKE scheme for which $\Sigma.\C \subseteq \Sigma.\M$ , so that it makes sense to treat a ciphertext also as a plaintext that can be encrypted. Prove that if $\Sigma$ has one-time secrecy, then so does the following scheme $\Sigma'$ :

$\begin{aligned} \Sigma'.\K & = \Sigma.\K \times \Sigma.\K \\ \Sigma'.\M &= \Sigma.\M \\ \Sigma'.\C &= \Sigma.\C \end{aligned}$

$\quad$

$\Sigma'.\Enc\bigl( (\key_1,\key_2), \ptxt \bigr)$ :

$\ctxt_1 := \Sigma.\Enc(\key_1, \ptxt)$

$\ctxt_2 := \Sigma.\Enc(\key_2, \ctxt_1)$

return $\ctxt_2$

$\quad$

$\Sigma'.\Dec\bigl( (\key_1,\key_2), \ctxt_2 \bigr)$ :

$\ctxt_1 := \Sigma.\Dec(\key_2, \ctxt_2)$

$\ptxt := \Sigma.\Dec(\key_1, \ctxt_1)$

return $\ptxt$
Let $\Sigma$ be an SKE scheme. Prove that if $\Sigma$ satisfies real-or-random OTS (definition 2.5.3) then it also satisfies left-or-right OTS (definition 2.7.1).
Let $\Sigma$ be an SKE scheme, and let $\Sigma^{+\bit0}$ be the encryption scheme defined by

$\Sigma^{+\bit0}.\Enc(\key,\ptxt) = \Sigma.\Enc(\key,\ptxt) \| \bit0.$
1. Show that $\Sigma^{+\bit0}$ does not have (real-or-random) OTS, even if $\Sigma$ does.
2. Show that $\Sigma^{+\bit0}$ does have left-or-right OTS (definition 2.7.1), if $\Sigma$ does.
Let $\Sigma$ be an SKE scheme, and let $\Sigma^{\times 2}$ be the encryption scheme defined by

$\Sigma^{\times 2}.\Enc(\key, \ptxt)$ :

$\ctxt := \Sigma.\Enc(\key,\ptxt)$

return $\ctxt \| \ctxt$
1. Show that $\Sigma^{\times 2}$ does not have (real-or-random) OTS, even if $\Sigma$ does.
2. Show that $\Sigma^{\times 2}$ does have left-or-right OTS (definition 2.7.1), if $\Sigma$ does.
Prove that the following two libraries are interchangeable if and only if $\Sigma$ satisfies left-or-right one-time secrecy:

$\lib{real}^\Sigma$

$\otsenc(\ptxt)$ :

$\key \gets \Sigma.\K$

$\ctxt := \Sigma.\Enc(\key,\ptxt)$

return $\ctxt$

$\equiv$

$\lib{dummy}^\Sigma$

$\otsenc(\ptxt)$ :

$\key \gets \Sigma.\K$

$\hl{\ptxt' \gets \Sigma.\M}$

$\ctxt := \Sigma.\Enc(\key,\hl{\ptxt'})$

return $\ctxt$

In other words, these two libraries are an equivalent definition for left-or-right one-time secrecy. You must prove both directions—that is, $\lib{real} \equiv \lib{dummy} \implies \lib{ots-left} \equiv \lib{ots-right}$ , and $\lib{ots-left} \equiv \lib{ots-right} \implies \lib{real} \equiv \lib{dummy}$ .
Prove that the following two libraries are interchangeable if and only if $\Sigma$ satisfies left-or-right one-time secrecy:

$\lib{real}^\Sigma$

$\otsenc(\ptxt_1, \ptxt_2)$ :

$\key_1 \gets \Sigma.\K$

$\key_2 \gets \Sigma.\K$

$\ctxt_1 := \Sigma.\Enc(\key_1,\ptxt_1)$

$\ctxt_2 := \Sigma.\Enc(\key_2,\ptxt_2)$

return $(\ctxt_1, \ctxt_2)$

$\equiv$

$\lib{swapped}^\Sigma$

$\otsenc(\ptxt_1, \ptxt_2)$ :

$\key_1 \gets \Sigma.\K$

$\key_2 \gets \Sigma.\K$

$\ctxt_1 := \Sigma.\Enc(\key_1,\ptxt_1)$

$\ctxt_2 := \Sigma.\Enc(\key_2,\ptxt_2)$

return $(\ctxt_2, \ctxt_1)$

In other words, these two libraries are an equivalent definition for left-or-right one-time secrecy. You must prove both directions—that is, $\lib{real} \equiv \lib{swapped} \implies \lib{ots-left} \equiv \lib{ots-right}$ , and $\lib{ots-left} \equiv \lib{ots-right} \implies \lib{real} \equiv \lib{swapped}$ .

Chapter Notes

Library-based security is a simplified dialect of the game-hopping methodology for security proofs, introduced by Shoup [206] and by Bellare and Rogaway [29,30]. In the game-based paradigm, security is defined in terms of an abstract interactive game played against an adversary; the programmatic code of the game plays a prominent role in security reasoning. Kilian and Rogaway [133] were the first to prove security in what we would now recognize as the modern game-hopping style. Library-based security shares many similarities with the state-separating proofs methodology, developed independently by Brzuska, Delignat-Lavaud, Fournet, Kohbrok, and Kohlweiss [56]. In both the library-based and state-separation methodologies, secrecy of values is reflected in their scope, and hybrid proofs involve frequently factoring out certain target libraries/modules.

Bellare, Desai, Jokipii, and Rogaway [15] were the first to formalize a security definition for encryption in the left-or-right paradigm. They also described another style of definition, which they called “real-or-random,” but which is different than how we use this term in the book. Theirs is analogous to the definition in exercise 2.27 and is actually equivalent to the left-or-right definition (one definition implies the other). Rogaway, Bellare, Black, and Krovetz [193] were the first to propose a security definition for encryption using our sense of the term “real-or-random.”

Rudiments of Provable Security

Chapter Contents

2.1. Attack scenarios as libraries

2.2. Interchangeable libraries

2.3. How to distinguish two libraries

2.4. How to prove that two libraries are interchangeable

2.4.1. The three-hop maneuver

2.5. Abstract cryptographic primitives

2.6. Modular cryptographic constructions

2.7. ☆ “Real-or-random” vs. “left-or-right”

Exercises

Chapter Notes