Preface

The foy of Cryptography is an undergraduate textbook in cryptography. This book evolved from lecture notes I developed for the cs427 course at Oregon State University (and before that, cs473 at the University of Montana).

Yes, I know that the title is ridiculous. All of the serious titles were already taken. I hope you understand that actual joy is not guaranteed.

What Is This Book About?

This book is about the fundamentals of provable security.

• Security: Cryptography is about controlling access to information. We break apart the nebulous concept of "security" into more specific goals: confidentiality, authenticity, integrity.
• Provable: We can formally define what it means to be secure, and then mathematically prove claims about security. One prominent theme in the book is the logic of composing building blocks together in secure ways.
• Fundamentals: This is an introductory book on the subject that covers the basics. After completing this course, you will have a solid theoretical foundation that you can apply to most real-world situations. You will also be equipped to study more advanced topics in cryptography.

This book is not a handbook telling you which cryptographic algorithm to use in every situation, nor a guide for securely implementing production-ready cryptographic libraries. We do not discuss specific cryptographic software (e.g., PGP, Tor, Signal, TrueCrypt) or cryptocurrencies like Bitcoin. You won’t learn how to become a hacker by reading this book.

Who Is This Book For?

This book is for anyone who might need to secure information with cryptography, and who is curious about what makes some things "secure" (and what makes other things insecure). I don’t imagine that most readers of this book will develop their own novel cryptography (e.g., designing new block ciphers), but they will be far more likely to use and combine cryptographic building blocks - thus our focus on the logic of composition.

What Background Is Needed To Understand This Book?

You will get the most out of this book if you have a solid foundation in standard undergraduate computer science material:

• Discrete mathematics (of the kind you typically find in year 2 or 3 of an undergraduate CS program) is required background. The book assumes that you are familiar with basic modular arithmetic, discrete probabilities, simple combinatorics, and especially proof techniques. Chapter 0 contains a brief review of some of these topics.
• Algorithms & data structures background is highly recommended, and theory of computation (automata, formal languages & computability) is also recommended. We deal with computations and algorithms at a high level of abstraction, and with mathematical rigor. Prior exposure to this style of thinking will be helpful.

Why Is Cryptography A Difficult Subject?

It’s all the math, right? Cryptography has a reputation of being a difficult subject because of the amount of difficult math, but I think this assessment misses the mark. A former victim, I mean student, summed it up bluntly when he shared in class (paraphrased):

Some other students were thinking of taking your course but were worried that it is really math-heavy. I wouldn’t say that this course is a lot of math exactly. It’s somehow even worse!

Thanks, I think.

Anyway, many corners of cryptography use math that most CS undergrads would find quite advanced (advanced factoring algorithms, elliptic curves, isogenies, even algebraic geometry), but these aren’t the focus of this book. Our focus is instead on the logic of composing different building blocks together in provably secure ways. Yes, you will probably learn some new math in this book - enough to understand RSA, for example. And yes, there are plenty of "proofs." But I honestly believe you’ll be fine if you did well in a standard discrete math course. I always tell my cs427 students that I’m not expecting them to love math, proofs, and theory - I only ask them to choose not to be scared of it.

If not math, then what? In an algorithms course, I could introduce and explain concepts with concrete examples - here’s what happens step-by-step when I run mergesort on this particular array, here’s what happens when I run Dijkstra’s algorithm on this particular graph, here are 42 examples of a spanning tree. You could study these concrete examples, or even make your own, to develop your understanding of the general case.

Cryptography is different because our main concerns are higher up the ladder of abstraction than most students are comfortable with. \({ }^{1}\) Yes, I can illustrate what happens

\({ }^{1}\) Of course, abstraction is the heart of math. I may be making a false distinction by saying "it’s not the math, it’s the abstraction." But I think there’s something to the distinction between a CS major’s typical math-aversion and what is really challenging about cryptography. step-by-step when you run a cryptographic algorithm on a particular input. This might help you understand what the algorithm does, but it can never illustrate why the algorithm is secure. This question of "why" is the primary focus of this book.

• Security is a global property about the behavior of a system across all possible inputs. You can’t demonstrate security by example, and there’s nothing to see in a particular execution of an algorithm. Security is about a higher level of abstraction.
• Most security definitions in this book are essentially: "the thing is secure if its outputs look like random junk." If I give an example that is concrete enough to show actual inputs and outputs, and if things are working as they should, then all the outputs will just look like meaningless garbage. Unfortunately, no one ever learned very much by staring at meaningless garbage.

Systems are insecure when they fail to adequately look like random junk. Occasionally they fail so spectacularly that you can actually see it by looking at concrete input and output values (as in the case of the ECB penguin). But more often, the reason for insecurity is far from obvious. For example, suppose an encryption scheme was insecure because the xOR of the first two output blocks is the same as the xOR of the third and fourth output blocks. I’m not convinced that it would be helpful to show concrete example values with this property. What’s more, sometimes the reason for insecurity only "jumps off the page" on specific, non-obvious, choices of inputs.

If you want to be equipped to answer questions like "why is this thing secure but this other very similar thing is not?", then you must develop an understanding at this higher level of abstraction. You’ll have to directly come to terms with abstract ideas like "this algorithm’s outputs look like random junk, under these circumstances" and the consequences of these kinds of ideas. It’s hard to arrive at understanding without the usual scafolding of concrete examples (seeing algorithms executed on specific inputs), but this book is my best effort at making the path as smooth as I know how.

Known Shortcomings

• I’ve used this book as a primary course reference for several years now, but I still consider it to be a draft. Of course I try my best to ensure the accuracy of the content, but there are sure to be plenty of bugs, ranging in their severity. Caveat emptor!

I welcome feedback of all kinds - not just on errors and typos but also on the selection, organization, and presentation of the material.

• I usually cover essentially this entire book during our 10 -week quarters. There is probably not enough material to sustain an entire 16 -week semester, though. I always find it easier to polish existing material than to add completely new material. Someday I hope to add more chapters (see the roadmap below), but for now you’ll have to get by without some important and interesting topics.
• There is no solutions manual, and I currently have no plans to make one.

Code-Based Games Philosophy

The security definitions and proofs in these notes are presented in a style that is known to the research community as code-based games. I’ve chosen this style because I think it offers significant pedagogical benefits:

• Every security definition can be expressed in the same style, as the indistinguishability of two games. In my terminology, the games are libraries with a common interface/API but different internal implementations. An adversary is any calling program on that interface. These libraries use a concrete pseudocode that reduces ambiguity about an adversary’s capabilities. For instance, the adversary controls arguments to subroutines that it calls and sees only the return value. The adversary cannot see any variables that are privately scoped to the library.
• A consistent framework for definitions leads to a consistent process for proving and breaking security - the two fundamental activities in cryptography.

In these notes, breaking a construction always corresponds to writing a program that expects a particular interface and behaves as differently as possible in the presence of two particular implementations of the interface.

Proving security nearly always refers to showing a sequence of libraries (called hybrids), each of which is indistinguishable from the previous one. Each of these hybrids is written in concrete pseudocode. By identifying what security property we wish to prove, we identify what the endpoints of this sequence must be. The steps that connect adjacent hybrids are stated in terms of syntactic rewriting rules for pseudocode, including down-to-earth steps like factoring out and inlining subroutines, changing the value of unused variables, and so on.

• Cryptography is full of conditional statements of security: "if A is a secure thingamajig, then B is a secure doohickey." A conventional proof of such a statement would address the contrapositive: "given an adversary that attacks the doohickey-security of \(B\), I can construct an attack on the thingamajig-security of \(A . "\)

In my experience, students struggle to find the right way to transform anstract, hypothetical B-attacking adversary into a successful A-attacking adversary. By defining security in terms of games/libraries, we can avoid this abstract challenge, and indeed avoid the context switch into the contrapositive altogether. In these notes, the thingamajig-security of A gives the student a new constructive rewriting rule that can be placed in his/her toolbox and used to bridge hybrids when proving the doohickey-security of B.

Code-based games were first proposed by Shoup \({ }^{2}\) and later expanded by Bellare & Rogaway. \({ }^{3}\) These notes adopt a simplified and unified style of games, since the goal is not to encompass every possible security definition but only the fundamental ones. The most significant difference in style is that the games in these notes have no explicit INITIALIZE

\({ }^{2}\) Victor Shoup: Sequences of Games: A Tool for Taming Complexity in Security Proofs. ia.cr/2004/332

\({ }^{3}\) Mihir Bellare & Philip Rogaway: Code-Based Game-Playing Proofs and the Security of Triple Encryption. ia.cr/2004/331 or FINALIZE step. As a result, all security definitions are expressed as indistinguishability of two games/libraries, even security definitions that are fundamentally about unforgeability. Yet, we can still reason about unforgeability properties within this framework. For instance, to say that no adversary can forge a MAC, it suffices to say that no adversary can distinguish a MAC-verification subroutine from a subroutine that always returns FALSE. An index of security definitions has been provided at the end of the book.

One instance where the approach falls short, however, is in defining collision resistance. I have not been able to define it in this framework in a way that is both easy to use and easy to interpret (and perhaps I achieved neither in the end). See Chapter 11 for my best attempt.

Other Boring Stuff

Copyright

This work is copyright by Mike Rosulek and made available under the Creative Commons BY-NC-SA \(4.0\) license. Under this license, you are free to:

Share: copy and redistribute the material in any medium or format.

Adapt: remix, transform, and build upon the material.

The licensor cannot revoke these freedoms as long as you follow the following license terms:

Attribution: You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.

NonCommercial: You may not use the material for commercial purposes.

ShareAlike: If you remix, transform, or build upon the material, you must distribute your contributions under the same license as the original.

You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.

About the cover

The cover design consists of assorted shell illustrations from Bibliothèque conchyliologique, published in 1846. The images are no longer under copyright, and were obtained from the Biodiversity Heritage Library (http://biodiversitylibrary.org/bibliography/11590).

Why shells? Just like a properly deployed cryptographic primitive, a properly deployed shell is the most robust line of defense for a mollusk. To an uniformed observer, a shell is just a shell. However, there are many kinds of shells, each of which provides protection against a different kind of attack. The same is true of the cryptographic building blocks we study in this course.

Acknowledgements

Some financial support for writing this book has been kindly provided by the National Science Foundation (awards #1149647, #1617197) and the Oregon State University Open Textbook Initiative.

Thanks to Brent Carmer & Leo Reyzin for many thoughtful suggestions and comments about the material. I am also grateful for the many students in cs 427 who have reported countless bugs.

Changelog

2021-01-03 Chapter 2 (provable security basics) is now much more explicit about how security definitions are a "template" that we "fill in" with specific algorithms (e.g., Enc, Dec). Chapter 5 (PRGs) now compares/contrasts two approaches for extending the stretch of a PRG \(-\) one secure and one insecure. This chapter also introduces a "socratic dialogue" approach to thinking about security proofs (previously there was only one such dialogue in Chapter 7). Hints to the exercises are now upside-down for extra security!

2020-02-05 Overhaul of Chapter 2 (provable security fundamentals). The structure is arguably more coherent now. The total number of examples is increased. I now also include both a successful security proof and an example of where an attempted security proof goes wrong (since the scheme is actually insecure).

2020-01-09 High-frequency winter revisions are continuing. This update focuses entirely on Chapter 13 (RSA): Many many more examples are included, in Sage! Discussion of CRT is (hopefully) clearer. Digital signatures content is finally there. There’s a new discussion of how to actually compute modular exponentiation on huge numbers, and a couple fun new exercises.

2020-01-05 Revising in preparation for teaching CS427 during Winter term.

• Chapter 0: More examples. Expanded treatment of modular arithmetic. Tips & tricks for modular arithmetic and probabilities.
• Chapter 1: Moderate reorganization of "things that cryptographers blissfully ignore."
• Chapters 12-15: Moved AEAD chapter into position as chapter 12. Public-key stuff is now chapters \(13-15\).
• Chapter 13 (RSA): More (but not enough) examples of multiplicative inverses. New discussion of algorithmic aspects of exponentiation \(\bmod N\). This chapter will eventually focus on signatures exclusively, but we’re not year that. Expect updates over the next few months.

2019-03-21 Chapter 11 (hash functions) significant revisions: no more impenetrable security definition for collision-resistance; explicit treatment of salts; better examples for Merkle-Damgård and length-extension. New draft Chapter 15 on AEAD (after next revision will be inserted after Chapter 11) 2019-01-07 Extensive revisions; only the major ones listed here. Lots of homework problems added/updated throughout. I tried to revise the entire book in time for my Winter 2019 offering, but ran out of time.

Added a changelog!

• Chapter 1: Kerckhoffs’ Principle now discussed here (previously only mentioned for the first time in Ch 2).
• Chapter 2: Now the concepts are introduced in context of specific one-time security definition, not in the abstract. More examples of interchangeable libraries.
• Chapter 3: Polynomial interpolation now shown explicitly with LaGrange polynomials (rather than Vandermonde matrices). Full interpolation example worked out.
• Chapter 4: Better organization. Real-world contextual examples of extreme (large & small) \(2^{n}\) values. Full proof of bad-event lemma. Generalized avoidance-sampling libraries.
• Chapter 5: Motivate PRGs via pseudo-OTP idea. Better illustration of PRG function, and conceptual pitfalls. How NOT to build a PRG. New section on stream cipher & symmetric ratchet.
• Chapter 6: Combined PRF & PRP chapters. Motivate PRFs via \(m \mapsto(r, F(k, r) \oplus m)\) construction. Better discussion of eager vs. lazy sampling of exponentially large table. How NOT to build a PRF. New section on constructing PRG from PRF, and more clarity on security proofs with variable number of hybrids. Better illustrations & formal pseudocode for Feistel constructions.
• Chapter 7: Other ways to avoid insecurity of deterministic encryption (stateful & nonce-based). Ridiculous Socratic dialog on the security of the PRF-based encryption scheme.

Chapter 8: Compare & contrast CTR & CBC modes.

Road Map

The following topics are shamefully missing from the book, but are planned or being considered:

1. authenticated key agreement, secure messaging / ratcheting (high priority)
2. random oracle & ideal cipher models (medium priority)
3. elliptic curves, post-quantum crypto (but I would need to learn them first)
4. DH-based socialist millionaires, PSI, PAKE, simple PIR, basic MPC concepts (low priority)

Review of Concepts & Notation

The material in this section is meant as a review. Despite that, many students report that they find this review useful for the rest of the book.

\(0.1\) Logs & Exponents

You probably learned (and then forgot) these identities in middle school or high school: \[\begin{aligned} \left(x^{a}\right)\left(x^{b}\right) &=x^{a+b} \\ \left(x^{a}\right)^{b} &=x^{a b} \\ \log _{x}(a b) &=\log _{x} a+\log _{x} b \\ a \log _{x} b &=\log _{x}\left(b^{a}\right) \end{aligned}\] Well, it’s time to get reacquainted with them again.

In particular, never ever write \(\left(x^{a}\right)\left(x^{b}\right)=x^{a b}\). If you write this, your cryptography instructor will realize that life is too short, immediately resign from teaching, and join a traveling circus. But not before changing your grade in the course to a zero.

Tips & Tricks

You may often be faced with some complicated expression and asked to find the value of that expression \(\bmod n\). This usually means: find the unique value in \(\mathbb{Z}_{n}\) that is congruent to the result. The straightforward way to do this is to first compute the result over the integers, and then reduce the answer \(\bmod n\) (i.e., with the \(\% n\) operator).

While this approach gives the correct answer (and is a good anchor for your understanding), it’s usually advisable to simplify intermediate values mod \(n\). Doing so will result in the same answer, but will usually be easier or faster to compute:

Example We can evaluate the expression \(6 \cdot 7 \cdot 8 \cdot 9 \cdot 10 \% 11\) without ever calculating that product over the integers, by using the following reasoning: \[\begin{aligned} 6 \cdot 7 \cdot 8 \cdot 9 \cdot 10 &=(42) \cdot 8 \cdot 9 \cdot 10 \\ & \equiv_{11} 9 \cdot 8 \cdot 9 \cdot 10 \\ &=(72) \cdot 9 \cdot 10 \\ & \equiv_{11} 6 \cdot 9 \cdot 10 \\ &=(54) \cdot 10 \\ & \equiv_{11} 10 \cdot 10 \\ &=100 \\ & \equiv_{11} 1 \end{aligned}\] In the steps that only work \(\bmod 11\), we write " \(\equiv_{11} "\). We can write "=" when the step holds over the integers, although it wouldn’t be wrong to write " \(\equiv_{11}\) " in those cases too. If wo expressions represent the same integer, then they surely represent values that are congruent mod \(11 .\)

My advice is to simplify intermediate values mod \(n\), but "simplify" doesn’t always mean "reduce mod \(n\) with the % \(n\) operation." Sometimes an expression can by "simplified" by substituting a value with something congruent, but not in the range \(\{0, \ldots, n-1\}\) : Example I can compute \(7^{500} \% 8\) in my head, by noticing that \(7 \equiv_{8}-1\) and simplifying thusly: \[7^{500} \equiv_{8}(-1)^{500}=1 .\] Similarly, I can compute \(89^{2} \% 99\) in my head, although I have not memorized the integer \(89^{2}\). All I need to do is notice that \(89 \equiv_{99}-10\) and compute this way: \[89^{2} \equiv_{99}(-10)^{2}=100 \equiv_{99} 1\] You can compute either of these examples the "hard way" to verify that these shortcuts lead to the correct answer.

Since addition, subtraction, and multiplication are defined over the integers (i.e., adding/subtracting/multiplying integers always results in an integer), these kinds of tricks can be helpful.

On the other hand, dividing integers doesn’t always result in an integer. Does it make sense to use division when working \(\bmod n\), where the result always has to lie in \(\mathbb{Z}_{n}\) ? We will answer this question later in the book.

\(0.3\) Strings

We write \(\{0,1\}^{n}\) to denote the set of \(n\)-bit binary strings, and \(\{0,1\}^{*}\) to denote the set of all (finite-length) binary strings. When \(x\) is a string of bits, we write \(|x|\) to denote the length (in bits) of that string, and we write \(\bar{x}\) to denote the result of flipping every bit in \(x\). When it’s clear from context that we’re talking about strings instead of numbers, we write \(0^{n}\) and \(1^{n}\) to denote strings of \(n\) zeroes and \(n\) ones, respectively (rather than the result of raising the integers 0 or 1 to the \(n\) power). As you might have noticed, I also try to use a different font and color for characters (including bits, anything that could be used to build a string through concatenation) vs. integers.

Definition \(0.5 \quad\) When \(x\) and \(y\) are strings of the same length, we write \(x \oplus y\) to denote the bitwise exclusive-or \((\oplus, \mathrm{xOR}) \quad(\mathrm{XOR})\) of the two strings. The expression \(x \oplus y\) is generally not defined when the strings are different lengths, but in rare occasions it is useful to consider the shorter string being padded with \(O s\). When that’s the case, we must have an explicit convention about whether the shorter string is padded with leading \(0 s\) or trailing \(O s\).

For example, \(0011 \oplus 0101=0110\). The following facts about the Xor operation are frequently useful: \[\begin{aligned} x \oplus x &=000 \cdots & & \text { XOR'ing a string with itself results in zeroes. } \\ x \oplus 000 \cdots &=x & & \text { XOR'ing with zeroes has no effect. } \\ x \oplus 111 \cdots &=\bar{x} & & \text { XOR'ing with ones flips every bit. } \\ x \oplus y &=y \oplus x & & \text { XOR is symmetric. } \\ (x \oplus y) \oplus z &=x \oplus(y \oplus z) & & \text { XOR is associative. } \end{aligned}\] See if you can use these properties to derive the very useful fact below: \[a=b \oplus c \Longleftrightarrow b=a \oplus c \Longleftrightarrow c=a \oplus b .\] There are a few ways to think about xor that may help you in this class: - Bit-flipping: Note that xOR’ing a bit with 0 has no effect, while xOR’ing with 1 flips that bit. You can think of \(x \oplus y\) as: "starting with \(x\), flip the bits at all the positions where \(y\) has a 1." So if \(y\) is all I’s, then \(x \oplus y\) gives the bitwise-complement of \(x\). If \(y=1010 \cdots\) then \(x \oplus y\) means "(the result of) flipping every other bit in \(x\)."

Many concepts in this course can be understood in terms of bit-flipping. For example, we might ask "what happens when I flip the first bit of \(x\) and send it into the algorithm?" This kind of question could also be phrased as "what happens when I send \(x \oplus 1000 \cdots\) into the algorithm?" Usually there is nothing special about flipping just the first bit of a string, so it will often be quite reasonable to generalize the question as "what happens when I send \(x \oplus y\) into the algorithm, for an arbitrary (not-all-zeroes) string \(y\) ?"

• Addition mod-2: xOR is just addition mod 2 in every bit. This way of thinking about xOR helps to explain why "algebraic" things like \((x \oplus y) \oplus z=x \oplus(y \oplus z)\) are true. They are true for addition, so they are true for XOR.

This also might help you remember why \(x \oplus x\) is all zeroes. If instead of xor we used addition, we would surely write \(x+x=2 x\). Since \(2 \equiv_{2} 0\), we get that \(2 x\) is congruent to \(0 x=0\).

Definition \(0.6\) We write \(x \| y\) to denote the result of concatenating \(x\) and \(y\).

\((\|\), concatenation)

\(0.4\) Functions

Let \(X\) and \(Y\) be finite sets. A function \(f: X \rightarrow Y\) is:

injective \((1-\)-to-1 \()\) if it maps distinct inputs to distinct outputs. Formally: \(x \neq x^{\prime} \Rightarrow\) \(f(x) \neq f\left(x^{\prime}\right)\). If there is an injective function from \(X\) to \(Y\), then we must have \(|Y| \geqslant|X|\)

surjective (onto) if every element in \(Y\) is a possible output of \(f\). Formally: for all \(y \in Y\) there exists an \(x \in X\) with \(f(x)=y\). If there is a surjective function from \(X\) to \(Y\), then we must have \(|Y| \leqslant|X|\).

bijective (1-to-1 correspondence) if \(f\) is both injective and surjective. If there is a bijective function from \(X\) to \(Y\), then we must have \(|X|=|Y|\).

Tips & Tricks

Knowing one of the probabilities \(\operatorname{Pr}[A]\) and \(\operatorname{Pr}[\neg A]\) (which is "the probability that A doesn’t happen") tells you exactly what the other probability is, via the relationship \[\operatorname{Pr}[A]=1-\operatorname{Pr}[\neg A]\] This is one of the most basic facts about probability, but it can be surprisingly useful since one of \(\operatorname{Pr}[A]\) and \(\operatorname{Pr}[\neg A]\) is often much easier to calculate than the other. If you get stuck trying to come up with an expression for \(\operatorname{Pr}[A]\), try working out an expression for \(\operatorname{Pr}[\neg A]\) instead.

Example I roll a six-sided die, six times. What is the probability that there is some repeated value? Let’s think about all the ways of getting a repeated value. Well, two of the rolls could be 1 , or three of rolls could be 1, or all of them could be 1, two of them could be 1 and the rest could be 2, etc. Oh no, am I double-counting repeated 2 s and repeated 1s? Uhh. .

An easier way to attack the problem is to realize that the probability we care about is actually \(1-\operatorname{Pr}[\) all 6 rolls are distinct]. This complementary event (all 6 rolls distinct) happens exactly when the sequence of dice rolls spell out a permutation of \(\{1, \ldots, 6\}\). There are \(6 !=\) 720 such permutations, out of \(6^{6}=46656\) total possible outcomes. Hence, the answer to the question is \[1-\frac{6 !}{6^{6}}=1-\frac{720}{46656}=\frac{45936}{46656} \approx 0.9846\] Another trick is one I like to call setting breakpoints on the universe. Imagine stopping the universe at a point where some random choices have happened, and others have not yet happened. This is best illustrated by example:

Example A classic question asks: when rolling two 6-sided dice what is the probability that the dice match? Here is a standard (and totally correct way) to answer the question:

When rolling two 6-sided dice, there are \(6^{2}=36\) total outcomes ( a pair of numbers), so each has probability 1/36 under a uniform distribution. There are 6 outcomes that make the dice match: both dice 1 , both dice 2, both dice 3, and so on. Therefore, the probability of rolling matching dice is \(6 / 36=1 / 6\).

A different way to arrive at the answer goes like this: Imagine I roll the dice one after another, and I pause the universe (set a breakpoint) after rolling the first die but before rolling the second one. The universe has already decided the result of the first die, so let’s call that value \(d\). The dice will match only if the second roll comes \(u p d\). Rolling \(d\) on the second die (indeed, rolling any particular value) happens with probability \(1 / 6 .\)

This technique of setting breakpoints is simple but powerful and frequently useful. Some other closely related tricks are: (1) postponing a random choice until the last possible moment, just before its result is used for the first time, and (2) switching the relative order of independent random choices.

Precise Terminology

It is tempting in this course to say things like " \(x\) is a random string." But a statement like this is sloppy on several accounts.

First, is 42 a random number? Is "heads" a random coin? What is even being asked by these questions? Being "random" is not a property of an outcome (like a number or a side of a coin) but a property of the process that generates an outcome. \({ }^{3}\) Instead of saying " \(x\) is a random string" it’s much more precise to say " \(x\) was chosen randomly"

Second, usually when we use the word "random" we don’t mean any old probability distribution. We usually mean to refer to the uniform distribution. Instead of saying " \(x\) was chosen randomly" it’s much more precise to say " \(x\) was chosen uniformly" (assuming that really is what you mean).

Every cryptographer I know (yes, even your dear author) says things like " \(x\) is a random string" all the time to mean " \(x\) was chosen uniformly [from some set of strings]." Usually the meaning is clear from context, at least to the other cryptographers in the room. But all of us could benefit by having better habits about this sloppy language. Students especially will benefit by internalizing the fact that randomness is a property of the process, not of the individual outcome.

Subroutine conventions

We’ll use mathematical notation to define the types of subroutine arguments: \[\frac{\operatorname{FOO}\left(x \in\{0,1\}^{*}\right):}{\ldots} \quad \text { means "void foo }(\operatorname{string} x)\{\ldots\}^{\prime \prime}\]

One-Time Pad & Kerckhoffs’ Principle

You can’t learn about cryptography without meeting Alice, Bob, and Eve. This chapter is about the classic problem of private communication, in which Alice has a message that she wants to convey to Bob, while also keeping the contents of the message hidden from an eavesdropper \({ }^{1}\) Eve. You’ll soon learn that there is more to cryptography than just private communication, but it is the logical place to start.

Encryption Basics & Terminology

Let’s begin to formalize our scenario involving Alice, Bob, and Eve. Alice has a message \(m\) that she wants to send (privately) to Bob. We call \(m\) the plaintext. We assume she will somehow transform that plaintext into a value \(c\) (called the ciphertext) that she will actually send to Bob. The process of transforming \(m\) into \(c\) is called encryption, and we will use Enc to refer to the encryption algorithm. When Bob receives \(c\), he runs a corresponding decryption algorithm Dec to recover the original plaintext \(m\).

We assume that the ciphertext may be observed by the eavesdropper Eve, so the (informal) goal is for the ciphertext to be meaningful to Bob but meaningless to Eve.

1"Eavesdropper" refers to someone who secretly listens in on a conversation between others. The term originated as a reference to someone who literally hung from the eaves of a building in order to hear conversations happening inside.

Secrets & Kerckhoffs’ Principle

Something important is missing from this picture. If we want Bob to be able to decrypt \(c\), but Eve to not be able to decrypt \(c\), then Bob must have some information that Eve doesn’t have (do you see why?). Something has to be kept secret from Eve.

You might suggest to make the details of the Enc and Dec algorithms secret. This is how cryptography was done throughout most of the last 2000 years, but it has major drawbacks. If the attacker does eventually learn the details of Enc and Dec, then the only way to recover security is to invent new algorithms. If you have a system with many users, then the only way to prevent everyone from reading everyone else’s messages is to invent new algorithms for each pair of users. Inventing even one good encryption method is already hard enough!

The first person to articulate this problem was Auguste Kerckhoffs. In 1883 he formulated a set of cryptographic design principles. Item #2 on his list is now known as Kerckhoff’s’ principle:

Kerckhoffs’Principle:

"Il faut qu’il n’exige pas le secret, et qu’il puisse sans inconvénient tomber entre les mains de l’ennemi."

Literal translation: [The method] must not be required to be secret, and it must be able to fall into the enemy’s hands without causing inconvenience.

Bottom line: Design your system to be secure even if the attacker has complete knowledge of all its algorithms.

If the algorithms themselves are not secret, then there must be some other secret information in the system. That information is called the (secret) key. The key is just an extra piece of information given to both the Enc and Dec algorithms. Another way to interpret Kerckhoffs’ principle is that all of the security of the system should be concentrated in the secrecy of the key, not the secrecy of the algorithms. If a secret key gets compromised, you only need to choose a new one, not reinvent an entirely new encryption algorithm. Multiple users can all safely use the same encryption algorithm but with independently chosen secret keys.

The process of choosing a secret key is called key generation, and we write KeyGen to refer to the (randomized) key generation algorithm. We call the collection of three algorithms (Enc, Dec, KeyGen) an encryption scheme. Remember that Kerckhoffs’ principle says that we should assume that an attacker knows the details of the KeyGen algorithm. But also remember that knowing the details (i.e., source code) of a randomized algorithm doesn’t mean you know the specific output it gave when the algorithm was executed.

Excuses, Excuses

Let’s practice some humility. Here is just a partial list of issues that are clearly important for the problem of private communication, but which are not addressed by our definition of the problem.

• We are not trying to hide the fact that Alice is sending something to Bob, we only want to hide the contents of that message. Hiding the existence of a communication channel is called steganography.
• We won’t consider the question of how \(c\) reliably gets from Alice to Bob. We’ll just take this issue for granted.
• For now, we are assuming that Eve just passively observes the communication between Alice & Bob. We aren’t considering an attacker that tampers with \(c\) (causing Bob to receive and decrypt a different value), although we will consider such attacks later in the book.
• We won’t discuss how Alice and Bob actually obtain a common secret key in the real world. This problem (known as key distribution) is clearly incredibly important, and we will discuss some clever approaches to it much later in the book.

In my defense, the problem we are solving is already rather non-trivial: once two users have established a shared secret key, how can they use that key to communicate privately?

• We won’t discuss how Alice and Bob keep their key secret, even after they have established it. One of my favorite descriptions of cryptography is due to Lea Kissner (former principal security engineer at Google): "cryptography is a tool for turning lots of different problems into key management problems."
• Throughout this course we simply assume that the users have the ability to uniformly sample random strings. Indeed, without randomness there is no cryptography. In the real world, obtaining uniformly random bits from deterministic computers is extremely non-trivial. John von Neumann famously said, "Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin." Again, even when we take uniform randomness for granted, we still face the non-trivial question of how to \(u\) se that randomness for private communication (and other applications), and also how to use only a manageable amount of randomness.

Not Cryptography

People use many techniques to try to hide information, but many are "non-cryptographic" since they don’t follow Kerckhoffs’ principle:

• Encoding/decoding methods like base64 ... ... are useful for incorporating arbitrary binary data into a structured file format that supports limited kinds of characters. But since base64 encoding/decoding involves no secret information, it adds nothing in terms of security.
• Sometimes the simplest way to describe an encryption scheme is with operations on binary strings (i.e., Os and 1s) data. As we will see, one-time pad is defined in terms of plaintexts represented as strings of bits. (Future schemes will require inputs to be represented as a bitstring of a specific length, or as an element of \(\mathbb{Z}_{n}\), etc.)

In order to make sense of some algorithms in this course, it may be necessary to think about data being converted into binary representation. Just like with base64, representing things in binary has no effect on security since it does not involve any secret information. Writing something in binary is not a security measure!

Correctness

The first property of one-time pad that we should confirm is that the receiver does indeed recover the intended plaintext when decrypting the ciphertext. Without this property, the thought of using one-time pad for communication seems silly. Written mathematically:

Claim 1.2 For all \(k, m \in\{0,1\}^{\lambda}\), it is true that \(\operatorname{Dec}(k, \operatorname{Enc}(k, m))=m\).

Proof This follows by substituting the definitions of OTP Enc and Dec, then applying the properties of xOR listed in Chapter \(0.3\). For all \(k, m \in\{0,1\}^{\lambda}\), we have: \[\begin{aligned} \operatorname{Dec}(k, \operatorname{Enc}(k, m)) &=\operatorname{Dec}(k, k \oplus m) \\ &=k \oplus(k \oplus m) \\ &=(k \oplus k) \oplus m \\ &=0^{\lambda} \oplus m \\ &=m \end{aligned}\] Example Encrypting the following plaintext \(m\) under the key \(k\) results in ciphertext \(c\), as follows:

Decrypting \(c\) using the same key \(k\) results in the original \(m\) :

Security

Suppose Alice and Bob are using one-time pad but are concerned that an attacker sees their ciphertext. They can’t presume what an attacker will do after seeing the ciphertext. But they would like to say something like, "because of the specific way the ciphertext was generated, it doesn’t reveal any information about the plaintext to the attacker, no matter what the attacker does with the ciphertext."

We must first precisely specify how the ciphertext is generated. The Enc algorithm already describes the process, but it is written from the point of view of Alice and Bob. When talking about security, we have to think about what Alice and Bob do, but from the eavesdropper’s point of view! From Eve’s point of view, Alice uses a key that was chosen in a specific way (uniformly at random), she encrypts a plaintext with that key using OTP, and finally reveals only the resulting ciphertext (and not the key) to Eve.

More formally, from Eve’s perspective, seeing a ciphertext corresponds to receiving an output from the following algorithm:

It’s crucial that you appreciate what this EAVESDROP algorithm represents. It is meant to describe not what the attacker does, but rather the process (carried out by Alice and Bob!) that produces what the attacker sees. We always treat the attacker as some (unspecified) process that receives output from this EAVESDROP algorithm. Our goal is to say something like "the output of EAVESDROP doesn’t reveal the input \(m\) ".

EAVESDROP is a randomized algorithm - remember that " \(k \leftarrow\{0,1\}^{\lambda "}\) means to sample \(k\) from the uniform distribution on \(\lambda\)-bit strings. If you call EAVESDROP several times, even on the same input, you are likely to get different outputs. Instead of thinking of "EAVESDROP \((m)\) " as a single string, you should think of it as a probability distribution over strings. Each time you call EAVESDROP \((m)\), you see a sample from that distribution.

Example Let’s take \(\lambda=3\) and work out by hand the distributions EAVESDROP(010) and EAVESDROP(111). In each case EAVESDROP chooses a value of \(k\) uniformly in \(\{0,1\}^{3}\) - each of the possible values with probability \(1 / 8\). For each possible choice of \(k\), we can compute what the output of EAVESDROP (c) will be:

So the distribution EAVESDROP \((010)\) assigns probabilty \(1 / 8\) to 010 , probability \(1 / 8\) to 011 , and so on.

In this example, notice how every string in \(\{0,1\}^{3}\) appears exactly once in the \(c\) column of EAVESDROP \((010)\). This means that EAVESDROP assigns probability \(1 / 8\) to every string in \(\{0,1\}^{3}\), which is just another way of saying that the distribution is the uniform distribution on \(\{0,1\}^{3}\). The same can be said about the distribution EAVESDROP(111), too. Both distributions are just the uniform distribution in disguise!

There is nothing special about 010 or 111 in these examples. For any \(\lambda\) and any \(m \in\) \(\{0,1\}^{\lambda}\), the distribution EAVESDROP \((m)\) is the uniform distribution over \(\{\theta, 1\}^{\lambda}\).

Claim 1.3 For every \(m \in\{0,1\}^{\lambda}\), the distribution EAVESDROP \((m)\) is the uniform distribution on \(\{0,1\}^{\lambda}\). Hence, for all \(m, m^{\prime} \in\{0,1\}^{\lambda}\), the distributions EAVESDROP \((m)\) and EAVESDROP \(\left(m^{\prime}\right)\) are identical.

Proof Arbitrarily fix \(m, c \in\{0,1\}^{\lambda}\). We will calculate the probability that EAVESDROP \((m)\) produces output \(c\). That event happens only when \[c=k \oplus m \Longleftrightarrow k=m \oplus c .\] The equivalence follows from the properties of xOR given in Section 0.3. That is, \[\operatorname{Pr}[\text { EAVESDROP }(m)=c]=\operatorname{Pr}[k=m \oplus c],\] where the probability is over uniform choice of \(k \leftarrow\{0,1\}^{\lambda}\).

We are considering a specific choice for \(m\) and \(c\), so there is only one value of \(k\) that makes \(k=m \oplus c\) true (causes \(m\) to encrypt to \(c\) ), and that value is exactly \(m \oplus c\). Since \(k\) is chosen uniformly from \(\{0,1\}^{\lambda}\), the probability of choosing the particular value \(k=m \oplus c\) is \(1 / 2^{\lambda}\)

In summary, for every \(m\) and \(c\), the probability that EAVESDROP \((m)\) outputs \(c\) is exactly \(1 / 2^{\lambda}\). This means that the output of EAVESDROP \((m)\), for any \(m\), follows the uniform distribution.

One way to interpret this statement of security in more down-to-earth terms:

If an attacker sees a single ciphertext, encrypted with one-time pad, where the key is chosen uniformly and kept secret from the attacker, then the ciphertext appears uniformly distributed.

Why is this significant? Taking the eavesdropper’s point of view, suppose someone chooses a plaintext \(m\) and you get to see the resulting ciphertext - a sample from the distribution EAVESDROP \((m)\). But this is a distribution that you can sample from yourself, even if you don’t know \(m\) ! You could have chosen a totally different \(m^{\prime}\) and run EAVESDROP( \(\left.m^{\prime}\right)\) in your imagination, and this would have produced the same distribution as EAVESDROP \((m)\). The "real" ciphertext that you see doesn’t carry any information about \(m\) if it is possible to sample from the same distribution without even knowing \(m\) !

Discussion

• Isn’t there a paradox? Claim \(1.2\) says that \(c\) can always be decrypted to get \(m\), but Claim \(1.3\) says that \(c\) contains no information about \(m\) ! The answer to this riddle is that Claim \(1.2\) talks about what can be done with knowledge of the key \(k\) (Alice & Bob’s perspective). Claim \(1.3\) talks about the output distribution of the EAVESDROP algorithm, which doesn’t include \(k\) (Eve’s perspective). In short, if you know \(k\), then you can decrypt \(c\) to obtain \(m\); if you don’t know \(k\), then \(c\) carries no information about \(m\) (in fact, it looks uniformly distributed). This is because \(m, c, k\) are all correlated in a delicate way. \({ }^{3}\)
• Isn’t there another paradox? Claim \(1.3\) says that the output of EAVESDROP \((m)\) doesn’t depend on \(m\), but we can see the EAVESDROP algorithm literally using its argument \(m\) right there in the last line! The answer to this riddle is perhaps best illustrated by the previous illustrations of the EAVESDROP \((010)\) and EAVESDROP(111) distributions. The two tables of values are indeed different (so the choice of \(m \in\) \(\{010,111\}\) clearly has some effect), but they represent the same probability distribution (since order doesn’t matter). Claim \(1.3\) considers only the resulting probability distribution.
• You probably think about security in terms of a concrete "goal" for the attacker: recover the key, recover the plaintext, etc. Claim \(1.3\) doesn’t really refer to attackers in that way, and it certainly doesn’t specify a goal. Rather, we are thinking about security by comparing to some hypothetical "ideal" world. I would be satisfied if the attacker sees only a source of uniform bits, because in this hypothetical world there are no keys and no plaintexts to recover! Claim \(1.3\) says that when we actually use OTP, it looks just like this hypothetical world, from the attacker’s point of view. If we imagine any "goal" at all for the attacker in this kind of reasoning, it’s to detect that ciphertexts don’t follow a uniform distribution. By showing that the attacker can’t even achieve this modest goal, it shows that the attacker couldn’t possibly achieve other, more natural, goals like key recovery and plaintext recovery.

Limitations

One-time pad is incredibly limited in practice. Most notably:

• Its keys are as long as the plaintexts they encrypt. This is basically unavoidable (see Exercise 2.11) and leads to a kind of chicken-and-egg dilemma in practice: If two users want to privately convey a \(\lambda\)-bit message, they first need to privately agree on a \(\lambda\)-bit string.
• A key can be used to encrypt only one plaintext (hence, "one-time" pad); see Exercise 1.6. Indeed, we can see that the EAVESDRop subroutine in Claim \(1.3\) provides no way for a caller to guarantee that two plaintexts are encrypted with the same key, so it is not clear how to use Claim \(1.3\) to argue about what happens in one-time pad when keys are intentionally reused in this way.

\({ }^{3}\) This correlation is explored further in Chapter \(3 .\) Despite these limitations, one-time pad illustrates fundamental ideas that appear in most forms of encryption in this course.

The Basics of Provable Security

Edgar Allan Poe was not only an author, but also a cryptography enthusiast. He once wrote, in a discussion on the state of the art in cryptography: \({ }^{1}\)

"Human ingenuity cannot concoct a cipher which human ingenuity cannot resolve."

This was an accurate assessment of the cryptography that existed in 1841 . Whenever someone would come up with an encryption method, someone else would inevitably find a way to break it, and the cat-and-mouse game would repeat again and again.

Modern 21st-century cryptography, however, is different. This book will introduce you to many schemes whose security we can prove in a very specific sense. The codemakers can win against the code-breakers.

It’s only possible to prove things about security by having formal definitions of what it means to be "secure." This chapter is about the fundamental skills that revolve around security definitions: how to write them, how to understand & interpret them, how to prove security using the hybrid technique, and how to demonstrate insecurity using attacks against the security definition.

What Doesn’t Go Into a Security Definition

A security definition should give guarantees about what can happen to a system in the presence of an attacker. But not all important properties of a system refer to an attacker. For encryption specifically:

• We don’t reference any attacker when we say that the Enc algorithm takes two arguments (a key and a plaintext), or that the KeyGen algorithm takes no arguments. Specifying the types of inputs/outputs (i.e., the "function signature") of the various algorithms is therefore not a statement about security. We call these properties the syntax of the scheme.

\({ }^{1}\) Edgar Allan Poe, "A Few Words on Secret Writing," Graham’s Magazine, July 1841, v19. - Even if there is no attacker, it’s still important that decryption is an inverse of encryption. This is not a security property of the encryption scheme. Instead, we call it a correctness property.

Below are the generic definitions for syntax and correctness of symmetric-key encryption:

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

• KeyGen: a randomized algorithm that outputs a key \(k \in \mathcal{K}\).
• Enc: a (possibly randomized) algorithm that takes a key \(k \in \mathcal{K}\) and plaintext \(m \in \mathcal{M}\) as input, and outputs a ciphertext \(c \in C\).
• Dec: a deterministic algorithm that takes a key \(k \in \mathcal{K}\) and ciphertext \(c \in C\) as input, and outputs a plaintext \(m \in \mathcal{M}\).

We call \(\mathcal{K}\) the key space, \(\mathcal{M}\) the message space, and \(C\) the ciphertext space of the scheme. Sometimes we refer to the entire scheme (the collection of all three algorithms) by a single variable \(\sum\). When we do so, we write \(\sum\).KeyGen, \(\sum\).Enc, \(\sum\).Dec, \(\sum . \mathcal{K}, \Sigma\). \(\mathcal{M}\), and \(\sum\). \(\mathcal{C}\) to refer to its components.

Definition 2.2 An encryption scheme \(\sum\) satisfies correctness if for all \(k \in \Sigma . \mathcal{K}\) and all \(m \in \Sigma . \mathcal{M}\), (SKE correctness) \[\operatorname{Pr}[\Sigma \cdot \operatorname{Dec}(k, \Sigma . \operatorname{Enc}(k, m))=m]=1\] The definition is written in terms of a probability because Enc is allowed to be a randomized algorithm. In other words, decrypting a ciphertext with the same key that was used for encryption must always result in the original plaintext.

Example An encryption scheme can have the appropriate syntax but still have degenerate behavior like \(\operatorname{Enc}(k, m)=0^{\lambda}\) (i.e., every plaintext is "encrypted" to \(\theta^{\lambda}\) ). Such a scheme would not satisfy the correctness property.

A different scheme defined by \(\operatorname{Enc}(k, m)=m\) (i.e., the "ciphertext" is always equal to the plaintext itself) and \(\operatorname{Dec}(k, c)=c\) does satisfy the correctness property, but would not satisfy any reasonable security property.

"Real-vs-Random" Style of Security Definition

Let’s try to make a security definition that formalizes the following intuitive idea:

"an encryption scheme is a good one if its ciphertexts look like random junk to an attacker."

Security definitions always consider the attacker’s view of the system. What is the "in terface" that Alice & Bob expose to the attacker by their use of the cryptography, and does that particular interface benefit the attacker?

In this example, we’re considering a scenario where the attacker gets to observe ciphertexts. How exactly are these ciphertexts generated? What are the inputs to Enc (key and plaintext), and how are they chosen? - Key: It’s hard to imagine any kind of useful security if the attacker knows the key. Hence, we consider that the key is kept secret from the attacker. Of course, the key is generated according to the KeyGen algorithm of the scheme.

At this point in the course, we consider encryption schemes where the key is used to encrypt only one plaintext. Somehow this restriction must be captured in our security definition. Later, we will consider security definitions that consider a key that is used to encrypt many things.

• Plaintext: It turns out to be useful to consider that the attacker actually chooses the plaintexts. This a "pessimistic" choice, since it gives much power to the attacker. However, if the encryption scheme is indeed secure when the attacker chooses the plaintexts, then it’s also secure in more realistic scenarios where the attacker has some uncertainty about the plaintexts.

These clarifications allow us to fill in more specifics about our informal idea of security:

"an encryption scheme is a good one if its ciphertexts look like random junk to an attacker... when each key is secret and used to encrypt only one plaintext, even when the attacker chooses the plaintexts."

A concise way to express all of these details is to consider the attacker as a calling program to the following subroutine:

A calling program can choose the argument to the subroutine (in this case, a plaintext), and see only the resulting return value (in this case, a ciphertext). The calling program can’t see values of privately-scoped variables (like \(k\) in this case). If the calling program makes many calls to the subroutine, a fresh key \(k\) is chosen each time.

The interaction between an attacker (calling program) and this ctXT subroutine appears to capture the relevant scenario. We would like to say that the outputs from the CTXT subroutine are uniformly distributed. A convenient way of expressing this property is to say that this crxT subroutine should have the same effect on every calling program as a CTXT subroutine that (explicitly) samples its output uniformly.

Intuitively, no calling program should have any way of determining which of these two implementations is answering subroutine calls. As an analogy, one way of saying that "FOO is a correct sorting algorithm" is to say that "no calling program would behave differently if Foo were replaced by an implementation of mergesort."

In summary, we can define security for encryption in the following way: "an encryption scheme is a good one if, when you plug its KeyGen and Enc algorithms into the template of the CTXT subroutine above, the two implementations of CTXT induce identical behavior in every calling program."

In a few pages, we introduce formal notation and definitions for the concepts introduced here. In particular, both the calling program and subroutine can be randomized algorithms, so we should be careful about what we mean by "identical behavior."

Example One-time pad is defined with KeyGen sampling \(k\) uniformly from \(\{0,1\}^{\lambda}\) and Enc \((k, m)=\) \(k \oplus m\). It satisfies our new security property since, when we plug in this algorithms into the above template, we get the following two subroutine implementations:

and these two implementations have the same effect on all calling programs.

"Left-vs-Right" Style of Security Definition

Here’s a different intuitive idea of security:

"an encryption scheme is a good one if encryptions of \(m_{L}\) look like encryptions of \(m_{R}\) to an attacker (for all possible \(\left.m_{L}, m_{R}\right)\) ”

As above, we are considering a scenario where the attacker sees some ciphertext(s). These ciphertexts are generated with some key; where does that key come from? These ciphertexts encrypt either some \(m_{L}\) or some \(m_{R}\); where do \(m_{L}\) and \(m_{R}\) come from? We can answer these questions in a similar way as the previous example. Plaintexts \(m_{L}\) and \(m_{R}\) can be chosen by the attacker. The key is chosen according to KeyGen so that it remains secret from the attacker (and is used to generate only one ciphertext).

"an encryption scheme is a good one if encryptions of \(m_{L}\) look like encryptions of \(m_{R}\) to an attacker, when each key is secret and used to encrypt only one plaintext, even when the attacker chooses \(m_{L}\) and \(m_{R} .\)

As before, we formalize this idea by imagining the attacker as a program that calls a particular interface. This time, the attacker will choose two plaintexts \(m_{L}\) and \(m_{R}\), and get a ciphertext in return. \({ }^{2}\) Depending on whether \(m_{L}\) or \(m_{R}\) is actually encrypted, those interfaces are implemented as follows:

\({ }^{2}\) There may be other reasonable ways to formalize this intuitive idea of security. For example, we might choose to give the attacker two ciphertexts instead of one, and demand that the attacker can’t determine which of them encrypts \(m_{L}\) and which encrypts \(m_{R}\). See Exercise \(2.15\).

EAVESDROP \(\left(m_{L}, m_{R} \in \sum . \mathcal{M}\right):\)
\(k \leftarrow \sum . \operatorname{KeyGen}\)
\(c:=\sum . \operatorname{Enc}\left(k, m_{R}\right)\)
return \(c\)

Now the formal way to say that encryptions of \(m_{L}\) "look like" encryptions of \(m_{R}\) is:

"an encryption scheme is a good one if, when you plug its KeyGen and Enc algorithms into the template of the EAVESDROP subroutines above, the two implementations of EAVESDROP induce identical behavior in every calling program."

Example Does one-time pad satisfy this new security property? To find out, we plug in its algorithms to the above template, and obtain the following implementations:

If these two implementations have the same effect on all calling programs (and indeed they do), then we would say that OTP satisfies this security property.

Is this a better/worse way to define security than the previous way? One security definition considers an attacker whose goal is to distinguish real ciphertexts from random values (real-vs-random paradigm), and the other considers an attacker whose goal is to distinguish real ciphertexts of two different plaintexts (left-vs-right paradigm). Is one "correct" and the other one "incorrect?"We save such discussion until later in the chapter.

Interchangeability

The idea that "no calling program behaves differently in the presence of these two libraries" still makes sense even for libraries with several subroutines. Since this is such a common concept, we devote new notation to it:

Definition 2.4 Let \(\mathcal{L}_{\text {left }}\) and \(\mathcal{L}_{\text {right }}\) be two libraries that have the same interface. We say that \(\mathcal{L}_{\text {left }}\) and \(\mathcal{L}_{\text {right }}\) (Interchangeable) are interchangeable, and write \(\mathcal{L}_{\text {left }} \equiv \mathcal{L}_{\text {right }}\), iffor all programs \(\mathcal{A}\) that output a boolean value, \[\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {left }} \Rightarrow \text { true }\right]=\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {right }} \Rightarrow \text { true }\right]\] This definition considers calling programs that give boolean output. Imagine a calling program / attacker whose only goal is to distinguish two particular libraries (indeed, we often refer to the calling program as a distinguisher). A boolean output is enough for that task. You can think of the output bit as the calling program’s "guess" for which library the calling program thinks it is linked to. The distinction between "calling program outputs true" and "calling program outputs false" is not significant. If two libraries don’t affect the calling program’s probability of outputting true, then they also don’t affect its probability of outputting false:

