Preface

The Joy of Cryptography is an undergraduate-level textbook that introduces readers to the fundamentals of provable security. With over four hundred exercises, it is suitable as the main reference for a first course on cryptography or as a secondary resource for a course on computer/network security.

Provable security: Provable security is what demystifies cryptography and promotes it from an ad hoc game of cat-and-mouse to a principled discipline. It is how we answer questions like, What does it mean to be secure? Can we prove things about security?

This book teaches readers how to understand and especially do provable security: how to formally define security goals, how to prove security properties, and how to demonstrate that insecure things are insecure.

Topics: Cryptography involves many different flavors of algorithms, called primitives, each designed to provide a different flavor of security guarantee. This book provides a comprehensive treatment of the most important primitives that keep our digital lives safe: how they work, how they are different from each other, and why they are secure:

• Unconditionally secure cryptography: one-time pad and secret sharing.

• Fundamental primitives: pseudorandom generators, pseudorandom functions, and pseudorandom permutations.

• Symmetric-key encryption: chosen-plaintext and chosen-ciphertext attacks, authenticated encryption.

• Hashing: collision-resistant hash functions, universal hash functions, and random oracles.

• Asymmetric-key cryptography: key exchange, public-key encryption, and digital signatures.

• Advanced topics: encrypted messaging and ratcheting, authenticated key exchange, zero-knowledge proofs, and post-quantum cryptography.

Open access: An online, web-based version of the book is available for free at:

This online version includes animated visualizations of all hybrid security proofs.

Typos and other errors can be reported at github.com/rosulek/joc.

Message to students

I'm honored to be your guide to my favorite corner of computer science. Cryptography has a well-deserved reputation as a beautiful, fascinating, exciting topic. However, it also tends to be regarded as difficult, even intimidating. I think it's important to understand what exactly makes the study of cryptography challenging, so you can be better prepared for what to expect.

What Makes Cryptography Difficult? Cryptography demands rigor, precision, and attention to detail; there are definitions, theorems, and proofs. Indeed, cryptography is a mathematical discipline.

However, I believe that what makes cryptography difficult to learn is not the depth of math involved. (A list of specific prerequisites appears later in this section.) Instead, I believe its difficulty stems from the following:

• In cryptography, we study algorithms at a high level of abstraction. Compare the following two kinds of questions:

  • What can we say about combining AES and SHA3 (two standard cryptographic algorithms) in this particular way?

  • If $A$ is an arbitrary algorithm with security property $X$, and $B$ is an arbitrary algorithm with security property $Y$, then what can we say about combining $A$ and $B$ in this particular way?

  The first question asks about the security properties of one fully specified algorithm. The second question is more abstract; it is about an algorithm built from components $A$ and $B$, which remain unspecified. In this book we generally deal in abstract questions like the second one.

• Concrete examples can help you understand what an algorithm does, but not why it's secure. That's because security is a global property about the behavior of a system on all inputs; it's not something you can see through concrete examples. Besides that, our typical security goal is that when an algorithm is working as expected, its outputs “look like random junk.” What good does it do to show examples of random junk, other than to instill a false sense of security?

• Security means reasoning about what is not possible—what an adversary can't do. It usually takes more care and effort to prove such negative statements.

• Cryptography involves multiple participants, with fundamentally different perspectives of the same system. It's crucial to understand which perspective is being invoked at any given time, because what is true from one may be false from another. You will need to learn how to inhabit and reconcile these multiple perspectives.

Mathematical prerequisites: The book is meant to be accessible to a third- or fourth-year undergraduate student in a typical computer science (CS) degree program.

You should be comfortable with material that is standard in a typical first course on discrete math, including:

• basic discrete objects: functions (injective/surjective), sets and set operations (union, intersection, Cartesian product), tuples, strings, concatenation;

• simple combinatorics: counting objects as $2^n$, ${n \choose 2}$, etc;

• discrete probability: union bound, principles of multiplication and addition, conditional probabilities;

• logic: boolean operators, implications, contrapositive, quantifiers;

• induction and recursion;

• rules of exponents and logarithms;

• binary numbers;

• basic modular arithmetic: addition, subtraction, multiplication, idempotence of modular reduction: $(a+b) \pct n = ((a \pct n) + (b \pct n)) \pct n$;

• basic linear algebra: matrices and vectors, matrix multiplication, transpose.

