BS Cyber Security, MS cryptography and advanced BSCS students can use this guide to study “A Graduate Course in Applied Cryptography” by Dan Boneh and Victor Shoup. The authors share it as a free draft on their book page, and the latest version is 0.6 from January 2023. It is not a finished edition: the preface says the draft is mostly complete with a few missing sections, and this page describes Version 0.6 as we read it, including the chapters that are still empty.
The book is mathematically demanding. It defines each security goal as an attack game and proves that constructions meet it, so it assumes comfort with probability, modular arithmetic and proofs. Part I covers encryption, stream and block ciphers, MACs, hash functions and authenticated encryption. Part II covers public-key encryption, signatures, elliptic curves and pairings, and attacks on number-theoretic assumptions. Part III covers login protocols, Schnorr signatures, zero knowledge, authenticated key exchange, threshold cryptography and multi-party computation. Beginners can skip the proofs, since each theorem has a short proof idea.
Book Overview
| Course | Cryptography / Applied Cryptography |
| Degree Programs | BS Cyber Security, MS (Cryptography), BSCS (advanced) |
| Level | Advanced undergraduate / graduate |
| Edition | Free draft, Version 0.6 (January 2023); earlier drafts 0.1 (2008) to 0.5 (2020) are also listed on the book page |
| Authors | Dan Boneh and Victor Shoup |
| Status | Draft by the authors: mostly complete, with some sections still marked To be written |
| Total Chapters | 23 chapters listed in three parts (Part I: 1–9, Part II: 10–17, Part III: 18–23) plus 4 appendices; 21 chapters have text, Chapters 1 and 17 are empty in this version |
| Exercises | End-of-chapter exercises in Chapters 2–16 and 18–23, about 490 in all, many with hints; no solutions in the PDF |
| Language | English |
| Format | PDF — one file of about 1,130 pages (9.1 MB) on the authors’ book page |
Chapter List
This page describes Version 0.6 of the draft (January 2023). The contents list 23 chapters, but Chapter 1 (Introduction) and Chapter 17 (Post-quantum cryptography from lattices) have no text in this version, so the blocks below cover the 21 chapters that are actually written, followed by the appendices.
Chapter 2: Encryption
Part I: Secret key cryptography · Difficulty: Medium · Key topics: Shannon cipher, perfect security, one-time pad, Shannon’s theorem, computational cipher, semantic security, negligible function, attack game
The chapter starts with the Shannon cipher, a pair of encryption and decryption functions over a key space, a message space and a ciphertext space, and defines perfect security. It shows that the one-time pad is perfectly secure and that Shannon’s theorem forces any perfectly secure cipher to use keys at least as long as the messages. It then relaxes the goal to computational ciphers and semantic security, defined through an attack game and the adversary’s advantage, and compares it with message recovery and bit guessing. A mathematical details section makes negligible functions and efficient adversaries precise, and the fun application is anonymous routing.
Key Points:
- A Shannon cipher is a pair (E, D) where D(k, E(k, m)) = m for every key k and message m.
- Perfect security means a ciphertext reveals nothing at all about which message was encrypted, even to an attacker with unlimited computing power.
- Shannon’s theorem: if a cipher is perfectly secure then the key space must be at least as large as the message space, so the key must be at least as long as the message.
- Semantic security replaces “unlimited attacker” with “efficient attacker”: no efficient adversary can tell encryptions of two chosen messages apart with more than a negligible advantage.
- Semantic security also rules out learning partial information, such as the parity of the message (Attack Game 2.3).
- Security is always stated for a single message per key; encrypting many messages needs the tools of Chapter 5.
Memory Tip: Perfect security is about information, semantic security is about computing power. The first holds against any attacker, the second only against attackers who run in reasonable time.
Common Mistake: Using a one-time pad key twice. The name means what it says: a repeated pad lets an eavesdropper XOR two ciphertexts and cancel the key.
Important Questions:
- Why can’t perfectly secure ciphers be used for large files? By Shannon’s theorem the key must be at least as long as the message, so a 1 GB video would need a 1 GB secret key agreed in advance.
- What does semantic security promise? That no efficient adversary can distinguish the encryptions of two messages of its choice with more than a negligible advantage, so ciphertexts leak nothing useful to such an adversary.
Chapter 3: Stream ciphers
Part I: Secret key cryptography · Difficulty: Medium · Key topics: pseudo-random generator, stream cipher, two-time pad, malleability, Blum-Micali, next bit test, Salsa and ChaCha, RC4
Starting from the one-time pad, the chapter replaces the long pad with the output of a pseudo-random generator stretched from a short seed, which gives a stream cipher that is semantically secure if the generator is secure. It defines PRG security through distinguishing games, shows that the two-time pad is insecure and that the one-time pad is malleable, and builds longer generators with parallel and sequential (Blum-Micali) composition. The next bit test is shown to capture PRG security. Case studies cover Salsa and ChaCha, linear generators, the 40-bit DVD encryption system and RC4, followed by random bit generation in practice.
Key Points:
- A stream cipher encrypts as G(s) XOR m, where the short seed s is the key and G is a pseudo-random generator.
- PRG security: no efficient statistical test can tell G(s) for a random seed from a truly random string of the same length.
- The two-time pad is insecure: XORing two ciphertexts made with the same key stream cancels the key stream and leaves the XOR of the two messages.
- Stream ciphers are malleable: flipping a ciphertext bit flips the same plaintext bit, with no way for the receiver to notice.
- Next bit test: a generator is secure exactly when no efficient adversary can predict the next output bit from the earlier bits.
- The DVD cipher uses a 40-bit key and can be broken far faster than trying all 2^40 keys; the linear congruential generator falls to simple algebra.
Memory Tip: A stream cipher is a one-time pad on a diet: the pad is regenerated from a short seed, so the seed must never be used for two messages.
Common Mistake: Reusing the same key (seed) for several messages and assuming the cipher is still secure. Semantic security covers one message per key only.
Important Questions:
- What is a pseudo-random generator? An efficient deterministic function that stretches a short random seed into a longer string such that no efficient test can distinguish its output from a uniformly random string.
- Why is the two-time pad insecure? Both ciphertexts hide their messages behind the same key stream, so c1 XOR c2 equals m1 XOR m2, which leaks information about both messages.
Chapter 4: Block ciphers
Part I: Secret key cryptography · Difficulty: Medium · Key topics: block cipher, DES, 3DES, AES, pseudo-random function, exhaustive search, side channels, Luby-Rackoff, tree construction, ideal cipher, Even-Mansour
Block ciphers are introduced as keyed permutations on a fixed block space whose security means looking like a random permutation, and pseudo-random functions are defined beside them. The chapter studies DES, the DES challenges, the 3E construction and AES, then surveys sophisticated attacks: algorithmic attacks on the cipher’s design, side channels, fault injection against AES and quantum exhaustive search. It shows when a secure block cipher is a secure PRF, builds PRGs from PRFs, and constructs block ciphers from PRFs (Luby-Rackoff) and PRFs from PRGs (the tree construction). It closes with the ideal cipher model and the Even-Mansour cipher.
Key Points:
- A block cipher is a family of permutations E(k, .) on a block space X; security means a random key gives a permutation that looks like a truly random one.
- AES uses 128-bit blocks with 128-, 192- or 256-bit keys; DES has a 56-bit key and a 64-bit block, which is why exhaustive search broke it in the DES challenges.
- Triple DES (a 3E construction) lengthens the effective key but is three times slower than DES and keeps the small 64-bit block.
- A PRF is a keyed function that looks like a random function; a secure block cipher on a large block is also a secure PRF.
- The Luby-Rackoff construction builds a block cipher from a PRF (a three-round Feistel structure), and the tree construction builds a PRF from a PRG.
- In the ideal cipher model the block cipher is treated as a family of random permutations; the Even-Mansour cipher XORs keys around a fixed public permutation.
- Side-channel and fault attacks target the implementation, not the mathematics of AES.
Memory Tip: A block cipher is a shuffled deck: each key picks one fixed shuffle of all possible blocks, and the shuffle is reversible. A PRF is the same idea without the requirement that it can be undone.
Common Mistake: Treating a block cipher as an encryption scheme by itself. Encrypting each block directly, with no mode of operation, leaks which blocks are equal; modes come in Chapter 5.
Important Questions:
- What makes a block cipher secure? An efficient adversary with a black box cannot tell whether it holds E(k, .) for a random key or a truly random permutation of the same block space.
- Why was AES needed after DES and Triple DES? DES’s 56-bit key fell to exhaustive search, and Triple DES is slow in software and its 64-bit block is a problem for many applications, so NIST ran an open process that selected AES.
Chapter 5: Chosen Plaintext Attack
Part I: Secret key cryptography · Difficulty: Medium · Key topics: CPA security, multi-key security, hybrid construction, randomized counter mode, CBC mode, nonce-based encryption, TLS 1.0 padding
This chapter moves from one message to many messages under one key, with an adversary who may influence some plaintexts. The introduction shows how reusing a stream cipher key on a file server lets an attacker who plants a large email recover key stream. The chapter defines multi-key semantic security and CPA security, then builds CPA-secure ciphers: a generic hybrid construction from a PRF, randomized counter mode and CBC mode, including a case study of CBC padding in TLS 1.0 and a comparison of concrete parameters. It also covers nonce-based encryption with nonce-based counter and CBC modes, and revocable broadcast encryption.
Key Points:
- In the CPA attack game the adversary submits pairs of messages and receives the encryption of one of them under the same key, many times over; its advantage must be negligible.
- A CPA-secure cipher cannot be deterministic: encrypting the same message twice must not give the same ciphertext, so each encryption uses fresh randomness or a nonce.
- Randomized counter mode and CBC mode both turn a secure PRF or block cipher into a CPA-secure cipher; counter mode encrypts independent blocks, CBC chains each block into the next.
- CBC needs an unpredictable IV; the nonce-based variant encrypts the nonce first to make it unpredictable.
- Nonce-based encryption only needs a nonce that never repeats under a key, not a random one.
- CPA security gives no integrity: ciphertexts can be altered without detection, which is the problem Chapters 6 to 9 solve.
Memory Tip: Counter mode is a pad you can compute in any order; CBC is a chain that must be built link by link. If you can parallelise encryption, think counter mode.
Common Mistake: Using a fixed or predictable IV with CBC. Uniqueness is not enough; for CPA security the IV must be unpredictable.
Important Questions:
- Why is semantic security not enough for encrypting many files with one key? It covers a single message per key. With a stream cipher an attacker who knows part of one file, or who gets an email stored, can recover key stream and decrypt other files.
- What is required of a nonce in nonce-based encryption? It must never be reused with the same key; it does not have to be secret or random.
Chapter 6: Message integrity
Part I: Secret key cryptography · Difficulty: Medium · Key topics: MAC, MAC security, PRF-based MAC, prefix-free PRF, CBC and cascade, extension attack, ECBC, NMAC, CMAC, PMAC
The chapter turns from eavesdroppers to active attackers. It defines a message authentication code as a tag computed from a message and a shared key, formulates MAC security as an attack game and shows that verification queries do not help the attacker. A secure PRF directly gives a MAC for short messages. For long messages the chapter builds prefix-free PRFs from CBC and cascade, shows that they are insecure MACs because of extension attacks, and then fixes them in three ways: encrypted PRF (ECBC and NMAC), prefix-free encodings and CMAC. It also covers ANSI CBC-MAC, the CMAC standard and the parallel PMAC; the searching on encrypted data section is marked To be written.
Key Points:
- A MAC is a pair of algorithms: sign computes a tag t from key k and message m, verify checks a pair (m, t); the message itself is not hidden.
- MAC security: after seeing tags on messages of its choice, an attacker cannot produce a valid tag on a new message.
- Any secure PRF with a large enough output is a secure MAC for messages that fit its input.
- CBC and cascade are secure only when no message is a prefix of another; for general messages they fall to extension attacks.
- ECBC and NMAC add a final PRF step under a second key; CMAC reaches the same goal with one key and a padding trick.
- PMAC is a parallelizable MAC, useful when a block cipher can be computed on many blocks at once.
- A MAC alone does not prevent an attacker from reordering or replaying valid messages.
Memory Tip: A MAC is a signature that needs a shared secret: only key holders can make a tag, but everyone who can check one can also forge one.
Common Mistake: Using raw CBC-MAC or a bare hash of key and message as a MAC on variable-length messages. Without a final step the tag is also a valid starting state for an extension.
Important Questions:
- Why is plain CBC not a secure MAC for variable-length messages? An extension attack lets the attacker take a tag on one message and compute a tag on a longer message without the key, because the tag is the internal chaining value.
- Does a MAC give confidentiality? No. It only detects modification; the message can be sent in the clear, as with public financial news where only integrity matters.
Chapter 7: Message integrity from universal hashing
Part I: Secret key cryptography · Difficulty: Hard · Key topics: universal hash function, multi-query UHF, polynomial hashing, hash-then-PRF, Carter-Wegman, nonce-based MAC, unconditionally secure MAC
Chapter 7 supplies the proofs that Chapter 6 postponed, through a general hash-then-PRF paradigm: shrink a long message to a short digest with a keyed hash, then apply a PRF to the digest. It defines universal hash functions and their multi-query variant and constructs them from polynomials, from CBC and cascade, and from a parallel construction based on a small PRF. The PRF(UHF) composition theorem then proves the security of ECBC, NMAC and PMAC0. The Carter-Wegman MAC, nonce-based MACs and unconditionally secure one-time MACs built from pairwise unpredictable functions follow. The timing attacks section is marked To be written.
Key Points:
- A universal hash function is a keyed hash for which any two different messages collide only with tiny probability over a random secret key.
- Hash-then-PRF: if H is a UHF and F is a secure PRF then F(k2, H(k1, m)) is a secure MAC.
- Polynomial hashing, evaluating a polynomial built from the message blocks at a secret point, is a fast UHF.
- CBC and cascade are computational UHFs, which is how the ECBC and NMAC proofs work.
- Carter-Wegman: a fresh PRF output derived from a nonce masks a UHF digest, so long messages are hashed with a cheap function and only the mask needs a PRF.
- One-time MACs can be unconditionally secure, meaning secure against attackers with unlimited computing power, when the key is used once.
Memory Tip: Squeeze, then lock: the cheap keyed hash squeezes a long message to a short digest, and the strong PRF locks the digest.
Common Mistake: Assuming a universal hash function is a MAC by itself. Its key is safe for one message only; the PRF layer is what hides the key across many messages.
Important Questions:
- What is the hash-then-PRF paradigm? Hash the message to a short digest with a universal hash function, then apply a secure PRF to the digest. The security of the MAC follows from the hash’s collision bound and the PRF’s security.
- What does the Carter-Wegman MAC gain over a PRF-only MAC? Speed on long messages, because the work on the message is a fast universal hash and only a short mask comes from the PRF, with a nonce so the mask is never reused.
Chapter 8: Message integrity from collision resistant hashing
Part I: Secret key cryptography · Difficulty: Medium · Key topics: collision resistance, birthday attack, Merkle-Damgard, Davies-Meyer, SHA256, HMAC, sponge, SHA3, Merkle tree, random oracle, HKDF
This chapter studies keyless collision resistant hash functions. It defines collision resistance, builds a MAC for large messages from a hash, and proves the birthday attack bound. The Merkle-Damgard paradigm, Joux’s multicollision attack and Davies-Meyer compression functions lead to the SHA256 case study and HMAC, and the sponge construction explains SHA3, SHAKE128 and SHAKE256. Merkle trees prove properties of a hashed list, and a long section covers key derivation, the random oracle model, the leftover hash lemma and HKDF. Weaker properties such as second preimage resistance and target collision resistance close the chapter, with commitments and auctions as the application.
Key Points:
- A hash function H is collision resistant if finding messages m0 and m1 with m0 different from m1 and H(m0) = H(m1) is infeasible.
- Birthday attack: a collision in an n-bit digest takes only about 2^(n/2) evaluations, so a 256-bit digest gives about 128 bits of collision resistance.
- Merkle-Damgard: iterate a compression function over message blocks; if the compression function is collision resistant, so is the whole hash.
- HMAC turns an unkeyed hash into a keyed PRF and MAC; the chapter analyses the two-key nest and then the HMAC standard.
- The sponge construction behind SHA3 absorbs input into a large state and squeezes output out; SHAKE128 and SHAKE256 give variable-length output.
- A Merkle tree lets you prove that one block belongs to a hashed list with a proof of only log n hashes.
- HKDF is the standard way to derive keys from a hash; the random oracle model is a heuristic for analysing such uses.
Memory Tip: Birthday rule of thumb: digest length is twice the security level you want. For 128-bit collision security, ask for 256 bits.
Practice Tip: In Python, hash a short message with hashlib.sha256 and print the digest, then change one letter and print again. The two digests share nothing visible, which is the “thorough scrambling” that hash functions are designed for.
Common Mistake: Building a MAC as hash(key + message). For Merkle-Damgard hashes that design has extension problems; use HMAC.
Important Questions:
- Why does a 256-bit hash give only about 128 bits of collision security? The birthday paradox: with k random digests a collision appears once k is about the square root of the digest space, which is 2^128 for 256-bit digests.
- What does a Merkle tree prove? That a given block sits at a given position in a hashed list, using a path of log n hashes checked against a short root hash, without revealing or sending the whole list.
Chapter 9: Authenticated Encryption
Part I: Secret key cryptography · Difficulty: Medium · Key topics: authenticated encryption, ciphertext integrity, CCA security, encrypt-then-MAC, padding oracle, associated data, GCM, TLS 1.3 record protocol, WEP
The chapter completes the symmetric story by combining confidentiality and integrity against attackers who interact with both sender and receiver. It defines ciphertext integrity and authenticated encryption, motivates CCA attacks with a concrete example and shows that authenticated encryption implies chosen ciphertext security. Generic composition is analysed in detail: encrypt-then-MAC is secure, MAC-then-encrypt is not in general, and padding oracle attacks on SSL show why. Nonce-based AE with associated data, Galois counter mode, the TLS 1.3 record protocol, an SSH attack on non-atomic decryption and the broken 802.11b WEP system are case studies. The private information retrieval application is marked To be written.
Key Points:
- Authenticated encryption (AE) means CPA security plus ciphertext integrity: an attacker cannot create a new ciphertext that decrypts successfully.
- AE implies CCA security, so an AE cipher stays secure even if the attacker can see how the receiver reacts to forged ciphertexts.
- Encrypt-then-MAC, with independent keys, is a secure generic composition.
- MAC-then-encrypt is not secure in general: padding oracle attacks on SSL recover plaintext from error behaviour.
- Associated data is data such as a packet header that is authenticated but not encrypted.
- Decryption must be atomic: releasing parts of a record before the check completes enabled an attack on an older SSH cipher suite.
- WEP, the 802.11b wireless protocol of 1999, is the book’s example of a badly broken system and shows how a weak design fails against real attackers.
Memory Tip: Encrypt first, then MAC the ciphertext. The receiver can then reject anything forged before it ever touches decryption.
Common Mistake: Giving different error messages or timings for “bad padding” and “bad MAC”. The difference is exactly what a padding oracle attack uses.
Important Questions:
- Why is CPA security insufficient for most applications? It gives no integrity, so an attacker can tamper with ciphertexts undetected, and tampering can break both secrecy and integrity of the messages.
- Why do real protocols prefer encrypt-then-MAC? It is provably secure with a CPA-secure cipher and a secure MAC, while MAC-then-encrypt is secure only for specific instances and is exposed to padding oracle attacks.
Chapter 10: Public key tools
Part II: Public key cryptography · Difficulty: Medium · Key topics: anonymous key exchange, trapdoor function, RSA, Diffie-Hellman, discrete log, CDH, DDH, Merkle puzzles, accumulators
Part II opens with the basic tools of public-key cryptography, introduced through a toy problem: two strangers on the phone must agree on a secret that a passive eavesdropper cannot guess. The chapter defines one-way trapdoor function schemes and instantiates them with RSA, then presents Diffie-Hellman key exchange and the discrete logarithm, computational Diffie-Hellman and decisional Diffie-Hellman assumptions, including random self-reducibility. It builds collision resistant hash functions from discrete log and RSA, shows attacks on the anonymous Diffie-Hellman protocol and describes Merkle puzzles as a partial symmetric-key solution. Accumulators are the fun application, and the chapter advises scanning Appendix A first.
Key Points:
- Diffie-Hellman: Alice sends g^a, Bob sends g^b, and both compute the shared secret g^(ab) in a cyclic group; an eavesdropper sees only g, g^a and g^b.
- The three assumptions: DL (find a from g^a), CDH (compute g^(ab) from g^a and g^b) and DDH (tell g^(ab) from a random element).
- A trapdoor function is easy to compute but hard to invert unless you know the trapdoor; RSA with e-th powers modulo n = pq is the main example.
- Anonymous Diffie-Hellman is secure only against passive eavesdroppers; an active attacker who can modify messages defeats it.
- Merkle puzzles achieve key exchange using only a block cipher, but the protocol is very inefficient.
- Collision resistant hash functions can also be built from number-theoretic problems, with collision resistance based on DL or on RSA.
Memory Tip: Hardness runs downhill: if you can solve discrete log you can solve CDH, and if you can solve CDH you can solve DDH. So DDH is the strongest assumption to rely on and DL the weakest.
Common Mistake: Treating plain Diffie-Hellman as an authenticated protocol. It gives a shared secret with whoever answered, not with the person you meant.
Important Questions:
- What is the decisional Diffie-Hellman assumption? That, for random exponents, the triple (g^a, g^b, g^(ab)) cannot be efficiently told apart from (g^a, g^b, g^c) with c random.
- Why is anonymous Diffie-Hellman not enough in practice? A man in the middle can run one exchange with each party and relay messages, learning both keys; real protocols need authentication, which is the subject of Chapter 21.
Chapter 11: Public key encryption
Part II: Public key cryptography · Difficulty: Medium · Key topics: public key, secret key, semantic security, randomized encryption, trapdoor-based encryption, RSA, ElGamal, oblivious transfer
The chapter defines public-key encryption through a key generation algorithm that outputs a public key and a secret key, so Alice can send Bob a ciphertext with no prior shared secret. It motivates the idea with two applications, sharing encrypted files with a hybrid scheme and key escrow, and then defines semantic security and shows it implies CPA security in this setting. It explains why public-key encryption must be randomized and gives two constructions: encryption from a trapdoor function scheme, instantiated with RSA, and ElGamal encryption, proved semantically secure both in the random oracle model and without it. The fun application is oblivious transfer from Diffie-Hellman.
Key Points:
- A public-key scheme is three algorithms: key generation outputs (pk, sk), encryption uses pk, decryption uses sk.
- Once Alice has Bob’s public key, only the ciphertext travels from Alice to Bob; no interaction is needed.
- Encryption must be randomized, because an attacker can encrypt guesses with the public key and compare.
- In the public-key setting semantic security already implies CPA security.
- Sharing encrypted files is hybrid encryption: the file is encrypted with a random symmetric key, and that key is encrypted under each reader’s public key.
- ElGamal encryption builds on Diffie-Hellman; its semantic security is proved from DDH, and also in the random oracle model.
- Key escrow lets a company recover an employee’s encrypted files through a server that holds copies of keys.
Memory Tip: For encryption, the public key locks and the secret key unlocks. Chapter 13 reverses the roles for signatures: the secret key signs and the public key checks.
Common Mistake: Using textbook RSA, with no randomness or padding, to encrypt messages directly. Equal plaintexts then give equal ciphertexts, which is not even CPA secure.
Important Questions:
- Why must public-key encryption be randomized? The encryption key is public, so a deterministic scheme lets an attacker encrypt candidate messages and compare them with the target ciphertext.
- How does ElGamal use Diffie-Hellman? The sender picks a fresh exponent, which acts like a one-time Diffie-Hellman exchange with the receiver’s public key, and the resulting shared group element is turned into a key that encrypts the message.
Chapter 12: Chosen ciphertext secure public key encryption
Part II: Public key cryptography · Difficulty: Hard · Key topics: CCA security, malleability, trapdoor-based CCA schemes, CCA-secure ElGamal, universal projective hash functions, PKCS1, Bleichenbacher attack, OAEP, private set intersection
Chapter 12 strengthens security to chosen ciphertext attack, described as the gold standard in the public-key setting. After the attack game it explains CCA security through ciphertext malleability, shows that adding a MAC does not give CCA security here the way it does in the symmetric setting, and relates CCA security to key escrow and to encryption as an abstract interface. Constructions follow: CCA-secure encryption from trapdoor functions, CCA-secure ElGamal, a scheme based on DDH without random oracles built on universal projective hash functions, and a generic transformation. The chapter ends with public-key encryption with associated data and a case study of PKCS1, Bleichenbacher’s attack, OAEP, OAEP+ and SAEP.
Key Points:
- In the CCA game the adversary may ask for decryptions of any ciphertext except the challenge, which models attackers who see how decryption behaves.
- CCA security forbids malleability: a changed ciphertext must not decrypt to a related message.
- The symmetric trick of adding a MAC does not work, since anyone can encrypt with the public key; CCA security needs a different design.
- Bleichenbacher’s attack broke RSA with PKCS1 padding by exploiting a server’s reaction to malformed ciphertexts.
- OAEP is the padding scheme for RSA encryption designed to give CCA security; OAEP+ and SAEP+ are variants discussed alongside it.
- One scheme in this chapter proves CCA security from DDH without random oracles, using universal projective hash functions.
- A generic transformation upgrades a weaker scheme to CCA security.
Memory Tip: CPA: the attacker may only encrypt. CCA: the attacker may also decrypt anything except the challenge. The stronger attacker needs the stronger defence.
Common Mistake: Assuming semantic security is enough because “the attacker only has the public key”. Real receivers decrypt messages and react, and that reaction is what CCA models.
Important Questions:
- What is a chosen ciphertext attack? An attack where the adversary can obtain decryptions of ciphertexts it chooses, other than the challenge ciphertext, in order to learn about the challenge message.
- What went wrong with RSA PKCS1 encryption? Bleichenbacher showed that a server that reveals whether a ciphertext decrypts to valid PKCS1 padding can be used as an oracle to decrypt chosen ciphertexts.
Chapter 13: Digital signatures
Part II: Public key cryptography · Difficulty: Hard · Key topics: signature security, full domain hash, RSA signatures, PKCS1 signatures, signcryption, certificates, PKI, revocation
The chapter motivates digital signatures with examples such as software distribution, where customers must verify an update without sharing a secret with the vendor. It defines signature schemes and security against chosen message attack, extends the message space using collision resistant or target collision resistant hashing, and builds signatures from trapdoor permutations with the full domain hash. A security analysis proves RSA full domain hash secure in the random oracle model with a loose reduction, and an RSA-based scheme with a tight proof follows. Further topics are PKCS1 signatures and Bleichenbacher’s attack on them, signcryption, certificates, the public-key infrastructure with certificate revocation and the legal aspects of digital signatures.
Key Points:
- A signature scheme has a secret signing key and a public verification key: only the key holder can sign, anyone can verify.
- Security means existential unforgeability under chosen message attack: no valid signature on a new message even after seeing signatures on messages of the attacker’s choice.
- Hashing first lets a scheme sign messages of any length; the hash must be collision resistant or at least target collision resistant.
- Full domain hash signs the hash of the message with the inverse of a trapdoor permutation such as RSA.
- Signcryption gives a recipient both confidentiality and proof of origin, useful for messaging when the receiver is offline.
- Certificates bind a public key to an identity; the PKI needs ways to cope with malicious or negligent certificate authorities and with revocation.
- The law’s idea of a valid signature is about intent, which differs from the cryptographic definition.
Memory Tip: MAC: a shared key, so anyone who can verify can forge. Signature: only the signer can sign, and anyone can verify. That is why signatures work for software updates and certificates.
Common Mistake: Signing a raw message with RSA without hashing and proper padding. Padding mistakes in PKCS1 signatures led to Bleichenbacher’s attack.
Important Questions:
- Why can’t a MAC replace a digital signature for software updates? A MAC needs a secret shared with every customer, and anyone holding that secret could forge updates, whereas a signature is verified with a public key that can be built into the software.
- What does a certificate do? It binds a public key to an identity, signed by a certificate authority, so that a verifier knows whose key it holds, with revocation as the way to withdraw a certificate that should no longer be trusted.
Chapter 14: Fast hash-based signatures
Part II: Public key cryptography · Difficulty: Medium · Key topics: one-time signatures, Lamport, Winternitz, HORS, Merkle signatures, indexed signatures, TESLA, post-quantum security
The chapter builds signature schemes from one-way and collision resistant hash functions instead of from a trapdoor permutation. It starts with basic Lamport one-time signatures, shrinks them with enhanced target collision resistance, and develops a general Lamport framework with containment free functions, Winternitz signatures with domination free functions and HORS short signatures whose public key is shrunk with a Merkle tree. Applications of one-time signatures include online/offline signing and authenticating streamed data. Indexed signatures then lead to many-time signatures, the complete Merkle stateless signature system and nonce-based Merkle signatures. The TESLA broadcast MAC for satellite navigation is the fun application.
Key Points:
- A one-time signature key pair can safely sign only one message; a q-time scheme can sign up to q messages.
- Hash-based signatures can be much faster than RSA, and with suitable parameters they resist quantum attackers, which is the main reason for interest in them.
- The drawback is size: signatures are far longer than RSA signatures, so they suit large objects like software updates, not web certificates.
- Lamport signatures reveal hash preimages chosen by the message bits; Winternitz and HORS trade signature size against computation.
- A Merkle tree combines many one-time public keys under a single short public key, which turns one-time signatures into many-time ones.
- TESLA is a broadcast MAC presented as a defence against spoofing of satellite navigation signals, where signing every message would be too costly.
Practice Tip: Implement a Lamport signature for a 16-bit message with Python’s hashlib. Count how many secret values you store and publish, and you will see directly why these signatures are large.
Common Mistake: Signing two messages with the same one-time key. Each signature reveals secret values, and two signatures can give an attacker enough to forge a third.
Important Questions:
- Why are hash-based signatures interesting for the post-quantum era? They rely only on the security of hash functions, and with suitable parameters they stay secure against an adversary with a quantum computer, unlike RSA.
- How do you get many-time signatures from one-time ones? Place many one-time public keys at the leaves of a Merkle tree, publish the root as the public key, and attach the leaf index and authentication path to each signature.
Chapter 15: Elliptic curve cryptography and pairings
Part II: Public key cryptography · Difficulty: Hard · Key topics: elliptic curve group, secp256r1, Curve25519, twist security, pairing, BLS signatures, identity based encryption, functional encryption, multilinear maps
The chapter begins from the cost of working modulo a 2048-bit prime and presents elliptic curve groups, where the best known discrete log attack takes roughly the square root of the group size, so a 256-bit group gives about AES-128 security. It covers the group of points on a curve, curves over finite fields, Montgomery and Edwards forms and standard curves such as secp256r1, secp256k1 and Curve25519, including twist security. It then develops pairing-based cryptography: signature schemes from pairings including BLS and aggregation, identity based encryption, functional encryption and multilinear maps. Fair exchange of signatures is the fun application.
Key Points:
- The general number field sieve is why modular groups need primes of at least 2048 bits; elliptic curve groups have no comparable shortcut, so a group of about 2^256 elements suffices for 128-bit security.
- The group operation on a 256-bit curve costs a few operations modulo a 256-bit prime, much cheaper than arithmetic modulo a 2048-bit prime.
- A curve is called twist secure if discrete log is hard both on the curve and on its twist, a requirement the chapter discusses for standard curves.
- A pairing is an efficiently computable bilinear map between groups; it adds extra structure that is very useful in cryptography.
- BLS signatures are short and can be aggregated into one signature that covers many signers.
- Identity based encryption lets a user’s identity string act as the public key; functional encryption generalises this to decryption keys for chosen functions.
Memory Tip: Elliptic curves buy the same security with much smaller numbers: 256 bits instead of 2048. Pairings add one extra operation that lets you check an equation in the exponent.
Common Mistake: Choosing your own curve parameters. Use a standard, vetted curve such as Curve25519 or secp256r1, whose security properties the chapter examines.
Important Questions:
- Why are elliptic curves preferred to Z_p* for discrete log systems? The best attacks on a good curve are generic, taking about the square root of the group size, so far smaller and faster groups reach the same security level than with modular arithmetic.
- What is a pairing used for? A pairing maps two group elements to a third group in a way that is linear in each argument, allowing a verifier to test relations among exponents, as in BLS signature verification.
Chapter 16: Attacks on number theoretic assumptions
Part II: Public key cryptography · Difficulty: Hard · Key topics: generic discrete log algorithms, composite order groups, static Diffie-Hellman attack, number field sieve, generic lower bound, factoring, RSA key generation attacks, fault injection, quantum attacks
This chapter examines how hard the assumptions of earlier chapters really are, and how real implementations fail. It presents discrete log algorithms that work in any cyclic group, including square-root-time algorithms, groups of composite order, information leakage and an attack on static Diffie-Hellman, and the relation among DL, CDH and DDH. It then covers the general number field sieve with discrete log records and a preprocessing attack, a lower bound for generic groups, factoring algorithms, RSA attacks caused by poor key generation, a fault injection attack on optimized RSA and an attack on low secret exponent RSA. Quantum attacks on factoring and discrete log are discussed last; the Notes section is marked To be written.
Key Points:
- Brute-force discrete log takes about q steps in a group of order q, while square-root-time algorithms need about the square root of q steps in any group.
- Groups of composite order are weaker than prime-order groups because the problem can be split into smaller pieces, which is why the earlier chapters use prime order.
- The general number field sieve attacks discrete log in Z_p* and factoring, and has solved discrete logs modulo prime sizes in the hundreds of bits.
- In generic groups, any discrete log algorithm needs about the square root of the group order, which supports the use of elliptic curves.
- Poor randomness in RSA key generation, fault injection during CRT-optimized RSA signing and a small secret exponent each break RSA in practice even when the math is sound.
- A quantum computer breaks factoring and discrete log, which is why long-lived secrets may need post-quantum cryptosystems.
Memory Tip: Remember the three families of attack: generic (work in any group), structured (the number field sieve uses the structure of Z_p*) and implementation (bad randomness, faults, small exponents). Good parameters stop the first two, good engineering stops the third.
Common Mistake: Believing that a mathematically hard problem guarantees a secure system. Several attacks in this chapter need no new mathematics, only a faulty key generator or a computation error.
Important Questions:
- Why is a 2048-bit prime needed for Z_p* but a 256-bit group for elliptic curves? The number field sieve runs in sub-exponential time on Z_p*, while the best known attack on a good elliptic curve is a generic square-root attack.
- What threat does quantum computing pose? A quantum computer can factor integers and compute discrete logs efficiently, so RSA, Diffie-Hellman and elliptic curve systems would be broken, which matters for data that must stay secret for decades.
Chapter 18: Protocols for identification and login
Part III: Protocols · Difficulty: Medium · Key topics: identification protocol, direct, eavesdropping and active attacks, password protocols, dictionary attacks, salt, slow hash, HOTP, TOTP, S/key, challenge-response, rainbow tables
Chapter 18 studies identification, also called the login problem, with examples such as a door lock, a car key fob and an ATM that may be fake. It defines interactive protocols and the security of ID protocols against direct, eavesdropping and active attacks. Password protocols come first, with dictionary attacks and the defences against them: public salts, secret salts, slow hash functions such as PBKDF2, memory-hard hash functions such as scrypt, and password management issues. One-time passwords (HOTP, TOTP and S/key) resist eavesdropping and challenge-response protocols resist active attacks. Rainbow tables are the fun application, and the hardening password storage section is marked To be written.
Key Points:
- The chapter uses three attacker levels: a direct attack (the attacker only talks to the verifier), an eavesdropping attack, and an active attack where the attacker can interact with the prover.
- In the basic password protocol the prover simply sends the password, so it is only safe when nobody can eavesdrop; if the verifier’s stored data leaks, a dictionary attack can recover weak passwords.
- Salts make precomputed tables useless across users; slow and memory-hard hash functions make each guess more expensive.
- HOTP derives one-time passwords from a counter and TOTP from the time, both with a PRF; S/key uses a hash chain.
- Challenge-response protocols, built from a MAC or a signature, resist active attackers because every login uses a fresh challenge.
- Rainbow tables are a time-memory trade-off for inverting a hash function, much faster than exhaustive search over all passwords.
Memory Tip: Direct, eavesdropping, active: each level of attacker is stronger than the last, so a protocol that survives active attacks also survives the other two.
Common Mistake: Storing passwords as a single unsalted fast hash such as SHA256(password). Offline guessing is then extremely cheap.
Important Questions:
- Why are salts used when storing password hashes? A salt makes the hash of the same password different for each user, so one precomputed table cannot be used against the whole password file.
- How does challenge-response stop a replay attack? The verifier sends a fresh random challenge each time and the prover answers with a MAC or signature on it, so an eavesdropper’s recorded answer is useless for a new login.
Chapter 19: Identification and signatures from Sigma protocols
Part III: Protocols · Difficulty: Hard · Key topics: Schnorr identification, Fiat-Shamir, Schnorr signatures, ECDSA, Sigma protocol, special soundness, special HVZK, Chaum-Pedersen, AND and OR proofs, witness independence
The chapter develops Schnorr’s identification protocol, which is secure against eavesdroppers under the discrete log assumption, and turns it into the efficient Schnorr signature scheme using the Fiat-Shamir idea, secure in the random oracle model. It analyses repeated impersonation attacks, discusses implementation and the ECDSA case study, and then generalises to Sigma protocols defined by special soundness and special honest verifier zero knowledge. Examples include Okamoto’s protocol, Chaum-Pedersen for Diffie-Hellman triples, protocols for linear relations, homomorphism pre-images and RSA. It also covers AND and OR proofs, witness independence with actively secure identification, and multi-extractability. A two-round protocol application is marked To be written.
Key Points:
- A Sigma protocol has three moves: the prover sends a commitment, the verifier sends a random challenge, and the prover sends a response.
- Special soundness: from two accepting transcripts with the same commitment and different challenges one can extract the prover’s secret, which makes the protocol a proof of knowledge.
- Special honest verifier zero knowledge: a simulator can create transcripts that look real without knowing the secret, so a transcript reveals nothing.
- The Fiat-Shamir heuristic replaces the verifier’s challenge with a hash of the commitment and the message, which turns identification into a signature.
- The Chaum-Pedersen protocol proves that a triple of group elements is a Diffie-Hellman triple.
- AND and OR constructions combine Sigma protocols to prove several statements, or one of several statements, at once.
- ECDSA, a widely deployed signature scheme, is discussed as a case study alongside Schnorr.
Memory Tip: Commit, challenge, respond. The random commitment hides the secret, the challenge forces the prover to be honest, and the response lets the verifier check it.
Common Mistake: Reusing or leaking the per-signature random value in Schnorr or ECDSA. The signing equation then exposes the secret key.
Important Questions:
- How does Fiat-Shamir turn identification into a signature? The signer computes the challenge as a hash of the commitment and the message, so no interactive verifier is needed, and the resulting signature is secure in the random oracle model.
- What do special soundness and special HVZK mean? The first lets you extract the secret from two related transcripts, so only a prover who knows it can succeed. The second says transcripts can be simulated without the secret, so they leak nothing.
Chapter 20: Proving properties in zero-knowledge
Part III: Protocols · Difficulty: Hard · Key topics: language and soundness, proofs on encrypted data, non-interactive proofs, Fiat-Shamir transform, NIZK, computational zero knowledge, range proofs
Chapter 20 uses Sigma protocols to prove that statements are true, instead of proving knowledge of a witness. It defines the language of true statements for a relation and a notion of soundness, then shows how to prove properties of encrypted data, with a generic protocol for non-linear relations. Non-interactive proofs follow, covering syntax, the Fiat-Shamir transform, non-interactive soundness and zero knowledge, a voting protocol example and the Chaum-Pedersen protocol made non-interactive. Computational zero knowledge brings range proofs, special computational HVZK and an unconstrained generic protocol. In Version 0.6 the sections on Bulletproofs, SNARKs and the closing application are marked To be written.
Key Points:
- The language of a relation is the set of statements that have a witness; soundness means no prover can make the verifier accept a statement outside the language.
- Special soundness implies soundness, but the new notion needs no witness extractor.
- Sigma protocols can prove properties of encrypted data, for example that a ciphertext encrypts a value in a given set, without revealing the value.
- The Fiat-Shamir transform makes the proof non-interactive, which needs a careful notion of non-interactive soundness.
- Range proofs show that a hidden value lies in a given range, an important application of computational zero knowledge.
- Bulletproofs and SNARKs are named in the chapter plan but their sections have not been written in this draft.
Memory Tip: Chapter 19 asks “do you know the secret?” (proof of knowledge). Chapter 20 asks “is this statement true?” (soundness). The same Sigma protocol machinery answers both.
Common Mistake: Mixing up proof of knowledge and proof of a statement. In many applications only the truth of the statement matters, not who knows the witness.
Important Questions:
- What is soundness for a Sigma protocol? It is infeasible for any prover to make the verifier accept a statement that has no witness, that is, one outside the language.
- What is a non-interactive zero knowledge proof? A single message that convinces a verifier a statement is true while revealing nothing else, built here from a Sigma protocol with the Fiat-Shamir transform.
Chapter 21: Authenticated Key Exchange
Part III: Protocols · Difficulty: Hard · Key topics: AKE, session key, trusted third party, perfect forward secrecy, HSM security, deniability, channel binding, TLS 1.3 handshake, PAKE, online TTP
Chapter 21 answers the question left open since Chapter 9: how do Alice and Bob get the shared key in the first place? Authenticated key exchange protocols give each party a fresh session key known only to the intended partner, usually with the help of an offline trusted third party. The chapter builds an encryption-based protocol, studies insecure variations, then adds perfect forward secrecy through ephemeral encryption, HSM security, identity protection, one-sided authentication, deniability and channel bindings. It gives formal definitions with security proofs, a case study of TLS 1.3 session setup, password authenticated key exchange protocols PAKE0 to PAKE+2 and key exchange with an online trusted third party. Establishing Tor channels is marked To be written.
Key Points:
- An AKE protocol must leave each party with a session key that is fresh, random and known only to the partner it believes it is talking to.
- An offline trusted third party registers users and gives each a long-term key, then plays no part in later sessions.
- Perfect forward secrecy: leaking long-term keys later must not expose past session keys, achieved by using ephemeral keys that are erased.
- HSM security asks that, if a session’s ephemeral data leaks while the long-term key stays protected inside a hardware security module, the damage is limited to that session.
- One-sided authentication covers the web case where the server proves its identity but the client does not, and it is combined with password login.
- Channel bindings give the higher-level application a unique name for the session.
- PAKE protocols let a client and server who share a password agree on a key and are designed to resist the phishing attacks that defeat simple password login.
Memory Tip: A key is only useful if you know who else holds it. AKE means key exchange plus authentication: “a key shared with whom?” is half of the definition.
Common Mistake: Running unauthenticated Diffie-Hellman and calling the result secure. Without authentication the key may be shared with an attacker.
Important Questions:
- What is perfect forward secrecy? The property that compromising a long-term key does not reveal earlier session keys, because each session used fresh ephemeral values that were then erased.
- Why is simple password login over a one-sided authenticated channel risky? A phishing attacker can trick a client into entering the password into a fake server, which is what password authenticated key exchange is designed to prevent.
Chapter 22: Threshold cryptography
Part III: Protocols · Difficulty: Hard · Key topics: Shamir secret sharing, threshold signatures, threshold BLS, threshold decryption, distributed key generation, linear secret sharing, access structures, gap security
Threshold cryptography protects secret keys by splitting them into shares held by different servers. The chapter starts with Shamir’s secret sharing scheme and its security. It then develops threshold signatures (a generic scheme, BLS threshold signing, security definitions, accountability versus privacy and accountable threshold BLS) and threshold decryption, including an insecure scheme, a secure scheme based on CDH and a pairing-free version. Distributed key generation removes the need for a trusted dealer. The chapter goes beyond threshold to monotone access structures, linear secret sharing and monotone span programs, and ends with gap security. The randomness beacon application is marked To be written.
Key Points:
- The motive: if an attacker steals a decryption or signing key, everything protected by it is lost; splitting the key into shares on N servers makes theft harder.
- Shamir sharing hides the secret as the constant term of a random polynomial; any t shares recover it, and fewer than t reveal nothing.
- Threshold signing and decryption work without ever reconstructing the secret key in one place.
- Threshold BLS is the chapter’s main signature example, with its security definitions and an accountable variant.
- Distributed key generation lets the servers create the key shares together, with no dealer who sees the whole key.
- Monotone access structures generalise “any t of N” to arbitrary rules about which groups may act, using linear secret sharing and monotone span programs.
Memory Tip: t points fix a polynomial of degree t minus 1. That is why t shares recover the secret while fewer give no information.
Common Mistake: Reconstructing the whole key on one machine to use it. That destroys the benefit of sharing; the point is to sign or decrypt without ever assembling the key.
Important Questions:
- How does Shamir secret sharing work? The dealer picks a random polynomial whose constant term is the secret and gives each party its value at a different point; any t parties can interpolate the polynomial and read off the secret.
- What does distributed key generation add? It removes the trusted dealer: the parties jointly create a key pair so that nobody ever holds the full secret key.
Chapter 23: Secure multi-party computation
Part III: Protocols · Difficulty: Hard · Key topics: MPC, honest-but-curious and malicious security, arithmetic circuits, Beaver’s protocol, garbled circuits, secure distributed core, universal composability, oblivious transfer, OT extension
Chapter 23 starts from a sealed-bid second-price auction run by a trusted server and the failure scenarios that arise if that server is compromised or cheats; multi-party computation removes the single point of trust. It covers informal and formal notions of security, assumptions and other applications, evaluation of arithmetic circuits with Beaver’s honest-but-curious 2.5-party protocol and a maliciously secure version, and Yao-style garbled circuits with garbling schemes and 2-party and 3-party protocols. It then presents an approach based on a secure distributed core and the universal composability framework with real and ideal executions and security proofs for OT, Beaver and garbled circuit protocols, followed by threshold MPC and OT extension.
Key Points:
- MPC lets several parties compute a function of their private inputs so that nothing is revealed beyond the output, without a trusted party.
- Honest-but-curious adversaries follow the protocol but try to learn more; malicious adversaries may deviate arbitrarily, so malicious security is much harder.
- Beaver’s protocol evaluates an arithmetic circuit using data supplied by a dealer in a preprocessing phase before the inputs are known.
- Garbled circuits encrypt a Boolean circuit gate by gate; the chapter gives a 2-party honest-but-curious protocol and a simpler 3-party protocol secure against one malicious party.
- The universal composability framework defines security by comparing a real protocol execution with an ideal one.
- OT extension reduces the cost of the many oblivious transfers that MPC needs.
Memory Tip: Ask two questions of any MPC protocol: how many parties may be corrupt, and what may corrupt parties do (watch only, or cheat)? Those two answers define its security.
Common Mistake: Treating honest-but-curious security as if it protected against cheating. A protocol secure only against honest-but-curious parties can be broken by a party who deviates from it.
Important Questions:
- What problem does MPC solve in the auction example? It removes the need to trust the server, since hacking one server or a server that cheats can no longer reveal the losing bids or the wrong winner.
- What is a garbled circuit? An encrypted version of a Boolean circuit that lets a party evaluate it on hidden inputs and learn only the output, forming the basis of Yao-style two-party computation.
Appendices A to D
Appendix · Difficulty: Medium · Key topics: cyclic groups, arithmetic modulo primes, quadratic residues, Euler’s theorem, birthday paradox, distinguishing distributions
Appendix A collects number theory for the public-key chapters: cyclic groups and generators, arithmetic modulo primes with Fermat’s and Lagrange’s theorems, the order of an element, the structure of Z_p*, quadratic residues and square roots, and a summary of problems that are easy or believed hard modulo a prime. It then turns to composite moduli, with Euler’s theorem and a summary of what becomes easy if the factorization is known. Appendix B proves the birthday paradox bound and shows how a collision probability graph behaves around the square root, then starts an example on telling two distributions apart. Appendices C (complexity theory) and D (probabilistic algorithms) say To be written in Version 0.6.
Key Points:
- Z_p* is a cyclic group: some generator g has powers that produce every nonzero element modulo p.
- Computing g^r mod p is easy even for huge r, but finding r from the result (the discrete logarithm) is believed hard.
- Euler’s theorem: a to the power phi(n) is 1 modulo n for every a coprime to n; for a prime this is Fermat’s theorem.
- When p is 3 mod 4, a square root of a quadratic residue modulo p is easy to compute with one exponentiation.
- Birthday paradox: after k samples from a set of size n a collision is likely once k is about the square root of n, with probability about 0.4 at that point for n = 10^6.
Practice Tip: Check Fermat’s theorem in Python with pow(3, 4, 5), which gives 1, and list the powers of 3 modulo 7 to see that 3 generates every nonzero element while 2 does not.
Common Mistake: Relying on the appendices as a complete background. In Version 0.6 they are brief notes, the statement of the Chinese remainder theorem is still missing and two appendices are empty, so use a number theory or probability text alongside.
Important Questions:
- What does the birthday paradox say about hash functions? Collisions among k random digests in a set of size n become likely when k is about the square root of n, so digests must be twice as long as the security level in bits.
- What are the easy and hard problems in Z_p*? Exponentiation, inversion, linear systems and square roots are easy; discrete log, CDH and DDH are believed to be hard.
How to Study This Book
The free PDF is Version 0.6 (January 2023), about 1,130 pages in three declared parts: Part I (Chapters 1 to 9) on secret key cryptography, Part II (Chapters 10 to 17) on public key cryptography and Part III (Chapters 18 to 23) on protocols, followed by four appendices. Do not plan to read it cover to cover. The authors say a beginning reader can skip the detailed proofs, because every security theorem is followed by a short proof idea, and can also skip the sections called Mathematical details. Chapters 1 and 17 are listed in the contents but have no text in this version, so the PDF jumps from the contents to Part I and from the end of Chapter 16 to Part III.
Before you start, check your prerequisites honestly. The book defines every security goal as an attack game and measures security by an adversary’s advantage, so you need discrete probability (events, conditional probability, random variables, the union bound), modular arithmetic and basic group theory, a feel for polynomial-time algorithms, and some patience with proofs. No programming is required. Appendices A and B are short notes and Appendices C and D are empty, so keep a discrete mathematics or probability text beside you.
A good first course in applied cryptography follows this path. Read Chapter 2 (Sections 2.1 and 2.2) for perfect and semantic security, Chapter 3 for stream ciphers and the two-time pad, Sections 4.1, 4.2 and 4.4 for block ciphers, DES, AES and PRFs, then Chapter 5 for CPA security and modes of operation. Continue with Sections 6.1 to 6.5 for MACs, Sections 8.1 to 8.7 for collision resistant hashing, SHA256 and HMAC, and Chapter 9 for authenticated encryption, which is where the symmetric story pays off. Chapter 7 and Sections 4.5 to 4.7 are proof-heavy and can wait for a second pass.
For public-key topics read Chapter 10 (Diffie-Hellman, RSA and the DL, CDH and DDH assumptions), Chapter 11 on public-key encryption, Sections 12.1 to 12.3 and 12.8 on CCA security and the PKCS1 and OAEP case study, and Sections 13.1 to 13.3 and 13.8 on signatures and certificates. Sections 15.1 to 15.3 give the elliptic curve material most courses need; the pairing sections 15.4 to 15.8 and Chapter 14 on hash-based signatures are for students who want depth. Chapter 16 is worth reading for its attacks, especially the RSA key generation and fault injection sections, and Section 16.5 for the quantum threat.
Part III is the most advanced part. Chapter 18 on login is accessible early, since it covers dictionary attacks, salting, slow hashes, HOTP and TOTP. Chapter 19 (Schnorr identification and signatures, ECDSA) and Sections 21.1 to 21.3 and 21.10 (authenticated key exchange, forward secrecy and the TLS 1.3 handshake) suit a second course. Chapters 20, 22 and 23, on zero knowledge, threshold cryptography and multi-party computation, read like research notes and are best for graduate students or for MS thesis reading.
Do not skip the case studies; they show why the definitions matter. The DVD cipher (Section 3.8), RC4 (3.9), CBC padding in TLS 1.0 (5.4.4), padding oracle attacks (9.4.2), the SSH attack (9.9), WEP (9.10) and Bleichenbacher’s attacks (12.8.3 and 13.6.1) each show a real failure that a definition would have prevented. A good habit is to write down, for every chapter, the attack game, what the adversary may ask and what advantage must be negligible.
Know the gaps before you rely on it. Besides Chapters 1 and 17, several chapter-ending fun application sections (6.12, 7.7, 9.11, 13.10, 18.8, 19.10, 20.7, 21.13, 22.7 and 23.8), the Bulletproofs and SNARK sections (20.5 and 20.6), the Notes of Chapter 16 and Appendices C and D say To be written. The Notes sections say citations are still to be added, although a bibliography of about 150 entries is at the end. There are no lab exercises or solutions; some of the roughly 490 exercises have hints, and the book does not cover lattice-based post-quantum schemes in this version. This page describes the draft as it stood when we read it, and a newer version may differ, so check the official page.
Used In These Programs
This book is used for Cryptography and Applied Cryptography courses in: BS Cyber Security, and as advanced reading for BS Computer Science and MS cryptography students. Browse all Cryptography books or all Computer Science books.
Who Should Read This
This book is written for advanced undergraduate and graduate students in BS Cyber Security, BSCS and MS programs who want to understand why cryptographic constructions are secure, not just how to call a library. It suits a second course after a basic security class, or a first course for students who are strong in mathematics, and it is a good reference for researchers and engineers who need the exact security definition behind a tool like AES-GCM, HMAC, TLS or Schnorr signatures. It is not a first book for someone who has never done a proof, and it is not a practical guide to using crypto libraries or to penetration testing. If probability or number theory is rusty, Mathematics for Computer Science covers probability, modular arithmetic, number theory and RSA, and Discrete Mathematics: An Open Introduction and Foundations of Computer Science help with proofs and probability. Computer Networking: Principles, Protocols and Practice gives the network and TLS context for Chapters 9 and 21.
Applicable Universities
This book is useful for students at Pakistani universities offering BS Cyber Security, BS Computer Science and MS programs with a cryptography or applied cryptography course, including Punjab University, Virtual University, COMSATS, FAST, UET, NUST, and other HEC-recognized institutions.
Official Copy of A Graduate Course in Applied Cryptography
Dan Boneh and Victor Shoup offer the draft as a free PDF on their book page, together with the earlier versions. Click below to open the official page and download the latest version (0.6, January 2023).
→ Visit Official PageFAQs
Is A Graduate Course in Applied Cryptography free?
Yes. Dan Boneh and Victor Shoup offer the draft PDF free on their book page, toc.cryptobook.us. It is a draft by the authors, not an open-licence book: neither the PDF nor the web page states a licence or terms of use, so treat all rights as reserved by the authors and use the official page rather than reposting the file.
Which version is this?
This page covers Version 0.6, posted on 14 January 2023, which the book page lists as the latest version. The PDF has about 1,130 pages. Earlier drafts are 0.5 (January 2020), 0.4 (September 2017), 0.3 (December 2016), 0.2 (August 2015) and 0.1 (January 2008). Because it is a draft, check the official page for anything newer.
How many chapters and exercises does it have?
The contents list 23 chapters in three parts and four appendices. In Version 0.6 Chapters 1 and 17 have no text and Appendices C and D are marked To be written, so 21 chapters are actually written. Chapters 2 to 16 and 18 to 23 end with exercises, about 490 in total, many with hints. The PDF contains no solutions.
Is it good for complete beginners?
No. It is a graduate-level text that expects discrete probability, modular arithmetic, basic group theory and comfort with proofs. The authors say a beginning reader can skip the detailed proofs and the Mathematical details sections, and each theorem is followed by a proof idea. Students new to security should start with a lighter book and come back to this one for Part I.
Does it cover post-quantum cryptography, zero knowledge and TLS?
Only partly. The chapter on post-quantum cryptography from lattices (Chapter 17) has no text in Version 0.6, though Chapter 14 covers hash-based signatures and Section 16.5 explains quantum attacks on factoring and discrete log. Zero knowledge is covered through Sigma protocols in Chapters 19 and 20, but the Bulletproofs and SNARK sections are unwritten. TLS 1.3 appears as case studies on the record protocol (Chapter 9) and session setup (Chapter 21).
Is it still current in 2026?
The core is: AES, SHA256 and SHA3, HMAC, authenticated encryption, TLS 1.3, elliptic curves, Schnorr and BLS signatures and multi-party computation have not changed in substance. The gaps are the missing lattice chapter, the unwritten Bulletproofs and SNARK sections and the lack of any current post-quantum standard, so pair it with newer standards documents. The draft dates from January 2023, so check the book page for a newer version.
Related Books
- Mathematics for Computer Science – Lehman, Leighton & Meyer (MIT OCW)
- Discrete Mathematics: An Open Introduction – Oscar Levin (4th Edition)
- Computer Networking: Principles, Protocols and Practice – Bonaventure (3rd Edition)
- Foundations of Computer Science – Aho & Ullman (C Edition)
This draft gives you the reasoning behind modern cryptography, from stream ciphers and AES to authenticated encryption, signatures, key exchange and multi-party computation, in one free book. Browse more Computer Science books for the rest of your semester.
A Graduate Course in Applied Cryptography, Version 0.6 (January 2023) by Dan Boneh and Victor Shoup. This is a free draft that the authors distribute on their book page; the PDF and the page state no licence, and all rights remain with the authors. Official source: https://toc.cryptobook.us/. This page links to the official site and does not host or copy the book.
© Copyright Policy
Freebooks.pk is an educational resource for students in Pakistan. Textbooks and other books belong to their respective boards, authors and publishers, and all rights remain with them. If you are the copyright holder of any material on this page and want it changed or removed, please contact us or file a request under our DMCA policy. We review every request and remove reported content promptly.