Example Here are some very simple and straightforward ways that two libraries may be interchangeable. Hopefully it’s clear that each pair of libraries has identical behavior, and therefore identical effect on all calling programs.

Despite being very simple examples, each of these concepts shows up as a building block in a real security proof in this book.

Their only difference happens in an unreachable block of code.

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

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

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

Example Here are more simple examples of interchangeable libraries that involve randomness: \[\begin{aligned} & \operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {left }} \Rightarrow \text { true }\right]=\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {right }} \Rightarrow \text { true }\right] \\ & \Leftrightarrow \quad 1-\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {left }} \Rightarrow \text { true }\right]=1-\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {right }} \Rightarrow \text { true }\right] \\ & \Leftrightarrow \quad \operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {left }} \Rightarrow \text { false }\right]=\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {right }} \Rightarrow \text { false }\right] . \end{aligned}\]

The uniform distribution over strings acts independently on different characters in the string ("|" refers to concatenation).

Sampling a value "eagerly" (as soon as possible) vs. sampling a value "lazily" (at the last possible moment before the value is needed). We assume that \(k\) is static/global across many calls to FOO, and initially undefined.

Formal Restatements of Previous Concepts

We can now re-state our security definitions from the previous section, using this new terminology.

Our "real-vs-random" style of security definition for encryption can be expressed as follows:

Definition \(2.5\) An encryption scheme \(\sum\) has one-time uniform ciphertexts if:

(Uniform ctxts)

In other words, if you fill in the specifics of \(\Sigma\) (i.e., the behavior of its KeyGen and Enc) into these two library "templates", and you get two libraries that are interchangeable (i.e., have the same effect on all calling programs), we will say that \(\Sigma\) has one-time uniform ciphertexts.

Throughout this course, we will use the "$" symbol to denote randomness (as in realvs-random \()^{3}\)

Our "left-vs-right" style of security definition can be expressed as follows:

An encryption scheme \(\sum\) has one-time secrecy if:

(One-time secrecy)

\({ }^{3}\) It is quite common in CS literature to use the "$" symbol when referring to randomness. This stems from thinking of randomized algorithms as algorithms that "toss coins." Hence, randomized algorithms need to have spare change (i.e., money) sitting around. By convention, randomness comes in US dollars. Previously in Claim \(1.3\) we argued that one-time-pad ciphertexts follow the uniform distribution. This actually shows that OTP satisfies the uniform ciphertexts definition:

Claim 2.7 One-time pad satisfies the one-time uniform ciphertexts property. In other words:

(OTP rule)

Because this property of OTP is quite useful throughout the course, I’ve given these two libraries special names (apart from \(\mathcal{L}_{\text {ots } \$ \text {-real }}^{\text {OTP }}\) and \(\mathcal{L}_{\text {ots } \$ \text {-rand }}^{\text {OTP }}\) ).

Discussion, Pitfalls

It is a common pitfall to imagine the calling program \(\mathcal{A}\) being simultaneously linked to both libraries, but this is not what the definition says. The definition of \(\mathcal{L}_{1} \equiv \mathcal{L}_{2}\) refers to two different executions: one where \(\mathcal{A}\) is linked only to \(\mathcal{L}_{1}\) for its entire lifetime, and one where \(\mathcal{A}\) is linked only to \(\mathcal{L}_{2}\) for its entire lifetime. There is never a time where some of \(\mathcal{A}\) ’s subroutine calls are answered by \(\mathcal{L}_{1}\) and others by \(\mathcal{L}_{2}\). This is an especially important distinction when \(\mathcal{A}\) makes several subroutine calls in a single execution.

Another common pitfall is confusion about the difference between the algorithms of an encryption scheme (e.g., what is shown in Construction 1.1) and the libraries used in a security definition (e.g., what is shown in Definition 2.6). The big difference is:

• The algorithms of the scheme show a regular user’s view of things. For example, the Enc algorithm takes two inputs: a key and a plaintext. Is there any way of describing an algorithm that takes two arguments other than writing something like Construction \(1.1 ?\)
• The libraries capture the attacker’s view of of a particular scenario, where the users use the cryptographic algorithms in a very specific way. For example, when we talk about security of encryption, we don’t guarantee security when Alice lets the attacker choose her encryption key! But letting the attacker choose the plaintext is fine; we can guarantee security in that scenario. That’s why Definition \(2.5\) describes a subroutine that calls Enc on a plaintext that is chosen by the calling program, but on a key \(k\) chosen by the library.

A security definition says that some task (e.g., distinguishing ciphertexts from random junk) is impossible, when the attacker is allowed certain influence over the inputs to the algorithms (e.g., full choice of plaintexts, but no influence over the key), and is allowed to see certain outputs from those algorithms (e.g., ciphertexts).

It’s wrong to summarize one-time secrecy as: "I’m not allowed to choose what to encrypt, I have to ask the attacker to choose for me." The correct interpretation is: "If I encrypt only one plaintext per key, then I am safe to encrypt things even if the attacker sees the resulting ciphertext and even if she has some influence or partial information on what I’m encrypting, because this is the situation captured in the one-time secrecy library"

Kerckhoffs’ Principle, Revisited

Kerckhoffs’ Principle says to assume that the attacker has complete knowledge of the algorithms being used. Assume that the choice of keys is the only thing unknown to the attacker. Let’s see how Kerckhoffs’ Principle is reflected in our formal security definitions.

Suppose I write down the source code of two libraries, and your goal is to write an effective distinguisher. So you study the source code of the two libraries and write the best distinguisher that exists. It would be fair to say that your distinguisher "knows" what algorithms are used in the libraries, because it was designed based on the source code of these libraries. The definition of interchangeability considers literally every calling program, so it must also consider calling programs like yours that "know" what algorithms are being used.

However, there is an important distinction to make. If you know you might be linked to a library that executes the statement " \(k \leftarrow\{0,1\}^{\lambda "}\), that doesn’t mean you know the actual value of \(k\) that was chosen at runtime. Our convention is that all variables within the library are privately scoped, and the calling program can learn about them only indirectly through subroutine outputs. In the library-distinguishing game, you are not allowed to pick a different calling program based on random choices that the library makes! After we settle on a calling program, we measure its effectiveness in terms of probabilities that take into account all possible outcomes of the random choices in the system.

In summary, the calling program "knows" what algorithms are being used (and how they are being used!) because the choice of the calling program is allowed to depend on the 2 specific libraries that we consider. The calling program "doesn’t know" things like secret keys because the choice of calling program isn’t allowed to depend on the outcome of random sampling done at runtime.

Kerckhoffs’ Principle, applied to our formal terminology:

Assume that the attacker knows every fact in the universe, except for:

1. which of the two possible libraries it is linked to in any particular execution, and
2. the random choices that the library will make during any particular execution (which are usually assigned to privately scoped variables within the library).

Claim \(2.9 \quad\) Construction \(2.8\) does not have one-time uniform ciphertexts (Definition 2.5).

Proof To see whether Construction \(2.8\) satisfies uniform one-time ciphertexts, we have to plug in its algorithms into the two libraries of Definition \(2.5\) and see whether the resulting libraries are interchangeable. We’re considering the following two libraries:

|l|
\(\frac{\operatorname{ctXT}\left(m \in\{0,1\}^{\lambda}\right):}{c \leftarrow\{0,1\}^{\lambda} / / \Sigma . C}\)
return \(c\)

To show that these two libraries are not interchangeable, we need to write a calling program that behaves differently in their presence. The calling program should make one or more calls to the сTXT subroutine. That means it needs to choose the input \(m\) that it passes, and it must make some conclusion (about which of the two libraries it is linked to) based on the return value that it gets. What \(m\) should the calling program choose as input to ctXT? What should the calling program look for in the return values?

There are many valid ways to write a good calling program, and maybe you can think of several. One good approach is to observe that bitwise-AND with \(k\) can never "turn a 0 into a 1." So perhaps the calling program should choose \(m\) to consist of all 0 s. When \(m=0^{\lambda}\), the \(\mathcal{L}_{\text {ots\$-real }}\) library will always return all zeroes, but the \(\mathcal{L}_{\text {ots\$-rand }}\) library may return strings with both \(\theta\) s and 1s.

We can formalize this idea with the following calling program:

\(\mathcal{A}:\)
\(c:=\operatorname{CTXT}\left(\theta^{\lambda}\right)\)
return \(c \stackrel{?}{=} 0^{\lambda}\)

Next, let’s ensure that this calling program behaves differently when linked to each of these two libraries.

When \(\mathcal{A}\) is linked to \(\mathcal{L}_{\text {ots\$-real }}, c\) is computed as \(k \& 0^{\lambda}\). No matter what \(k\) is, the result is always all-zeroes. Therefore, \(\mathcal{A}\) will always return true.

In other words, \(\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {ots } \$ \text {-real }} \Rightarrow\right.\) true \(]=1\).

When \(\mathcal{A}\) is linked to \(\mathcal{L}_{\text {ots\$-rand }}, c\) is chosen uniformly from \(\{0,1\}^{\lambda}\). The probability that \(c\) then happens to be all-zeroes is \(1 / 2^{\lambda}\).

In other words, \(\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {ots\$-rand }} \Rightarrow\right.\) true \(]=1 / 2^{\lambda}\).

Since these two probabilities are different, this shows that \(\mathcal{L}_{\text {ots\$-real }}^{\Sigma} \not \equiv \mathcal{L}_{\text {ots\$-rand }}^{\Sigma}\).In other words, the scheme does not satisfy this uniform ciphertexts property.

So far we have two security definitions. Does this encryption scheme satisfy one but not the other?

Claim 2.10 Construction \(2.8\) does not satisfy one-time secrecy (Definition 2.6).

Proof This claim refers to a different security definition, which involves two different libraries. When we plug in the details of Construction \(2.8\) into the libraries of Definition \(2.6\), we get the following:

Now we need to write a calling program that behaves differently in the presence of these two libraries. We can use the same overall idea as last time, but not the same actual calling program, since these libraries provide a different interface. In this example, the calling program needs to call the EAVESDROP subroutine which takes \(t\) wo arguments \(m_{L}\) and \(m_{R}\) How should the calling program choose \(m_{L}\) and \(m_{R}\) ? Which two plaintexts have different looking ciphertexts?

A good approach is to choose \(m_{L}\) to be all zeroes and \(m_{R}\) to be all ones. We know from before that an all-zeroes plaintext always encrypts to an all-zeroes ciphertext, so the calling program can check for that condition. More formally, we can define the calling program:

Next, we need to compute its output probabilities in the presence of the two libraries.

When \(\mathcal{A}\) is linked to \(\mathcal{L}_{\text {ots- }}, \underline{c}, \mathrm{is}\) computed as an encryption of \(m_{L}=\) \(0^{\lambda}\). No matter what \(k\) is, the result is always all-zeroes. So,

When \(\mathcal{A}\) is linked to \(\mathcal{L}_{\text {ots-R }}, c\) is computed as an encryption of \(m_{R}=\) \(1^{\lambda}\). In other words, \(c:=k \& 1^{\lambda}\). But the bitwise-AND of any string \(k\) with all 1s is just \(k\) itself. So \(c\) is just equal to \(k\), which was chosen uniformly at random. The probability that a uniformly random \(c\) happens to be all-zeroes is \[\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {ots-R }} \Rightarrow \text { true }\right]=1 / 2^{\lambda}\] Since these two probabilities are different, \(\mathcal{L}_{\text {ots-L }}^{\Sigma} \not \equiv \mathcal{L}_{\text {ots-R }}^{\Sigma}\) and the scheme does not have one-time secrecy.

Chaining Several Components

Before getting to a security proof, we introduce a convenient lemma. Consider a compound program like \(\mathcal{A} \diamond \mathcal{L}_{1} \diamond \mathcal{L}_{2}\). Our convention is that subroutine calls only happen from left to right across the \(\diamond\) symbol, so in this example, \(\mathcal{L}_{1}\) can make calls to subroutines in \(\mathcal{L}_{2}\), but not vice-versa. Depending on the context, it can sometimes be convenient to interpret \(\mathcal{A} \diamond \mathcal{L}_{1} \diamond \mathcal{L}_{2}\) as:

• \(\left(\mathcal{A} \diamond \mathcal{L}_{1}\right) \diamond \mathcal{L}_{2}\) : a compound calling program linked to \(\mathcal{L}_{2}\). After all, \(\mathcal{A} \diamond \mathcal{L}_{1}\) is a program that makes calls to the interface of \(\mathcal{L}_{2}\).

or: \(\mathcal{A} \diamond\left(\mathcal{L}_{1} \diamond \mathcal{L}_{2}\right): \mathcal{A}\) linked to a compound library. After all, \(\mathcal{A}\) is a program that makes calls to the interface of \(\left(\mathcal{L}_{1} \diamond \mathcal{L}_{2}\right)\)

The placement of the parentheses does not affect the functionality of the overall program, just like how splitting up a real program into different source files doesn’t affect its functionality. In fact, every security proof in this book will have some intermediate steps that involve compound libraries. We will make heavy use of the following helpful result:

Lemma 2.11 If \(\mathcal{L}_{\text {left }} \equiv \mathcal{L}_{\text {right }}\) then, for any library \(\mathcal{L}^{*}\), we have \(\mathcal{L}^{*} \diamond \mathcal{L}_{\text {left }} \equiv \mathcal{L}^{*} \diamond \mathcal{L}_{\text {right }}\).

(Chaining)

Proof Note that we are comparing \(\mathcal{L}^{*} \diamond \mathcal{L}_{\text {left }}\) and \(\mathcal{L}^{*} \diamond \mathcal{L}_{\text {right }}\) as compound libraries. Hence we consider a calling program \(\mathcal{A}\) that is linked to either \(\mathcal{L}^{*} \diamond \mathcal{L}_{\text {left }}\) or \(\mathcal{L}^{*} \diamond \mathcal{L}_{\text {right }}\).

Let \(\mathcal{A}\) be such an arbitrary calling program. We must show that \(\mathcal{A} \diamond\left(\mathcal{L}^{*} \diamond \mathcal{L}_{\text {left }}\right)\) and \(\mathcal{A} \diamond\left(\mathcal{L}^{*} \diamond \mathcal{L}_{\text {right }}\right)\) have identical output distributions. As mentioned above, we can interpret \(\mathcal{A} \diamond \mathcal{L}^{*} \diamond \mathcal{L}_{\text {left }}\) as a calling program \(\mathcal{A}\) linked to the library \(\mathcal{L}^{*} \diamond \mathcal{L}_{\text {left }}\), but also as a calling program \(\mathcal{A} \diamond \mathcal{L}^{*}\) linked to the library \(\mathcal{L}_{\text {left. }}\). Since \(\mathcal{L}_{\text {left }} \equiv \mathcal{L}_{\text {right, }}\), swapping \(\mathcal{L}_{\text {left for }} \mathcal{L}_{\text {right }}\) has no effect on the output of any calling program. In particular, it has no effect when the calling program happens to be the compound program \(\mathcal{A} \diamond \mathcal{L}^{*}\). Hence we have:

Since \(\mathcal{A}\) was arbitrary, we have proved the lemma.

An Example Hybrid Proof

In this section we will prove something about the following scheme, which encrypts twice with OTP, using independent keys:

Construction \(2.12\)

("Double OTP")

It would not be too hard to directly show that ciphertexts in this scheme are uniformly distributed, as we did for plain OTP. However, the new hybrid technique will allow us to leverage what we already know about OTP in an elegant way, and avoid any probability calculations.

Claim 2.13 Construction 2.12 has one-time uniform ciphertexts (Definition 2.6).

Proof In terms of libraries, we must show that:

l \(\mathcal{L}_{\text {ots } \$ \text {-rand }}^{\Sigma}\)
\(\operatorname{ctXT}(m)\) return \(c\)

\[\begin{aligned} & \operatorname{Pr}\left[\mathcal{A} \diamond\left(\mathcal{L}^{*} \diamond \mathcal{L}_{\text {left }}\right) \Rightarrow \text { true }\right]=\operatorname{Pr}\left[\left(\mathcal{A} \diamond \mathcal{L}^{*}\right) \diamond \mathcal{L}_{\text {left }} \Rightarrow \text { true }\right] \quad \text { (change of perspective) } \\ & =\operatorname{Pr}\left[\left(\mathcal{A} \diamond \mathcal{L}^{*}\right) \diamond \mathcal{L}_{\text {right }} \Rightarrow \text { true }\right] \quad\left(\text { since } \mathcal{L}_{\text {left }} \equiv \mathcal{L}_{\text {right }}\right. \text { ) } \\ & =\operatorname{Pr}\left[\mathcal{A} \diamond\left(\mathcal{L}^{*} \diamond \mathcal{L}_{\text {right }}\right) \Rightarrow \text { true }\right] \text {. (change of perspective) } \end{aligned}\] Instead of directly comparing these two libraries, we will introduce some additional libraries \(\mathcal{L}_{\text {hyb }-1}, \mathcal{L}_{\text {hyb-2 }}, \mathcal{L}_{\text {hyb-3 }}\), and show that: \[\mathcal{L}_{\text {ots\$-real }}^{\Sigma} \equiv \mathcal{L}_{\text {hyb-1 }} \equiv \mathcal{L}_{\text {hyb-2 }} \equiv \mathcal{L}_{\text {hyb-3 }} \equiv \mathcal{L}_{\text {ots\$-rand }}^{\Sigma}\] Since the \(\equiv\) symbol is transitive, this will achieve our goal.