Some of these concepts are briefly reviewed in appendix A, but the book is not ideal as a first exposure. Mathematical concepts not listed above (e.g., multiplicative modular inverses, totient function, Chinese remainder theorem, finite fields) are introduced as needed, and prior exposure is not assumed.

Computer science prerequisites: This book uses source code to unambiguously define not only cryptographic algorithms but also their security goals. You must be able to correctly interpret the meaning of that source code. It is especially important to understand when two different programs “do the same thing.”

Source code in this book is given only in a high-level pseudocode, so it's not important to have experience with any particular programming language. What's more important is a solid conceptual understanding of:

• flow control: conditional and looping constructs;

• variables: types and scope, especially the idea of scopes that are inaccessible from certain blocks of code;

• information dependency: When does one value/variable influence another?

• simple data structures: sets, arrays, associative arrays (dictionaries), strings;

• subroutines: calling principles, factoring out lines of code into a subroutine, inlining subroutine calls, recursion.

These elementary concepts are typically covered in an introductory course sequence in programming.

As I mentioned above, cryptography also involves a high degree of abstraction. It is therefore helpful, though not mandatory, to have prior exposure thinking about computational processes in this way. In undergraduate CS curricula, this usually happens in a theory of computation (automata) course.

Exercises: Each chapter contains a selection of exercises. Exercises marked with h have hints, which are located at the end of the chapter. Those marked with $\star$ are, in my opinion, significantly above average in difficulty or scope.

Message to teachers

Selection of material: Two philosophies have guided my selection of material for this book:

• Emphasize provable security above all else. Provable security is not just “learning about cryptography using definitions, theorems, and proofs,” but defining and proving things specifically about security properties—that is, an algorithm's behavior in the presence of a particular adversarial attack. There are plenty of mathematical facts that involve cryptography but are not about security properties (for example, this factoring/primality algorithm is correct, elliptic curve addition satisfies the axioms of a group, or there is a unique polynomial interpolating a set of points). The book includes some material of this flavor, but only selectively.

• Within the realm of provable security, focus on the constructions and techniques that inform cryptography in the real world.

If you and I haven't agreed on what to include in a cryptography textbook, it can probably be understood through the lens of these two guiding principles.

Organization: The book is designed so that material builds cumulatively on previous concepts. However, there are a few exceptions:

• Chapters and sections marked ☆ could be skipped in the interest of time. Subsequent material does not build heavily on them.

• Chapters on advanced topics (17–20) do not build on each other, so they can be read in any order.

Novel Approach to Provable Security: The main difference between this book and competitors is its overall approach to provable security. Below is a summary of my most opinionated choices.

All security definitions use a unified game-based style, where an interaction between adversary and challenger is specified precisely using pseudocode. I call these games libraries. The adversary plays the role of a calling program who can access the game/library through its designated interface of subroutines.

All security definitions are distinguishing games. Rather than defining a single game, in which the adversary tries to guess a secret bit $b$, I explicitly write both the $b=0$ and $b=1$ branches as two separate games; the adversary's goal is to distinguish between them. For example, an encryption scheme $\Sigma$ has IND$-CPA security if the following two games are indistinguishable (definition 8.1.1):

In the left library, $\key$ is privately scoped to the library and initialized at the beginning of time. Thus, every call to the $\cpaenc$ subroutine uses the same value of $\key$. In the right library, $\Sigma.\C(\ell)$ denotes the set of possible ciphertexts that result from encrypting length-$\ell$ plaintexts.

Even authenticity properties, as in digital signatures and authenticated encryption, are formalized as distinguishing games. For example, a digital signature scheme is secure if its verification oracle is indistinguishable from an oracle that “always” says no (see definition 16.1.2 for the more precise formulation).

All security proofs use a game-hopping approach, whose focus is not on explicitly writing a reduction algorithm but on making well-defined modifications to the pseudocode of a game/library. This unified approach to proofs is the book's “killer feature.” Each “hop” in the proof is a small change to the pseudocode of a game, along with a justification that the change has only a negligible effect on the adversary. Many changes/hops have self-evident justification (e.g., removing an unreachable statement). Some consecutive hybrids are indistinguishable because of a cryptographic assumption (e.g., $F$ is a secure PRF). In these cases, we do not write an explicit reduction algorithm but instead do the following. The assumption will be defined via two games, $G_0$ and $G_1$, which we assume are indistinguishable. We rewrite one hybrid game in our proof, so that $G_0$ appears as a separate, self-contained module (being sure that “factoring out” $G_0$ has no effect on the game's behavior). Now, with a literal instance of $G_0$ appearing as a subgame, we may replace it with $G_1$, and then inline the result to obtain a monolithic game again. Thus, we make a series of three indistinguishable changes to a game (factor out $G_0$, swap with $G_1$, inline $G_1$), each of which we can justify has negligible or no effect on the adversary. An explicit reduction algorithm is not the center of attention. Rather, it exists implicitly as the part of the game that remains unchanged when $G_1$ replaces $G_0$. An example is worth a thousand words, so I simply recommend examining the proof of claim 8.3.2 (CPA security of the $R \| (F(\key,R) \oplus \ptxt)$ encryption scheme) as a good representative example.

