Lecture 5 · Tuesday 07 October 2025

A tour of Minicrypt, then number theory

A transitional lecture. The first half closes the symmetric world by naming its minimal assumption; the second opens the asymmetric world by building the arithmetic that supplies new assumptions of its own.

Decks: 01_Crypto_101_Sym.pdf, 02_Crypto_101_Asym.pdf Chapters 1 and 2

Before ThisWhere Lecture 4 Left Off

Lecture 4 finished the symmetric toolkit. It built collision-resistant hashing from a compression function through the Merkle-Damgård transform, showed how the padding and the length block matter (SHA-1 (Secure Hash Algorithm 1) is the cautionary example), and presented the sponge as the alternative absorbing-and-squeezing design behind SHA-3. Hash-Based Message Authentication Code (HMAC) followed as the way to key a hash function safely, avoiding the length-extension forgery that a naive prefix construction admits. The lecture then raised the security requirement from Chosen-Plaintext Attack (CPA) to Chosen-Ciphertext Attack (CCA) and asked how to combine confidentiality with authenticity: encrypt-and-Message Authentication Code (MAC) and MAC-then-encrypt both have counterexamples, and encrypt-then-MAC is the composition that provably yields authenticated encryption. The upshot was a complete symmetric stack, provided a key is already shared.

This LectureWhat It Adds

Two things, in sequence. First, the lecture asks what the symmetric constructions assume. One-way functions are the minimal object; from one-way functions come pseudorandom generators, from a PRG the GGM (Goldreich-Goldwasser-Micali) tree gives a pseudorandom function, and from a PRF the Feistel network gives a pseudorandom permutation by Luby-Rackoff. The resulting world is Impagliazzo's Minicrypt, in which one-way functions exist and everything symmetric follows. The boundary of Minicrypt is the point of the tour. Nothing in it gives public-key encryption, which requires structured assumptions in addition to hard ones.

Second, the lecture starts supplying that structure. It rehearses modular arithmetic and asks which residues are invertible, introduces the group $\mathbb{Z}_n^{*}$ of residues invertible modulo $n$ and Euler's totient, and gives the extended Euclidean algorithm as the routine that computes inverses. Euler's theorem and Fermat's little theorem follow, and with them the observation that exponents reduce modulo $\varphi(n)$, the trapdoor RSA will use. Primality testing comes next, motivated by key generation: the Fermat test, its liars and the Carmichael numbers on which the Fermat test is wrong for every base. The lecture closes on the two hard problems the next lecture builds upon, integer factoring and the discrete logarithm, and on the key distribution problem that makes public-key cryptography necessary.

Study PlanWhat to Read, in Lecture Order

The Minicrypt half is on the Chapter 1 page, because the Minicrypt slides are in the symmetric deck. The number theory is on the Chapter 2 page.

  1. Chapter 1: Secret-Key Cryptography: the Minicrypt sections. One-way functions and hard-core predicates, Pseudorandom Generators (PRGs), the GGM (Goldreich-Goldwasser-Micali) tree, Feistel and Luby-Rackoff, laying out the dependency graph of which primitive is built from which.
  2. Chapter 2 §1: The key distribution problem. Why $O(n^2)$ (quadratic in the number $n$ of users) symmetric keys are prohibitively inconvenient and impossible to bootstrap, and why public-key encryption can never be unconditionally secure.
  3. §2: Modular arithmetic. Congruences, the ring $\mathbb{Z}_n$, the group $\mathbb{Z}_n^{*}$, Euler's totient. The lab runs the extended Euclidean algorithm step by step: with inputs $160$ and $7$, the algorithm returns $d = 23$.
  4. §3: Euler and Fermat. The two theorems, the reduction of exponents modulo $\varphi(n)$, and square-and-multiply. The note on the Chinese remainder theorem goes beyond the deck but is needed for the exercises.
  5. §4: Primality testing. The Fermat test and its failure modes. The lab puts the Fermat test and the Miller-Rabin test side by side on the same bases, starting with $561$.
  6. §5: Factoring and discrete logarithms. Study the two assumptions and the sub-exponential attacks on each one. The animation of a generator's orbit shows why the inverse direction provides no structure for computing the inverse.

PracticeExercises for This Lecture