The intermediate libraries are called hybrids, since they will contain a mix of characteristics from the two "endpoints" of this sequence. These hybrids are chosen so that it is very easy to show that consecutive libraries in this sequence are interchangeable. The particular hybrids we have in mind here are:

Next, we provide a justification for each "

UTF8mj三

" in the expression above. For each pair of adjacent libraries, we highlight their differences below:

The only difference between these two libraries is that the highlighted expressions have been factored out into a separate subroutine, and some variables have been renamed. In both libraries, \(c_{2}\) is chosen as the xOR of \(c_{1}\) and a uniformly chosen string. These differences make no effect on the calling program. Importantly, the subroutine that we have factored out is exactly the one in the \(\mathcal{L}_{\text {otp-real }}\) library (apart from renaming the subroutine).

Claim 2.7 says that \(\mathcal{L}_{\text {otp-real }} \equiv \mathcal{L}_{\text {otp-rand }}\), so Lemma \(2.11\) says that we can replace an instance of \(\mathcal{L}_{\text {otp-real }}\) in a compound library with \(\mathcal{L}_{\text {otp-rand, as we have done here. This change will }}\) have no effect on the calling program.

The only difference between these two libraries is that a subroutine call has been inlined. This difference has no effect on the calling program.

The only difference between these two libraries is that the two highlighted lines have been removed. But it should be clear that these lines have no effect: \(k_{1}\) is used only to compute \(c_{1}\), which is never used again. Hence, this difference has no effect on the calling program.

The final hybrid is exactly \(\mathcal{L}_{\text {ots\$-rand }}^{\Sigma}\) (although with a variable name changed). We have shown that \(\mathcal{L}_{\text {ots\$-rand }}^{\Sigma} \equiv \mathcal{L}_{\text {ots\$-real }}^{\Sigma}\), meaning that this encryption scheme has one-time uniform ciphertexts.

Summary of the Hybrid Technique

We have now seen our first example of the hybrid technique for security proofs. All security proofs in this book use this technique.

• Proving security means showing that two particular libraries, say \(\mathcal{L}_{\text {left }}\) and \(\mathcal{L}_{\text {right }}\), are interchangeable.
• Often \(\mathcal{L}_{\text {left and }} \mathcal{L}_{\text {right }}\) are significantly different, making them hard to compare directly. To make the comparison more manageable, we can show a sequence of hybrid libraries, beginning with \(\mathcal{L}_{\text {left }}\) and ending with \(\mathcal{L}_{\text {right }}\). The idea is to break up the large "gap" between \(\mathcal{L}_{\text {left }}\) and \(\mathcal{L}_{\text {right }}\) into smaller ones that are easier to justify.
• It is helpful to think of "starting" at \(\mathcal{L}_{\text {left, }}\) and then making a sequence of small modifications to it, with the goal of eventually reaching \(\mathcal{L}_{\text {right. }}\). You must justify why each modification doesn’t affect the calling program (i.e., why the two libraries before/after your modification are interchangeable).
• As discussed in Section 2.2, simple things like inlining/factoring out subroutines, changing unused variables, changing unreachable statements, or unrolling loops are always "allowable" modifications in a hybrid proof since they have no effect on the calling program. As we progress in the course, we will see more kinds of useful modifications.

A Contrasting Example

Usually the boundary between secure and insecure is razor thin. Let’s make a small change to the previous encryption scheme to illustrate this point. Instead of applying OTP to the plaintext twice, with independent keys, what would happen if we use the same key?

Construction \(2.14\) \((" \mathrm{dOuB} \ell \exists \mathrm{OTP})\)

You probably noticed that the ciphertext \(c_{2}\) is computed as \(c_{2}:=k \oplus(k \oplus m)\), which is just a fancy way of saying \(c_{2}:=m\). There is certainly no way this kind of "double-OTP" is secure.

For educational purposes, let’s try to repeat the steps of our previous security proof on this (insecure) scheme and see where things break down. If we wanted to show that Construction \(2.14\) has uniform ciphertexts, we would have to show that the following two libraries are interchangeable:

\(\stackrel{?}{\equiv} \quad \frac{\mathcal{L}_{\text {ots } \$ \text {-rand }}^{\Sigma}}{}\)

In the previous hybrid proof, the first step was to factor out the statements " \(k_{2} \leftarrow\{0,1\}^{\lambda}\); \(c_{2}:=k_{2} \oplus c_{1} "\) into a separate subroutine, so we could argue that the result of \(c_{2}\) was uniformly distributed. If we do something analogous with this example, we get:

Do you see the problem? In " \(\mathcal{L}_{\mathrm{hyb}}\) ", we have tried to move the variable \(k\) into \(\mathcal{L}_{\text {otp-real }}\). Since this scope is private, every operation we want to do with \(k\) has to be provided by its container library \(\mathcal{L}_{\text {otp-real }}\). But there is a mismatch: \(\mathcal{L}_{\text {otp-real }}\) only gives us a way to use \(k\) in one XOR expression, whereas we need to use the same \(k\) in two XOR expressions to match the behavior of \(\mathcal{L}_{\text {ots\$-real }}\). The compound library \(\mathcal{L}_{\text {hyb }}\) has an unresolved reference to \(k\) in the line " \(c_{1}:=k \oplus m\)," and therefore doesn’t have the same behavior as \(\mathcal{L}_{\text {ots\$-real. }}{ }^{4}\) This is the step of the security proof that breaks down.

Here’s a more conceptual way to understand what went wrong here. The important property of OTP is that its ciphertexts look uniform when the key is used to encrypt only one plaintext. This "double OTP" variant uses OTP in a way that doesn’t fulfill that condition, and therefore provides no security guarantee. The previous (successful) proof was able to factor out some XOR’s in terms of \(\mathcal{L}_{\text {otp-real without breaking anything, and that's how we }}\) know the scheme was using OTP in a way that is consistent with its security guarantee.

As you can hopefully see, the process of a security proof provides a way to catch these kinds of problems. It is very common in a hybrid proof to factor out some statements in terms of a library from some other security definition. This step can only be done successfully if the underlying cryptography is being used in an appropriate way.

One Security Definition Implies Another

One way to compare/contrast two security definitions is to prove that one implies the other. In other words, if an encryption scheme satisfies definition #1, then it also satisfies definition #2.

Theorem 2.15 If an encryption scheme \(\sum\) has one-time uniform ciphertexts (Definition 2.5), then \(\sum\) also has one-time secrecy (Definition 2.6). In other words: \[\mathcal{L}_{\text {ots\$-real }}^{\Sigma} \equiv \mathcal{L}_{\text {ots\$-rand }}^{\Sigma} \Longrightarrow \mathcal{L}_{\text {ots-L }}^{\Sigma} \equiv \mathcal{L}_{\text {ots-R }}^{\Sigma}\] If you are comfortable with what all the terminology means, then the meaning of this statement is quite simple and unsurprising. "If all plaintexts \(m\) induce a uniform distribution of ciphertexts, then all \(m\) induce the same distribution of ciphertexts."

This fairly straight-forward statement can be proven formally, giving us another example of the hybrid proof technique:

Proof We are proving an if-then statement. We want to show that the "then"-part of the statement is true; that is, \(\mathcal{L}_{\text {ots-L }}^{\Sigma} \equiv \mathcal{L}_{\text {ots-R" }}^{\Sigma}\).We are allowed to use the fact that the "if"-part is true; that is, \(\mathcal{L}_{\text {ots\$-real }}^{\Sigma} \equiv \mathcal{L}_{\text {ots\$-rand }}^{\Sigma}\)

\({ }^{4}\) I would say that the library "doesn’t compile" due to a scope/reference error. The proof uses the hybrid technique. We will start with the library \(\mathcal{L}_{\text {ots-L, }}\) and make a small sequence of justifiable changes to it, until finally reaching \(\mathcal{L}_{\text {ots-R. Along the way, we }}\) can use the fact that \(\mathcal{L}_{\text {ots\$-real }} \equiv \mathcal{L}_{\text {ots\$-rand. This suggests some "strategy" for the proof: if }}\) we can somehow get \(\mathcal{L}_{\text {ots\$-real }}\) to appear as a component in one of the hybrid libraries, then we can replace it with \(\mathcal{L}_{\text {ots\$-rand }}\) (or vice-versa), in a way that hopefully makes progress towards our goal of transforming \(\mathcal{L}_{\text {ots-L }}\) to \(\mathcal{L}_{\text {ots-R. }}\)

Below we list the sequence of hybrid libraries, and justify why each one is interchangeable with the previous library.

The starting point of our hybrid sequence is \(\mathcal{L}_{\text {ots-L }}^{\Sigma}\)

Factoring out a block of statements into a

subroutine makes it possible to write the library as a compound one, but does not affect its external behavior. Note that the new subroutine is exactly the \(\mathcal{L}_{\text {ots\$-real }}^{\Sigma}\) library from Definition 2.5. This was a strategic choice, because of what happens next.

\(\mathcal{L}_{\text {ots\$-real }}^{\Sigma}\) has been replaced with \(\mathcal{L}_{\text {ots\$-rand }}\) Lemma \(2.11\) says that this change has no effect on the library’s behavior, since the two \(\mathcal{L}_{\text {ots\$- } \star}\) libraries are interchangeable.

The argument to стхт has been changed from \(m_{L}\) to \(m_{R}\). This has no effect on the library’s behavior since ctXT does not actually use its argument in these hybrids!

The previous transition is the most important one in the proof, as it gives insight into how we came up with this particular sequence of hybrids. Looking at the desired endpoints of our sequence of hybrids \(-\mathcal{L}_{\text {ots-L }}^{\Sigma}\) and \(\mathcal{L}_{\text {ots-R }}^{\Sigma}-\) we see that they differ only in swapping \(m_{L}\) for \(m_{R}\). If we are not comfortable eyeballing things, we’d like a better justification for why it is "safe" to exchange \(m_{L}\) for \(m_{R}\) (i.e., why it has no effect on the calling program). However, the uniform ciphertexts property shows that \(\mathcal{L}_{\text {ots-L }}^{\Sigma}\) in fact has the same behavior as a library \(\mathcal{L}_{\text {hyb-2 }}\) that doesn’t use either of \(m_{L}\) or \(m_{R}\). In a program that doesn’t use \(m_{L}\) or \(m_{R}\), it is clear that we can switch them! Having made this crucial change, we can now perform the same sequence of steps, but in reverse.

|l|
\(\frac{\operatorname{CTXT}(m):}{k \leftarrow \Sigma . \operatorname{KeyGen}}\)
\(c \leftarrow \Sigma . \operatorname{Enc}(k, m)\)
return \(c\)

\(\mathcal{L}_{\text {ots\$-rand }}^{\Sigma}\) has been replaced with \(\mathcal{L}_{\text {ots\$-real }}^{\Sigma} .\) This is another application of the chaining lemma.

A subroutine call has been inlined, which has no effect on the library’s behavior. The result is exactly \(\mathcal{L}_{\text {ots-R }}^{\Sigma}\)

Putting everything together, we showed that \(\mathcal{L}_{\text {ots- }}^{\Sigma} \equiv \mathcal{L}_{\text {hyb-1 }} \equiv \cdots \equiv \mathcal{L}_{\text {hyb-4 }} \equiv \mathcal{L}_{\text {ots-R }}\). This completes the proof, and we conclude that \(\sum\) satisfies the definition of one-time secrecy.

One Security Definition Doesn’t Imply Another

Another way we might compare security definitions is to identify any schemes that satisfy one definition without satisfying the other. This helps us understand the boundaries and "edge cases" of the definition.

A word of warning: If we have two security definitions that both capture our intuitions rather well, then any scheme which satisfies one definition and not the other is bound to appear unnatural and contrived. The point is to gain more understanding of the security definitions themselves, and unnatural/contrived schemes are just a means to do that.

Theorem \(2.16\) There is an encryption scheme that satisfies one-time secrecy (Definition 2.6) but not one-time uniform ciphertexts (Definition 2.5). In other words, one-time secrecy does not necessarily imply one-time uniform ciphertexts.

Proof One such encryption scheme is given below:

This scheme is just OTP with the bits 00 added to every ciphertext. The following facts about the scheme should be believable (and the exercises encourage you to prove them formally if you would like more practice at that sort of thing):

• This scheme satisfies one-time one-time secrecy, meaning that encryptions of \(m_{L}\) are distributed identically to encryptions of \(m_{R}\), for any \(m_{L}\) and \(m_{R}\) of the attacker’s choice. We can characterize the ciphertext distribution in both cases as " \(\lambda\) uniform bits followed by 00 ." Think about how you might use the hybrid proof technique to formally prove that this scheme satisfies one-time secrecy!
• This scheme does not satisfy the one-time uniform ciphertexts property. Its ciphertexts always end with 00 , whereas uniform strings end with 00 with probability 1/4. Think about how you might formallize this observation as a calling program / distinguisher for the relevant two libraries!

You might be thinking, surely this can be fixed by redefining the ciphertext space as \(C\) as the set of \(\lambda+2\)-bit strings whose last two bits are 00 . This is a clever idea, and indeed it would work. If we change the definition of the ciphertext space \(C\) following this suggestion, then the scheme would satisfy the uniform ciphertexts property (this is because the \(\mathcal{L}_{\text {ots\$-rand }}\) library samples uniformly from whatever \(C\) is specified as part of the encryption scheme).

But this observation raises an interesting point. Isn’t it weird that security hinges on how narrowly you define the set \(C\) of ciphertexts, when \(C\) really has no effect on the functionality of encryption? Again, no one really cares about this contrived "OTP + 00 " encryption scheme. The point is to illuminate interesting edge cases in the security definition itself!

Secret Sharing

DNS is the system that maps human-memorable Internet domains like irs.gov to machine-readable IP addresses like \(166.123 .218 .220\). If an attacker can masquerade as the DNS system and convince your computer that irs.gov actually resides at some other IP address, it might result in a bad day for you.

To protect against these kinds of attacks, a replacement called DNSSEC has been proposed. DNSSEC uses cryptography to make it impossible to falsify a domain-name mapping. The cryptography required to authenticate DNS mappings is certainly interesting, but an even more fundamental question remains: Who can be trusted with the master cryptographic keys to the system? The non-profit organization in charge of these kinds of things (ICANN) has chosen the following system. The master key is split into 7 pieces and distributed on smart cards to 7 geographically diverse people, who keep them in safe-deposit boxes.

At least five key-holding members of this fellowship would have to meet at a secure data center in the United States to reboot [DNSSEC] in case of a very unlikely system collapse.

"If you round up five of these guys, they can decrypt [the root key] should the West Coast fall in the water and the East Coast get hit by a nuclear bomb," [said] Richard Lamb, program manager for DNSSEC at ICANN. \({ }^{1}\)

How is it possible that any 5 out of the 7 key-holders can reconstruct the master key, but (presumably) 4 out of the 7 cannot? The solution lies in a cryptographic tool called a secret-sharing scheme, the topic of this chapter.

Security Definition

We’d like a security guarantee that says something like:

if you know only an unauthorized set of shares, then you learn no information about the choice of secret message.

To translate this informal statement into a formal security definition, we define two libraries that allow the calling program to learn a set of shares (for an unauthorized set), and that differ only in which secret is shared. If the two libraries are interchangeable, then we conclude that seeing an unauthorized set of shares leaks no information about the choice of secret message. The definition looks like this:

Definition 3.3 Let \(\sum\) be a threshold secret-sharing scheme. We say that \(\sum\) is secure if \(\mathcal{L}_{\mathrm{tsss}-\mathrm{L}}^{\Sigma} \equiv \mathcal{L}_{\mathrm{tsss}-\mathrm{R}}^{\Sigma}\), where:

(TSSS security)

In an attempt to keep the notation uncluttered, we have not written the type of the argument \(U\), which is \(U \subseteq\{1, \ldots, \Sigma . n\}\)

Discussion & Pitfalls

• Similar to the definition of one-time secrecy of encryption, we let the calling program choose the two secret messages that will be shared. As before, this models an attack scenario in which the adversary has partial knowledge or influence on the secret \(m\) being shared.
• The calling program also chooses the set \(U\) of users’ shares to obtain. The libraries make it impossible for the calling program to obtain the shares of an authorized set (returning err in that case). This does not mean that a user is never allowed to distribute an authorized number of shares (this would be strange indeed, since it would make any future reconstruction impossible). It just means that we want a security definition that says something about an attacker who sees only an unauthorized set of shares, so we formalize security in terms of libraries with this restriction.
• Consider a 6-out-of-10 threshold secret-sharing scheme. With the libraries above, the calling program can receive the shares of users \(\{1, \ldots, 5\}\) (an unauthorized set) in one call to SHARE, and then receive the shares of users \(\{6, \ldots, 10\}\) in another call. It might seem like the calling program can then combine these shares to reconstruct the secret (if the same message was shared in both calls). However, this is not the case because these two sets of shares came from two independent executions of the Share algorithm. Shares generated by one call to Share should not be expected to function with shares generated by another call, even if both calls to Share used the same secret message.
• Recall that in our style of defining security using libraries, it is only the internal differences between the libraries that must be hidden. Anything that is the same between the two libraries need not be hidden. One thing that is the same for the two libraries here is the fact that they output the shares belonging to the same set of users \(U\). This security definition does not require shares to hide which user they belong to. Indeed, you can modify a secret-sharing scheme so that each user’s identity is appended to his/her corresponding share, and the result would still satisfy the security definition above.
• Just like the encryption definition does not address the problem of key distribution, the secret-sharing definition does not address the problem of who should run the Share algorithm (if its input \(m\) is so secret that it cannot be entrusted to any single person), or how the shares should be delivered to the \(n\) different users. Those concerns are considered out of scope by the problem of secret-sharing (although we later discuss clever approaches to the first problem). Rather, the focus is simply on whether it is even possible to encode data in such a way that an unauthorized set of shares gives no information about the secret, while any authorized set completely reveals the secret.

An Insecure Approach

One way to understand the security of secret sharing is to see an example of an "obvious" but insecure approach for secret sharing, and study why it is insecure. Let’s consider a 5-out-of- 5 secret-sharing scheme. This means we want to split a secret into 5 pieces so that any 4 of the pieces leak nothing. One way you might think to do this is to literally chop up the secret into 5 pieces. For example, if the secret is 500 bits, you might give the first 100 bits to user 1 , the second 100 bits to user 2 , and so on.

Construction \(3.4\) (Insecure TSSS)

It is true that the secret can be constructed by concatenating all 5 shares, and so this construction satisfies the correctness property. (The only authorized set is the set of all 5 users, so we write Reconstruct to expect all 5 shares.)

However, the scheme is insecure (as promised). Suppose you have even just 1 share. It is true that you don’t know the secret in its entirety, but the security definition (for 5out-of- 5 secret sharing) demands that a single share reveals nothing about the secret. Of course knowing 100 bits of something is not the same as than knowing nothing about it.

We can leverage this observation to make a more formal attack on the scheme, in the form of a distinguisher between the two \(\mathcal{L}_{\mathrm{tsss}-\star}\) libraries. As an extreme case, we can distinguish between shares of an all- \(-\) secret and shares of an all- 1 secret:

Let’s link this calling program to both of the \(\mathcal{L}_{\mathrm{tsss}-\star}\) libraries and see what happens:

When \(\mathcal{A}\) is linked to \(\mathcal{L}_{\mathrm{tsss}-\mathrm{L}}\), it receives a share of \(0^{500}\), which will itself be a string of all zeroes. In this case, \(\mathcal{A}\) outputs 1 with probability \(1 .\)

When \(\mathcal{A}\) is linked to \(\mathcal{L}_{\mathrm{tsss}-\mathrm{R}, \text { it }}\) receives a share of \(1^{500}\) which will be a string of all ones. In this case, \(\mathcal{A}\) outputs 1 with probability \(0 .\)

We have constructed a calling program which behaves very differently (indeed, as differently as possible) in the presence of the two libraries. Hence, this secret-sharing scheme is not secure.

Hopefully this example demonstrates one of the main challenges (and amazing things) about secret-sharing schemes. It is easy to reveal information about the secret gradually as more shares are obtained, like in this insecure example. However, the security definition of secret sharing is that the shares must leak absolutely no information about the secret, until the number of shares passes the threshold value.

\(3.2\) A Simple 2-out-of-2 Scheme

Believe it or not, we have already seen a simple secret-sharing scheme! In fact, it might even be best to think of one-time pad as the simplest secret-sharing scheme.

Construction \(3.5\) (2-out-of-2 TSSS)

Since it’s a 2-out-of-2 scheme, the only authorized set of users is \(\{1,2\}\), so Reconstruct is written to expect both shares \(s_{1}\) and \(s_{2}\) as its inputs. Correctness follows easily from what we’ve already learned about the properties of XOR.

Example If we want to share the string \(m=1101010001\) then the Share algorithm might choose \[\begin{aligned} s_{1} &:=0110000011 \\ s_{2} &:=s_{1} \oplus m \\ &=0110000011 \oplus 1101010001=1011010010 \end{aligned}\] Then the secret can be reconstructed by XORing the two shares together, via: \[s_{1} \oplus s_{2}=0110000011 \oplus 1011010010=1101010001=m .\] Remember that this example shows just one possible execution of Share(1101010001), but Share is a randomized algorithm and many other values of \(\left(s_{1}, s_{2}\right)\) are possible.

Theorem 3.6 Construction \(3.5\) is a secure 2-out-of-2 threshold secret-sharing scheme.

Proof Let \(\Sigma\) denote Construction 3.5. We will show that \(\mathcal{L}_{\mathrm{tsss}-\mathrm{L}}^{\Sigma} \equiv \mathcal{L}_{\mathrm{tsss}-\mathrm{R}}^{\Sigma}\) using a hybrid proof.

As usual, the starting point is \(\mathcal{L}_{\mathrm{tsss}-\mathrm{L}}^{\Sigma}\), shown here with the details of the secret-sharing scheme filled in (and the types of the subroutine ar guments omitted to reduce clutter).

\(\operatorname{SHARE}\left(m_{L}, m_{R}, U\right)\)

if \(|U| \geqslant 2:\) return err

if \(U=\{1\}\) :

\(s_{1} \leftarrow\{0,1\}^{\ell}\)

\(s_{2}:=s_{1} \oplus m_{R}\)

return \(\left\{s_{1}\right\}\)

elsif \(U=\{2\}\) :

\(s_{1} \leftarrow\{0,1\}^{\ell}\)

\(s_{2}:=s_{1} \oplus m_{L}\)

return \(\left\{s_{2}\right\}\)

else return \(\emptyset\)

It has no effect on the library’s behavior if we duplicate the main body of the library into 3 branches of a new if-statement. The reason for doing so is that the scheme generates \(s_{1}\) and \(s_{2}\) differently. This means that our proof will eventually handle the 3 different unauthorized sets \((\{1\},\{2\}\), and \(\emptyset\) ) in fundamentally different ways.

The definition of \(s_{2}\) has been changed in the first if-branch. This has no effect on the library’s behavior since \(s_{2}\) is never actually used in this branch.

Recognizing the second branch of the if-statement as a one-time pad encryption (of \(m_{L}\) under key \(s_{1}\) ), we factor out the generation of \(s_{2}\) in terms of the library \(\mathcal{L}_{\text {ots-L }}^{\text {OTP }}\) from the one-time secrecy definition. This has no effect on the library’s behavior. Importantly, the subroutine in \(\mathcal{L}_{\text {ots-L }}^{\text {OTP }}\) expects two arguments, so that is what we must pass. We choose to pass \(m_{L}\) and \(m_{R}\) for reasons that should become clear very soon.

We have replaced \(\mathcal{L}_{\text {ots-L }}^{\text {OTP }}\) with \(\mathcal{L}_{\text {ots-R }}^{\text {OTP }}\). From the one-time secrecy of one-time pad (and the composition lemma), this change has no effect on the library’s behavior. SHARE \(\left(m_{L}, m_{R}, U\right)\) : if \(|U| \geqslant 2:\) return err if \(U=\{1\}\) :

\(s_{1} \leftarrow\{0,1\}^{\ell}\) \(s_{2}:=s_{1} \oplus m_{R}\) \(\operatorname{return}\left\{s_{1}\right\}\)

elsif \(U=\{2\}\) :

\(s_{1} \leftarrow\{0,1\}^{\ell}\)

\(s_{2}:=s_{1} \oplus m_{R}\) return \(\left\{s_{2}\right\}\)

else return \(\emptyset\) A subroutine has been inlined; no effect on the library’s behavior. \(\mathcal{L}_{\text {tsss-R }}^{\Sigma}\)

\(\operatorname{SHARE}\left(m_{L}, m_{R}, U\right)\) :

if \(|U| \geqslant 2:\) return err

\(s_{1} \leftarrow\{0,1\}^{\ell}\)

\(s_{2}:=s_{1} \oplus m_{R}\) \(\operatorname{return}\left\{s_{i} \mid i \in U\right\}\) The code has been simplified. Specifically, the branches of the if-statement can all be unified, with no effect on the library’s behavior. The result is \(\mathcal{L}_{\text {tsss-R }}^{\Sigma}\).

We showed that \(\mathcal{L}_{\mathrm{tsss}-\mathrm{L}}^{\Sigma} \equiv \mathcal{L}_{\text {hyb-1 }} \equiv \cdots \equiv \mathcal{L}_{\text {hyb-5 }} \equiv \mathcal{L}_{\mathrm{tsss}-\mathrm{R}}^{\Sigma}\), and so the secret-sharing scheme is secure.

We in fact proved a slightly more general statement. The only property of one-time pad we used was its one-time secrecy. Substituting one-time pad for any other one-time secret encryption scheme would still allow the same proof to go through. So we actually proved the following:

Theorem 3.7 If \(\sum\) is an encryption scheme with one-time secrecy, then the following 2-out-of-2 threshold secret-sharing scheme \(\mathcal{S}\) is secure:

Polynomials Over the Reals

Theorem \(3.8\) Let \(\left\{\left(x_{1}, y_{1}\right), \ldots,\left(x_{d+1}, y_{d+1}\right)\right\} \subseteq \mathbb{R}^{2}\) be a set of points whose \(x_{i}\) values are all distinct. Then (Poly Interpolation) there is a unique degree-d polynomial \(f\) with real coefficients that satisfies \(y_{i}=f\left(x_{i}\right)\) for all \(i .\)

Proof To start, consider the following polynomial: \[\ell_{1}(\boldsymbol{x})=\frac{\left(\boldsymbol{x}-x_{2}\right)\left(\boldsymbol{x}-x_{3}\right) \cdots\left(\boldsymbol{x}-x_{d+1}\right)}{\left(x_{1}-x_{2}\right)\left(x_{1}-x_{3}\right) \cdots\left(x_{1}-x_{d+1}\right)}\] The notation is potentially confusing. \(\ell_{1}\) is a polynomial with formal variable \(\boldsymbol{x}\) (written in bold). The non-bold \(x_{i}\) values are just plain numbers (scalars), given in the theorem statement. Therefore the numerator in \(\ell_{1}\) is a degree- \(d\) polynomial in \(\boldsymbol{x}\). The denominator is just a scalar, and since all of the \(x_{i}\) ’s are distinct, we are not dividing by zero. Overall, \(\ell_{1}\) is a degree- \(d\) polynomial.

What happens when we evaluate \(\ell_{1}\) at one of the special \(x_{i}\) values?

• Evaluating \(\ell_{1}\left(x_{1}\right)\) makes the numerator and denominator the same, so \(\ell_{1}\left(x_{1}\right)=1\).

Evaluating \(\ell_{1}\left(x_{i}\right)\) for \(i \neq 1\) leads to a term \(\left(x_{i}-x_{i}\right)\) in the numerator, so \(\ell_{1}\left(x_{i}\right)=0\).

Of course, \(\ell_{1}\) can be evaluated at any point (not just the special points \(x_{1}, \ldots, x_{d+1}\) ), but we don’t care about what happens in those cases.

We can similarly define other polynomials \(\ell_{j}\) : \[\ell_{j}(\boldsymbol{x})=\frac{\left(\boldsymbol{x}-x_{1}\right) \cdots\left(\boldsymbol{x}-x_{j-1}\right)\left(\boldsymbol{x}-x_{j+1}\right) \cdots\left(\boldsymbol{x}-x_{d+1}\right)}{\left(x_{j}-x_{1}\right) \cdots\left(x_{j}-x_{j-1}\right)\left(x_{j}-x_{j+1}\right) \cdots\left(x_{j}-x_{d+1}\right)}\] The pattern is that the numerator is "missing" the term \(\left(\boldsymbol{x}-x_{j}\right)\) and the denominator is missing the term \(\left(x_{j}-x_{j}\right)\), because we don’t want a zero in the denominator. Polynomials of this kind are called LaGrange polynomials. They are each degree- \(d\) polynomials, and they satisfy the property: \[\ell_{j}\left(x_{i}\right)= \begin{cases}1 & \text { if } i=j \\ 0 & \text { if } i \neq j\end{cases}\] Now consider the following polynomial: \[f(\boldsymbol{x})=y_{1} \ell_{1}(\boldsymbol{x})+y_{2} \ell_{2}(\boldsymbol{x})+\cdots+y_{d+1} \ell_{d+1}(\boldsymbol{x})\] Note that \(f\) is a degree- \(d\) polynomial since it is the sum of degree-d polynomials (again, the \(y_{i}\) values are just scalars)

What happens when we evaluate \(f\) on one of the special \(x_{i}\) values? Since \(\ell_{i}\left(x_{i}\right)=1\) and \(\ell_{j}\left(x_{i}\right)=0\) for \(j \neq i\), we get: \[\begin{aligned} f\left(x_{i}\right) &=y_{1} \ell_{1}\left(x_{i}\right)+\cdots+y_{i} \ell_{i}\left(x_{i}\right)+\cdots+y_{d+1} \ell_{d+1}\left(x_{i}\right) \\ &=y_{1} \cdot 0+\cdots+y_{i} \cdot 1+\cdots+y_{d+1} \cdot 0 \\ &=y_{i} \end{aligned}\] So \(f\left(x_{i}\right)=y_{i}\) for every \(x_{i}\), which is what we wanted. This shows that there is some degree- \(d\) polynomial with this property.

Now let’s argue that this \(f\) is unique. Suppose there are two degree- \(d\) polynomials \(f\) and \(f^{\prime}\) such that \(f\left(x_{i}\right)=f^{\prime}\left(x_{i}\right)=y_{i}\) for \(i \in\{1, \ldots, d+1\}\). Then the polynomial \(g(\boldsymbol{x})=f(\boldsymbol{x})-f^{\prime}(\boldsymbol{x})\) also is degree- \(d\), and it satisfies \(g\left(x_{i}\right)=0\) for all \(i\). In other words, each \(x_{i}\) is a root of \(g\), so \(g\) has at least \(d+1\) roots. But the only degree-d polynomial with \(d+1\) roots is the identically-zero polynomial \(g(\boldsymbol{x})=0\). If \(g(\boldsymbol{x})=0\) then \(f=f^{\prime}\). In other words, any degree- \(d\) polynomial \(f^{\prime}\) that satisfies \(f^{\prime}\left(x_{i}\right)=y_{i}\) must be equal to \(f\). So \(f\) is the unique polynomial with this property.

Example Let’s figure out the degree-3 polynomial that passes through the points \((3,1),(4,1),(5,9),(2,6)\)

First, let’s construct the appropriate LaGrange polynomials: \[\begin{aligned} &\ell_{1}(\boldsymbol{x})=\frac{\left(\boldsymbol{x}-x_{2}\right)\left(\boldsymbol{x}-x_{3}\right)\left(\boldsymbol{x}-x_{4}\right)}{\left(x_{1}-x_{2}\right)\left(x_{1}-x_{3}\right)\left(x_{1}-x_{4}\right)}=\frac{(\boldsymbol{x}-4)(\boldsymbol{x}-5)(\boldsymbol{x}-2)}{(3-4)(3-5)(3-2)}=\frac{\boldsymbol{x}^{3}-11 \boldsymbol{x}^{2}+38 \boldsymbol{x}-40}{2} \\ &\ell_{2}(\boldsymbol{x})=\frac{\left(\boldsymbol{x}-x_{1}\right)\left(\boldsymbol{x}-x_{3}\right)\left(\boldsymbol{x}-x_{4}\right)}{\left(x_{2}-x_{1}\right)\left(x_{2}-x_{3}\right)\left(x_{2}-x_{4}\right)}=\frac{(\boldsymbol{x}-3)(\boldsymbol{x}-5)(\boldsymbol{x}-2)}{(4-3)(4-5)(4-2)}=\frac{\boldsymbol{x}^{3}-10 \boldsymbol{x}^{2}+31 \boldsymbol{x}-30}{-2} \\ &\ell_{3}(\boldsymbol{x})=\frac{\left(\boldsymbol{x}-x_{1}\right)\left(\boldsymbol{x}-x_{2}\right)\left(\boldsymbol{x}-x_{4}\right)}{\left(x_{3}-x_{1}\right)\left(x_{3}-x_{2}\right)\left(x_{3}-x_{4}\right)}=\frac{(\boldsymbol{x}-3)(\boldsymbol{x}-4)(\boldsymbol{x}-2)}{(5-3)(5-4)(5-2)}=\frac{\boldsymbol{x}^{3}-9 \boldsymbol{x}^{2}+26 \boldsymbol{x}-24}{6} \\ &\ell_{4}(\boldsymbol{x})=\frac{\left(\boldsymbol{x}-x_{1}\right)\left(\boldsymbol{x}-x_{2}\right)\left(\boldsymbol{x}-x_{3}\right)}{\left(x_{4}-x_{1}\right)\left(x_{4}-x_{2}\right)\left(x_{4}-x_{3}\right)}=\frac{(\boldsymbol{x}-3)(\boldsymbol{x}-4)(\boldsymbol{x}-5)}{(2-3)(2-4)(2-5)}=\frac{\boldsymbol{x}^{3}-12 \boldsymbol{x}^{2}+47 \boldsymbol{x}-60}{-6} \end{aligned}\] As a sanity check, notice how: \[\begin{aligned} &\ell_{1}\left(x_{1}\right)=\ell_{1}(3)=\frac{3^{3}-11 \cdot 3^{2}+38 \cdot 3-40}{2}=\frac{2}{2}=1 \\ &\ell_{1}\left(x_{2}\right)=\ell_{1}(4)=\frac{4^{3}-11 \cdot 4^{2}+38 \cdot 4-40}{2}=\frac{0}{2}=0 \end{aligned}\] It will make the next step easier if we rewrite all LaGrange polynomials to have the same denominator 6: \[\begin{array}{ll} \ell_{1}(\boldsymbol{x})=\frac{3 \boldsymbol{x}^{3}-33 \boldsymbol{x}^{2}+114 \boldsymbol{x}-120}{6} & \ell_{3}(\boldsymbol{x})=\frac{\boldsymbol{x}^{3}-9 \boldsymbol{x}^{2}+26 \boldsymbol{x}-24}{6} \\ \ell_{2}(\boldsymbol{x})=\frac{-3 \boldsymbol{x}^{3}+30 \boldsymbol{x}^{2}-93 \boldsymbol{x}+90}{6} & \ell_{4}(\boldsymbol{x})=\frac{-\boldsymbol{x}^{3}+12 \boldsymbol{x}^{2}-47 \boldsymbol{x}+60}{6} \end{array}\] Our desired polynomial is

And indeed, \(f\) gives the correct values:

\[\begin{aligned} &f\left(x_{1}\right)=f(3)=\frac{3^{3}}{2}-2 \cdot 3^{2}-\frac{9 \cdot 3}{2}+19=1=y_{1} \\ &f\left(x_{2}\right)=f(4)=\frac{4^{3}}{2}-2 \cdot 4^{2}-\frac{9 \cdot 4}{2}+19=1=y_{2} \\ &f\left(x_{3}\right)=f(5)=\frac{5^{3}}{2}-2 \cdot 5^{2}-\frac{9 \cdot 5}{2}+19=9=y_{3} \\ &f\left(x_{4}\right)=f(2)=\frac{2^{3}}{2}-2 \cdot 2^{2}-\frac{9 \cdot 2}{2}+19=6=y_{4} \end{aligned}\]

Polynomials \(\bmod p\)

We will see a secret-sharing scheme based on polynomials, whose Share algorithm must choose a polynomial with uniformly random coefficients. Since we cannot have a uniform distribution over the real numbers, we must instead consider polynomials with coefficients in \(\mathbb{Z}_{p}\)

It is still true that \(d+1\) points determine a unique degree- \(d\) polynomial when working modulo \(p\), if \(p\) is a prime! \[\begin{aligned} & f(\boldsymbol{x})=y_{1} \cdot \ell_{1}(\boldsymbol{x})+y_{2} \cdot \ell_{2}(\boldsymbol{x})+y_{3} \cdot \ell_{3}(\boldsymbol{x})+y_{4} \cdot \ell_{4}(\boldsymbol{x}) \\ & =1 \cdot \ell_{1}(\boldsymbol{x})+1 \cdot \ell_{2}(\boldsymbol{x})+9 \cdot \ell_{3}(\boldsymbol{x})+6 \cdot \ell_{4}(\boldsymbol{x}) \end{aligned}\] \[\begin{aligned} & =\frac{1}{6}\left(3 x^{3}-12 x^{2}-27 x+114\right) \\ & =\frac{x^{3}}{2}-2 x^{2}-\frac{9 x}{2}+19 \end{aligned}\] Theorem 3.9 Let \(p\) be a prime, and let \(\left\{\left(x_{1}, y_{1}\right), \ldots,\left(x_{d+1}, y_{d+1}\right)\right\} \subseteq\left(\mathbb{Z}_{p}\right)^{2}\) be a set of points whose \(x_{i}\) val\((\) Interp \(\bmod p) \quad\) ues are all distinct. Then there is a unique degree-d polynomial \(f\) with coefficients from \(\mathbb{Z}_{p}\) that satisfies \(y_{i} \equiv_{p} f\left(x_{i}\right)\) for all \(i\).

The proof is the same as the one for Theorem 3.8, if you interpret all arithmetic modulo p. Addition, subtraction, and multiplication mod \(p\) are straight forward; the only nontrivial question is how to interpret "division mod \(p\) " which is necessary in the definition of the \(\ell_{j}\) polynomials. For now, just accept that you can always "divide" mod \(p\) (except by zero) when \(p\) is a prime. If you are interested in how division mod \(p\) works, look ahead to Chapter \(13 .\)

We can also generalize the observation that \(d+1\) points uniquely determine a degree- \(d\) polynomial. It turns out that:

For any \(k\) points, there are exactly \(p^{d+1-k}\) polynomials of degree- \(d\) that hit those points, \(\bmod p\).

Note how when \(k=d+1\), the statement says that there is just a single polynomial hitting the points.

Corollary 3.10 Let \(\mathcal{P}=\left\{\left(x_{1}, y_{1}\right), \ldots,\left(x_{k}, y_{k}\right)\right\} \subseteq\left(\mathbb{Z}_{p}\right)^{2}\) be a set of points whose \(x_{i}\) values are distinct. Letd (# of polys) satisfy \(k \leqslant d+1\) and \(p>d\). Then the number of degree-d polynomials \(f\) with coefficients in \(\mathbb{Z}_{p}\) that satisfy the condition \(y_{i} \equiv_{p} f\left(x_{i}\right)\) for all \(i\) is exactly \(p^{d+1-k}\).

Proof The proof is by induction on the value \(d+1-k\). The base case is when \(d+1-k=0\). Then we have \(k=d+1\) distinct points, and Theorem \(3.9\) says that there is a unique polynomial satisfying the condition. Since \(p^{d+1-k}=p^{0}=1\), the base case is true.

For the inductive case, we have \(k \leqslant d\) points in \(\mathcal{P}\). Let \(x^{*} \in \mathbb{Z}_{p}\) be a value that does not appear as one of the \(x_{i}\) ’s. Every polynomial must give some value when evaluated at \(x^{*} . \mathrm{So}\) \[\begin{aligned} &\text { [# of degree- } d \text { polynomials passing through points in } \mathcal{P}] \\ &\qquad=\sum_{y^{*} \in \mathbb{Z}_{p}}\left[\# \text { of degree- } d \text { polynomials passing through points in } \mathcal{P} \cup\left\{\left(x^{*}, y^{*}\right)\right\}\right] \\ &\stackrel{(\star)}{=} \sum_{y^{*} \in \mathbb{Z}_{p}} p^{d+1-(k+1)} \\ &\quad=p \cdot\left(p^{d+1-k-1}\right)=p^{d+1-k} \end{aligned}\] The equality marked \((\star)\) follows from the inductive hypothesis, since each of the terms involves a polynomial passing through a specified set of \(k+1\) points with distinct \(x\) coordinates. Example

When we plot this polynomial over the real

121 numbers (the picture on the left), we get a familiar parabola.

Let’s see what this polynomial "looks like" modulo 11 (i.e., in \(\mathbb{Z}_{11}\) ). Working mod 11 means to "wrap around" every time the polynomial crosses over a multiple of 11 along the \(y\)-axis. This results in the blue plot below:

This is a picture of a mod-11 parabola. In fact, since we care only about \(\mathbb{Z}_{11}\) inputs to \(f\), you could rightfully say that just the 11 highlighted points alone (not the blue curve) are a picture of a mod-11 parabola.

Construction \(3.11\)

(Shamir SSS)

Correctness follows from the interpolation theorem.

Example Here is an example of 3-out-of-5 secret sharing over \(\mathbb{Z}_{11}\) (so \(\left.p=11\right)\). Suppose the secret being shared is \(m=7 \in \mathbb{Z}_{11}\). The Share algorithm chooses a random degree-2 polynomial with constant coefficient \(7 .\)

Let’s say that the remaining two coefficients are chosen as \(f_{2}=1\) and \(f_{1}=4\), resulting in the following polynomial: \[f(x)=1 x^{2}+4 x+7\] This is the same polynomial illustrated in the previous example:

For each user \(i \in\{1, \ldots, 5\}\), we distribute the share \((i, f(i) \% 11)\). These shares correspond to the highlighted points in the mod-11 picture above.

Remember that this example illustrates just one possible execution of Share. Because Share is a randomized algorithm, there are many valid sharings of the same secret (induced by different choices of the highlighted coefficients in \(f\) ).

Security

To show the security of Shamir secret sharing, we first show a convenient lemma about the distribution of shares in an unauthorized set:

Lemma 3.12 Letp be a prime and define the following two libraries:

\mid

\(\mathcal{L}_{\text {shamir-real }}\) chooses a random degree-( \(\left.t-1\right)\) polynomial that passes through the point \((0, m)\), then evaluates it at the given \(x\)-coordinates (specified by \(U\) ). \(\mathcal{L}_{\text {shamir-rand }}\) simply gives uniformly chosen points, unrelated to any polynomial.

The claim is that these libraries are interchangeable \(: \mathcal{L}_{\text {shamir-real }} \equiv \mathcal{L}_{\text {shamir-rand }}\).

Proof Fix a message \(m \in \mathbb{Z}_{p}\), fix set \(U\) of users with \(|U|<t\), and for each \(i \in U\) fix a value \(y_{i} \in \mathbb{Z}_{p}\). We wish to consider the probability that a call to \(\operatorname{POLY}(m, t, U)\) outputs \(\left\{\left(i, y_{i}\right) \mid i \in U\right\}\), in each of the two libraries. \({ }^{2}\)

In library \(\mathcal{L}_{\text {shamir-real }}\), the subroutine chooses a random degree- \((t-1)\) polynomial \(f\) such that \(f(0) \equiv_{p} m\). From Corollary \(3.10\), we know there are \(p^{t-1}\) such polynomials.

In order for POLY to output points consistent with our chosen \(y_{i}\) ’s, the library must have chosen one of the polynomials that passes through \((0, m)\) and all of the \(\left\{\left(i, y_{i}\right) \mid i \in\right.\) \(U\}\) points. The library must have chosen one of the polynomials that passes through a specific choice of \(|U|+1\) points, and Corollary \(3.10\) tells us that there are \(p^{t-(|U|+1)}\) such polynomials.

The only way for pOLY to give our desired output is for it to choose one of the \(p^{t-(|U|+1)}\) "good" polynomials, out of the \(p^{t-1}\) possibilities. This happens with probability exactly \[\frac{p^{t-|U|-1}}{p^{t-1}}=p^{-|U|}\] Now, in library \(\mathcal{L}_{\text {shamir-rand, POLY chooses its }}|U|\) output values uniformly in \(\mathbb{Z}_{p}\). There are \(p^{|U|}\) ways to choose them. But only one of those ways causes POLY \((m, t, U)\) to output our specific choice of \(\left\{\left(i, y_{i}\right) \mid i \in U\right\}\). Hence, the probability of receiving this output is \(p^{-|U|}\)

For all possible inputs to POLY, both libraries assign the same probability to every possible output. Hence, the libraries are interchangeable.

Theorem 3.13 Shamir’s secret-sharing scheme (Construction 3.11) is secure according to Definition \(3.3 .\)

\({ }^{2}\) This is similar to how, in Claim 2.7, we fixed a particular \(m\) and \(c\) and computed the probability that \(\operatorname{EAVESDROP}(m)=c\) Proof Let \(\mathcal{S}\) denote the Shamir secret-sharing scheme. We prove that \(\mathcal{L}_{\mathrm{tsss}-\mathrm{L}}^{\mathcal{S}} \equiv \mathcal{L}_{\mathrm{tsss}-\mathrm{R}}^{\mathcal{S}}\) via a hybrid argument.

Our starting point is \(\mathcal{L}_{\mathrm{tsss}-\mathrm{L}}^{\mathcal{S}}\) shown here with the details of Shamir secret-sharing filled in.

Almost the entire body of the SHARE subroutine has been factored out in terms of the \(\mathcal{L}_{\text {shamir-real library }}\) defined above. The only thing remaining is the "choice" of whether to share \(m_{L}\) or \(m_{R}\). Restructuring the code in this way has no effect on the library’s behavior.

By Lemma 3.12, we can replace \(\mathcal{L}_{\text {shamir-real with }} \mathcal{L}_{\text {shamir-rand, }}\), having no effect on the library’s behavior.

The argument to POLY has been changed from \(m_{L}\) to \(m_{R}\). This has no effect on the library’s behavior, since POLY is actually ignoring its argument in these hybrids.

A subroutine has been inlined, which has no effect on the library’s behavior. The resulting library is \(\mathcal{L}_{\mathrm{tsss}-\mathrm{R}}{ }^{\mathcal{S}}\)

We showed that \(\mathcal{L}_{\mathrm{tsss}-\mathrm{L}}^{\mathcal{S}} \equiv \mathcal{L}_{\mathrm{hyb}-1} \equiv \cdots \equiv \mathcal{L}_{\mathrm{hyb}-4} \equiv \mathcal{L}_{\mathrm{tsss}-\mathrm{R}}^{\mathcal{S}}\), so Shamir’s secret sharing scheme is secure.

* \(3.5 \quad\) Visual Secret Sharing

Here is a fun variant of 2-out-of-2 secret-sharing called visual secret sharing. In this variant, both the secret and the shares are black-and-white images. We require the same security property as traditional secret-sharing - that is, a single share (image) by itself reveals no information about the secret (image). What makes visual secret sharing different is that we require the reconstruction procedure to be done visually.

More specifically, each share should be printed on transparent sheets. When the two shares are stacked on top of each other, the secret image is revealed visually. We will discuss a simple visual secret sharing scheme that is inspired by the following observations: \[\begin{aligned} &\text { when } \square \text { is stacked on top of } \square \text {, the result is } \\ &\text { when } \square \text { is stacked on top of } \square \text {, the result is } \\ &\text { when } \square \text { is stacked on top of } \square \text {, the result is } \\ &\text { when } \square \text { is stacked on top of } \square \text { the result is } \end{aligned}\] Importantly, when stacking shares on top of each other in the first two cases, the result is a \(2 \times 2\) block that is half-black, half-white (let’s call it "gray"); while in the other cases the result is completely black.

The idea is to process each pixel of the source image independently, and to encode each pixel as a \(2 \times 2\) block of pixels in each of the shares. A white pixel should be shared in a way that the two shares stack to form a "gray" \(2 \times 2\) block, while a black pixel is shared in a way that results in a black \(2 \times 2\) block.

More formally:

Construction \(3.14\)

It is not hard to see that share \(s_{1}\) leaks no information about the secret image \(m\), because it consists of uniformly chosen \(2 \times 2\) blocks. In the exercises you are asked to prove that \(s_{2}\) also individually leaks nothing about the secret image.

Note that whenever the source pixel is white, the two shares have identical \(2 \times 2\) blocks (so that when stacked, they make a "gray" block). Whenever a source pixel is black, the two shares have opposite blocks, so stack to make a black block.

Example

Basing Cryptography on Intractable Computations

John Nash was a mathematician who earned the 1994 Nobel Prize in Economics for his work in game theory. His life story was made into a successful movie, \(A\) Beautiful Mind.

In 1955, Nash was in correspondence with the United States National Security Agency (NSA), \({ }^{1}\) discussing new methods of encryption that he had devised. In these letters, he also proposes some general principles of cryptography (bold highlighting not in the original):

... in principle the enemy needs very little information to begin to break down the process. Essentially, as soon as \(\lambda\) bits \(^{2}\) of enciphered message have been transmitted the key is about determined. This is no security, for a practical key should not be too long. But this does not consider how easy or difficult it is for the enemy to make the computation determining the key. If this computation, although possible in principle, were sufficiently long at best then the process could still be secure in a practical sense.

Nash is saying something quite profound: it doesn’t really matter whether attacks are impossible, only whether attacks are computationally infeasible. If his letters hadn’t been kept classified until 2012, they might have accelerated the development of "modern" cryptography, in which security is based on intractable computations. As it stands, he was decades ahead of his time in identifying one of the most important concepts in modern cryptography.

Asymptotic Running Time

It is instructive to think about the monetary cost of an enormous computation, but it doesn’t necessarily help us draw the line between "feasible" attacks (which we want to protect against) and "infeasible" ones (which we agreed we don’t need to care about). We need to be able to draw such a line in order to make security definitions that say "only feasible attacks are ruled out."

Once again, John Nash thought about this question. He suggested to consider the asymptotic cost of an attack - how does the cost of a computation scale as the security parameter \(\lambda\) goes to infinity?

So a logical way to classify enciphering processes is by the way in which the computation length for the computation of the key increases with increasing length of the key. This is at best exponential and at worst probably a relatively small power of \(\lambda, a \cdot \lambda^{2}\) or \(a \cdot \lambda^{3}\), as in substitution ciphers.

Nash highlights the importance of attacks that run in polynomial time:

Definition 4.1 A program runs in polynomial time if there exists a constant \(c>0\) such that for all sufficiently long input strings \(x\), the program stops after no more than \(O\left(|x|^{c}\right)\) steps.

Polynomial-time algorithms scale reasonably well (especially when the exponent is small), but exponential-time algorithms don’t. It is probably no surprise to modern readers to see "polynomial-time" as a synonym for "efficient." However, it’s worth pointing out that, again, Nash is years ahead of his time relative to the field of computer science.

In the context of cryptography, our goal will be to ensure that no polynomial-time attack can successfully break security. We will not worry about attacks like brute-force that require exponential time.

Polynomial time is not a perfect match to what we mean when we informally talk about "efficient" algorithms. Algorithms with running time \(\Theta\left(n^{1000}\right)\) are technically polynomialtime, while those with running time \(\Theta\left(n^{\log \log \log n}\right)\) aren’t. Despite that, polynomial-time is extremely useful because of the following closure property: repeating a polynomial-time process a polynomial number of times results in a polynomial-time process overall.

Potential Pitfall: Numerical Algorithms

When we study public-key cryptography, we will discuss algorithms that operate on very large numbers (e.g., thousands of bits long). You must remember that representing the number \(N\) on a computer requires only \(\sim \log _{2} N\) bits. This means that \(\log _{2} N\), rather than \(N\), is our security parameter! We will therefore be interested in whether certain operations on the number \(N\) run in polynomial-time as a function of \(\log _{2} N\), rather than in \(N\). Keep in mind that the difference between running time \(O(\log N)\) and \(O(N)\) is the difference between writing down a number and counting to the number.

For reference, here are some numerical operations that we will be using later in the class, and their known efficiencies:

Again, "efficient" means polynomial-time. Furthermore, we only consider polynomialtime algorithms that run on standard, classical computers. In fact, all of the problems in the right-hand column do have known polynomial-time algorithms on quantum computers.

Other Properties

Lemma 4.6 If \(\mathcal{L}_{1} \equiv \mathcal{L}_{2}\) then \(\mathcal{L}_{1} \approx \mathcal{L}_{2}\). Also, if \(\mathcal{L}_{1} \approx \mathcal{L}_{2} \approx \mathcal{L}_{3}\) then \(\mathcal{L}_{1} \approx \mathcal{L}_{3}\).

\((\approx\) facts)

Analogous to Lemma \(2.11\), we also have the following library chaining lemma, which you are asked to prove as an exercise:

Lemma \(4.7\) If \(\mathcal{L}_{\text {left }} \approx \mathcal{L}_{\text {right }}\) then \(\mathcal{L}^{*} \diamond \mathcal{L}_{\text {left }} \approx \mathcal{L}^{*} \diamond \mathcal{L}_{\text {right }}\) for any polynomial-time library \(\mathcal{L}^{*}\).

(Chaining)

Bad-Event Lemma

A common situation is when two libraries are expected to execute exactly the same statements, until some rare & exceptional condition happens. In that case, we can bound an attacker’s distinguishing advantage by the probability of the exceptional condition.

More formally,

Lemma 4.8 Let \(\mathcal{L}_{\text {left }}\) and \(\mathcal{L}_{\text {right }}\) be libraries that each define a variable named ’bad’ that is initialized to (Bad events) \(\quad 0 .\) If \(\mathcal{L}_{\text {left }}\) and \(\mathcal{L}_{\text {right }}\) have identical code, except for code blocks reachable only when bad \(=1\) (e.g., guarded by an "if bad \(=1\) "statement), then \[\left|\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {left }} \Rightarrow 1\right]-\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {right }} \Rightarrow 1\right]\right| \leqslant \operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {left }} \text { sets bad }=1\right] .\] \(\star\) Proof Fix an arbitrary calling program \(\mathcal{A}\). In this proof, we use conditional probabilites \({ }^{8}\) to isolate the cases where bad is changed to 1 . We define the following events:

\(-\mathcal{B}_{\text {left }}:\) the event that \(\mathcal{A} \diamond \mathcal{L}_{\text {left }}\) sets bad to 1 at some point.

\(-\mathcal{B}_{\text {right }}\) : the event that \(\mathcal{A} \diamond \mathcal{L}_{\text {right }}\) sets bad to 1 at some point.

We also write \(\overline{\mathcal{B}_{\text {left }}}\) and \(\overline{\mathcal{B}_{\text {right }}}\) to denote the corresponding complement events. From conditional probability, we can write: \[\begin{aligned} \operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {left }} \Rightarrow 1\right]=\operatorname{Pr}[&\left.\mathcal{A} \diamond \mathcal{L}_{\text {left }} \Rightarrow 1 \mid \mathcal{B}_{\text {left }}\right] \operatorname{Pr}\left[\mathcal{B}_{\text {left }}\right] \\ &+\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {left }} \Rightarrow 1 \mid \overline{\mathcal{B}_{\text {left }}}\right] \operatorname{Pr}\left[\overline{\mathcal{B}_{\text {left }}}\right] \\ \operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {right }} \Rightarrow 1\right]=\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {right }} \Rightarrow 1 \mid \mathcal{B}_{\text {right }}\right] \operatorname{Pr}\left[\mathcal{B}_{\text {right }}\right] \\ &+\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {right }} \Rightarrow 1 \mid \overline{\mathcal{B}_{\text {right }}}\right] \operatorname{Pr}\left[\overline{\mathcal{B}_{\text {right }}}\right] \end{aligned}\] Our first observation is that \(\operatorname{Pr}\left[\mathcal{B}_{\text {left }}\right]=\operatorname{Pr}\left[\mathcal{B}_{\text {right }}\right]\). This is because at the time bad is changed to 1 for the first time, the library has only been executing instructions that are the same in \(\mathcal{L}_{\text {left }}\) and \(\mathcal{L}_{\text {right. }}\). In other words, the choice to set bad to 1 is determined by the same sequence of instructions in both libraries, so it occurs with the same probability in both libraries.