I make real-or-random indistinguishability, not left-or-right indistinguishability, the default approach for defining security of encryption. This choice reinforces a theme of the book, that we can define security by requiring outputs to “look like random junk.” Left-or-right security for encryption is an outlier, and students in my experience find it confusingly artificial: Why would an encryption algorithm require us to supply two plaintexts? The left-or-right style is still presented (sections 2.7, 8.1.2, and 9.2.1) as an alternative, and the two styles are contrasted in the text and in exercises. I define CCA security not by forbidding the adversary from decrypting challenge ciphertexts but by “patching” the decryption oracle to give the expected plaintext in these cases (definition 9.2.1). In general, I try to acknowledge that security definitions are choices, not sacred proclamations, so there are often several valid ways to approach a security definition.

MACs are not presented as a separate primitive; rather, message authentication is discussed as a property already enjoyed by PRFs. Thus, we do not discuss nonce-based or randomized MACs.

Resources: If you are interested in creating your own materials that follow this book's formatting style, you can find some tools available at:

About this online edition

You are reading an open-access, online edition of The Joy of Cryptography. It is free to read, but please bear in mind that, like the paper version, it is copyright CC-BY-ND-NC. In particular, you may not disseminate derivative works. No part of this book may be used to train artificial intelligence systems without permission in writing from the MIT Press.

I have decided to make an open-access edition of the book available only as a website, and not to maintain an open-access PDF version. Much older drafts of the book were available only in PDF and can be found circulating online. I strongly encourage you to use this newer edition of the book, which is significantly better in every conceivable way.

Additional Community Resources

Below are some additional educational resources related to The Joy of Cryptography:

• Nadim Kobeissi has designed a course on applied cryptography that includes high-quality slide decks closely following the presentation in The Joy of Cryptography. LaTeX source code is available!

Please feel free to contact me with additional contributions.

Errata

Below are known errata in the print edition, fixed in the online edition. To report additional bugs, click here.

• p47 (after Claim 2.6.2): “properties of different primitive” $\leadsto$ “properties of different primitives”

• p109 (“Birthday probabilities: take-home message”): “probability of a repeat is roughly of $q^2/N$.” $\leadsto$ delete “of”

• p138 (hints for exercises 5.12 and 5.13): “$\overline{\seed} = \seed \oplus \bit1^\secpar$” $\leadsto$ “$\overline{X} = X \oplus \bit1^\secpar$”

• p254: capitalize first sentence of section 9.2.1, oops.

• p334: “make the same first $t$ inputs” $\leadsto$ “use the same first $t$ inputs”

• p343 (proof of Claim 11.4.2): “over a uniform choice of $\key \gets \Z_\pmod$” $\leadsto$ the key is uniform in $\bits^\secpar = \Z_{2^\secpar}$, not $\Z_\pmod$.

• p400 (Example 13.2.2): “K2 = A^b ; K1” $\leadsto$ “K2 = A^b ; K2”

Acknowledgments

I am grateful for thoughtful technical feedback on this edition of The Joy of Cryptography from Martin Albrecht, Joël Alwen, Yevgeniy Dodis, Nadim Kobeissi, Hugo Krawczyk, Chris Peikert, and Douglas Stebila. Thank you to Jake Johanson and Zane Othman-Gomez for extensively beta-testing an early draft of this book and providing an unfiltered student perspective. Sincere, special thanks are due to the outstanding teachers and mentors that shaped my professional journey: Terry Balk taught me math (I wish we had had a chance to chat about cryptography!), Manoj Prabhakaran taught me cryptography, and Michael Loui taught me to embrace scholarly writing.

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

Thanks to Nicholas Rougeux for the website's graphic design.

There would be no Joy of Cryptography without the support and encouragement of the amazing Laura Rosulek. ily!

1. Next Chapter1. One-Time Pad and the Provable Security Mindset