As a shorthand notation, we define \(p^{*} \stackrel{\operatorname{def}}{=} \operatorname{Pr}\left[\mathcal{B}_{\text {left }}\right]=\operatorname{Pr}\left[\mathcal{B}_{\text {right }}\right]\). Then we can write the advantage of \(\mathcal{A}\) as:

\(\operatorname{advantage}_{\mathcal{A}}=\left|\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {left }} \Rightarrow 1\right]-\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {right }} \Rightarrow 1\right]\right|\)

\({ }^{8}\) The use of conditional probabilites here is delicate and prone to subtle mistakes. For a discussion of the pitfalls, consult the paper where this lemma first appeared: Mihir Bellare & Phillip Rogaway: "Code-Based Game-Playing Proofs and the Security of Triple Encryption," in Eurocrypt 2006. ia.cr/2004/331 \[\begin{gathered} =\left|\begin{array}{c} \left(\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {left }} \Rightarrow 1 \mid \mathcal{B}_{\text {left }}\right] \cdot p^{*}+\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {left }} \Rightarrow 1 \mid \overline{\mathcal{B}_{\text {left }}}\right]\left(1-p^{*}\right)\right) \\ -\left(\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {right }} \Rightarrow 1 \mid \mathcal{B}_{\text {right }}\right] \cdot p^{*}+\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {right }} \Rightarrow 1 \mid \overline{\mathcal{B}_{\text {right }}}\right]\left(1-p^{*}\right)\right) \\ p^{*}\left(\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {left }} \Rightarrow 1 \mid \mathcal{B}_{\text {left }}\right]-\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {right }} \Rightarrow 1 \mid \mathcal{B}_{\text {right }}\right]\right) \\ \left(1-p^{*}\right)\left(\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {left }} \Rightarrow 1 \mid \overline{\mathcal{B}_{\text {left }}}\right]-\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {right }} \Rightarrow 1 \mid \overline{\mathcal{B}_{\text {right }}}\right]\right) \end{array}\right| \end{gathered}\] In both of the expressions \(\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {left }} \Rightarrow 1 \mid \overline{\mathcal{B}_{\text {left }}}\right]\) and \(\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {right }} \Rightarrow 1 \mid \overline{\mathcal{B}_{\text {right }}}\right]\), we are conditioning on bad never being set to 0 . In this case, both libraries are executing the same sequence of instructions, so the probabilities are equal (and the difference of the probabilities is zero). Substituting in, we get: \[\operatorname{advantage}_{\mathcal{A}}=p^{*}\left|\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {left }} \Rightarrow 1 \mid \mathcal{B}_{\text {left }}\right]-\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {right }} \Rightarrow 1 \mid \mathcal{B}_{\text {right }}\right]\right|\] Intuitively, the proof is confirming the idea that differences can only be noticed between \(\mathcal{L}_{\text {left }}\) and \(\mathcal{L}_{\text {right }}\) when bad is set to 1 (corresponding to our conditioning on \(\mathcal{B}_{\text {left }}\) and \(\mathcal{B}_{\text {right }}\) ).

The quantity within the absolute value is the difference of two probabilities, so the largest it can be is 1 . Therefore, \[\text { advantage }_{\mathcal{A}} \leqslant p^{*} \stackrel{\text { def }}{=} \operatorname{Pr}\left[\mathcal{B}_{\text {left }}\right]=\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {left }} \text { sets bad }=1\right]\] This completes the proof.

Example Consider \(\mathcal{L}_{\text {left }}\) and \(\mathcal{L}_{\text {right }}\) from the previous example (where the calling program tries to "predict" the result of uniformly sampling a \(\lambda\)-bit string). We can prove that they are indistinguishable with the following sequence of hybrids:

Let us justify each of the steps:

• \(\mathcal{L}_{\text {left }} \equiv \mathcal{L}_{\mathrm{hyb}-\mathrm{L}}:\) The only difference is that \(\mathcal{L}_{\mathrm{hyb}-\mathrm{L}}\) maintains a variable "bad." Since it never actually reads from this variable, the change can have no effect.
• \(\mathcal{L}_{\mathrm{hyb}-\mathrm{L}}\) and \(\mathcal{L}_{\mathrm{hyb}-\mathrm{R}}\) differ only in the highlighted line, which can only be reached when bad \(=1\). Therefore, from the bad-event lemma:

\[\left|\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {hyb-L }} \Rightarrow 1\right]-\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {hyb-R }} \Rightarrow 1\right]\right| \leqslant \operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {hyb-L }} \text { sets bad }=1\right]\] But \(\mathcal{A} \diamond \mathcal{L}_{\mathrm{hyb}-\mathrm{L}}\) only sets bad \(=1\) if the calling program successfully predicts \(s\) in one of the calls to PREDICT. With q calls to PREDICT, the total probability of this happening is at most \(q / 2^{\lambda}\), which is negligible when the calling program runs in polynomial time. Hence \(\mathcal{L}_{\text {hyb-L }} \approx \mathcal{L}_{\text {hyb-R. }}\)

• \(\mathcal{L}_{\mathrm{hyb}-\mathrm{R}} \equiv \mathcal{L}_{\text {right }}\) : Similar to above, note how the first 3 lines of PREDICT in \(\mathcal{L}_{\text {hyb-R }}\) don’t actually do anything. The subroutine is going to return false no matter what. Both libraries have identical behavior.

Since \(\mathcal{L}_{\text {left }} \equiv \mathcal{L}_{\text {hyb-L }} \approx \mathcal{L}_{\text {hyb-R }} \equiv \mathcal{L}_{\text {right }}\), this proves that \(\mathcal{L}_{\text {left }} \approx \mathcal{L}_{\text {right }}\)

Birthday Probabilities

If \(q\) people are in a room, what is the probability that two of them have the same birthday (if we assume that each person’s birthday is uniformly chosen from among the possible days in a year)? This question is known as the birthday problem, and it is famous because the answer is highly unintuitive to most people. \({ }^{9}\)

Let’s make the question more general. Imagine taking \(q\) independent, uniform samples from a set of \(N\) items. What is the probability that the same value gets chosen more than once? In other words, what is the probability that the following program outputs 1 ? \[\mathcal{B}(q, N)\] for \(i:=1\) to \(q:\)
\(\quad s_{i} \leftarrow\{1, \ldots, N\}\)
for \(j:=1\) to \(i-1\) :
\(\quad\) if \(s_{i}=s_{j}\) then return 1
return 0

Let’s give a name to this probability: \[\text { BirthdayProb }(q, N) \stackrel{\text { def }}{=} \operatorname{Pr}[\mathcal{B}(q, N) \text { outputs } 1]\] It is possible to write an exact formula for this probability:

Lemma 4.9 BirthdayProb \((q, N)=1-\prod_{i=1}^{q-1}\left(1-\frac{i}{N}\right)\)

\({ }^{9}\) It is sometimes called the "birthday paradox," even though it is not really a paradox. The actual birthday paradox is that the "birthday paradox" is not a paradox. Proof Let us instead compute the probability that \(\mathcal{B}\) outputs 0 , which will allow us to then solve for the probability that it outputs 1 . In order for \(\mathcal{B}\) to output 0 , it must avoid the early termination conditions in each iteration of the main loop. Therefore: \[\begin{aligned} \operatorname{Pr}[\mathcal{B}(q, N) \text { outputs } 0]=& \operatorname{Pr}[\mathcal{B}(q, N) \text { doesn't terminate early in iteration } i=1] \\ & \cdot \operatorname{Pr}[\mathcal{B}(q, N) \text { doesn't terminate early in iteration } i=2] \\ & \vdots \\ & \cdot \operatorname{Pr}[\mathcal{B}(q, N) \text { doesn't terminate early in iteration } i=q] \end{aligned}\] In iteration \(i\) of the main loop, there are \(i-1\) previously chosen values \(s_{1}, \ldots, s_{i-1}\). The program terminates early if any of these are chosen again as \(s_{i}\), otherwise it continues to the next iteration. Put differently, there are \(i-1\) (out of \(N\) ) ways to choose \(s_{i}\) that lead to early termination \(-\) all other choices of \(s_{i}\) avoid early termination. Since the \(N\) possibilities for \(s_{i}\) happen with equal probability: \[\operatorname{Pr}[\mathcal{B}(q, N) \text { doesn't terminate early in iteration } i]=1-\frac{i-1}{N}\] Putting everything together: \[\begin{aligned} \operatorname{Birthday} \operatorname{Prob}(q, N) &=\operatorname{Pr}[\mathcal{B}(q, N) \text { outputs } 1] \\ &=1-\operatorname{Pr}[\mathcal{B}(q, N) \text { outputs } 0] \\ &=1-\left(1-\frac{1}{N}\right)\left(1-\frac{2}{N}\right) \cdots\left(1-\frac{q-1}{N}\right) \\ &=1-\prod_{i=1}^{q-1}\left(1-\frac{i}{N}\right) \end{aligned}\] This completes the proof.

Example This formula for BirthdayProb \((q, N)\) is not easy to understand at a glance. We can get a better sense of its behavior as a function of q by plotting it. Below is a plot with \(N=365\), corresponding to the classic birthday problem:

With only \(q=23\) people the probability of a shared birthday already exceeds 50%. The graph could be extended to the right (all the way to \(q=365\) ), but even at \(q=70\) the probability exceeds \(99.9 \%\).

Asymptotic Bounds on the Birthday Probability

It will be helpful to have an asymptotic formula for how BirthdayProb \((q, N)\) grows as a function of \(q\) and \(N\). We are most interested in the case where \(q\) is relatively small compared to \(N\) (e.g., when \(q\) is a polynomial function of \(\lambda\) but \(N\) is exponential).

Lemma 4.10 If \(q \leqslant \sqrt{2 N}\), then \[0.632 \frac{q(q-1)}{2 N} \leqslant \text { BirthdayProb }(q, N) \leqslant \frac{q(q-1)}{2 N}\] Since the upper and lower bounds differ by only a constant factor, it makes sense to write BirthdayProb \((q, N)=\Theta\left(q^{2} / N\right)\)

Proof We split the proof into two parts.

• To prove the upper bound, we use the fact that when \(x\) and \(y\) are positive,

\[\begin{aligned} (1-x)(1-y) &=1-(x+y)+x y \\ & \geqslant 1-(x+y) \end{aligned}\] More generally, when all terms \(x_{i}\) are positive, \(\prod_{i}\left(1-x_{i}\right) \geqslant 1-\sum_{i} x_{i}\). Hence, \[1-\prod_{i}\left(1-x_{i}\right) \leqslant 1-\left(1-\sum_{i} x_{i}\right)=\sum_{i} x_{i}\] Applying that fact, \[\text { BirthdayProb }(q, N) \stackrel{\text { def }}{=} 1-\prod_{i=1}^{q-1}\left(1-\frac{i}{N}\right) \leqslant \sum_{i=1}^{q-1} \frac{i}{N}=\frac{\sum_{i=1}^{q-1} i}{N}=\frac{q(q-1)}{2 N}\] To prove the lower bound, we use the fact that when \(0 \leqslant x \leqslant 1\), \[1-x \leqslant e^{-x} \leqslant 1-0.632 x\] This fact is illustrated below. The significance of \(0.632\) is that \(1-\frac{1}{e}=0.63212 \ldots\)

We can use both of these upper and lower bounds on \(e^{-x}\) to show the following: \[\prod_{i=1}^{q-1}\left(1-\frac{i}{N}\right) \leqslant \prod_{i=1}^{q-1} e^{-\frac{i}{N}}=e^{-\sum_{i=1}^{q-1} \frac{i}{N}}=e^{-\frac{q(q-1)}{2 N}} \leqslant 1-0.632 \frac{q(q-1)}{2 N} .\] With the last inequality we used the fact that \(q \leqslant \sqrt{2 N}\), and therefore \(\frac{q(q-1)}{2 N} \leqslant 1\) (this is necessary to apply the inequality \(e^{-x} \leqslant 1-0.632 x\) ). Hence: \[\begin{aligned} \text { BirthdayProb }(q, N) \stackrel{\text { def }}{=} 1-\prod_{i=1}^{q-1}\left(1-\frac{i}{N}\right) \\ & \geqslant 1-\left(1-0.632 \frac{q(q-1)}{2 N}\right)=0.632 \frac{q(q-1)}{2 N} \end{aligned}\] This completes the proof.

Example Below is a plot of these bounds compared to the actual value of BirthdayProb( q, \(N)(\) for \(N=\) \(365)\)

As mentioned previously, BirthdayProb \((q, N)\) grows roughly like \(q^{2} / N\) within the range of values we care about ( \(q\) small relative to \(N)\).

The Birthday Problem in Terms of Indistinguishable Libraries

Below are two libraries which will also be useful for future topics.

Both libraries provide a SAMP subroutine that samples a random element of \(\{0,1\}^{\lambda}\). The implementation in \(\mathcal{L}_{\text {samp-L }}\) samples uniformly and independently from \(\{0,1\}^{\lambda}\) each time. It samples with replacement, so it is possible (although maybe unlikely) for multiple calls to SAMP to return the same value in \(\mathcal{L}_{\text {samp-L. }}\).

On the other hand, \(\mathcal{L}_{\text {samp-R }}\) samples \(\lambda\)-bit strings without replacement. It keeps track of a set \(R\), containing all the values it has previously sampled, and avoids choosing them again (" \(\{0,1\}^{\lambda} \backslash R^{\prime \prime}\) is the set of \(\lambda\)-bit strings excluding the ones in \(R\) ). In this library, SAMP will never output the same value twice. The "obvious" distinguishing strategy. A natural way (but maybe not the only way) to distinguish these two libraries, therefore, would be to call sAMP many times. If you ever see a repeated output, then you must certainly be linked to \(\mathcal{L}_{\text {samp-L. After some number }}\) of calls to SAMP, if you still don’t see any repeated outputs, you might eventually stop and guess that you are linked to \(\mathcal{L}_{\text {samp-R. }}\).

Let \(\mathcal{A}_{q}\) denote this "obvious" calling program that makes \(q\) calls to sAMP and returns 1 if it sees a repeated value. Clearly, the program can never return 1 when it is linked to \(\mathcal{L}_{\text {samp-R. }}\) On the other hand, when it is linked to \(\mathcal{L}_{\text {samp-L }}\), it returns 1 with probability exactly BirthdayProb \(\left(q, 2^{\lambda}\right)\). Therefore, the advantage of \(\mathcal{A}_{q}\) is exactly BirthdayProb \(\left(q, 2^{\lambda}\right)\).

This program behaves differently in the presence of these two libraries, therefore they are not interchangeable. But are the libraries indistinguishable? We have demonstrated a calling program with advantage BirthdayProb \(\left(q, 2^{\lambda}\right)\). We have not specified \(q\) exactly, but if \(\mathcal{A}_{q}\) is meant to run in polynomial time (as a function of \(\lambda\) ), then \(q\) must be a polynomial function of \(\lambda\). Then the advantage of \(\mathcal{A}_{q}\) is \(\operatorname{BirthdayProb}\left(q, 2^{\lambda}\right)=\Theta\left(q^{2} / 2^{\lambda}\right)\), which is negligible!

To show that the librares are indistinguishable, we have to show that all calling programs have negligible advantage. It is not enough just to show that this particular calling program has negligible advantage. Perhaps surprisingly, the "obvious" calling program that we considered is the best possible distinguisher!

Lemma 4.11 Let \(\mathcal{L}_{\mathrm{samp}-\mathrm{L}}\) and \(\mathcal{L}_{\mathrm{samp}-\mathrm{R}}\) be defined as above. Then for all calling programs \(\mathcal{A}\) that make \(q\) (Repl. Sampling) queries to the SAMP subroutine, the advantage of \(\mathcal{A}\) in distinguishing the libraries is at most BirthdayProb \(\left(q, 2^{\lambda}\right)\).

In particular, when \(\mathcal{A}\) is polynomial-time (in \(\lambda\) ), \(q\) grows as a polynomial in the security parameter. Hence, \(\mathcal{A}\) has negligible advantage. Since this is true for all polynomial-time \(\mathcal{A}\), we have \(\mathcal{L}_{\mathrm{samp}-\mathrm{L}} \approx \mathcal{L}_{\mathrm{samp}-\mathrm{R} \text {. }}\)

Proof Consider the following hybrid libraries:

First, let us prove some simple observations about these libraries:

\(\mathcal{L}_{\text {hyb-L }} \equiv \mathcal{L}_{\text {samp-L }}:\) Note that \(\mathcal{L}_{\text {hyb-L }}\) simply samples uniformly from \(\{0,1\}^{\lambda}\). The extra \(R\) and bad variables in \(\mathcal{L}_{\text {hyb-L }}\) don’t actually have an effect on its external behavior (they are used only for convenience later in the proof). \(\mathcal{L}_{\text {hyb-R }} \equiv \mathcal{L}_{\text {samp-R }}:\) Whereas \(\mathcal{L}_{\text {samp-R }}\) avoids repeats by simply sampling from \(\{0,1\}^{\lambda} \backslash R\), this library \(\mathcal{L}_{\text {hyb-R samples } r}\) uniformly from \(\{0,1\}^{\lambda}\) and retries if the result happens to be in \(R\). This method is called rejection sampling, and it has the same effect \({ }^{10}\) as sampling \(r\) directly from \(\{0,1\}^{\lambda} \backslash R\).

Conveniently, \(\mathcal{L}_{\text {hyb-L }}\) and \(\mathcal{L}_{\text {hyb-R }}\) differ only in code that is reachable when bad \(=1\) (highlighted). So, using Lemma 4.8, we can bound the advantage of the calling program: \[\begin{aligned} \mid \operatorname{Pr}[\mathcal{A}&\left.\diamond \mathcal{L}_{\text {samp-L }} \Rightarrow 1\right]-\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {samp-R }} \Rightarrow 1\right] \mid \\ &=\left|\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {hyb-L }} \Rightarrow 1\right]-\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {hyb-R }} \Rightarrow 1\right]\right| \\ & \leqslant \operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {hyb-L }} \text { sets bad }:=1\right] \end{aligned}\] Finally, we can observe that \(\mathcal{A} \diamond \mathcal{L}_{\text {hyb-L }}\) sets bad := 1 only in the event that it sees a repeated sample from \(\{0,1\}^{\lambda}\). This happens with probability BirthdayProb \(\left(q, 2^{\lambda}\right)\).

Discussion

• Stating the birthday problem in terms of indistinguishable libraries makes it a useful tool in future security proofs. For example, when proving the security of a construction we can replace a uniform sampling step with a sampling-without-replacement step. This change has only a negligible effect, but now the rest of the proof can take advantage of the fact that samples are never repeated.

Another way to say this is that, when you are thinking about a cryptographic construction, it is "safe to assume" that randomly sampled long strings do not repeat, and behave accordingly.

• However, if a security proof does use the indistinguishability of the birthday libraries, it means that the scheme can likely be broken when a user happens to repeat a uniformly sampled value. Since this becomes inevitable as the number of samples approaches \(\sqrt{2^{\lambda+1}} \sim 2^{\lambda / 2}\), it means the scheme only offers \(\lambda / 2\) bits of security. When a scheme has this property, we say that it has birthday bound security. It is important to understand when a scheme has this property, since it informs the size of keys that should be chosen in practice.

A Generalization

A calling program can distinguish between the previous libraries if sAmp ever returns the same value twice. In any given call to SAMP, the variable \(\mathcal{R}\) denotes the set of "problematic" values that cause the libraries to be distinguished. At any point, \(R\) has only polynomially many values, so the probability of chosing such a problematic one is negligible.

Suppose we considered a different set of values to be problematic. As long as there are only polynomially many problematic values in each call to SAMP, the reasoning behind the proof wouldn’t change much. This idea leads to the following generalization, in which the calling program explicitly writes down all of the problematic values:

\({ }^{10}\) The two approaches for sampling from \(\{0,1\}^{\lambda} \backslash R\) may have different running times, but our model considers only the input-output behavior of the library. Lemma 4.12 The following two libraries are indistinguishable, provided that the argument \(\mathcal{R}\) to SAMP is passed as an explicit list of items.

Suppose the calling program makes \(q\) calls to SAMP, and in the \(i\) th call it uses an argument \(\mathcal{R}\) with \(n_{i}\) items. Then the advantage of the calling program is at most: \[1-\prod_{i=1}^{q}\left(1-\frac{n_{i}}{2^{\lambda}}\right)\] We can bound this advantage as before. If \(\sum_{i=1}^{q} n_{i} \leqslant 2^{\lambda}\), then the advantage is between \(0.632\left(\sum_{i=1}^{q} n_{i}\right) / 2^{\lambda}\) and \(\left(\sum_{i=1}^{q} n_{i}\right) / 2^{\lambda}\). When the calling program runs in polynomial time and must pass \(\mathcal{R}\) as an explicit list (i.e., take the time to "write down" the elements of \(\mathcal{R}\) ), \(\sum_{i=1}^{q} n_{i}\) is a polynomial in the security parameter and the calling program’s advantage is negligible.

The birthday scenario corresponds to the special case where \(n_{i}=i-1\) (in the \(i\) th call, \(R\) consists of the \(i-1\) results from previous calls to SAMP). In that case, \(\sum_{i=1}^{q} n_{i}=q(q-1) / 2\) and the probabilities collapse to the familiar birthday probabilities.

Pseudorandom Generators

One-time pad requires a key that’s as long as the plaintext. Let’s forget that we know about this limitation. Suppose Alice & Bob share only a short \(\lambda\)-bit secret \(k\), but they want to encrypt a \(2 \lambda\)-bit plaintext \(m\). They don’t know that (perfect) one-time secrecy is impossible in this setting (Exercise 2.11), so they try to get it to work anyway using the following reasoning:

• The only encryption scheme they know about is one-time pad, so they decide that the ciphertext will have the form \(c=m \oplus\) ??. This means that the unknown value \(? ?\) must be \(2 \lambda\) bits long.
• In order for the security of one-time pad to apply, the unknown value ?? should be uniformly distributed.
• The process of obtaining the unknown value ?? from the shared key \(k\) should be deterministic, so that the sender and receiver compute the same value and decryption works correctly.

Let \(G\) denote the process that transforms the key \(k\) into this mystery value. Then \(G\) : \(\{0,1\}^{\lambda} \rightarrow\{0,1\}^{2 \lambda}\), and the encryption scheme is \(\operatorname{Enc}(k, m)=m \oplus G(k)\)

It is not hard to see that if \(G\) is a deterministic function, then there are only \(2^{\lambda}\) possible outputs of \(G\), so the distribution of \(G(k)\) cannot be uniform in \(\{0,1\}^{2 \lambda}\). We therefore cannot argue that the scheme is secure in the same way as one-time pad.

However, what if the distribution of \(G(k)\) values is not perfectly uniform but only "close enough" to uniform? Suppose no polynomial-time algorithm can distinguish the distribution of \(G(k)\) values from the uniform distribution. Then surely this ought to be "close enough" to uniform for practical purposes. This is exactly the idea of pseudorandomness. It turns out that if \(G\) has a pseudorandomness property, then the encryption scheme described above is actually secure (against polynomial-time adversaries, in the sense discussed in the previous chapter).

Discussion & Pitfalls

• Do not confuse the interface of a PRG (it takes in a seed as input) with the interface of the security libraries \(\mathcal{L}_{\text {prg- } \star}\) (their QUERY subroutine doesn’t take any input)! A PRG is indeed an algorithm into which you can feed any string you like. However, security is only guaranteed when the PRG is being used exactly as described in the security libraries - in particular, when the seed is chosen uniformly/secretly and not used for anything else.

Nothing prevents a user from putting an adversarially-chosen \(s\) into a PRG, or revealing a PRG seed to an adversary, etc. You just get no security guarantee from doing it, since it’s not the situation reflected in the PRG security libraries.

• It doesn’t really make sense to say that "0010110110 is a random string" or "0000000001 is a pseudorandom string." Randomness and pseudorandomness are properties of the process used to generate a string, not properties of the individual strings themselves. When we have a value \(z=G(s)\) where \(G\) is a PRG and \(s\) is chosen uniformly, you could say that \(z\) was "chosen pseudorandomly" You could say that the output of some process is a "pseudorandom distribution."But it is slightly sloppy (although common) to say that a string \(z\) "is pseudorandom".
• There are common statistical tests you can run, which check whether some data has various properties that you would expect from a uniform distribution. \({ }^{1}\) For example, are there roughly an equal number of \(\odot\) s and 1 s? Does the substring 01010 occur with roughly the frequency I would expect? If I interpret the string as a series of points in the unit square \([0,1)^{2}\), is it true that roughly \(\pi / 4\) of them are within Euclidean distance 1 of the origin?

The definition of pseudorandomness is kind of a "master" definition that encompasses all of these statistical tests and more. After all, what is a statistical test, but a polynomial-time procedure that obtains samples from a distribution and outputs a yes/no decision? Pseudorandomness means that every statistical test that "passes" uniform data will also "pass" pseudorandomly generated data.

How NOT to Build a PRG

We can appreciate the challenges involved in building a PRG "from scratch" by first looking at an obvious idea for a PRG and understanding why it’s insecure.

Example Let’s focus on the case of a length-doubling PRG. It should take in \(\lambda\) bits and output \(2 \lambda\) bits. The output should look random when the input is sampled uniformly. A natural idea is for the candidate PRG to simply repeat the input twice. After all, if the input \(s\) is random, then \(s \| s\) is also random, too, right? \[\frac{G(s):}{\text { return } s \| s}\] To understand why this PRG is insecure, first let me ask you whether the following strings look like they were sampled uniformly from \(\{0,1\}^{8}\) :

\(11011101,01010101,01110111,01000100, \cdots\)

Do you see any patterns? Every string has its first half equal to its second half. That is a conspicuous pattern because it is relatively rare for a uniformly chosen string to have this property. Of course, this is exactly what is wrong with this simplistic PRG G defined above. Every output of \(G\) has equal first/second halves. But it is rare for uniformly sampled strings to have this property. We can formalize this observation as an attack against the PRG-security of \(G\) :

The first line means to obtain the result of QUERY and set its first half to be the string \(x\) and its second half to be \(y\). This calling program simply checks whether the output of QUERY has equal halves.

To complete the attack, we must show that this calling program has non-negligible bias distinguishing the \(\mathcal{L}_{\text {prg- } \star \text { libraries. }}\)

• When linked to \(\mathcal{L}_{\text {prg-real, }}\) the calling program receives outputs of \(G\), which always have matching first/second halves. So \(\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\mathrm{prg} \text {-real }}^{G} \Rightarrow 1\right]=1\). Below we have filled in \(\mathcal{L}_{\text {prg-real }}\) with the details of our \(G\) algorithm:

When linked to \(\mathcal{L}_{\mathrm{prg}-\mathrm{rand}}\), the calling program receives uniform samples from \(\{0,1\}^{2 \lambda}\).

\(\mathcal{A}\) outputs 1 whenever we sample a string from \(\{0,1\}^{2 \lambda}\) with equal first/second halves. What exactly is the probability of this happening? There are several ways to see that the probability is \(1 / 2^{\lambda}\) (this is like asking the probability of rolling doubles with two dice, but each die has \(2^{\lambda}\) sides instead of 6). Therefore, \(\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\mathrm{prg} \text {-rand }}^{G} \Rightarrow 1\right]=1 / 2^{\lambda}\).

The advantage of this adversary is \(1-1 / 2^{\lambda}\) which is certainly non-negligible - it does not even approach 0 as \(\lambda\) grows. This shows that \(G\) is not a secure PRG.

This example illustrates how randomness/pseudorandomness is a property of the entire process, not of individual strings. If you take a string of 1 s and concatenate it with another string of 1s, you get a long string of 1s. "Containing only 1s" is a property of individual strings. If you take a "random string" and concatenate it with another "random string" you might not get a "random long string." Being random is not a property of an individual string, but of the entire process that generates it.

Outputs from this \(G\) have equal first/second halves, which is an obvious pattern. The challenge of desiging a secure PRG is that its outputs must have no discernable pattern! Any pattern will lead to an attack similar to the one shown above.

Related Concept: Random Number Generation

The security of a PRG requires the seed to be chosen uniformly. In practice, the seed has to come from somewhere. Generally a source of "randomness" is provided by the hardware or operating system, and the process that generates these random bits is (confusingly) called a random number generator (RNG).

In this course we won’t cover low-level random number generation, but merely point out what makes it different than the PRGs that we study:

• The job of a PRG is to take a small amount of "ideal" (in other words, uniform) randomness and extend it.
• By contrast, an RNG usually takes many inputs over time and maintains an internal state. These inputs are often from physical/hardware sources. While these inputs are "noisy" in some sense, it is hard to imagine that they would be statistically uniform. So the job of the RNG is to "refine" (sometimes many) sources of noisy data into uniform outputs.

Two Approaches to Increase Stretch

Suppose \(G:\{0,1\}^{\lambda} \rightarrow\{0,1\}^{2 \lambda}\) is a length-doubling PRG (i.e., a PRG with stretch \(\lambda\) ). Below are two ideas for constructing a PRG with longer stretch:

Although the constructions are similar, only one of them is secure. Before reading any further, can you guess which of \(H_{1}, H_{2}\) is a secure PRG and which is insecure? By carefully comparing these two approaches, I hope you develop a better understanding of the PRG security definition.

A Security Proof

I think it’s helpful to illustrate the "stragey" of security proofs by starting from the desired conclusion and working backwards. What better way to do this than as a Socratic dialogue in the style of Galileo? \(?^{2}\)

SALVIATI: I’m sure that \(H_{1}\) is the secure PRG.

SIMPLICIO: If I understand the security definition for PRGs correctly, you mean that the output of \(H_{1}\) looks indistinguishable from uniform, when the input to \(H_{1}\) is uniform. Why do you say that?

SALVIATI: Simple! \(H_{1}\) ’s output consists of segments called \(x, u\), and \(v\). Each of these are outputs of \(G\), and since \(G\) itself is a PRG its outputs look uniform.

SIMPLICIO: I wish I had your boldness, Salviati. I myself am more cautious. If \(G\) is a secure PRG, then its outputs are indeed indistinguishable from uniform, but surely only when its input is uniform! Are you so sure that’s the case here?

SALVIATI: You raise a good point, Simplicio. In these endeavors it is always preferable to err on the side of caution. When we want to claim that \(H_{1}\) is a secure PRG, we consider the nature of its outputs when its seeds is uniform. Since \(H_{1}\) sends that seed s directly into \(G\), your concern is addressed.

SImPLICIO: Yes, I can see how in the expression \(x \| y:=G(s)\) the input to \(G\) is uniform, and so its outputs \(x\) and \(y\) are indistinguishable from random. Since \(x\) is part of \(H_{1}\) ’s output, we are making progress towards showing that the entire output of \(H_{1}\) is indistinguishable from random! However, the output of \(H_{1}\) also contains terms \(u\) and \(v\). When I examine how they are generated, as \(u \| v:=G(y)\), I become concerned again. Surely \(y\) is not uniform, so I see no way to apply the security if \(G\) !

\({ }^{2}\) Don’t answer that. SALVIATI: Oh, bless your heart. The answer could not be any more obvious! It is true that \(y\) is not uniformly distributed. But did you not just convince yourself that \(y\) is indistinguishable from uniform? Should that suffice?

SIMPLICIO: Incredible! I believe I understand now. Let me try to summarize: We suppose the input \(s\) to \(H_{1}\) is chosen uniformly, and examine what happens to \(H_{1}\) ’s outputs. In the expression \(x \| y:=G(s)\), the input to \(G\) is uniform, and thus \(x\) and \(y\) are indistinguishable from uniform. Now, considering the expression \(u \| v:=G(y)\), the result is indistinguishable from a scenario in which \(y\) is truly uniform. But if \(y\) were truly uniform, those outputs \(u\) and \(v\) would be indistinguishable from uniform! Altogether, \(x, u\), and \(v\) (the outputs of \(H_{1}\) ) are each indistinguishable from uniform!

I hope that was as fun for you as it was for me. \({ }^{3}\) The formal security proof and its sequence of hybrids will follow the outline given in Simplicio’s summary. We start by applying the PRG security definition to the first call to \(G\), and replace its outputs with truly uniform values. After this change, the input to the second call to \(G\) becomes uniform, allowing us to apply the PRG security definition again.

Claim 5.5 If \(G\) is a secure length-doubling \(P R G\), then \(H_{1}\) (defined above) is a secure (length-tripling) PRG.

Proof One of the trickier aspects of this proof is that we are using a secure PRG \(G\) to prove the security of another PRG \(H_{1}\). That means both \(\mathcal{L}_{\mathrm{prg}-\star}^{H_{1}}\) and \(\mathcal{L}_{\mathrm{prg}-\star}^{G}\) will appear in this proof. Both libraries/interfaces have a subroutine named "QUERY", and we will rename these subroutines QUERY \(H_{1}\) and QUERY QU disambiguate. \(^{\text {and }}\) to

We want to show that \(\mathcal{L}_{\text {prg-real }}^{H_{1}} \approx \mathcal{L}_{\text {prg-rand }}^{H_{1}} .\) As usual, we do so with a hybrid sequence. Since we assume that \(G\) is a secure \(P R G\), we are allowed to use the fact that \(\mathcal{L}_{\text {prg-real }}^{G} \approx\) \(\mathcal{L}_{\text {prg-rand }}^{G}\)

\(\mathcal{L}_{\text {prg-real }}^{H}:\left\{\begin{array}{l}\mathcal{L}_{\mathrm{prg} \text {-real }}^{H_{1}} \\ \frac{\text { QUERY }_{H_{1}}():}{s \leftarrow\{0,1\}^{\lambda}} \\ x \| y:=G(s) \\ u \| v:=G(y) \\ \text { return } x\|u\| v\end{array}\right\} H_{1}(s)\)

The starting point is \(\mathcal{L}_{\text {prg-real }}^{H_{1}}\), shown here with the details of \(H_{1}\) filled in.

The first invocation of \(G\) has been factored out into a subroutine. The resulting hybrid library includes an instance of \(\mathcal{L}_{\mathrm{prg}-\mathrm{real}}^{G}\)

’3f you’re wondering what the hell just happened: In Galileo’s 1632 book Dialogue Concerning the Two Chief World Systems, he lays out the arguments for heliocentrism using a dialog between Salviati (who advocated the heliocentric model) and Simplicio (who believed the geocentric model).

From the PRG security of \(G\), we can replace the instance of \(\mathcal{L}_{\text {prg-real }}^{G}\) with \(\mathcal{L}_{\text {prg-rand }}^{G}\). The resulting hybrid library is indistinguishable.

\(\frac{\operatorname{QuERY}_{H_{1}}():}{x \| y \leftarrow\{0,1\}^{2 \lambda}}\)
\(u \| v:=G(y)\)
return \(x\|u\| v\)

A subroutine has been inlined.

Choosing \(2 \lambda\) uniformly random bits and then splitting them into two halves has exactly the same effect as choosing \(\lambda\) uniformly random bits and independently choosing \(\lambda\) more.

\(\frac{\text { QUERY }_{H_{1}}():}{x \leftarrow\{\Theta, 1\}^{\lambda}}\)
\(u \| v:=\) QUERY \(_{G}()\)
return \(x\|u\| v\)

\(\mathcal{L}_{\mathrm{prg} \text {-real }}^{G}\)
\(\frac{\text { QUERY }_{G}():}{s \leftarrow\{\theta, 1\}^{\lambda}}\)
return \(G(s)\)

The remaining appearance of \(G\) has been factored out into a subroutine. Now \(\mathcal{L}_{\mathrm{prg}-\mathrm{real}}^{G}\) makes its second appearance.

Again, the PRG security of \(G\) lets us replace \(\mathcal{L}_{\text {prg-real }}^{G}\) with \(\mathcal{L}_{\text {prg-rand }}^{G}\). The resulting hybrid library is indistinguishable.

\(\left.\frac{\text { QUERY }_{H_{1}}()}{x \leftarrow\{\theta, 1}\right\}^{\lambda}\)
\(u \| v \leftarrow\{0,1\}^{2 \lambda}\)
return \(x\|u\| v\)

A subroutine has been inlined.

Similar to above, concatenating \(\lambda\) uniform bits with \(2 \lambda\) independently uniform bits has the same effect as sampling \(3 \lambda\) uniform bits. The result of this change is \(\mathcal{L}_{\mathrm{prg} \text {-rand }}^{H_{1}}\). Through this sequence of hybrid libraries, we showed that: \[\mathcal{L}_{\text {prg-real }}^{H_{1}} \equiv \mathcal{L}_{\text {hyb-1 }} \approx \mathcal{L}_{\text {hyb-2 }} \equiv \mathcal{L}_{\text {hyb-3 }} \equiv \mathcal{L}_{\text {hyb-4 }} \equiv \mathcal{L}_{\text {hyb-5 }} \approx \mathcal{L}_{\text {hyb-6 }} \equiv \mathcal{L}_{\text {hyb-7 }} \equiv \mathcal{L}_{\text {prg-rand }}^{H_{1}}\] Hence, \(H_{1}\) is a secure PRG.

Where the Proof Breaks Down for \(\mathrm{H}_{2}\)

The only difference between \(H_{1}\) and \(H_{2}\) is that the variable \(y\) is included in the output. How does that minor change affect the reasoning that we applied to \(H_{1}\) ?

\(\frac{H_{2}(s)}{x \| y}:=G(s)\)
\(u \| v:=G(y)\)
return \(x\|y\| u \| v\)

We argued that outputs \(u\) and \(v\) are indistinguishable from uniform since its input \(y\) is also indistinguishable from random. But it’s not quite so simple: A PRG’s output is indistinguishable from random if (1) its seed is uniform, and (2) the seed is not used for anything else! This construction \(\mathrm{H}_{2}\) violates condition (2) because it includes the "seed" \(y\) in the output.

We can see this idea reflected in the formal PRG definition. In \(\mathcal{L}_{\text {prg-real, }}\), the seed \(s\) is chosen uniformly, given as input to \(G\), and then goes out of scope! If we try to reproduce the security proof for \(H_{1}\) with \(H_{2}\) instead, we’ll get stuck when we are trying to factor out the second call to \(G\) in terms of \(\mathcal{L}_{\text {prg-real }}\) :

We are trying to factor out the two highlighted lines into a separate library, renaming \(y\) into \(s\) in the process. But \(s\) can only exist inside the private scope of the new library, while there still exists a "dangling reference" \(y\) in the original library.

Speaking more generally about PRGs, suppose we have a call to \(G\) somewhere and want to argue that its outputs are pseudorandom. We can only express this call to \(G\) in terms of \(\mathcal{L}_{\mathrm{prg} \text {-real }}^{G}\) if the input to \(G\) is uniform and is used nowhere else. That’s not true here - we can’t express one of the calls to \(G\) in terms of \(\mathcal{L}_{\mathrm{prg} \text {-real' }}^{G}\), so we can’t be sure that the outputs of that call to \(G\) look random.

These subtle issues are not limited to PRGs. Every hybrid security proof in this course includes steps where we factor out some statements in terms of some pre-existing library. Don’t take these steps for granted! They will fail (often because of scoping issues) if the construction isn’t using the building block correctly. You should always treat such "factoring out" steps as "sanity checks" for your proof.

A Concrete Attack on \(\mathrm{H}_{2}\)

So far, we’ve only demonstrated that we get stuck when trying to prove the security of \(\mathrm{H}_{2}\). But that doesn’t necessarily mean that \(\mathrm{H}_{2}\) is insecure - it could mean that we’re just not clever enough to see a different security proof. To show that \(\mathrm{H}_{2}\) is actually insecure, we must demonstrate a successful distinguishing attack.

Attacking a PRG amounts to finding "patterns" in their outputs. Does \(H_{2}\) have a pattern in its outputs? Yes, in this case the pattern is that if you write the output in the form \(x\|y\| u \| v\), then \(u \| v\) is always equal to \(G(y)\). The calling program can check for this condition, which is unlikely to happen for truly uniform values.

You may wonder, is it legal for the calling program to compute \(G(y)\) ? Well, \(G\) is a publicly known algorithm (Kerckhoffs’ principle!), and \(y\) is right there as part of the input. Nothing prevents the calling program from running \(G\) "in its head".

Claim 5.6 Construction \(\mathrm{H}_{2}\) is not a secure \(P R G\), even if \(G\) is.

Proof Consider the following distinguisher \(\mathcal{A}\) : \[\begin{aligned} &x\|y\| u \| v:=\text { QUERY }() \\ &\text { return } G(y) \stackrel{?}{=} u \| v \end{aligned}\] When \(\mathcal{A}\) is linked to \(\mathcal{L}_{\text {prg-real }}^{H_{2}}\), the outputs indeed satisfy the condition \(G(y)=u \| v\), so \(\mathcal{A}\) outputs true with probability \(1 .\)

When \(\mathcal{A}\) is linked to \(\mathcal{L}_{\text {prg-rand }}^{H_{2}}\), the outputs are truly uniform. It is helpful to imagine \(x\) and \(y\) being chosen before \(u\) and \(v\). As soon as \(y\) is chosen, the value \(G(y)\) is uniquely determined, since \(G\) is a deterministic algorithm. Then \(\mathcal{A}\) will output true if \(u \| v\) is chosen exactly to equal this \(G(y)\). Since \(u\) and \(v\) are chosen uniformly, and are a total of \(2 \kappa\) bits long, this event happens with probability \(1 / 2^{2 \kappa}\).

\(\mathcal{A}\) ’s advantage is the difference in these probabilities: \(1-1 / 2^{2 \kappa}\), which is nonnegligible.

Discussion

In the attack on \(\mathrm{H}_{2}\), we never tried to distinguish the output of \(G\) from uniform. \(\mathrm{H}_{2}\) is insecure even if \(G\) is the best PRG in the world! It’s insecure because of the incorrect way it uses \(G\).

From now on in this book, we’ll be studying higher-level constructions that are assembled from various building blocks \(-\) in this chapter, fancy PRGs constructed from simpler PRGs. "Security" means: if the building blocks are secure then the construction is secure. "Insecurity" means: even if the building blocks are secure, the construction can be insecure. So when you’re showing insecurity, you shouldn’t directly attack the building blocks! You should assume the building blocks are secure and attack the way that the building blocks are being used.

\({ }^{4}\) Compare to the case of distinguishing \(G(s)\) from uniform, for a secure \(G\). The calling program knows the algorithm \(G\) but doesn’t have the seed \(s-\) it only knows the output \(G(s)\). In the case of \(H_{2}\), the calling program learns both \(y\) and \(G(y)\) !

* \(5.5\) Applications: Stream Cipher & Symmetric Ratchet

The PRG-feedback construction can be generalized in a natural way, by continuing to feed part of \(G\) ’s output into \(G\) again. The proof works in the same way as for the previous construction \(-\) the security of \(G\) is applied one at a time to each application of \(G\).

Claim 5.7 If \(G\) is a secure length-doubling \(P R G\), then for any \(n\) (polynomial function of \(\lambda\) ) the following construction \(H_{n}\) is a secure PRG with stretch \(n \lambda\) :

The fact that this chain of PRGs can be extended indefinitely gives another useful functionality:

Definition 5.8 A stream cipher is an algorithm \(G\) that takes a seed s and length \(\ell\) as input, and outputs a (Stream cipher) string. It should satisfy the following requirements:

1. \(G(s, \ell)\) is a string of length \(\ell\).
2. If \(i<j\), then \(G(s, i)\) is a prefix of \(G(s, j)\).
3. For each \(n\), the function \(G(\cdot, n)\) is a secure \(P R G\).

Because of the 2 nd rule, you might want to think about a single infinitely long string that is the limit of \(G(s, n)\) as \(n\) goes to infinity. The finite-length strings \(G(s, n)\) are all the prefixes of this infinitely long string.

The PRG-feedback construction can be used to construct a secure stream cipher in the natural way: given seed \(s\) and length \(\ell\), keep iterating the PRG-feedback main loop until \(\ell\) bits have been generated.

Symmetric Ratchet

Suppose Alice & Bob share a symmetric key \(k\) and are using a secure messaging app to exchange messages over a long period of time. Later in the course we will see techniques that Alice & Bob could use to securely encrypt many messages using a single key. However, suppose Bob’s device is compromised and an attacker learns \(k\). Then the attacker can decrypt all past, present, and future ciphertexts that it saw! Alice & Bob can protect against such a key compromise by using the PRG-feedback stream cipher to constantly "update" their shared key. Suppose they do the following, starting with their shared key \(k\) :

• They use \(k\) to seed a chain of length-doubling PRGs, and both obtain the same stream of pseudorandom keys \(t_{1}, t_{2}, \ldots\)
• They use \(t_{i}\) as a key to send/receive the \(i\) th message. The details of the encryption are not relevant to this example.
• After making a call to the PRG, they erase the \(P R G\) input from memory, and only remember the PRG’s output. After using \(t_{i}\) to send/receive a message, they also erase it from memory.

This way of using and forgetting a sequence of keys is called a symmetric ratchet.

Construction \(5.9\) (Symm Ratchet)

Suppose that an attacker compromises Bob’s device after \(n\) ciphertexts have been sent. The only value residing in memory is \(s_{n}\), which the attacker learns. Since \(G\) is deterministic, the attacker can now compute \(t_{n+1}, t_{n+2}, \ldots\) in the usual way and decrypt all future ciphertexts that are sent.

However, we can show that the attacker learns no information about \(t_{1}, \ldots, t_{n}\) from \(s_{n}\), which implies that the previous ciphertexts remain safe. By compromising the key \(s_{n}\), the adversary only compromises the security of future messages, but not past messages. Sometimes this property is called forward secrecy, meaning that messages in the present are protected against a key-compromise that happens in the future.

This construction is called a ratchet, since it is easy to advance the key sequence in the forward direction (from \(s_{n}\) to \(s_{n+1}\) ) but hard to reverse it (from \(s_{n+1}\) to \(s_{n}\) ). The exercises explore the problem of explicitly reversing the ratchet, but the more relevant property for us is whether the attacker learns anything about the ciphertexts that were generated before the compromise.

Claim 5.10 If the symmetric ratchet (Construction 5.9) is used with a secure PRG \(G\) and an encryption scheme \(\sum\) that has uniform ciphertexts (and \(\left.\sum . \mathcal{K}=\{0,1\}^{\lambda}\right)\), then the first \(n\) ciphertexts are pseudorandom, even to an eavesdropper who compromises the key \(s_{n}\).

Proof We are considering an attack scenario in which \(n\) plaintexts are encrypted, and the adversary sees their ciphertexts as well as the ratchet-key \(s_{n}\). This situation is captured by the following library:

As we have seen, the shaded box (the process that computes \(t_{1}, \ldots, t_{n}\) from \(s_{0}\) ) is actually a PRG. Let us rewrite the library in terms of this \(\mathrm{PRG} H_{n}\) :

Now, we can apply the PRG security of \(H_{n}\) and instead choose \(t_{1}, \ldots, t_{n}\) and \(s_{n}\) uniformly. This change is indistinguishable, by the security of the PRG. Note that we have not written out the standard explicit steps (factor out the first two lines of ATTACK in terms of \(\mathcal{L}_{\text {prg-real }}\), replace with \(\mathcal{L}_{\text {prg-rand, }}\), and inline).

At this point, the encryption scheme is being used "as intended" meaning that we generate its keys \(t_{i}\) uniformly/indepenendtly, and use each key only for one encryption and nothing else. Formally speaking, this means we can factor out the body of the for-loop in terms of \(\mathcal{L}_{\text {ots } \$-r e a l:}\)
We can now replace \(\mathcal{L}_{\text {ots\$-real with }} \mathcal{L}_{\text {ots\$-rand }}\) and inline the subroutine (without showing the intermediate library). The result is:

This final library is indistinguishable from the first one. As promised, we showed that the attacker cannot distinguish the first \(n\) ciphertexts from random values, even when seeing \(s_{n}\).

This proof used the uniform-ciphertexts property, but the same logic applies to basically any encryption property you care about - just imagine factoring out the encryption steps in terms of a different library than \(\mathcal{L}_{\text {ots\$-real. }}\).

Pseudorandom Functions & Block Ciphers

Imagine if Alice & Bob had an infinite amount of shared randomness - not just a short key. They could split it up into \(\lambda\)-bit chunks and use each one as a one-time pad whenever they want to send an encrypted message of length \(\lambda\).

Alice could encrypt by saying, "hey Bob, this message is encrypted with one-time pad using chunk #674696273 as key." Bob could decrypt by looking up location #674696273 in his copy of the shared randomness. As long as Alice doesn’t repeat a key/chunk, an eavesdropper (who doesn’t have the shared randomness) would learn nothing about the encrypted messages. Although Alice announces (publicly) which location/chunk was used as each one-time pad key, that information doesn’t help the attacker know the value at that location.

It is silly to imagine an infinite amount of shared randomness. However, an exponential amount of something is often just as good as an infinite amount. A shared table containing "only" \(2^{\lambda}\) one-time pad keys would be quite useful for encrypting as many messages as you could ever need.

A pseudorandom function (PRF) is a tool that allows Alice & Bob to achieve the effect of such an exponentially large table of shared randomness in practice. In this chapter we will explore PRFs and their properties. In a later chapter, after introducing new security definitions for encryption, we will see that PRFs can be used to securely encrypt many messages under the same key, following the main idea illustrated above.

Discussion, Pitfalls

The name "pseudorandom function" comes from the perspective of viewing \(T\) not as an (associative) array, but as a function \(T:\{0,1\}^{\text {in }} \rightarrow\{0,1\}^{\text {out }}\). There are \(2^{\text {out } \cdot 2^{\text {in }} \text { possible }}\) functions for \(T\) (an incredibly large number), and \(\mathcal{L}_{\text {prf-rand }}\) chooses a "random function" by uniformly sampling its truth table as needed.

For each possible seed \(k\), the residual function \(F(k, \cdot)\) is also a function from \(\{0,1\}^{i n} \rightarrow\) \(\{0,1\}^{\text {out }}\). There are "only" \(2^{\lambda}\) possible functions of this kind (one for each choice of \(k\) ), and \(\mathcal{L}_{\text {prf-real }}\) chooses one of these functions randomly. In both cases, the libraries give the calling program input/output access to the function that was chosen. You can think of this in terms of the picture from Section 5.1, but instead of strings, the objects are functions.

Note that even in the case of a "random function" \(\left(\mathcal{L}_{\text {prf-rand }}\right)\), the function \(T\) itself is still deterministic! To be precise, this library chooses a deterministic function, uniformly, from the set of all possible deterministic functions. But once it makes this choice, the input/output behavior of \(T\) is fixed. If the calling program calls LOOKUP twice with the same \(x\), it receives the same result. The same is true in \(\mathcal{L}_{\text {prf-real }}\), since \(F\) is a deterministic function and \(k\) is fixed throughout the entire execution. To avoid this very natural confusion, it is perhaps better to think in terms of "randomly initialized lookup tables" rather than "random functions."

How NOT to Build a PRF

We can appreciate the challenges involved in building a PRF by looking at a natural approach that doesn’t quite work.

Example Suppose we have a length-doubling \(P R G G:\{0,1\}^{\lambda} \rightarrow\{0,1\}^{2 \lambda}\) and try to use it to construct a PRF F as follows: \[\frac{F(k, x):}{\text { return }} G(k) \oplus x\] You might notice that all we have done is rename the encryption algorithm of "pseudo-OTP" (Construction 5.2). We have previously argued that this algorithm is a secure method for onetime encryption, and that the resulting ciphertexts are pseudorandom. Is this enough for a secure PRF? No, we can attack the security of this PRF. Attacking \(F\) means designing distinguisher that behaves as differently as possible in the presence of the two \(\mathcal{L}_{\mathrm{prf}-\star}^{F}\) libraries. We want to show that \(F\) is insecure even if \(G\) is an excellent PRG. We should not try to base our attack on distinguishing outputs of \(G\) from random. Instead, we must try to break the inappropriate way that \(G\) is used to construct a PRF.

The distinguisher must use the interface of the \(\mathcal{L}_{\mathrm{prf}-\star}\) libraries \(-\mathrm{i}\).e., make some calls to the LOOKUP subroutine and output 0 or 1 based on the answers it gets. The LOOKUP subroutine takes an argument, so the distinguisher has to choose which arguments to use.

One observation we can make is that if a calling program sees only one value of the form \(G(k) \oplus x\), it will look pseudorandom. This is essentially what we showed in Section 5.3. So we should be looking for a calling program that makes more than one call to LOOKUP.

If we make two calls to LOOKUP - say, on inputs \(x_{1}\) and \(x_{2}-\) the responses from \(\mathcal{L}_{\text {prf-real }}\) will be \(G(k) \oplus x_{1}\) and \(G(k) \oplus x_{2}\). To be a secure PRF, these responses must look independent and uniform. Do they? They actually have a pattern that the calling program can notice: their XOR is always \(x_{1} \oplus x_{2}\), a value that is already known to the calling program.

We can condense all of our observations into the following distinguisher:

\(\mathbb{A}\)
pick \(x_{1}, x_{2} \in\{0,1\}^{2 \lambda}\) arbitrarily so that \(x_{1} \neq x_{2}\)
\(z_{1}:=\operatorname{LOOKUP}\left(x_{1}\right)\)
\(z_{2}:=\operatorname{LOOKUP}\left(x_{2}\right)\)
return \(z_{1} \oplus z_{2} \stackrel{?}{=} x_{1} \oplus x_{2}\)

Let’s compute its advantage in distinguishing \(\mathcal{L}_{\mathrm{prf}-\mathrm{real}}^{F}\) from \(\mathcal{L}_{\mathrm{prf}-\mathrm{rand}}^{F}\) by considering \(\mathcal{A}\) ’s behavior when linked to these two libraries:

\(\quad \diamond \mid\)

l \(\mathcal{L}_{\text {prf-real }}^{F}\)

When \(\mathcal{A}\) is linked to \(\mathcal{L}_{\mathrm{prf}-\mathrm{real}}^{F}\), the library will choose a key \(k\). Then \(z_{1}\) is set to \(G(k) \oplus x_{1}\) and \(z_{2}\) is set to \(G(k) \oplus x_{2}\). So \(z_{1} \oplus z_{2}\) is always equal to \(x_{1} \oplus x_{2}\), and \(\mathcal{A}\) always outputs 1 . That is, \[\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {prf-real }}^{F} \Rightarrow 1\right]=1\]

When \(\mathcal{A}\) is linked to \(\mathcal{L}_{\text {prf-rand }}^{F}\), the responses of the two calls to LOOKUP will be chosen uniformly and independently because LOOKUP is being called on distinct inputs. Consider the moment in time when the second call to LOOKUP is about to happen. At that point, \(x_{1}, x_{2}\), and \(z_{1}\) have all been determined, while \(z_{2}\) is about to be chosen uniformly by the library. Using the properties of XOR, we see that \(\mathcal{A}\) will output 1 if and only if \(z_{2}\) is chosen to be exactly the value \(x_{1} \oplus x_{2} \oplus z_{1}\). This happens only with probability \(1 / 2^{2 \lambda}\). That is, \[\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {prf-rand }}^{F} \Rightarrow 1\right]=1 / 2^{2 \lambda}\] The advantage of \(\mathcal{A}\) is therefore \(1-1 / 2^{2 \lambda}\) which is certainly non-negligible since it doesn’t even approach 0. This shows that \(F\) is not a secure PRF.

At a more philosophical level, we wanted to identify exactly how \(G\) is being used in an inappropriate way. The PRG security libraries guarantee security when \(G\) ’s seed is chosen freshly for each call to \(G\). This construction of \(F\) violates that rule and allows the same seed to be used twice in different calls to \(G\), where the results are supposed to look independent.

This example shows the challenge of building a PRF. Even though we know how to make any individual output pseudorandom, it is difficult to make all outputs collectively appear independent, when in reality they are derived from a single short seed.

Constructing a PRG from a PRF

As promised, a PRF can be used to construct a PRG. The construction is quite natural. For simplicity, suppose we have a PRF \(F:\{0,1\}^{\lambda} \times\{0,1\}^{\lambda} \rightarrow\{0,1\}^{\lambda}(\) i.e., in \(=\) out \(=\lambda)\). We can build a length-doubling PRG in the following way:

Construction \(6.2\)

(Counter PRG)

There is nothing particularly special about the inputs \(0 \cdots 00\) and \(0 \cdots 01\) to \(F\). All that matters is that they are distinct. The construction can be extended to easily give more than 2 blocks of output, by treating the input to \(F\) as a simple counter (hence the name of this construction).

The guarantee of a PRF is that when its seed is chosen uniformly and it is invoked on distinct inputs, its outputs look independently uniform. In particular, its output on inputs \(0 \cdots 00\) and \(0 \cdots 01\) are indistinguishable from uniform. Hence, concatenating them gives a string which is indistinguishable from a uniform \(2 \lambda\)-bit string. That really is all there is to the security of this construction, but unfortunately there is a slight technical issue which makes the security proof more complicated than you might guess. We will have to introduce a new technique of variable hybrids to cope with it.

Claim 6.3 If \(F\) is a secure PRF, then the counter PRG construction \(G\) above is a secure PRG.

Proof In order to prove that \(G\) is a secure PRG, we must prove that the following libraries are indistinguishable:

During the proof, we are allowed to use the fact that \(F\) is a secure PRF. That is, we can use the fact that the following two libraries are indistinguishable:

The inconvenience in the proof stems from a mismatch of the \(s\) variable in \(\mathcal{L}_{\text {prg-real and }}\) the \(k\) variable in \(\mathcal{L}_{\text {prf-real. }}\) In \(\mathcal{L}_{\text {prg-real, }} s\) is local to the QUERY subroutine. Over the course of an execution, \(s\) will take on many values. Since \(s\) is used as the PRF seed, we must write the calls to \(F\) in terms of the LOOKUP subroutine of \(\mathcal{L}_{\text {prf-real. }}\). But in \(\mathcal{L}_{\text {prf-real }}\) the PRF seed is fixed for the entire execution. In other words, we can only use \(\mathcal{L}_{\text {prf-real }}\) to deal with a single PRF seed at a time, but \(\mathcal{L}_{\text {prg-real }}\) deals with many PRG seeds at a time.

To address this, we will have to apply the security of \(F\) (i.e., replace \(\mathcal{L}_{\text {prf-real }}\) with \(\mathcal{L}_{\text {prf-rand }}\) ) many times during the proof - in fact, once for every call to QUERY made by the calling program. Previous security proofs had a fixed number of hybrid steps (e.g., the proof of Claim \(5.5\) used 7 hybrid libraries to show \(\mathcal{L}_{\text {prg-real }} \approx \mathcal{L}_{\text {hyb-1 }} \approx \cdots \approx \mathcal{L}_{\text {hyb-7 }} \approx\) \(\mathcal{L}_{\text {prg-rand }}\) ). This proof will have a variable number of hybrids that depends on the calling program. Specifically, we will prove \[\mathcal{L}_{\text {prg-real }}^{G} \approx \mathcal{L}_{\text {hyb-1 }} \approx \ldots \approx \mathcal{L}_{\text {hyb- } q} \approx \mathcal{L}_{\text {prg-rand }}^{G}\] where \(q\) is the number of times the calling program calls QUERY.

\(\mathcal{L}_{\text {prf-real }}^{F}\)
\(k \leftarrow\{0,1\}^{\lambda}\)
\(\frac{\operatorname{LOOKUP}\left(x \in\{0,1\}^{i n}\right):}{\operatorname{return} F(k, x)}\)

\(\mathcal{L}_{\text {prf-rand }}^{F}\)
\(T:=\) empty assoc. array
\(\frac{\text { LOOKUP }\left(x \in\{0,1\}^{i n}\right):}{\text { if } T[x] \text { undefined: }}\)
\(T[x] \leftarrow\{0,1\}^{\text {out }}\)
return \(T[x]\)

Don’t be overwhelmed by all these hybrids. They all follow a simple pattern. In fact, the \(i\) th hybrid looks like this:

In other words, the hybrid libraries all differ in the value \(i\) that is inserted into the code above. If you’re familiar with C compilers, think of this as adding "#define i 427 " to the top of the code above, to obtain \(\mathcal{L}_{\text {hyb-427 }}\)

First note what happens for extreme choices of \(i\) :

• In \(\mathcal{L}_{\text {hyb- } 0}\), the if-branch is never taken (count \(\leqslant 0\) is never true). This library behaves exactly like \(\mathcal{L}_{\mathrm{prg} \text {-real }}^{G}\) by giving PRG outputs on every call to QUERY.
• If \(q\) is the total number of times that the calling program calls QUERY, then in \(\mathcal{L}_{\text {hyb- } q \text {, }}\), the if-branch is always taken (count \(\leqslant q\) is always true). This library behaves exactly like \(\mathcal{L}_{\text {prg-rand }}^{G}\) by giving truly uniform output on every call to QUERY.

In general, \(\mathcal{L}_{\mathrm{hyb}-i}\) will respond to the first \(i\) calls to QUERY by giving truly random output. It will respond to all further calls by giving outputs of our PRG construction.

We have argued that \(\mathcal{L}_{\text {prg-real }}^{G} \equiv \mathcal{L}_{\text {hyb-0 }}\) and \(\mathcal{L}_{\text {prg-rand }}^{G} \equiv \mathcal{L}_{\text {hyb-q }}\). To complete the proof, we must show that \(\mathcal{L}_{\mathrm{hyb}-(i-1)} \approx \mathcal{L}_{\mathrm{hyb}-i}\) for all \(i\). The main reason for going to all this trouble of defining so many hybrid libraries is that \(\mathcal{L}_{\text {hyb- }(i-1)}\) and \(\mathcal{L}_{\text {hyb- } i}\) are completely identical except in how they respond to the \(i\) th call to QUERY. This difference involves a single call to the PRG (and hence a single PRF seed), which allows us to apply the security of the PRF.

In more detail, let \(i\) be arbitrary, and consider the following sequence of steps starting with \(\mathcal{L}_{\text {hyb-( }(i-1)}\) :

We have taken \(\mathcal{L}_{\text {hyb- }(i-1)}\) and simply expanded the else-branch (count \(\geqslant i\) ) into two subcases \((\) count \(=i\) and count \(>i\) ). However, both cases lead to the same block of code (apart from a change to a local variable’s name), so the change has no effect on the calling program.

We have factored out the calls to \(F\) that use seed \(s^{*}\) (corresponding to the count \(=i\) case) in terms of \(\mathcal{L}_{\text {prf-real. This }}\) change no effect on the calling program.

Since count \(=i\) happens only once, only two calls to LOOKUP will be made across the entire lifetime of the library, and they are on distinct inputs. Therefore, the if-branch in LOOKUP will always be taken, and \(T\) is never needed (it is only needed to "remember" values and give the same answer when the same \(x\) is used twice as argument to LOOKUP). Simplifying the library therefore has no effect on the calling program:

Inlining the subroutine has no effect on the calling program. The resulting library responds with uniformly random output to the first \(i\) calls to QUERY, and responds with outputs of our PRG \(G\) to the others. Hence, this library has identical behavior to \(\mathcal{L}_{\text {hyb-i }}\)

We showed that \(\mathcal{L}_{\mathrm{hyb}-(i-1)} \approx \mathcal{L}_{\mathrm{hyb}-i}\), and therefore: \[\mathcal{L}_{\text {prg-real }}^{G} \equiv \mathcal{L}_{\text {hyb-0 }} \approx \mathcal{L}_{\text {hyb-1 }} \approx \ldots \approx \mathcal{L}_{\text {hyb-q }} \equiv \mathcal{L}_{\text {prg-rand }}^{G}\] This shows that \(\mathcal{L}_{\mathrm{prg}-\mathrm{real}}^{G} \approx \mathcal{L}_{\mathrm{prg} \text {-rand }}^{G}\), so \(G\) is a secure \(\mathrm{PRG}\)

A Theoretical Construction of a PRF from a PRG

We have already seen that it is possible to feed the output of a PRG back into the PRG again, to extend its stretch (Claim 5.7). This is done by making a long chain (like a linked list) of PRGs. The trick to constructing a PRF from a PRG is to chain PRGs together in a binary tree (similar to Exercise \(5.8(\mathrm{a}))\). The leaves of the tree correspond to final outputs of the PRF. If we want a PRF with an exponentially large domain (e.g., in \(=\lambda)\), the binary tree itself is exponentially large! However, it is still possible to compute any individual leaf efficiently by simply traversing the tree from root to leaf. This tree traversal itself is the PRF algorithm. This construction of a PRF is due to Goldreich, Goldwasser, and Micali, in the paper that defined the concept of a PRF.

Imagine a complete binary tree of height in (in will be the input length of the PRF). Every node in this tree has a position which can be written as a binary string. Think of a node’s position as the directions to get there starting at the root, where a 0 means "go left" and 1 means "go right." For example, the root has position \(\epsilon\) (the empty string), the right child of the root has position 1 , etc.

The PRF construction works by assigning a label to every node in the tree, using the a length-doubling PRG \(G:\{0,1\}^{\lambda} \rightarrow\{0,1\}^{2 \lambda}\). For convenience, we will write \(G_{L}(k)\) and \(G_{R}(k)\) to denote the first \(\lambda\) bits and last \(\lambda\) bits of \(G(k)\), respectively. Labels in the tree are \(\lambda\)-bit strings, computed according to the following two rules:

1. The root node’s label is the PRF seed.
2. If the node at position \(p\) has label \(v\), then its left child (at position \(p \| \theta\) ) gets label \(G_{L}(v)\), and its right child (at position \(p \| 1\) ) gets label \(G_{R}(v)\).

In the picture above, a node’s label is the string being sent on its incoming edge. The tree has \(2^{\text {in }}\) leaves, whose positions are the strings \(\{0,1\}^{i n}\). We define \(F(k, x)\) to be the label of node/leaf \(x\). To compute this label, we can traverse the tree from root to leaf, taking left and right turns at each node according to the bits of \(x\) and computing the labels along that path according to the labeling rule. In the picture above, the highlighted path corresponds to the computation of \(F(k, 1001 \cdots)\).

It is important to remember that the binary tree is a useful conceptual tool, but it is exponentially large in general. Running the PRF on some input does not involve computing labels for the entire tree, only along a single path from root to leaf.

Construction \(6.4\)

(GGM PRF)

Claim 6.5 If \(G\) is a secure PRG, then Construction \(6.4\) is a secure PRF.

Proof We prove the claim using a sequence of hybrids. The number of hybrids in this case depends on the input-length parameter in. The hybrids are defined as follows:

\(\mathcal{L}_{\text {hyb-d }}\)
\(T:=\) empty assoc. array
QUERY \((x):\)
\(\frac{p:=\text { first }}{d}\) bits of \(x\)
if \(T[p]\) undefined:
\(T[p] \leftarrow\{0,1\}^{\lambda}\)
\(v:=T[p]\)
for \(i=d+1\) to in:
if \(x_{i}=0\) then \(v:=G_{L}(v)\)
if \(x_{i}=1\) then \(v:=G_{R}(v)\)
return \(v\)

The hybrids differ only in their hard-coded value of \(d\). We will show that \[\mathcal{L}_{\text {prf-real }}^{F} \equiv \mathcal{L}_{\text {hyb-0 }} \approx \mathcal{L}_{\text {hyb-1 }} \approx \cdots \approx \mathcal{L}_{\text {hyb-in }} \equiv \mathcal{L}_{\text {prf-rand }}^{F}\] We first start by understanding the behavior of \(\mathcal{L}_{\text {hyb- } d}\) for extreme choices of \(d\). Simplifications to the code are shown on the right.

In \(\mathcal{L}_{\text {hyb-0 }}\), we always have \(p=\epsilon\), so the only entry of \(T\) that is accessed is \(T[\epsilon]\). Then renaming \(T[\epsilon]\) to \(k\), we see that \(\mathcal{L}_{\text {hyb- } 0} \equiv\) \(\mathcal{L}_{\text {prf-real }}^{F}\). The only difference is when the PRF seed \(k(T[\epsilon])\) is sampled: eagerly at initialization time in \(\mathcal{L}_{\text {prf-real }}^{F}\) vs. at the last possible minute in \(\mathcal{L}_{\text {hyb- } 0}\).

In \(\mathcal{L}_{\text {hyb-in, we always have } p=}\) \(x\) and the body of the forloop is always unreachable. In that case, it is easy to see that \(\mathcal{L}_{\text {hyb-in }}\) has identical behavior to \(\mathcal{L}_{\text {prf-rand }}^{F}\)

The general pattern is that \(\mathcal{L}_{\text {hyb- } d}\) "chops off" the top \(d\) levels of the conceptual binary tree. When computing the output for some string \(x\), we don’t start traversing the tree from the root but rather \(d\) levels down the tree, at the node whose position is the \(d\)-bit prefix of \(x\) (called \(p\) in the library). We initialize the label of this node as a uniform value (unless it has already been defined), and then continue the traversal to the leaf \(x\).

To finish the proof, we show that \(\mathcal{L}_{\text {hyb- }(d-1)}\) and \(\mathcal{L}_{\text {hyb- } d}\) are indistinguishable:

\(T:=\) empty assoc. array

\(\operatorname{LOOKUP}(x)\)

\(p:=\) first \(d-1\) bits of \(x\) if \(T[p]\) undefined:

\(T[p] \leftarrow\{0,1\}^{\lambda}\)

\(T[p \| \mathcal{0}]:=G_{L}(T[p])\)

\(T[p \| 1]:=G_{R}(T[p])\)

\(p^{\prime}:=\) first \(d\) bits of \(x\)

\(v:=T\left[p^{\prime}\right]\)

for \(i=d+1\) to in:

if \(x_{i}=0\) then \(v:=G_{L}(v)\)

if \(x_{i}=1\) then \(v:=G_{R}(v)\) return \(v\) The library that is shown here is different from \(\mathcal{L}_{\text {hyb- }(d-1)}\) in the highlighted parts. However, these dif ferences have no effect on the calling program. The library here advances \(d-1\) levels down the tree (to the node at location \(p\) ), initializes that node’s label as a uniform value, then computes the labels for both its children, and finally continues computing labels toward the leaf. The only significant difference from \(\left.\mathcal{L}_{\mathrm{hyb}-(} d-1\right)\) is that it computes the labels of both of \(p\) ’s children, even though only one is on the path to \(x\). Since it computes the label correctly, though, it makes no difference when (or if) this extra label is computed. \(T:=\) empty assoc. array

\(\operatorname{LOOKUP}(x)\)

\(p:=\) first \(d-1\) bits of \(x\) if \(T[p]\) undefined:

\(T[p \| \theta] \| T[p \| 1]:=\operatorname{QUERY}()\)

\(p^{\prime}:=\) first \(d+1\) bits of \(x\)

\(v:=T\left[p^{\prime}\right]\)

for \(i=d+1\) to \(i n\) :

if \(x_{i}=0\) then \(v:=G_{L}(v)\)

if \(x_{i}=1\) then \(v:=G_{R}(v)\)

return \(v\)

\(T:=\) empty assoc. array

\(\operatorname{LOOKUP}(x)\)

\(p:=\) first \(d-1\) bits of \(x\) if \(T[p]\) undefined:

\(T[p \| \odot] \| T[p \| 1]:=\operatorname{Query}()\)

\(p^{\prime}:=\) first \(d+1\) bits of \(x\)

\(v:=T\left[p^{\prime}\right]\)

for \(i=d+1\) to \(i n\) :

if \(x_{i}=0\) then \(v:=G_{L}(v)\)

if \(x_{i}=1\) then \(v:=G_{R}(v)\)

return \(v\) We have factored out the body of the if-statement in terms of \(\mathcal{L}_{\mathrm{prg}-\mathrm{real}}^{G}\) since it involves an call to \(G\) on uniform input. Importantly, the seed to \(G\) (called \(T[p]\) in the previous hybrid) was not used anywhere else - it was a string of length \(d-1\) while the library only reads \(T\left[p^{\prime}\right]\) for \(p^{\prime}\) of length \(d\). The change has no effect on the calling program.

We have applied the security of \(G\) and replaced \(\mathcal{L}_{\text {prg-real with }}\) \(\mathcal{L}_{\text {prg-rand. }}\). The change is indistinguishable. Hence, \(F\) is a secure PRF.

Discussion, Pitfalls

In the definition, both the functions \(F\) and \(F^{-1}\) take the seed \(k\) as input. Therefore, only someone with \(k\) can invert the block cipher. Think back to the definition of a PRF without the seed \(k\), it is hard to compute \(F(k, x)\). A block cipher has a forward and reverse direction, and computing either of them is hard without \(k\) !

Switching Lemma (PRPs are PRFs, Too!)

Imagine you can query a PRP on chosen inputs (as in the \(\mathcal{L}_{\text {prp-real }}\) library), and suppose the blocklength of the PRP is blen \(=\lambda\). You would only be able to query that PRP on a negligible fraction of its exponentially large input domain. It seems unlikely that you would even be able to tell that it was a PRP (i.e., an invertible function) rather than a PRF (an unrestricted function).

This idea can be formalized as follows.

Lemma 6.7 Let \(\mathcal{L}_{\text {prf-rand }}\) and \(\mathcal{L}_{\text {prp-rand }}\) be defined as in Definitions \(6.1 \&\) 6.6, with parameters in \(=\) out \(=\) (PRP switching) blen \(=\lambda\) (so that the interfaces match up). Then \(\mathcal{L}_{\text {prf-rand }} \approx \mathcal{L}_{\text {prp-rand }}\).

Proof Recall the replacement-sampling lemma, Lemma 4.11, which showed that the following libraries are indistinguishable:

ment. Now consider the following library \(\mathcal{L}^{*}\) :

\(\mathcal{L}^{*}\)
\(T:=\) empty assoc. array
\(\frac{\text { LOOKUP }\left(x \in\{0,1\}^{\lambda}\right):}{\text { if } T[x] \text { undefined: }}\)
\(T[x] \leftarrow \operatorname{sAmP}()\)
return \(T[x]\)

When we link \(\mathcal{L}^{*} \diamond \mathcal{L}_{\text {samp-L }}\) we obtain \(\mathcal{L}_{\text {prf-rand }}\) since the values in \(T[x]\) are sampled uniformly. When we link \(\mathcal{L}^{*} \diamond \mathcal{L}_{\text {samp-R }}\) we obtain \(\mathcal{L}_{\text {prp-rand }}\) since the values in \(T[x]\) are sampled uniformly subject to having no repeats (consider \(R\) playing the role of \(T\).values in \(\mathcal{L}_{\text {prp-rand }}\) ). Then from Lemma 4.11, we have: \[\mathcal{L}_{\text {prf-rand }} \equiv \mathcal{L}^{*} \diamond \mathcal{L}_{\text {samp-L }} \approx \mathcal{L}^{*} \diamond \mathcal{L}_{\text {samp-R }} \equiv \mathcal{L}_{\text {prp-rand }}\] which completes the proof.

Using the switching lemma, we can conclude that every PRP (with blen \(=\lambda\) ) is also a PRF:

Corollary \(6.8\) Let \(F:\{0,1\}^{\lambda} \times\{0,1\}^{\lambda} \rightarrow\{0,1\}^{\lambda}\) be a secure PRP (with blen \(\left.=\lambda\right)\). Then \(F\) is also a secure \(P R F\)

Proof As we have observed above, \(\mathcal{L}_{\text {prf-real }}^{F}\) and \(\mathcal{L}_{\text {prp-real }}^{F}\) are literally the same library. Since \(F\) is a secure PRP, \(\mathcal{L}_{\text {prp-real }}^{F} \approx \mathcal{L}_{\text {prp-rand }}^{F}\). Finally, by the switching lemma, \(\mathcal{L}_{\text {prp-rand }}^{F} \approx \mathcal{L}_{\mathrm{prf}-\mathrm{rand}}^{F}\). Putting everything together: \[\mathcal{L}_{\text {prf-real }}^{F} \equiv \mathcal{L}_{\text {prp-real }}^{F} \approx \mathcal{L}_{\text {prp-rand }}^{F} \approx \mathcal{L}_{\text {prf-rand }}^{F}\] hence \(F\) is a secure PRF.

Keep in mind that the switching lemma applies only when the blocklength is sufficiently large (at least \(\lambda\) bits long). This comes from the fact that \(\mathcal{L}_{\text {samp-L }}\) and \(\mathcal{L}_{\text {samp-R }}\) in the proof are indistinguishable only when sampling with long (length- \(\lambda\) ) strings (look at the proof of Lemma \(4.11\) to recall why). Exercise \(6.14\) asks you to show that a random permutation over a small domain can be distinguished from a random (unconstrained) function; so, a PRP with a small blocklength is not a PRF.

Constructing a PRP from a PRF: The Feistel Construction

How can you build an invertible block cipher out of a PRF that is not necessarily invertible? In this section, we show a simple technique called the Feistel construction (named after IBM cryptographer Horst Feistel).

The main idea in the Feistel construction is to convert a not-necessarily-invertible function \(F:\{0,1\}^{n} \rightarrow\{0,1\}^{n}\) into an invertible function \(F^{*}:\{0,1\}^{2 n} \rightarrow\{0,1\}^{2 n}\). The function \(F^{*}\) is called the Feistel round with round function \(F\) and is defined as follows:

Construction \(6.9\)

(Feistel round)

\[\frac{F^{*}(x \| y):}{/ / e a c h}\] \[\begin{aligned} & \text { return } y \|(F(y) \oplus x) \end{aligned}\]

No matter what \(F\) is, its Feistel round \(F^{*}\) is invertible. Not only that, but its inverse is a kind of "mirror image" of \(F^{*}\) :

Note how both the forward and inverse Feistel rounds use \(F\) in the forward direction!

Example Let’s see what happens in the Feistel construction with a trivial round function. Consider the constant function \(F(y)=0^{n}\), which is the "least invertible" function imaginable. The Feistel construction gives: \[\begin{aligned} F^{*}(x \| y) &=y \|(F(y) \oplus x) \\ &=y \|\left(0^{n} \oplus x\right) \\ &=y \| x \end{aligned}\] The result is a function that simply switches the order of its halves - clearly invertible.

Example Let’s try another simple round function, this time the identity function \(F(y)=y\). The Feistel construction gives: \[\begin{aligned} F^{*}(x \| y) &=y \|(F(y) \oplus x) \\ &=y \|(y \oplus x) \end{aligned}\] This function is invertible because given \(y\) and \(y \oplus x\) we can solve for \(x\) as \(y \oplus(y \oplus x)\). You can verify that this is what happens when you plug \(F\) into the inverse Feistel construction.

We can also consider using a round function \(F\) that has a key/seed. The result will be an \(F^{*}\) that also takes a seed. For every seed \(k, F^{*}(k, \cdot)\) will have an inverse (which looks like its mirror image).

Construction \(6.10\)

(Keyed Feistel) \[\frac{F^{*}(k, x \| y):}{\text { return } y \|}(F(k, y) \oplus x)\] Now suppose \(F\) is a secure PRF and we use it as a Feistel round function, to obtain a keyed function \(F^{*}\). Since \(F^{*}(k, \cdot)\) is invertible for every \(k\), and since \(F^{*}\) uses a secure PRF in some way, you might be tempted to claim that \(F^{*}\) is a secure PRP. Unfortunately, it is not! The output of \(F^{*}\) contains half of its input, making it quite trivial to break the PRP-security of \(F^{*}\)

We can avoid this trivial attack by performing several Feistel rounds in succession, resulting in a construction called a Feistel cipher. At each round, we can even use a different key to the round function. If we use \(k_{1}\) in the first round, \(k_{2}\) in the second round, and so on, then \(k_{1}, k_{2}, \ldots\) is called the key schedule of the Feistel cipher. The formal definition of an \(r\)-round Feistel cipher is given below: Construction 6.11

(Feistel cipher)

Theorem \(6.12\) (Luby-Rackoff)

Because each round is invertible (given the appropriate round key), the overall Feistel cipher is also invertible. Note that the inverse of the Feistel cipher uses inverse Feistel rounds and reverses the order of the key schedule.

Surprisingly, a 3-round Feistel cipher can actually be secure, although a 2-round Feistel cipher is never secure (see the exercises). More precisely: when \(F\) is a secure PRF with in \(=\) out \(=\lambda\), then using \(F\) as the round function of a 3-round Feistel cipher results in a secure PRP. The Feistel cipher has blocklength \(2 \lambda\), and it has a key of length \(3 \lambda(3\) times longer than the key for \(F)\). Implicitly, this means that the three round keys are chosen independently.

If \(F:\{0,1\}^{\lambda} \times\{0,1\}^{\lambda} \rightarrow\{0,1\}^{\lambda}\) is a secure \(P R F\), then the 3-round Feistel cipher \(\mathbb{F}_{3}\) (Construction 6.11) is a secure PRP.

Unfortunately, the proof of this theorem is beyond the scope of this book.

\(\star \quad 6.6\) Strong Pseudorandom Permutations

Since a block cipher \(F\) has a corresponding inverse \(F^{-1}\), it is natural to think of \(F\) and \(F^{-1}\) as interchangeable in some sense. However, the PRP security definition only guarantees a security property for \(F\) and not its inverse. In the exercises, you will see that it is possible to construct \(F\) which is a secure PRP, whose inverse \(F^{-1}\) is not a secure PRP!

It would be very natural to ask for a PRP whose \(F\) and \(F^{-1}\) are both secure. We will later see applications where this property would be convenient. An even stronger requirement would allow the distinguisher to query both \(F\) and \(F^{-1}\) in a single interaction (rather than one security definition where the distinguisher queries only \(F\), and another definition where the distinguisher queries only \(F^{-1}\) ). If a PRP is indistinguishable from a random permutation under that setting, then we say it is a strong PRP (SPRP).

In the formal security definition, we provide the calling program \(t\) wo subroutines: one for forward queries and one for reverse queries. In \(\mathcal{L}_{\text {sprp-real }}\), these subroutines are implemented by calling the PRP or its inverse accordingly. In \(\mathcal{L}_{\text {sprp-rand, we emulate the }}\) behavior of a randomly chosen permutation that can be queried in both directions. We maintain two associative arrays \(T\) and \(T_{i n v}\) to hold the truth tables of these permutations, and sample their values on-demand. The only restriction is that \(T\) and \(T_{i n v}\) maintain consistency \(\left(T[x]=y\right.\) if and only if \(\left.T_{i n v}[y]=x\right)\). This also ensures that they always represent an invertible function. We use the same technique as before to ensure invertibility.

\({ }^{3}\) In all fairness, there is a possibility that government agencies like NSA know of weaknesses in many cryptographic algorithms, but keep them secret. I know of a rather famous cryptographer (whom I will not name here) who believes this is likely, based on the fact that NSA has hired more math & cryptography PhDs than have gone on to do public research. Definition 6.13 Let \(F:\{0,1\}^{\lambda} \times\{0,1\}^{\text {blen }} \rightarrow\{0,1\}^{\text {blen }}\) be a deterministic function. We say that \(F\) is a secure (SPRP security) strong pseudorandom permutation \((\boldsymbol{S P R P})\) if \(\mathcal{L}_{\mathrm{sprp}-\mathrm{real}}^{F} \approx \mathcal{L}_{\mathrm{sprp}-\mathrm{rand}}^{F}\), where:

Earlier we showed that using a PRF as the round function in a 3-round Feistel cipher results in a secure PRP. However, that PRP is not a strong PRP. Even more surprisingly, adding an extra round to the Feistel cipher does make it a strong PRP! We present the following theorem without proof:

Theorem 6.14 If \(F:\{0,1\}^{\lambda} \times\{0,1\}^{\lambda} \rightarrow\{0,1\}^{\lambda}\) is a secure PRF, then the 4-round Feistel cipher \(\mathbb{F}_{4}\) (Con(Luby-Rackoff) struction 6.11) is a secure SPRP.

Hint:

\(\star\) (b) Exercise 5.9(b) constructs a secure length-doubling PRG that ignores half of its input. Show that \(F^{\prime}\) is insecure when instantiated with such a PRG. Give a distinguisher and compute its advantage.

Note: You are not attacking the PRF security of \(F\), nor the PRG security of \(G\). You are attacking the invalid way in which they have been combined.

6.5. Let \(F\) be a secure PRF, and let \(m \in\{0,1\}^{i n}\) be a fixed (therefore known to the adversary) string. Define the new function \[F_{m}(k, x)=F(k, x) \oplus F(k, m)\] Show that \(F_{m}\) is not a secure PRF. Describe a distinguisher and compute its advantage.

\(\star\) 6.6. In the previous problem, what happens when \(m\) is secret and part of the PRF seed? Let \(F\) be a secure PRF, and define the new function: Define the new function \[F^{\prime}((k, m), x)=F(k, x) \oplus F(k, m) .\] The seed of \(F^{\prime}\) is \((k, m)\), which you can think of as a \(\lambda+i n\) bit string. Show that \(F^{\prime}\) is indeed a secure PRF.

6.7. Let \(F\) be a secure PRF. Let \(\bar{x}\) denote the bitwise complement of the string \(x\). Define the new function: \[F^{\prime}(k, x)=F(k, x) \| F(k, \bar{x})\] Show that \(F^{\prime}\) is not a secure PRF. Describe a distinguisher and compute its advantage.

6.8. Suppose \(F\) is a secure PRF with input length in, but we want to use it to construct a PRF with longer input length. Below are some approaches that don’t work. For each one, describe a successful distinguishing attack and compute its advantage: (a) \(F^{\prime}\left(k, x \| x^{\prime}\right)=F(k, x) \| F\left(k, x^{\prime}\right)\), where \(x\) and \(x^{\prime}\) are each in bits long.

(b) \(F^{\prime}\left(k, x \| x^{\prime}\right)=F(k, x) \oplus F\left(k, x^{\prime}\right)\), where \(x\) and \(x^{\prime}\) are each in bits long.

(c) \(F^{\prime}\left(k, x \| x^{\prime}\right)=F(k, x) \oplus F\left(k, x \oplus x^{\prime}\right)\), where \(x\) and \(x^{\prime}\) are each in bits long.

(d) \(F^{\prime}\left(k, x \| x^{\prime}\right)=F(k, \vartheta \| x) \oplus F\left(k, 1 \| x^{\prime}\right)\), where \(x\) and \(x^{\prime}\) are each in \(-1\) bits long.

6.9. Define a PRF \(F\) whose key \(k\) we write as \(\left(k_{1}, \ldots, k_{i n}\right)\), where each \(k_{i}\) is a string of length out. Then \(F\) is defined as: \[F(k, x)=\bigoplus_{i: x_{i}=1} k_{i}\] Show that \(F\) is not a secure PRF. Describe a distinguisher and compute its advantage.

6.10. Define a PRF \(F\) whose key \(k\) is an in \(\times 2\) array of out-bit strings, whose entries we refer to as \(k[i, b]\). Then \(F\) is defined as: \[F(k, x)=\bigoplus_{i=1}^{i n} k\left[i, x_{i}\right]\] Show that \(F\) is not a secure PRF. Describe a distinguisher and compute its advantage.

6.11. A function \(\{0,1\}^{n} \rightarrow\{0,1\}^{n}\) is chosen uniformly at random. What is the probability that the function is invertible?

6.12. Let \(F\) be a secure PRP with blocklength blen \(=128\). Then for each \(k\), the function \(F(k, \cdot)\) is a permutation on \(\{0,1\}^{128}\). Suppose I choose a permutation on \(\{0,1\}^{128}\) uniformly at random. What is the probability that the permutation I chose agrees with a permutation of the form \(F(k, \cdot)\) ? Compute the probability as an actual number \(-\) is it a reasonable probability or a tiny one?

6.13. Suppose \(R:\{0,1\}^{n} \rightarrow\{0,1\}^{n}\) is chosen uniformly among all such functions. What is the probability that there exists an \(x \in\{0,1\}^{n}\) such that \(R(x)=x ?\)

Hint:

\(\mathrm{~ t r o t f e u m x o r d d e ~ ว น t ~ 8 u s n ~ f a m s u r ~}\)

6.14. In this problem, you will show that the PRP switching lemma holds only for large domains. Let \(\mathcal{L}_{\text {prf-rand }}\) and \(\mathcal{L}_{\text {prp-rand }}\) be as in Lemma 6.7. Choose any small value of blen \(=\) in \(=\) out that you like, and show that \(\mathcal{L}_{\text {prf-rand }} \neq \mathcal{L}_{\text {prp-rand }}\) with those parameters. Describe a distinguisher and compute its advantage.

6.15. Let \(F:\{0,1\}^{i n} \rightarrow\{0,1\}^{\text {out }}\) be a (not necessarily invertible) function. We showed how to use \(F\) as a round function in the Feistel construction ony when in =out.

Describe a modification of the Feistel construction that works even when the round function satisfies in \(\neq\) out. The result should be an invertible with input/output length in \(+\) out. Be sure to show that your proposed transform is invertible! You are not being asked to show any security properties of the Feistel construction. 6.16. Show that a 1-round keyed Feistel cipher cannot be a secure PRP, no matter what its round functions are. That is, construct a distinguisher that successfully distinguishes \(\mathcal{L}_{\text {prp-real }}^{F}\) and \(\mathcal{L}_{\text {prp-rand }}^{F}\), knowing only that \(F\) is a 1-round Feistel cipher. In particular, the purpose is to attack the Feistel transform and not its round function, so your attack should work no matter what the round function is.

6.17. Show that a 2-round keyed Feistel cipher cannot be a secure PRP, no matter what its round functions are. Your attack should work without knowing the round keys, and it should work even with different (independent) round keys.

Hint:

\(\mathrm{~ s ә п . т ว ก b ~ о м า ~ s ә п ! n b ә л ~ у}\)

6.18. Show that any function \(F\) that is a 3-round keyed Feistel cipher cannot be a secure strong PRP. As above, your distinguisher should work without knowing what the round functions are, and the attack should work with different (independent) round functions.

6.19. In this problem you will show that PRPs are hard to invert without the key (if the blocklength is large enough). Let \(F\) be a candidate PRP with blocklength blen \(\geqslant \lambda\). Suppose there is a program \(\mathcal{A}\) where: \[\operatorname{Pr}_{y \leftarrow\{0,1\}^{b l e n}}\left[\mathcal{A}(y) \diamond \mathcal{L}_{\text {prf-real }}^{F} \text { outputs } F^{-1}(k, y)\right] \text { is non-negligible. }\] The notation means that \(\mathcal{A}\) receives a random block \(y\) as an input (and is also linked to \(\left.\mathcal{L}_{\text {prf-real }}\right) . k\) refers to the private variable within \(\mathcal{L}_{\text {prf-real. So, when given the ability to }}\) evaluate \(F\) in the forward direction only (via \(\mathcal{L}_{\text {prf-real }}\) ), \(\mathcal{A}\) can invert a uniformly chosen block \(y\).

Prove that if such an \(\mathcal{A}\) exists, then \(F\) is not a secure PRP. Use \(\mathcal{A}\) to construct a distinguisher that violates the PRP security definition. Where do you use the fact that blen \(\geqslant \lambda\) ? How do you deal with the fact that \(\mathcal{A}\) may give the wrong answer with high probability?

6.20. Let \(F\) be a secure PRP with blocklength \(b\) len \(=\lambda\), and consider \(\widehat{F}(k, x)=F(k, k) \oplus F(k, x)\).

(a) Show that \(\widehat{F}\) is not a strong PRP (even if \(F\) is).

\(\star(b)\) Show that \(\widehat{F}\) is a secure (normal) PRP.

Security Against Chosen Plaintext Attacks

Our previous security definitions for encryption capture the case where a key is used to encrypt only one plaintext. Clearly it would be more useful to have an encryption scheme that allows many plaintexts to be encrypted under the same key.

Fortunately we have arranged things so that we get the "correct" security definition when we modify the earlier definition in a natural way. We simply let the libraries choose a secret key once and for all, which is used to encrypt all plaintexts. More formally:

Definition 7.1 Let \(\Sigma\) be an encryption scheme. We say that \(\Sigma\) has security against chosen-plaintext (CPA security) attacks (CPA security) if \(\mathcal{L}_{\text {cpa-L }}^{\Sigma} \approx \mathcal{L}_{\text {cpa-R }}^{\Sigma}\), where:

Notice how the key \(k\) is chosen at initialization time and is static for all calls to Enc. CPA security is often called "IND-CPA" security, meaning "indistinguishability of ciphertexts under chosen-plaintext attack."

Impossibility of Deterministic Encryption

The reason a bare block cipher does not provide CPA security is that it is deterministic. Calling \(\operatorname{Enc}(k, m)\) twice - with the same key and same plaintext - leads to the same ciphertext. Even one-time pad is deterministic. \({ }^{1}\) One of the first and most important aspects of CPA security is that it is incompatible with deterministic encryption. Deterministic encryption can never be CPA-secure! In other words, we can attack the CPA-security of any scheme \(\Sigma\), knowing only that it has deterministic encryption. The attack is a simple generalization of our attack against a bare PRP:

\(\mathcal{A}\)
arbitrarily choose distinct plaintexts \(x, y \in \mathcal{M}\)
\(c_{1}:=\operatorname{EAVESDROP}(x, x)\)
\(c_{2}:=\operatorname{EAVESDROP}(x, y)\)
return \(c_{1} \stackrel{?}{=} c_{2}\)

A good way to think about what goes wrong with deterministic encryption is that it leaks whether two ciphertexts encode the same plaintext, and this is not allowed by CPA security. Think of sealed envelopes as an analogy for encryption. I shouldn’t be able to tell whether two sealed envelopes contain the same text! We are only now seeing this issue because this is the first time our security definition allows an adversary to see multiple ciphertexts encrypted under the same key.

\({ }^{1}\) Remember, we can always consider what will happen when running one-time pad encryption twice with the same key + plaintext. The one-time secrecy definition doesn’t give us any security guarantees about using one-time pad in this way, but we can still consider it as a thought experiment

Avoiding Deterministic Encryption

Is CPA security even possible? How exactly can we make a non-deterministic encryption scheme? This sounds challenging! We must design an Enc algorithm such that calling it twice with the same plaintext and key results in different ciphertexts (otherwise the attack \(\mathcal{A}\) above violates CPA security). What’s more, it must be possible to decrypt all of those different encryptions of the same plaintext to the correct value!

There are 3 general ways to design an encryption scheme that is not deterministic:

• Encryption/decryption can be stateful, meaning that every call to Enc or Dec will actually modify the value of \(k\). The symmetric ratchet construction described in Section \(5.5\) could be thought of as such a stateful construction. The key is updated via the ratchet mechanism for every encryption. A significant drawback with stateful encryption is that synchronization between sender and receiver is fragile and can be broken if a ciphertext is lost in transit.
• Encryption can be randomized. Each time a plaintext is encrypted, the Enc algorithm chooses fresh, independent randomness specific to that encryption. The main challenge in designing a randomized encryption method is to incorporate randomness into each ciphertext in such a way that decryption is still possible. Although this sounds quite challenging, we have already seen such a method, and we will prove its CPA security in the next sections. In this book we will focus almost entirely on randomized encryption.
• Encryption can be nonce-based. A "nonce" stands for "number used only once" and it refers to an extra argument that is passed to the Enc and Dec algorithms. A nonce does not need to be chosen randomly; it does not need to be secret; it only needs to be distinct among all calls made to Enc. By guaranteeing that some input to Enc will be different every time (even when the key and plaintext are repeated), the Enc algorithm can be deterministic and still provide CPA security.

Nonce-based encryption requires a change to the interface of encryption, and therefore a change to the correctness & security definitions as well. The encryption/decryption algorithms syntax is updated to \(\operatorname{Enc}(k, v, m)\) and \(\operatorname{Dec}(k, v, c)\), where \(v\) is a nonce. The correctness property is that \(\operatorname{Dec}(k, v, \operatorname{Enc}(k, v, m))=m\) for all \(k, v, m\), so both encryption & decryption algorithms should use the same nonce. The security definition allows the adversary to choose the nonce, but gives an error if the adversary tries to encrypt multiple ciphertexts with the same nonce. In this way, the definition enforces that the nonces are distinct.

Note that the calling program provides a single value \(v\) (not a \(v_{L}\) and \(v_{R}\) ). Both libraries use the nonce \(v\) that is given, and this implies that the encryption scheme does not need to hide \(v\). If something is the same between both libraries, then it is not necessary to hide it in order to make the libraries indistinguishable.

If an encryption scheme does not fall into one of these three categories, it cannot satisfy our definition of CPA-security. You can and should use deterministic encryption as a sanity check against any proposed encryption algorithm.

Block Cipher Modes of Operation

One of the drawbacks of the previous CPA-secure encryption scheme is that its ciphertexts are \(\lambda\) bits longer than its plaintexts. In the common case that we are using a block cipher with blocklength blen \(=\lambda\), this means that ciphertexts are twice as long as plaintexts. Is there any way to encrypt data (especially lots of it) without requiring such a significant overhead?

A block cipher mode refers to a way to use a block cipher to efficiently encrypt a large amount of data (more than a single block). In this chapter, we will see the most common modes for CPA-secure encryption of long plaintexts.

ECB: Electronic Codebook (NEVER NEVER USE THIS! NEVER!!)

The most obvious way to use a block cipher to encrypt a long message is to just apply the block cipher independently to each block. The only reason to know about this mode is to know never to use it (and to publicly shame anyone who does). It can’t be said enough times: never use ECB mode! It does not provide security of encryption; can you see why?

Construction \(8.1\)

(ECB Mode)

CBC: Cipher Block Chaining

\(\mathrm{CBC}\) (which stands for cipher block chaining) is the most common mode in practice. The CBC encryption of an \(\ell\)-block plaintext is \(\ell+1\) blocks long. The first ciphertext block is called an initialization vector (IV). Here we have described CBC mode as a randomized encryption, with the IV of each ciphertext being chosen uniformly. As you know, randomization is necessary (but not sufficient) for achieving CPA security, and indeed CBC mode provides CPA security.

Construction 8.2

(CBC Mode)

CTR: Counter

The next most common mode in practice is counter mode (usually abbreviated as CTR mode). Just like CBC mode, it involves an additional IV block \(r\) that is chosen uniformly. The idea is to then use the sequence \[F(k, r) ; \quad F(k, r+1) ; \quad F(k, r+2) ; \quad \cdots\] as a long one-time pad to mask the plaintext. Since \(r\) is a block of bits, the addition expressions like \(r+1\) refer to addition modulo \(2^{\text {blen }}\) (this is the typical behavior of unsigned addition in a processor).

Construction \(8.3\)

(CTR Mode)

OFB: Output Feedback

OFB (output feedback) mode is rarely used in practice. We’ll include it in our discussion because it has the easiest security proof. As with \(C B C\) and CTR modes, OFB starts with a random IV \(r\), and then uses the sequence: \[F(k, r) ; \quad F(k, F(k, r)) ; \quad F(k, F(k, F(k, r))) ; \quad \cdots\] as a one-time pad to mask the plaintext

Construction \(8.4\)

(OFB Mode)

Compare & Contrast

CBC and CTR modes are essentially the only two modes that are ever considered in practice for CPA security. Both provide the same security guarantees, and so any comparison between the two must be based on factors outside of the CPA security definition. Here are a few properties that are often considered when choosing between these modes:

• Although we have not shown the decryption algorithm for CTR mode, it does not even use the block cipher’s inverse \(F^{-1}\). This is similar to our PRF-based encryption scheme from the previous chapter (in fact, CTR mode collapses to that construction when restricted to 1-block plaintexts). Strictly speaking, this means CTR mode can be instantiated from a PRF; it doesn’t need a PRP. However, in practice it is rare to encounter an efficient PRF that is not a PRP.
• CTR mode encryption can be parallelized. Once the IV has been chosen, the \(i\) th block of ciphertext can be computed without first computing the previous \(i-1\) blocks. CBC mode does not have this property, as it is inherently sequential. Both modes have a parallelizable decryption algorithm, though.
• If calls to the block cipher are expensive, it might be desirable to pre-compute and store them before the plaintext is known. CTR mode allows this, since only the IV affects the input given to the block cipher. In CBC mode, the plaintext influences the inputs to the block cipher, so these calls cannot be pre-computed before the plaintext is known.
• It is relatively easy to modify CTR to support plaintexts that are not an exact multiple of the blocklength. (This is left as an exercise.) We will see a way to make CBC mode support such plaintexts as well, but it is far from trivial.
• So far all of the comparisons have favored CTR mode, so here is one important property that favors \(C B C\) mode. It is common for implementers to misunderstand the security implications of the IV in these modes. Many careless implementations allow an IV to be reused. Technically speaking, reusing an IV (other than by accident, as the birthday bound allows) means that the scheme was not implemented correctly. But rather than dumping the blame on the developer, it is good design practice to anticipate likely misuses of a system and, when possible, try to make them non-catastrophic.

The effects of IV-reuse in CTR mode are quite devastating to message privacy (see the exercises). In CBC mode, reusing an IV can actually be safe, if the two plaintexts have different first blocks!

Don’t Take Length-Leaking for Granted!

We have just gone from requiring encryption to leak no partial information to casually allowing some specific information to leak. Let us not be too hasty about this!

If we want to truly support plaintexts of arbitrary length, then leaking the length is in fact unavoidable. But "unavoidable" doesn’t mean "free of consequences." By observing only the length of encrypted network traffic, many serious attacks are possible. Here are several examples:

• When accessing Google maps, your browser receives many image tiles that comprise the map that you see. Each image tile has the same pixel dimensions. However, they are compressed to save resources, and not all images compress as significantly as others. Every region of the world has its own rather unique "fingerprint" of imagetile lengths. So even though traffic to and from Google maps is encrypted, the sizes of the image tiles are leaked. This can indeed be used to determine the region for which a user is requesting a map. \({ }^{2}\) The same idea applies to auto-complete suggestions in a search form.
• Variable-bit-rate (VBR) encoding is a common technique in audio/video encoding. When the data stream is carrying less information (e.g., a scene with a fixed camera position, or a quiet section of audio), it is encoded at a lower bit rate, meaning that each unit of time is encoded in fewer bits. In an encrypted video stream, the changes in bit rate are reflected as changes in packet length. When a user is watching a movie on Netflix or a Youtube video (as opposed to a live event stream), the bit-rate changes are consistent and predictable. It is therefore rather straight-forward to determine which video is being watched, even on an encrypted connection, just by observing the packet lengths.
• VBR is also used in many encrypted voice chat programs. Attacks on these tools have been increasing in sophistication. The first attacks on encrypted voice programs showed how to identify who was speaking (from a set of candidates), just by observing the stream of ciphertext sizes. Later attacks could determine the language being spoken. Eventually, when combined with sophisticated linguistic models, it was shown possible to even identify individual words to some extent!

It’s worth emphasizing again that none of these attacks involve any attempt to break the encryption. The attacks rely solely on the fact that encryption leaks the length of the plaintexts.

Padding

Padding just refers to any approach to encode arbitrary-length data into data that is a multiple of the blocklength. The only requirement is that this encoding is reversible. More formally, a padding scheme should consist of two algorithms:

• pad: takes as input a string of any length, and outputs a string whose length is a multiple of the blocklength
• unpad: the inverse of pad. We require that unpad \((\operatorname{pad}(x))=x\) for all strings \(x\).

The idea is that the sender can encrypt pad \((x)\), which is guaranteed to be a multiple of the blocklength; the receiver can decrypt and run unpad on the result to obtain \(x\).

In the real world, data almost always comes in bytes and not bits, so that will be our assumption here. In this section we will write bytes in hex, for example \(8 f\). Typical blocklengths are 128 bits (16 bytes) or 256 bits ( 32 bytes).

Here are a few common approaches for padding:

Null padding: The simplest padding approach is to just fill the final block with null bytes \((00\) ). The problem with this approach is that it is not always reversible. For example, pad( 314159 ) and pad( \(314159 \quad 00)\) will give the same result. It is not possible to distinguish between a null byte that was added for padding and one that was intentionally the last byte of the data.

ANSI X.923 standard: Data is padded with null bytes, except for the last byte of padding which indicates how many padding bytes there are. In essence, the last byte of the padded message tells the receiver how many bytes to remove to recover the original message.

Note that in this padding scheme (and indeed in all of them), if the original unpadded data is already a multiple of the block length, then an entire extra block of padding must be added. This is necessary because it is possible for the original data to end with some bytes that look like valid padding (e.g., 000003 ), and we do not want these bytes to be removed erroneously.

Example Below are some examples of valid and invalid X.923 padding (using 16-byte blocks):

PKCS#7 standard: If \(b\) bytes of padding are needed, then the data is padded not with null bytes but with \(b\) bytes. Again, the last byte of the padded message tells the receiver how many bytes to remove.

\[\begin{aligned} & 71 \text { da } 775 \text { a } 5 \text { e } 77 \text { eb a8 } 73 \text { c5 } 50 \text { b5 } 81 \text { d5 } 96 \quad 01 \Rightarrow \text { valid } \\ & \text { 5b lc } 01415 \text { d } 5386 \quad 4 \text { e e4 } 94 \quad 13 \text { e8 } 7 \text { a } 89 \text { c4 } 71 \Rightarrow \text { invalid } \\ & \text { d4 Od d8 7b } 5324 \text { c6 d1 af } 5 f \quad \text { d6 f6 } 00 \quad \text { co } 00 \quad 04 \Rightarrow \text { invalid } \end{aligned}\] Example Below are some examples of valid and invalid PKCS#7 padding (using 16-byte blocks):

ISO/IEC 7816-4 standard: The data is padded with a 80 byte followed by null bytes. To remove the padding, remove all trailing null bytes and ensure that the last byte is 80 (and then remove it too).

The significance of 80 is clearer when you write it in binary as 10000000 . So another way to describe this padding scheme is: append a 1 bit, and then pad with 0 bits until reaching the blocklength. To remove the padding, remove all trailing 0 bits as well as the rightmost 1 bit. Hence, this approach generalizes easily to padding data that is not a multiple of a byte.

Example Below are some examples of valid and invalid ISO/IEC 7816-4 padding (using 16-byte blocks):

The choice of padding scheme is not terribly important, and any of these is generally fine. Just remember that padding schemes are not a security feature! Padding is a public method for encoding data, and it does not involve any secret keys. The only purpose of padding is to enable functionality - using block cipher modes like CBC with data that is not a multiple of the block length.

Furthermore, as we will see in the next chapter, padding is associated with certain attacks against improper use of encryption. Even though this is not really the fault of the padding (rather, it is the fault of using the wrong flavor of encryption), it is such a common pitfall that it is always worth considering in a discussion about padding.

Ciphertext Stealing

Another approach with a provocative name is ciphertext stealing (CTS, if you are not yet tired of three-leter acronyms), which results in ciphertexts that are not a multiple of the blocklength. The main idea behind ciphertext stealing is to use a standard block-cipher mode that only supports full blocks (e.g., CBC mode), and then simply throw away some bits of the ciphertext, in such a way that decryption is still possible. If the last plaintext blocks is \(j\) bits short of being a full block, it is generally possible to throw away \(j\) bits of the ciphertext. In this way, a plaintext of \(n\) bits will be encrypted to a ciphertext of \(b l e n+n\) bits, where blen is the length of the extra IV block. \[\begin{aligned} & \begin{array}{l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l}01 & 34 & 11 & \mathrm{~d} 9 & 81 & 88 & 05 & 57 & 1 \mathrm{~d} & 73 & \mathrm{c} 3 & 05 & 05 & 05 & 05 & 05\end{array} \Rightarrow \text { valid } \\ & 955105 \quad 4 a \text { d6 } 5 \text { 5a a3 } 44 \text { af b3 } 850303030303 \Rightarrow \text { valid } \\ & 71 \text { da } 775 \text { a } 5 \text { e } 77 \text { eb a8 } 73 \text { c5 } 50 \text { b5 } 81 \text { d5 } 96 \quad 01 \Rightarrow \text { valid } \end{aligned}\] \[\begin{aligned} & \text { d4 Od d8 7b } 5324 \text { c6 d1 af } 5 f \quad d 6 \quad f 604 \quad 000404 \Rightarrow \text { invalid } \end{aligned}\]

As an example, let’s see ciphertext stealing as applied to CBC mode. Suppose the blocklength is blen and the last plaintext block \(m_{\ell}\) is \(j\) bits short of being a full block. We start by extending \(m_{\ell}\) with \(j\) zeroes (i.e., null-padding the plaintext) and performing CBC encryption as usual.

Now our goal is to identify \(j\) bits of the CBC ciphertext that can be thrown away while still making decryption possible. In this case, the appropriate bits to throw away are the last \(j\) bits of \(c_{\ell-1}\) (the next-to-last block of the \(C B C\) ciphertext). The reason is illustrated in the figure below:

Suppose the receiver obtains this CBC ciphertext but the last \(j\) bits of \(c_{\ell-1}\) have been deleted. How can he/she decrypt? The important idea is that those missing \(j\) bits were redundant, because there is another way to compute them.

In \(\mathrm{CBC}\) encryption, the last value given as input into the block cipher is \(c_{\ell-1} \oplus m_{\ell}\). Let us give this value a name \(x^{*}:=c_{\ell-1} \oplus m_{\ell}\). Since the last \(j\) bits of \(m_{\ell}\) are \(0^{\prime}\) s, \({ }^{3}\) the last \(j\) bits of \(x^{*}\) are the last \(j\) bits of \(c_{\ell-1}-\) the missing bits. Even though these bits are missing from \(c_{\ell-1}\), the receiver has a different way of computing them as \(x^{*}:=F^{-1}\left(k, c_{\ell}\right)\).

Putting it all together, the receiver does the following: First, it observes that the ciphertext is \(j\) bits short of a full block. It computes \(F^{-1}\left(k, c_{\ell}\right)\) and takes the last \(j\) bits of this value to be the missing bits from \(c_{\ell-1}\). With the missing bits recovered, the receiver does \(\mathrm{CBC}\) decryption as usual. The result is a plaintext consisting of \(\ell\) full blocks, but we know that the last \(j\) bits of that plaintext are 0 padding that the receiver can remove.

It is convenient in an implementation for the boundaries between blocks to be in predictable places. For that reason, it is slightly awkward to remove \(j\) bits from the middle of the ciphertext during encryption (or add them during decryption), as we have done here. So in practice, the last two blocks of the ciphertext are often interchanged. In the example above, the resulting ciphertext (after ciphertext stealing) would be:

\(c_{0}\left\|c_{1}\right\| c_{2} \cdots c_{\ell-3}\left\|c_{\ell-2}\right\| c_{\ell} \| c_{\ell-1}^{\prime}\), where \(c_{\ell-1}^{\prime}\) is the first blen \(-j\) bits of \(c_{\ell-1} .\)

\({ }^{3}\) The receiver knows this fact, because the ciphertext is \(j\) bits short of a full block. The length of the (shortened) ciphertext is a signal about how many 0 -bits of padding were used during encryption. That way, all ciphertext blocks except the last one are the full blen bits long, and the boundaries between blocks appear consistently every blen bits. This "optimization" does add some significant edge cases to any implementation. One must also decide what to do when the plaintext is already an exact multiple of the blocklength - should the final two ciphertext blocks be swapped even in this case? Below we present an implementation of ciphertext stealing (CTS) that does not swap the final two blocks in this case. This means that it collapses to plain CBC mode when the plaintext is an exact multiple of the block length.

Construction \(8.6\)

(CBC-CTS)

The marked lines correspond to plain \(C B C\) mode.

Hint:

(d) Suppose the final plaintext block is padded using the final \(j\) bits of the previous ciphertext block \(c_{\ell-1}\). Although correct decryption is still possible, the construction is no longer secure. Show an attack violating the CPA$-security of this construction. Why doesn’t the proof approach from part (c) work?

Chosen Ciphertext Attacks

In this chapter we discuss the limitations of the CPA security definition. In short, the CPA security definition considers only the information leaked to the adversary by honestlygenerated ciphertexts. It does not, however, consider what happens when an adversary is allowed to inject its own maliciously crafted ciphertexts into an honest system. If that happens, then even a CPA-secure encryption scheme can fail in spectacular ways. We begin by seeing such an example of spectacular and surprising failure, called a padding oracle attack:

Malleability of CBC Encryption

Recall the definition of \(\mathrm{CBC}\) decryption. If the ciphertext is \(c=c_{0} \cdots c_{\ell}\) then the ith plaintext block is computed as: \[m_{i}:=F^{-1}\left(k, c_{i}\right) \oplus c_{i-1}\] From this we can deduce two important facts:

• Two consecutive blocks \(\left(c_{i-1}, c_{i}\right)\) taken in isolation are a valid encryption of \(m_{i}\). Looking ahead, this fact allows the attacker to focus on decrypting a single block at a time.
• xoring a ciphertext block with a known value (say, \(x\) ) has the effect of xoring the corresponding plaintext block by the same value. In other words, for all \(x\), the ciphertext \(\left(c_{i-1} \oplus x, c_{i}\right)\) decrypts to \(m_{i} \oplus x\) :

\[\operatorname{Dec}\left(k,\left(c_{i-1} \oplus x, c_{i}\right)\right)=F^{-1}\left(k, c_{i}\right) \oplus\left(c_{i-1} \oplus x\right)=\left(F^{-1}\left(k, c_{i}\right) \oplus c_{i-1}\right) \oplus x=m_{i} \oplus x\] If we send such a ciphertext \(\left(c_{i-1} \oplus x, c_{i}\right)\) to the padding oracle, we would therefore learn whether \(m_{i} \oplus x\) is a (single block) with valid padding. Instead of thinking in terms of padding, it might be best to think of the oracle as telling you whether \(m_{i} \oplus x\) ends in one of the suffixes \(01,0002,000003\), etc.

By carefully choosing different values \(x\) and asking questions of this form to the padding oracle, we will show how it is possible to learn all of \(m_{i}\). We summarize the capability so far with the following subroutine:

\(/ /\) suppose \(c\) encrypts an (unknown) plaintext \(m_{1}\|\cdots\| m_{\ell}\)
\(/ /\) does \(m_{i} \oplus x\) end in one of the valid pading strings?
\(\frac{\text { CHECKXOR }(c, i, x):}{\text { return PADDINGORACLE }\left(c_{i-1} \oplus x, c_{i}\right)}\)

Given a ciphertext \(c\) that encrypts an unknown message \(m\), we can see that an adversary can generate another ciphertext whose contents are related to \(m\) in a predictable way. This property of an encryption scheme is called malleability.

Learning the Last Byte of a Block

We now show how to use the cHEcKXOR subroutine to determine the last byte of a plaintext block \(m\). There are two cases to consider, depending on the contents of \(m\). The attacker does not initially know which case holds:

For the first (and easier) of the two cases, suppose the second-to-last byte of \(m\) is nonzero. We will try every possible byte \(b\) and ask whether \(m \oplus b\) has valid padding. Since \(m\) is a block and \(b\) is a single byte, when we write \(m \oplus b\) we mean that \(b\) is extended on the left with zeroes. Since the second-to-last byte of \(m\) (and hence \(m \oplus b\) ) is nonzero, only one of these possibilities will have valid padding - the one in which \(m \oplus b\) ends in byte 01 . Therefore, if \(b\) is the candidate byte that succeeds (i.e., \(m \oplus b\) has valid padding) then the last byte of \(m\) must be \(b \oplus 01\). Example Using LEARNLASTBYTE to learn the last byte of a plaintext block:

For the other case, suppose the second-to-last byte of \(m\) is zero. Then \(m \oplus b\) will have valid padding for several candidate values of \(b\) :

Example Using LEARNLASTBYTE to learn the last byte of a plaintext block:

Whenever more than one candidate \(b\) value yields valid padding, we know that the second-to-last byte of \(m\) is zero (in fact, by counting the number of successful candidates, we can know exactly how many zeroes precede the last byte of \(m\) ).

If the second-to-last byte of \(m\) is zero, then the second-to-last byte of \(m \oplus 01 \quad b\) is nonzero. The only way for both strings \(m \oplus 01 \quad b\) and \(m \oplus b\) to have valid padding is when \(m \oplus b\) ends in byte 01 . We can re-try all of the successful candidate \(b\) values again, this time with an extra nonzero byte in front. There will be a unique candidate \(b\) that is successful in both rounds, and this will tell us that the last byte of \(m\) is \(b \oplus 01\).

The overall approach for learning the last byte of a plaintext block is summarized in the LEARNLASTBYTE subroutine in Figure 9.1. The set \(B\) contains the successful candidate bytes from the first round. There are at most 16 elements in \(B\) after the first round, since there are only 16 valid possibilities for the last byte of a properly padded block. In the worst case, LEARNLASTBYTE makes \(256+16=272\) calls to the padding oracle (via CHECKXOR).

Learning Other Bytes of a Block

Once we have learned one of the trailing bytes of a plaintext block, it is slightly easier to learn additional ones. Suppose we know the last 3 bytes of a plaintext block, as in the example below. We would like to use the padding oracle to discover the 4 th-to-last byte. Example Using LEARNPREVBYTE to learn the 4th-to-last byte when the last 3 bytes of the block are already known.

Since we know the last 3 bytes of \(m\), we can calculate a string \(x\) such that \(m \oplus x\) ends in 000004 . Now we can try Xor’ing the 4 th-to-last byte of \(m \oplus x\) with different candidate bytes \(b\), and asking the padding oracle whether the result has valid padding. Valid padding only occurs when the result has 00 in its 4 th-to-last byte, and this happens exactly when the 4 th-to-last byte of \(m\) exactly matches our candidate byte \(b\).

The process is summarized in the LEARNPREVBYTE subroutine in Figure 9.1. In the worst case, this subroutine makes 256 queries to the padding oracle.

Putting it all together. We now have all the tools required to decrypt any ciphertext using only the padding oracle. The process is summarized below in the LEARNALL subroutine.

In the worst case, 256 queries to the padding oracle are required to learn each byte of the plaintext. \({ }^{2}\) However, in practice the number can be much lower. The example in this section was inspired by a real-life padding oracle attack \({ }^{3}\) which includes optimizations that allow an attacker to recover each plaintext byte with only 14 oracle queries on average.

Discussion

• Is this a realistic concern? You may wonder whether this whole situation is somewhat contrived just to give cryptographers harder problems to solve. That was probably a common attitude towards the security definitions introduced in this chapter. However, in 1998, Daniel Bleichenbacher demonstrated a devastating attack against early versions of the SSL protocol. By presenting millions of carefully crafted ciphertexts to a webserver, an attacker could eventually recover arbitrary SSL session keys.

In practice, it is hard to make the external behavior of a server not depend on the result of decryption. This makes CPA security rather fragile in the real world. In the case of padding oracle attacks, mistakes in implementation can lead to different error messages for invalid padding. In other cases, even an otherwise careful implementation can provide a padding oracle through a timing side-channel (if the server’s response time is different for valid/invalid padded plaintexts).

As we will see, it is in fact possible to provide security in these kinds of settings, and with low additional overhead. These days there is rarely a good excuse for using encryption which is only CPA-secure.

• Padding is in the name of the attack. But padding is not the culprit. The culprit is using a (merely) CPA-secure encryption scheme while allowing some information to leak about the result of decryption. The exercises expand on this idea further.
• If padding is added to only the last block of the plaintext, how can this attack recover the entire plaintext? This common confusion is another reason to not place so much blame on the padding scheme. A padding oracle has the following behavior: "give me an encryption of \(m_{1}\|\cdots\| m_{\ell}\) and I’ll tell you some information about \(m_{\ell}\) (whether it ends with a certain suffix)." Indeed, the padding oracle checks only the last block. However, CBC mode has the property that if you have an encryption of \(m_{1}\|\cdots\| m_{\ell}\), then you can easily construct a different ciphertext that encrypts \(m_{1}\|\cdots\| m_{\ell-1}\). If you send this ciphertext to the padding oracle, you will get information about \(m_{\ell-1}\). By modifying the ciphertext (via the malleability of CBC), you give different plaintext blocks the chance to be the "last block" that the padding oracle looks at.
• The attack seems superficially like brute force, but it is not: The attack makes 256 queries per byte of plaintext, so it costs about \(256 \ell\) queries for a plaintext of \(\ell\) bytes. Brute-forcing the entire plaintext would cost \(256^{\ell}\) since that’s how many \(\ell\)-byte plaintexts there are. So the attack is exponentially better than brute force. The lesson is: brute-forcing small pieces at a time is much better then brute-forcing the entire thing.

An Example

The padding oracle attack already demonstrates that \(C B C\) mode does not provide security in the presence of chosen ciphertext attacks. But that attack was quite complicated since the adversary was restricted to learn just 1 bit of information at a time about a decrypted ciphertext. An attack against full CCA security can be much more direct, since the adversary has full access to decrypted ciphertexts.

Example Consider the adversary below attacking the CCA security of \(C B C\) mode (with block length blen)

\(\mathcal{A}\)
\(c=c_{0}\left\|c_{1}\right\| c_{2}:=\) EAVESDROP \(\left(0^{2 \text { blen }}, 1^{2 b l e n}\right)\)
\(m:=\operatorname{DECRYPT}\left(c_{0} \| c_{1}\right)\)
return \(m \stackrel{?}{=} 0^{\text {blen }}\)

It can easily be verified that this adversary achieves advantage 1 distinguishing \(\mathcal{L}_{\mathrm{cca}-\mathrm{L}}\) from \(\mathcal{L}_{\mathrm{cca}-\mathrm{R}}\). The attack uses the fact (also used in the padding oracle attack) that if \(c_{0}\left\|c_{1}\right\| c_{2}\) encrypts \(m_{1} \| m_{2}\), then \(c_{0} \| c_{1}\) encrypts \(m_{1}\). To us, it is obvious that ciphertext \(c_{0} \| c_{1}\) is related to \(c_{0}\left\|c_{1}\right\| c_{2}\). Unfortunately for \(C B C\) mode, the security definition is not very clever - since \(c_{0} \| c_{1}\) is simply different than \(c_{0}\left\|c_{1}\right\| c_{2}\), the DECRYPT subroutine happily decrypts it.

Example Perhaps unsurprisingly, there are many very simple ways to catastrophically attack the CCA security of \(C B C\)-mode encryption. Here are some more (where \(\bar{x}\) denotes the result of flipping every bit in \(x)\)

The first attack uses the fact that modifying \(c_{2}\) has no effect on the first plaintext block. The second attack uses the fact that flipping every bit in the IV flips every bit in \(m_{1}\).

Again, in all of these cases, the DECRYPT subroutine is being called on a different (but related) ciphertext than the one returned by EAVESDROP.

Discussion

So if I use a CCA-secure encryption scheme, I should never decrypt a ciphertext that I encrypted myself?

Remember: when we define the Enc and Dec algorithms of an encryption scheme, we are describing things from the normal user’s perspective. As a user of an encryption scheme, you can encrypt and decrypt whatever you like. It would indeed be strange if you encrypted something knowing that it should never be decrypted. What’s the point?

The security definition describes things from the attacker’s perspective. The \(\mathcal{L}_{\text {cca- } \star}\) libraries tell us what are the circumstances under which the encryption scheme provides security? They say (roughly):

an attacker can’t tell what’s inside a ciphertext \(c^{*}\), even if she has some partial information about that plaintext, even if she had some partial influence over the choice of that plaintext, and even if she is allowed to decrypt any other ciphertext she wants.

Of course, if a real-world system allows an attacker to learn the result of decrypting \(c^{*}\), then by definition the attacker learns what’s inside that ciphertext.

CCA security is deeply connected with the concept of malleability. Malleability means that, given a ciphertext that encrypts an unknown plaintext \(m\), it is possible to generate a different ciphertext that encrypts a plaintext that is related to \(m\) in a predictable way. For example:

• If \(c_{0}\left\|c_{1}\right\| c_{2}\) is a CBC encryption of \(m_{1} \| m_{2}\), then \(c_{0} \| c_{1}\) is a CBC encryption of \(m_{1}\).
• If \(c_{0}\left\|c_{1}\right\| c_{2}\) is a CBC encryption of \(m_{1} \| m_{2}\), then \(c_{0}\left\|c_{1}\right\| c_{2} \| 0^{\text {blen }}\) is a CBC encryption of some plaintext that begins with \(m_{1} \| m_{2}\).
• If \(c_{0} \| c_{1}\) is a CBC encryption of \(m_{1}\), then \(\left(c_{0} \oplus x\right) \| c_{1}\) is a \(\mathrm{CBC}\) encryption of \(m_{1} \oplus x\).

Note from the second example that we don’t need to know exactly the relationship between the old and new ciphertexts.

If an encryption scheme is malleable, then a typical attack against its CCA security would work as follows:

1. Request an encryption \(c\) of some plaintext.
2. Applying the malleability of the scheme, modify \(c\) to some other ciphertext \(c^{\prime}\).
3. Ask for \(c^{\prime}\) to be decrypted.

Since \(c^{\prime} \neq c\), the security library allows \(c^{\prime}\) to be decrypted. The malleability of the scheme says that the contents of \(c^{\prime}\) should be related to the contents of \(c\). In other words, seeing the contents of \(c^{\prime}\) should allow the attacker to determine what was initially encrypted in

Pseudorandom Ciphertexts

We can also modify the pseudorandom-ciphertexts security definition (CPA$ security) in a similar way:

Definition 9.2 Let \(\sum\) be an encryption scheme. We say that \(\sum\) has pseudorandom ciphertexts in the (CCA$ security) presence of chosen-ciphertext attacks (CCA$ security) if \(\mathcal{L}_{\mathrm{cca} \$ \text {-real }}^{\Sigma} \approx \mathcal{L}_{\mathrm{cca} \$ \text {-rand }}^{\Sigma}\) where:

Just like for CPA security, if a scheme has CCA$ security, then it also has CCA security, but not vice-versa. See the exercises.

\(\star 9.4\) A Simple CCA-Secure Scheme

Recall the definition of a strong pseudorandom permutation (PRP) (Definition 6.13). A strong PRP is one that is indistinguishable from a randomly chosen permutation, even to an adversary that can make both forward (i.e., to \(F\) ) and reverse (i.e., to \(F^{-1}\) ) queries.

This concept has some similarity to the definition of CCA security, in which the adversary can make queries to both Enc and its inverse Dec. Indeed, a strong PRP can be used to construct a CCA-secure encryption scheme in a natural way:

Construction \(9.3 \quad\) Let \(F\) be a pseudorandom permutation with block length blen \(=n+\lambda\). Define the following encryption scheme with message space \(\mathcal{M}=\{0,1\}^{n}\) :

In this scheme, \(m\) is encrypted by appending a random value \(r\) to it, then applying a PRP. While this scheme is conceptually quite simple, it is generally not used in practice since it requires a block cipher with a fairly large block size, and these are rarely encountered.

We can informally reason about the security of this scheme as follows:

• Imagine an adversary linked to one of the CCA libraries. As long as the random value \(r\) does not repeat, all inputs to the \(\mathrm{PRP}\) are distinct. The guarantee of a pseudorandom function/permutation is that its outputs (which are the ciphertexts in this scheme) will therefore all look independently uniform.
• The CCA library prevents the adversary from asking for \(c\) to be decrypted, if \(c\) was itself generated by the library. For any other value \(c^{\prime}\) that the adversary asks to be decrypted, the guarantee of a strong PRP is that the result will look independently random. In particular, the result will not depend on the choice of plaintexts used to generate challenge ciphertexts. Since this choice of plaintexts is the only difference between the two CCA libraries, these decryption queries (intuitively) do not help the adversary.

We now prove the CCA security of Construction \(9.3\) formally:

Claim 9.4 If \(F\) is a strong \(P R P\) (Definition 6.13) then Construction 9.3 has CCA$ security (and therefore CCA security).

Proof As usual, we prove the claim in a sequence of hybrids.

The starting point is \(\mathcal{L}_{\text {cca\$-real }}^{\Sigma}\), as expected, where \(\Sigma\) refers to Construction 9.3.

We have applied the strong PRP security (Definition 6.13) of \(F\), skipping some standard intermediate steps. We factored out all invocations of \(F\) and \(F^{-1}\) in terms of the \(\mathcal{L}_{\text {sprp-real }}\) library, replaced that library with \(\mathcal{L}_{\text {sprp-rand, }}\), and finally inlined it.

This proof has some subtleties, so it’s a good time to stop and think about what needs to be done. To prove CCA$-security, we must reach a hybrid in which the responses of CTXT are uniform. In the current hybrid there are two properties in the way of this goal:

• The ciphertext values \(c\) are sampled from \(\{0,1\}^{\text {blen }} \backslash T\).values, rather than \(\{0,1\}^{\text {blen }}\).
• When the if-condition in ctXT is false, the return value of ctXT is not a fresh random value but an old, repeated one. This happens when \(T[m \| r]\) is already defined. Note that both CTXT and DECRYPT assign to \(T\), so either one of these subroutines may be the cause of a pre-existing \(T[m \| r]\) value.

Perhaps the most subtle fact about our current hybrid is that arguments of cTXT can affect responses from DECRYPT! In CTXT, the library assigns \(m \| r\) to a value \(T_{\text {inv }}[c]\). Later calls to DECRYPT will not read this value directly; these values of \(c\) are off-limits due to the guard condition in the first line of DECRYPT. However, DECRYPT samples a value from \(\{0,1\}^{\text {blen }} \backslash T_{i n v}\).values, which indeed uses the values \(T_{i n v}[c]\). To show CCA$ security, we must remove this dependence of DECRYPT on previous values given to CTXT.

We have added some book-keeping that is not used anywhere. Every time an assignment of the form \(T[m \| r]\) happens, we add \(r\) to the set \(\mathcal{R}\). Looking ahead, we eventually want to ensure that \(r\) is chosen so that the if-statement in cTXT is always taken, and the return value of cTXT is always a fresh random value.

\(\mathcal{S}:=\emptyset ; \quad R:=\emptyset\)

\(T, T_{i n v}:=\) empty assoc. arrays

\(\underline{\operatorname{CTXT}(m)}\)

\(r \leftarrow\{0,1\}^{\lambda} \backslash \mathcal{R}\)

if \(T[m \| r]\) undefined:

\(c \leftarrow\{0,1\}^{\text {blen }}\)

\(T[m \| r]:=c ; T_{i n v}[c]:=m \| r\)

\(\mathcal{R}:=\mathcal{R} \cup\{r\}\)

\(c:=T[m \| r]\)

\(\mathcal{S}:=\mathcal{S} \cup\{c\}\)

return \(c\)

DECRYPT \(\left(c \in \sum . C\right):\)

if \(c \in \mathcal{S}\) return er \(r\)

if \(T_{i n v}[c]\) undefined:

\(m \| r \leftarrow\{0,1\}^{\text {blen }}\)

\(T_{i n v}[c]:=m \| r ; T[m \| r]:=c\)

\(\mathcal{R}:=\mathcal{R} \cup\{r\}\)

return first \(n\) bits of \(T_{i n v}[c]\) We have applied Lemma \(4.12\) three separate times. The standard intermediate steps (factor out, swap library, inline) have been skipped, and this shows only the final result.

In ctXT, we’ve added a restriction to how \(r\) is sampled. Looking ahead, sampling \(r\) in this way means that the if-statement in cTXT is always taken.

In CTXT, we’ve removed the restriction in how \(c\) is sampled. Since \(c\) is the final return value of CTXT, this gets us closer to our goal of this return value being uniformly random.

In DECRYPT, we have removed the restriction in how \(m \| r\) is sampled. As described above, this is because \(T_{i n v}\). values contains previous arguments of CTXT, and we don’t want these arguments to affect the result of DECRYPT in any way. \(\mathcal{S}:=\emptyset ; \quad R:=\emptyset\)

\(T, T_{i n v}:=\) empty assoc. arrays

\(\underline{\operatorname{CTXT}(m)}\)

\(r \leftarrow\{\theta, 1\}^{\lambda} \backslash \mathcal{R}\)

\(c \leftarrow\{0,1\}^{\text {blen }}\)

\(T[m \| r]:=c ; T_{i n v}[c]:=m \| r\)

\(\mathcal{R}:=\mathcal{R} \cup\{r\}\)

\(\mathcal{S}:=\mathcal{S} \cup\{c\}\)

return \(c\)

DECRYPT \(\left(c \in \sum . C\right):\)

if \(c \in \mathcal{S}\) return err

if \(T_{i n v}[c]\) undefined:

\(m \| r \leftarrow\{0,1\}^{\text {blen }}\)

\(T_{i n v}[c]:=m \| r ; T[m \| r]:=c\)

\(\mathcal{R}:=\mathcal{R} \cup\{r\}\)

return first \(n\) bits of \(T_{i n v}[c]\)

\(\mathcal{S}:=\emptyset ; \quad \mathcal{R}:=\emptyset\)

\(T, T_{i n v}:=\) empty assoc. arrays

\(\underline{\operatorname{ctXT}(m):}\)

\(r \leftarrow\{0,1\}^{\lambda} \backslash \mathcal{R}\)

\(c \leftarrow\{0,1\}^{\text {blen }}\)

\(/ / T[m \| r]:=c ; T_{\text {inv }}[c]:=m \| r\)

\(\mathcal{R}:=\mathcal{R} \cup\{r\}\)

\(\mathcal{S}:=\mathcal{S} \cup\{c\}\)

return \(c\)

\(\operatorname{DECRYPT}(c \in \Sigma . C)\)

if \(c \in \mathcal{S}\) return er \(r\)

if \(T_{i n v}[c]\) undefined:

\(m \| r \leftarrow\{0,1\}^{\text {blen }}\)

\(T_{i n v}[c]:=m \| r ; T[m \| r]:=c\)

\(\mathcal{R}:=\mathcal{R} \cup\{r\}\)

return first \(n\) bits of \(T_{i n v}[c]\) In the previous hybrid, the if-statement in CTXT is always taken. This is because if \(T[m \| r]\) is already defined, then \(r\) would already be in \(R\), but we are sampling \(r\) to avoid everything in \(\mathcal{R}\). We can therefore simply execute the body of the if-statement without actually checking the condition.

In the previous hybrid, no line of code ever reads from \(T\); they only write to \(T\). It has no effect to remove a line that assigns to \(T\), so we do so in CTXT.

CTXT also writes to \(T_{i n v}[c]\), but for a value \(c \in \mathcal{S}\). The only line that reads from \(T_{i n v}\) is in DECRYPT, but the first line of DECRYPT prevents it from being reached for such a \(c \in \mathcal{S}\). It therefore has no effect to remove this assignment to \(T_{i n v}\).

if \(c \in \mathcal{S}\) return err

if \(T_{i n v}[c]\) undefined: \(m \| r \leftarrow\{0,1\}^{\text {blen }}\)

\(T_{i n v}[c]:=m \| r ; T[m \| r]:=c\)

\(/ / R:=R \cup\{r\}\)

return first \(n\) bits of \(T_{i n v}[c]\)

\(\mathcal{S}:=\emptyset\)

\(T, T_{i n v}:=\) empty assoc. arrays

\(\operatorname{CTXT}(m)\)

\(c \leftarrow\{\theta, 1\}^{\text {blen }}\)

\(\mathcal{S}:=\mathcal{S} \cup\{c\}\)

We have applied Lemma \(4.12\) to the sampling step in DECRYPT. The standard intermediate steps have

return \(c\) been skipped. Now the second if-statement in

DECRYPT \(\left(c \in \sum . C\right)\) DECRYPT exactly matches \(\mathcal{L}_{\text {sprp-rand }}\).

if \(c \in \mathcal{S}\) return err

if \(T_{i n v}[c]\) undefined:
\(\quad m \| r \leftarrow\{0,1\}^{\text {blen }} \backslash T_{i n v}\).values

\(T_{i n v}[c]:=m \| r ; T[m \| r]:=c\)

return first \(n\) bits of \(T_{i n v}[c]\)

We have applied the strong PRP security of \(F\) to replace \(\mathcal{L}_{\text {sprp-rand }}\) with \(\mathcal{L}_{\text {sprp-real. }}\). The standard intermediate steps have been skipped. The result is \(\mathcal{L}_{\mathrm{cca} \$ \text {-rand }}\). We showed that \(\mathcal{L}_{\text {cca\$-real }}^{\Sigma} \approx \mathcal{L}_{\text {cca\$-rand }}^{\Sigma}\), so the scheme has CCA$ security.

Message Authentication Codes

The challenge of CCA-secure encryption is dealing with ciphertexts that were generated by an adversary. Imagine there was a way to "certify" that a ciphertext was not adversarially generated - i.e., it was generated by someone who knows the secret key. We could include such a certification in the ciphertext, and the Dec algorithm could raise an error if it asked to decrypt something with invalid certification.

What we are asking for is not to hide the ciphertext but to authenticate it: to ensure that it was generated by someone who knows the secret key. The tool for the job is called a message authentication code. One of the most important applications of a message authentication code is to transform a CPA-secure encryption scheme into a CCA-secure one.

As you read this chapter, keep in mind that privacy and authentication are indeed different properties. It is possible to have one or the other or indeed both simultaneously. But one does not imply the other, and it is crucial to think about them separately.

How to Think About Authenticity Properties

Every security definition we’ve seen so far is about hiding information, so how do we make a formal definition about authenticity?

Before we see the security definition for MACs, let’s start with a much simpler (potentially obvious?) statement: "an adversary should not be able to guess a uniformly chosen \(\lambda\)-bit value." We can formalize this idea with the following two libraries:

|c|
\(r \leftarrow\{0,1\}^{\lambda}\)
\(\frac{\operatorname{GUESS}(g):}{\text { return } g} \stackrel{?}{=} r\)

The left library allows the calling program to attempt to guess a uniformly chosen "target" string. The right library doesn’t even bother to verify the calling program’s guess - in fact it doesn’t even bother to sample a random target string!

The GUESs subroutines of these libraries give the same output on nearly all inputs. There is only one input \(r\) on which they disagree. If a calling program can manage to find the value \(r\), then it can easily distinguish the libraries. Therefore, by saying that these libraries are indistinguishable, we are really saying that it’s hard for an adversary to find/generate this special value! That’s the kind of property we want to express.

Indeed, in this case, an adversary who makes \(q\) queries to the Guess subroutine achieves an advantage of at most \(q / 2^{\lambda}\). For polynomial-time adversaries, this is a negligible advantage (since \(q\) is a polynomial function of \(\lambda\) ).

More generally, suppose we have two libraries, and a subroutine in one library checks some condition (and could return either true or false), while in the other library this subroutine always returns false. If the two libraries are indistinguishable, the calling program can’t tell whether the library is actually checking the condition or always saying false. This means it must be very hard to find an input for which the "correct" answer is true.

The MAC Security Definition

We want to say that only someone who knows the secret key can come up with valid MAC tags. In other words, the adversary cannot come up with valid MAC tags.

Actually, that property is not quite enough to be useful. A more useful property is: even if the adversary knows valid MAC tags corresponding to various messages, she cannot produce a valid MAC tag for a different message. We call it a forgery if the adversary can produce a "new" valid MAC tag.

To translate this security property to a formal definition, we define two libraries that allow the adversary to request MAC tags on chosen messages. The libraries also provide a mechanism to let the adversary check whether it has successfully found a forgery (since there is no way of checking this property without the secret key). One library will actually perform the check, and the other library will simply assume that forgeries are impossible. The two libraries are different only in how they behave when the adversary calls this verification subroutine on a forgery. By demanding that the two libraries be indistinguishable, we are actually demanding that it is difficult for the calling program to generate a forgery.

Let \(\Sigma\) be a MAC scheme. We say that \(\sum\) is a secure MAC if \(\mathcal{L}_{\text {mac-real }}^{\Sigma} \approx \mathcal{L}_{\text {mac-fake }}^{\Sigma}\), where:

Discussion:

• The adversary can see valid tags of chosen messages, from the GETTAG subroutine. However, these tags shouldn’t count as a successful forgery. The way this is enforced is in the cHEcKTAG subroutine of \(\mathcal{L}_{\text {mac-fake }}\) - instead of always responding false, it gives the correct answer (true) for any tags generated by GETTAG.

In order for the two libraries to behave differently, the adversary must call cHECKTAG on input \((m, t)\) such that \(m\) was never used as an argument to GETTAG (so that \(\mathcal{L}_{\text {mac-fake }}\) responds false) but where the tag is actually correct (so that \(\mathcal{L}_{\text {mac-real }}\) responds true).

• The adversary can successfully distinguish if it finds any forgery - a valid MAC tag of any "fresh" message. The definition doesn’t care whether it’s the tag of any particular meaningful message.

MAC Applications

Although MACs are less embedded in public awareness than encryption, they are extremely useful. A frequent application of MACs is to store some information in an untrusted place, where we don’t intend to hide the data, only ensure that the data is not changed.

• A browser cookie is a small piece of data that a webserver stores in a user’s web browser. The browser presents the cookie data to the server upon each request.

Imagine a webserver that stores a cookie when a user logs in, containing that user’s account name. What stops an attacker from modifying their cookie to contain a different user’s account name? Adding a MAC tag of the cookie data (using a key known only to the server) ensures that such an attack will not succeed. The server can trust any cookie data whose MAC tag is correct.

When Alice initiates a network connection to Bob, they must perform a TCP handshake: 1. Alice sends a special SYN packet containing her initial sequence number \(A\). In TCP, all packets from Alice to Bob include a sequence number, which helps the parties detect when packets are missing or out of order. It is important that the initial sequence number be random, to prevent other parties from injecting false packets.

3. Bob sends a special SYN+ACK packet containing \(A+1\) (to acknowledge Alice’s \(A\) value) and the initial sequence number \(B\) for his packets.
4. Alice sends a special \(A C K\) packet containing \(B+1\), and then the connection is established.

When Bob is waiting for step 3, the connection is considered "half-open." While waiting, Bob must remember \(B\) so that he can compare to the \(B+1\) that Alice is supposed to send in her final ACK. Typically the operating system allocates only a very limited amount of resources for these half-open connections.

In the past, it was possible to perform a denial of service attack by starting a huge number of TCP connections with a server, but never sending the final ACK packet. The server’s queue for half-open connections fills up, which prevents other legitimate connections from starting.

A clever backwards-compatible solution to this problem is called SYN cookies. The idea is to let Bob choose his initial sequence number \(B\) to be a MAC of the client’s IP address, port number, and some other values. Now there is nothing to store for half-open connections. When Alice sends the final ACK of the handshake, Bob can recompute the initial sequence number from his MAC key.

These are all cases where the person who generates the \(\mathrm{MAC}\) is the same person who later verifies the MAC. You can think of this person as choosing not to store some information, but rather leaving the information with someone else as a "note to self."

There are other useful settings where one party generates a MAC while the other verifies.

• In two-factor authentication, a user logs into a service using something they know (e.g., a password) and something they have (e.g., a mobile phone). The most common two-factor authentication mechanism is called timed one-time passwords (TOTP). When you (as a user) enable two-factor authentication, you generate a secret key \(k\) and store it both on your phone and with the service provider. When you wish to log in, you open a simple app on your phone which computes \(p=M A C(k, T)\), where \(T\) is the current date \(+\) time (usually rounded to the nearest 30 seconds). The value \(p\) is the "timed one-time password." You then log into the service using your usual (long-term) password and the one-time password \(p\). The service provider has \(k\) and also knows the current time, so can verify the MAC \(p\).

From the service provider’s point of view, the only other place \(k\) exists is in the phone of this particular user. Intuitively, the only way to generate a valid one-time password at time \(T\) is to be in posession of this phone at time \(T\). Even if an attacker sees both your long-term and one-time password over your shoulder, this does not help him gain access to your account in the future (well, not after 30 seconds in the future).

\(\star 10.2\) A PRF is a MAC

The definition of a PRF says (more or less) that even if you’ve seen the output of the PRF on several chosen inputs, all other outputs look independently & uniformly random. Furthermore, uniformly chosen values are hard to guess, as long as they are sufficiently long (e.g., \(\lambda\) bits).

In other words, after seeing some outputs of a PRF, any other PRF output will be hard to guess. This is exactly the intuitive property we require from a MAC. And indeed, we will prove in this section that a PRF is a secure MAC. While the claim makes intuitive sense, proving it formally is a little tedious. This is due to the fact that that in the MAC security game, the adversary can make many verification queries CHECKTAG \((m, t)\) before asking to see the correct MAC of \(m\). Dealing with this event is the source of all the technical difficulty in the proof.

We start with a technical claim that captures the idea that "if you can blindly guess at uniformly chosen values and can also ask to see the values, then it is hard to guess a random value before you have seen it."

Claim \(10.3\) The following two libraries are indistinguishable:

Both libraries maintain an associative array \(T\) whose values are sampled uniformly the first time they are needed. Calling programs can try to guess these values via the guess subroutine, or simply learn them via REVEAL. Note that the calling program can call GUESS \((m, \cdot)\) both before and after calling \(\operatorname{REVEAL}(m)\).

Intuitively, since the values in \(T\) are \(\lambda\) bits long, it should be hard to guess \(T[m]\) before calling ReVEAL \((m)\). That is exactly what we formalize in \(\mathcal{L}_{\text {guess-R. }}\) In fact, this library doesn’t bother to even choose \(T[m]\) until \(\operatorname{ReVEAL}(m)\) is called. All calls to GUESs \((m, \cdot)\) made before the first call to \(\operatorname{REVEAL}(m)\) will return false.

Proof Let \(q\) be the number of queries that the calling program makes to GUESs. We will show that the libraries are indistinguishable with a hybrid sequence of the form: \[\mathcal{L}_{\text {guess-L }} \equiv \mathcal{L}_{\text {hyb-0 }} \approx \mathcal{L}_{\text {hyb-1 }} \approx \ldots \approx \mathcal{L}_{\text {hyb- }} \equiv \mathcal{L}_{\text {guess-R }}\]

| \(\mathcal{L}_{\text {guess-L }}\)
\(\frac{T: \text { empty assoc. array }}{\text { GUESs }\left(m \in\{0,1\}^{i n}, g \in\{0,1\}^{\lambda}\right):}\)
if \(T[m]\) undefined:
\(T[m] \leftarrow\{0,1\}^{\lambda}\)
return \(g \stackrel{?}{=} T[m]\)
\(\frac{\text { REVEAL }\left(m \in\{0,1\}^{i n}\right):}{\text { if } T[m] \text { undefined: }}\)
\(T[m] \leftarrow\{0,1\}^{\lambda}\)
return \(T[m]\)

The \(h\) th hybrid library in the sequence is defined as:

\(\mathcal{L}_{\text {hyb- } h}\)
count \(:=0\)
\(T:=\) empty assoc. array
GUESs \((m, g):\)
\(\quad \operatorname{count}:=\) count \(+1\)
if \(T[m]\) undefined and count \(>h:\)
\(T[m] \leftarrow\{0,1\}^{\lambda}\)
return \(g \stackrel{?}{=} T[m]\)
\(\quad / /\) returns false if \(T[m]\) undefined
REVEAL \((m)\) :
if \(T[m]\) undefined:
\(T[m] \leftarrow\{0,1\}^{\lambda}\)
return \(T[m]\)

This hybrid library behaves like \(\mathcal{L}_{\text {guess-R }}\) for the first \(h\) queries to GUESs, in the sense that it will always just return falsewhen \(T[m]\) is undefined. After \(h\) queries, it will behave

In \(\mathcal{L}_{\text {hyb- } 0}\), the clause "count \(>0 "\) is always true so this clause can be removed from the if-condition. This modification results in \(\mathcal{L}_{\text {guess-L }}\), so we have \(\mathcal{L}_{\text {guess-L }} \equiv \mathcal{L}_{\text {hyb- } 0}\).

In \(\mathcal{L}_{\text {hyb-q }}\), the clause "count \(>q "\) in the if-statement is always false since the calling program makes only \(q\) queries. Removing the unreachable if-statement it results in \(\mathcal{L}_{\text {guess-R, }}\), so we have \(\mathcal{L}_{\text {guess }-\mathrm{R}} \equiv \mathcal{L}_{\text {hyb-q }} .\)

It remains to show that \(\mathcal{L}_{\text {hyb- } h} \approx \mathcal{L}_{\text {hyb- }(h+1)}\) for all \(h\). We can do so by rewriting these two libraries as follows:

The library on the left is equivalent to \(\mathcal{L}_{\text {hyb- } h}\) since the only change is the highlighted lines, which don’t actually affect anything. In the library on the right, if \(T[m]\) is undefined during the first \(h+1\) calls to GUESs, the subroutine will return false (either by avoiding the if-statement altogether or by triggering the highlighted lines). This matches the behavior of \(\mathcal{L}_{\mathrm{hyb}-(h+1)}\), except that the library shown above samples the value \(T[m]\) which in \(\left.\mathcal{L}_{\text {hyb- }(} h+1\right)\) would not be sampled until the next call of the form GUESs \((m, \cdot)\) or \(\operatorname{ReVeAL}(m) .\) But the method of sampling is the same, only the timing is different. This difference has no effect on the calling program.

So the two libraries above are indeed equivalent to \(\mathcal{L}_{\text {hyb- } h}\) and \(\mathcal{L}_{\text {hyb- }(h+1)}\). They differ only in code that is reachable when bad \(=1\). From Lemma \(4.8\), we know that these two libraries are indistinguishable if \(\operatorname{Pr}[\mathrm{bad}=1]\) is negligible. In these libraries there is only one chance to set bad \(=1\), and that is by guessing/predicting uniform \(T[m]\) on the \((h+1)\) th call to GUESs. This happens with probability \(1 / 2^{\lambda}\), which is indeed negligible.