Sources and References

Primary textbook — Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman, An Introduction to Mathematical Cryptography, 2nd ed., Springer Undergraduate Texts in Mathematics, 2014. Supplementary texts — Dan Boneh and Victor Shoup, A Graduate Course in Applied Cryptography (draft v0.6, freely available at toc.cryptobook.us); Michael A. Nielsen and Isaac L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, 2000; Peter Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” FOCS 1994; Lov K. Grover, “A fast quantum mechanical algorithm for database search,” STOC 1996. Online resources — MIT 6.875 Cryptography lecture notes (Vinod Vaikuntanathan); Stanford CS 359C Post-Quantum Cryptography notes; NIST Post-Quantum Cryptography Standardization documentation (csrc.nist.gov/projects/post-quantum-cryptography); Dan Bernstein and Tanja Lange, “Post-Quantum Cryptography,” Nature 549 (2017), 188–194.

Chapter 1: The Discrete Logarithm Problem and Diffie-Hellman

1.1 Diffie-Hellman Key Exchange

Public-key cryptography rests on a simple but powerful asymmetry: certain mathematical operations are easy to perform but hard to reverse. The Diffie-Hellman protocol, introduced in 1976, was the first published scheme to exploit this asymmetry for key agreement, allowing two parties to establish a shared secret over an entirely public channel.

An eavesdropper Eve sees \( g \), \( g^a \), and \( g^b \), but not \( a \), \( b \), or \( g^{ab} \) — provided the discrete logarithm problem (DLOG) is hard in \( G \). The DLOG problem asks: given \( g \) and \( h = g^x \), find \( x \). The security of DH rests on the intractability of this problem.

1.2 Square-and-Multiply

For DH to be practical, computing \( g^a \) must be efficient even when \( a \) is hundreds of bits long. Naive repeated multiplication requires \( a \) group operations, which is exponential in the bit-length of \( a \). The square-and-multiply algorithm brings this down to \( O(\log a) \) operations.

The algorithm processes each bit of \( a \) with at most two group operations (one squaring, one optional multiplication), yielding at most \( 2\lfloor \log_2 a \rfloor \) operations total. This is \( O(\log a) \), making exponentiation efficient even for 256-bit or 2048-bit exponents.

1.3 Design Requirements for the Group G

Not every group is suitable for Diffie-Hellman. Five requirements must be satisfied simultaneously, each motivated by a concrete practical or security concern.

These five requirements drastically narrow the field. Two families of groups satisfy all of them in practice: the multiplicative group \( (\mathbb{Z}/p\mathbb{Z})^* \) for a large prime \( p \), and the group of points on an elliptic curve over a finite field. All other commonly studied groups either have easy DLOG (e.g., \( (\mathbb{Z}/n\mathbb{Z}, +) \)) or fail other criteria.

1.4 Why \((\mathbb{Z}/n\mathbb{Z}, +)\) Fails

The additive group of integers modulo \( n \) looks superficially like a cyclic group suitable for DH. However, its DLOG problem — given \( g \) and \( h = g \cdot x \pmod{n} \) (i.e., \( gx \equiv h \pmod{n} \)), find \( x \) — reduces to computing \( x = g^{-1} h \pmod{n} \). The modular inverse \( g^{-1} \pmod{n} \) is computed efficiently by the Extended Euclidean Algorithm, making DLOG trivial. This disqualifies the additive group entirely.

1.5 The Extended Euclidean Algorithm

The Extended Euclidean Algorithm (EEA) computes \( \gcd(a, b) \) and simultaneously finds Bézout coefficients \( s, t \) such that \( sa + tb = \gcd(a,b) \). It is the backbone of modular arithmetic.

Runtime analysis via Fibonacci argument. Each step produces a remainder \( r_{i+1} = r_{i-1} \bmod r_i < r_{i-1} \). More precisely, if \( q_i \geq 2 \) then \( r_{i+1} \leq r_{i-1}/2 \), and if \( q_i = 1 \) then \( r_{i+2} < r_i/2 \) (since two steps with quotient 1 cut the remainder at least in half). In the worst case (all quotients equal 1), the sequence \( r_0, r_1, r_2, \ldots \) follows the Fibonacci recurrence, and since \( F_k \approx \phi^k / \sqrt{5} \), the number of steps is \( O(\log_\phi b) = O(\log b) \). Thus EEA runs in \( O(\log n) \) divisions, or equivalently \( O((\log n)^2) \) bit operations.

1.6 DLOG Algorithms

Several classical algorithms attack DLOG. Understanding them guides parameter selection.

Pohlig-Hellman is the precise algebraic reason behind requirement 4 in the DH group definition: choosing a group whose order has large prime factors is not merely a convention but a hard necessity. A group of order \( 2^{100} \), for instance, would have \( p_1 = 2 \) and \( e_1 = 100 \), and DLOG would cost only \( O(100 \cdot (\log |G| + \sqrt{2})) = O(\log^2 |G|) \) operations — polynomial in the key size.

Baby-step Giant-step (BSGS). For a group element \( h = g^x \) with \( x \in [0, q) \), write \( x = im + j \) where \( m = \lceil \sqrt{q} \rceil \). Precompute a table of \( g^j \) for \( j = 0, \ldots, m-1 \). Then compute \( h \cdot (g^{-m})^i \) for \( i = 0,1,\ldots \) until a match with the table is found. Time and space complexity: \( O(\sqrt{q}) \). This is the baseline against which other algorithms are compared.

Pohlig-Hellman. If \( |G| = \prod p_i^{e_i} \) has small prime factors, DLOG in \( G \) reduces to DLOG in each prime-power subgroup of order \( p_i^{e_i} \), which costs \( O(e_i \sqrt{p_i}) \) per factor. Combined cost is \( O(\sum e_i \sqrt{p_i}) \). For security, one must use a group whose order has a large prime factor \( q \) (ideally prime order); then Pohlig-Hellman gains nothing, and BSGS in the subgroup of order \( q \) costs \( O(\sqrt{q}) \).

Index calculus. In \( (\mathbb{Z}/p\mathbb{Z})^* \), a factor base \( \mathcal{B} = \{\text{small primes}\} \) is chosen. One collects relations by checking whether random powers \( g^k \bmod p \) factor over \( \mathcal{B} \). A linear algebra step over \( \mathbb{Z}_{p-1} \) then recovers discrete logs for all elements of \( \mathcal{B} \), and individual logs follow quickly. The resulting sub-exponential complexity is \( L_p[1/2, c] = e^{c(\log p)^{1/2}(\log \log p)^{1/2}} \), which is much faster than \( O(\sqrt{p}) \) for large \( p \). Index calculus has no known analogue on elliptic curves, which is why ECC offers much shorter key sizes.

Pollard rho. Uses a pseudo-random walk on \( G \) with Floyd’s cycle detection, achieving \( O(\sqrt{q}) \) expected time but only \( O(1) \) space (unlike BSGS which needs \( O(\sqrt{q}) \) space). For elliptic curves, Pollard rho is essentially optimal among known algorithms.

The table below summarizes the complexity landscape:

The existence of index calculus for \( (\mathbb{Z}/p\mathbb{Z})^* \) explains why elliptic curve keys can be 8–12× shorter than DH keys at equivalent security.

Chapter 2: Modular Arithmetic and Algebraic Structures

The cryptographic constructions in Chapter 1 require working in specific algebraic structures — the multiplicative group \( \mathbb{Z}_p^* \), rings of integers modulo composites, and polynomial quotient rings — and their security depends intimately on the arithmetic properties of those structures. This chapter develops the toolkit: cyclic groups and generators (which explain when DH is well-defined), Euler’s theorem (the engine behind RSA correctness), the Chinese Remainder Theorem (the reason CRT-RSA is 4× faster than naive RSA), quadratic residues (which explain why DDH fails in \( \mathbb{Z}_p^* \) and motivates the move to prime-order subgroups), and polynomial rings (the algebraic setting for Ring-LWE in Chapter 5). Each section is both self-contained and forward-pointing: the abstract algebra here will reappear concretely in every subsequent protocol.

2.1 The Group \(\mathbb{Z}_p^*\) and Cyclic Structure

Fix a prime \( p \). The multiplicative group \( \mathbb{Z}_p^* = \{1, 2, \ldots, p-1\} \) under multiplication modulo \( p \) is a cyclic group of order \( p-1 \). Being cyclic means there exists a generator (primitive root) \( g \) such that every element of \( \mathbb{Z}_p^* \) is a power of \( g \). This is non-trivial: not every group is cyclic, and even for \( \mathbb{Z}_p^* \) the proof requires some field theory. The upshot for cryptography is that DH key exchange makes sense in \( \mathbb{Z}_p^* \) — we can take arbitrary powers of a fixed base and cover the whole group.

Fermat’s little theorem is a consequence of Lagrange’s theorem applied to \( \mathbb{Z}_p^* \): the order of any element divides the group order \( p-1 \). More generally, Euler’s theorem states \( a^{\phi(n)} \equiv 1 \pmod{n} \) for any \( a \) with \( \gcd(a,n) = 1 \), where \( \phi \) is Euler’s totient function.

2.2 Order of an Element

Several key properties follow:

• \( a^{|G|} = 1 \) (Lagrange), so \( \text{ord}(a) \mid |G| \).
• \( a^s = 1 \) if and only if \( \text{ord}(a) \mid s \).
• \( a^x = a^y \) if and only if \( x \equiv y \pmod{\text{ord}(a)} \).

These properties are central to analyzing algorithms involving modular exponentiation, including primality tests and key generation procedures.

2.3 Euler’s Phi Function

Key formulas:

• For prime \( p \): \( \phi(p) = p - 1 \).
• For prime power: \( \phi(p^k) = p^{k-1}(p-1) \).
• Multiplicativity: if \( \gcd(m,n)=1 \) then \( \phi(mn) = \phi(m)\phi(n) \).
• For \( n = p_1^{e_1} \cdots p_r^{e_r} \): \(\phi(n) = n \prod_{p \mid n} (1 - 1/p)\).

2.4 Chinese Remainder Theorem

The Chinese Remainder Theorem (CRT) is one of the most powerful tools in modular arithmetic. It establishes that working modulo a product \( mn \) (when \( \gcd(m,n) = 1 \)) is equivalent to working modulo \( m \) and \( n \) simultaneously.

Constructive proof. Given \( (a, b) \in \mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z} \), apply Bézout’s theorem to find \( s, t \) with \( sm + tn = 1 \). Set \( x = a \cdot tn + b \cdot sm \pmod{mn} \). Then \( x \equiv a \cdot tn \equiv a(1 - sm) \equiv a \pmod{m} \) and similarly \( x \equiv b \pmod{n} \). Uniqueness follows since the map is between sets of the same finite size.

CRT underlies CRT-RSA (for fast decryption), Pohlig-Hellman, and the ring structure of cyclotomic rings used in lattice cryptography.

2.5 Quadratic Residues

Quadratic residues appear naturally when studying the structure of \( \mathbb{Z}_p^* \), but their cryptographic significance is subtle and important: they provide a computable partial information about elements of \( \mathbb{Z}_p^* \) that can be used to distinguish \( g^{ab} \) from a random group element — thereby breaking DDH in the full group \( \mathbb{Z}_p^* \). This is the precise reason why DDH-based schemes (like ElGamal) must work in the prime-order subgroup, not the full group.

The Legendre symbol \( \left(\frac{a}{p}\right) \) is defined as \( +1 \) if \( a \) is a QR, \( -1 \) if QNR, and \( 0 \) if \( p \mid a \). There are exactly \( (p-1)/2 \) quadratic residues in \( \mathbb{Z}_p^* \). The Legendre symbol is multiplicative: \( \left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right) \). This multiplicativity is the DDH killer: since \( \left(\frac{g^{ab}}{p}\right) = \left(\frac{g^a}{p}\right)^b \), an adversary can efficiently compute whether \( g^{ab} \) is a QR given \( g^a \) and \( b \) (from \( g^b \)), whereas for a random \( g^c \) no such constraint exists. Computing square roots mod \( p \) can be done efficiently via the Tonelli-Shanks algorithm: write \( p - 1 = 2^s \cdot q \) with \( q \) odd, find a QNR \( n \), and iteratively reduce the exponent using the Sylow 2-subgroup structure. The algorithm runs in \( O(\log^2 p) \) time.

2.6 Rings, Fields, and Polynomial Quotient Rings

The ring \( \mathbb{Z}_q = \mathbb{Z}/q\mathbb{Z} \) is a field if and only if \( q \) is prime. For composite \( q = ab \), the elements \( a \) and \( b \) are zero divisors with no inverses.

Polynomial quotient rings are essential for lattice-based cryptography. Given a prime \( q \) and a polynomial \( p(x) \in \mathbb{Z}_q[x] \), the ring \( \mathbb{Z}_q[x]/(p(x)) \) consists of all polynomials with coefficients in \( \mathbb{Z}_q \) reduced modulo \( p(x) \). Each element has a unique representative of degree less than \( \deg(p(x)) \), obtained via polynomial long division.

This parallels the fact that \( \mathbb{Z}/n\mathbb{Z} \) is a field iff \( n \) is prime. Irreducible polynomials play the role of primes in the polynomial ring setting. When \( p(x) = x^d + 1 \) for \( d = 2^k \), this polynomial is irreducible over \( \mathbb{Z} \) (a cyclotomic polynomial), making \( \mathbb{Z}_q[x]/(x^d+1) \) a natural choice for ring-LWE.

2.7 Primality Testing

Generating large primes is a prerequisite for RSA and DH parameter generation. The naive approach (trial division up to \( \sqrt{n} \)) is exponential in the bit length. Two modern approaches:

Miller-Rabin test (probabilistic). Write \( n-1 = 2^s d \) with \( d \) odd. A witness for compositeness is an \( a \) such that \( a^d \not\equiv 1 \pmod{n} \) and \( a^{2^r d} \not\equiv -1 \pmod{n} \) for all \( r \in \{0,\ldots,s-1\} \). If \( n \) is prime, no witness exists (by Fermat). If \( n \) is composite, at least \( 3/4 \) of bases are witnesses. Running \( k \) rounds with random bases gives error probability \( \leq 4^{-k} \). With \( k = 40 \), the false-prime probability is \( 2^{-80} \), negligible in practice.

AKS primality test. Agrawal, Kayal, and Saxena (2004) proved that PRIMES is in P: there is a deterministic polynomial-time algorithm. AKS checks, for appropriate \( r \), whether \( (x+a)^n \equiv x^n + a \pmod{x^r-1, n} \) for several values of \( a \). Runtime is \( \tilde{O}((\log n)^{6}) \), deterministic. Though slower than Miller-Rabin in practice, AKS resolved a decades-old open question and is a landmark in complexity theory.

Carmichael numbers are composite integers \( n \) satisfying \( a^{n-1} \equiv 1 \pmod{n} \) for all \( \gcd(a,n)=1 \). They fool the naive Fermat test but not Miller-Rabin (Miller-Rabin is not based on \( a^{n-1} \equiv 1 \) alone). The smallest Carmichael number is 561 = 3·11·17.

Chapter 3: Elliptic Curves

The multiplicative group \( \mathbb{Z}_p^* \) supports Diffie-Hellman but has a critical weakness: the index calculus algorithm (Section 1.6) solves DLOG in sub-exponential time \( L_p[1/2] \). This means a 2048-bit prime is needed to achieve 112-bit security — a significant bandwidth and computation cost. Elliptic curves offer a different trade-off: their group of rational points \( E(\mathbb{F}_q) \) has no known analogue of index calculus, so the best DLOG algorithms are Pollard rho at \( O(\sqrt{q}) \) — fully exponential in the key size. The consequence is that a 256-bit elliptic curve provides the same 128-bit security as a 3072-bit DH group, with 12× smaller keys and proportionally faster operations.

The reason index calculus fails for elliptic curves is structural: index calculus relies on factoring random group elements over a “factor base” of small primes, which works because the integers have multiplicative structure. Points on an elliptic curve have no such multiplicative decomposition; there is no notion of “small” or “smooth” that applies. This structural difference is also, from a different angle, why elliptic curves remain quantum-vulnerable despite ECC’s classical advantages: Shor’s algorithm needs only the group’s abelian structure, which ECC possesses.

3.1 Definition and Weierstrass Form

An elliptic curve over a field \( \mathbb{F}_q \) is, in its simplest form, the set of solutions to a short Weierstrass equation together with a distinguished point at infinity.

The discriminant condition ensures that the curve is smooth, which is necessary for the group law to be well-defined. In projective coordinates \( [X:Y:Z] \), the point at infinity is \( [0:1:0] \), and the Weierstrass equation becomes \( Y^2 Z = X^3 + aXZ^2 + bZ^3 \). Projective coordinates are used in efficient implementations to avoid field inversions.

3.2 The Group Law

The chord-and-tangent construction gives \( E(\mathbb{F}_q) \) the structure of an abelian group with identity \( \mathcal{O} \).

The geometric picture: draw the line through \( P \) and \( Q \); it meets the curve in a third point \( R \); reflect \( R \) over the \( x \)-axis to get \( P + Q \). Associativity of this law is non-trivial and requires a careful algebraic verification (via explicit polynomial identities) or an appeal to the theory of divisors and the Riemann-Roch theorem on algebraic curves.

3.3 Hasse’s Theorem and Torsion

This is a profound result: the number of rational points is close to \( q+1 \), with deviation controlled by the trace of Frobenius \( t = q+1-\#E(\mathbb{F}_q) \). Hasse’s theorem was proved using the Riemann hypothesis for function fields over finite fields. It implies that the group order is between \( (\sqrt{q}-1)^2 \) and \( (\sqrt{q}+1)^2 \), so all elements have order \( O(\sqrt{q}) \) — a useful bound for attack analysis.

The \( n \)-torsion subgroup \( E[n] = \{P \in E(\bar{\mathbb{F}}_q) : nP = \mathcal{O}\} \) over the algebraic closure satisfies \( E[n] \cong (\mathbb{Z}/n\mathbb{Z})^2 \) when \( \text{char}(\mathbb{F}_q) \nmid n \). Torsion subgroups underlie the definition of Weil and Tate pairings, which are used in pairing-based cryptography.

3.4 Discrete Logarithm on Elliptic Curves

The absence of a known sub-exponential DLOG algorithm for elliptic curves (over prime-order subgroups without special structure) is the central security advantage of ECC over DH in \( (\mathbb{Z}/p\mathbb{Z})^* \). The best known algorithms — Pollard rho and BSGS — take \( O(\sqrt{q}) \) time. For a 256-bit prime-order curve, this is \( O(2^{128}) \), equivalent in security to a 3072-bit DH modulus or 3072-bit RSA key, while requiring only 256 bits to represent a point.

The Pohlig-Hellman reduction applies to ECC as well: if the curve order has small prime factors, DLOG becomes much easier. This is why real-world curves have prime (or near-prime) order.

3.5 Real-World Curves

NIST P-256 (secp256r1). Defined by \( y^2 = x^3 - 3x + b \) over a 256-bit prime field \( \mathbb{F}_p \), with \( p = 2^{256} - 2^{224} + 2^{192} + 2^{96} - 1 \). The constants \( b \) and the base point were chosen by NIST with a hash of a seed string (a “nothing-up-my-sleeve” procedure). P-256 is widely deployed in TLS and used in NIST’s ECDSA standard.

Curve25519. Proposed by Bernstein (2006). Uses Montgomery form \( Bv^2 = u^3 + Au^2 + u \) with \( A = 486662 \), \( B = 1 \), over \( \mathbb{F}_p \) with \( p = 2^{255} - 19 \). The prime \( p \) has special structure enabling fast arithmetic. Crucially, the Montgomery ladder algorithm computes scalar multiplication using only \( x \)-coordinates, achieving constant-time execution with no secret-dependent branches — a major advantage against side-channel attacks. Curve25519 is used in Signal, WireGuard, and TLS 1.3. Its design is transparent and carefully documented for security.

secp256k1. Weierstrass form \( y^2 = x^3 + 7 \) over a 256-bit prime, used in Bitcoin’s ECDSA. Unlike P-256 or Curve25519, it lacks special optimizations for the field arithmetic, but is notable for the simplicity of its curve constants.

3.6 Montgomery Ladder

The Montgomery ladder computes \( nP \) for scalar \( n \) using a loop that processes each bit of \( n \), maintaining two accumulators \( R_0 = kP \) and \( R_1 = (k+1)P \) updated as:

The key property: both branches perform one doubling and one addition, so the sequence of operations is independent of the scalar bits. This eliminates timing differences, protecting against timing side-channel attacks. Montgomery ladder is the recommended method for scalar multiplication on Curve25519 and similar curves.

3.7 Failure of DDH on \((\mathbb{Z}/p\mathbb{Z})^*\)

The Decisional Diffie-Hellman (DDH) assumption asks whether an adversary can distinguish \( (g, g^a, g^b, g^{ab}) \) from \( (g, g^a, g^b, g^c) \) with \( c \) random. In \( (\mathbb{Z}/p\mathbb{Z})^* \), DDH is false as stated for the full group: the Legendre symbol distinguisher works by checking \( \left(\frac{g^{ab}}{p}\right) = \left(\frac{g^a}{p}\right)^{\log_g g^b} \), which can be computed efficiently. For this reason, DDH is assumed only in the prime-order subgroup of \( \mathbb{Z}_p^* \) of order \( q \mid p-1 \). On elliptic curves over prime-order groups, no analogous distinguisher is known, and DDH is believed to hold.

Chapter 4: Formal Security Definitions

Chapters 1–3 established the computational problems that underpin cryptographic security. But saying “DH is secure because DLOG is hard” is not yet a mathematical statement — it conflates the hardness of an abstract problem with the security of a specific protocol. A protocol’s security must be defined independently of any particular attack, then proved by reduction. This chapter develops the formal framework that makes such proofs possible.

The game-based approach, pioneered by Goldwasser-Micali and refined into the modern asymmetric-cryptography canon through the work of Bellare and Rogaway, addresses a simple question: what does it mean for an adversary to have “broken” an encryption scheme? Colloquially, breaking encryption means reading the message. But this is too strong and too narrow: too strong because we cannot hope to prevent a lucky guess; too narrow because a scheme that leaks the parity of the message is also broken in a meaningful sense. The right notion, semantic security, says a scheme is secure if a ciphertext reveals nothing about the plaintext — formally, the ciphertext provides zero computational advantage over guessing. IND-CPA formalizes this.

4.1 Game-Based Security

Modern cryptography defines security through games between a challenger and an adversary. The challenger runs a scheme; the adversary tries to break it. The adversary wins if they achieve a specific goal (e.g., guess a hidden bit) with probability noticeably better than random chance.

This framework makes “security” a precise, falsifiable mathematical statement. A scheme is broken if there exists an efficient adversary with non-negligible advantage; it is secure if no such adversary exists (assuming hard mathematical problems).

4.2 DLOG, CDH, DDH Hierarchy

Security proofs always reduce a protocol’s security to the assumed hardness of some computational problem. The three most important problems in discrete-log-based cryptography form a strict hierarchy, and choosing the right assumption for a proof matters both for confidence (a weaker assumption yields a stronger theorem) and for diagnosing exactly what breaks if the assumption fails.

The hardness hierarchy is:

Each arrow means “if the left problem is hard, so is the right.” Reading contrapositively: if the right problem turns out to be easy, the left is also easy. Cryptographic protocols should be proved under the weakest necessary assumption — that assumption is the most credible and hardest to break.

• DLOG: Given \( g^x \), find \( x \). The strongest assumption: even this does not directly break passive DH.
• CDH (Computational DH): Given \( g^a, g^b \), compute \( g^{ab} \). Breaking CDH would enable passive recovery of the DH shared secret. Strictly weaker than DLOG: there is no known reduction from CDH to DLOG in general groups.
• DDH (Decisional DH): Distinguish \( (g^a, g^b, g^{ab}) \) from \( (g^a, g^b, g^c) \) with \( c \) random. The weakest and therefore most useful assumption for protocol proofs. ElGamal’s IND-CPA security reduces precisely to DDH: hardness of DDH implies that the ciphertext \( (g^b,\, g^{ab} \cdot m) \) is computationally indistinguishable from the one-time pad \( (g^b,\, g^c \cdot m) \), revealing nothing about \( m \).

The hierarchy is strict in general. The canonical example where DDH fails while CDH is believed hard is \( (\mathbb{Z}/p\mathbb{Z})^* \): the Legendre symbol \( \left(\frac{\cdot}{p}\right) \) immediately distinguishes \( g^{ab} \) from a random \( g^c \), because \( \left(\frac{g^{ab}}{p}\right) = \left(\frac{g^a}{p}\right)^b \) is a computable constraint on \( g^{ab} \), while \( g^c \) has independent Legendre symbol. For this reason, DDH is only assumed in the prime-order subgroup of \( \mathbb{Z}_p^* \), and elliptic curves — where no analogous algebraic distinguisher is known — are strictly preferable for DDH-based constructions. In the random oracle model, DDH and CDH are equivalent for certain groups, but the gap is real and must be respected in concrete instantiations.

4.3 IND-CPA Security

IND-CPA formalizes semantic security: the ciphertext reveals nothing about which message was encrypted. Any deterministic encryption scheme (like textbook RSA) immediately fails IND-CPA, since the adversary can simply re-encrypt \( m_0 \) and \( m_1 \) and compare with \( c^* \).

4.4 IND-CCA1 and IND-CCA2

Chosen-ciphertext attacks model a more powerful adversary who can also query a decryption oracle.

• IND-CCA1: The adversary may query \( \text{Dec}_{sk}(\cdot) \) before seeing the challenge ciphertext \( c^* \), but not after. This models a “lunchtime attack” scenario.
• IND-CCA2: The adversary may query \( \text{Dec}_{sk}(\cdot) \) both before and after seeing \( c^* \), with the sole restriction that they cannot query \( c^* \) itself. This is the strongest standard notion.

IND-CCA2 matters because many natural encryption schemes are malleable: given a ciphertext \( c \) of \( m \), one can construct \( c' \neq c \) that decrypts to a related message \( m' \). A malleable scheme cannot be IND-CCA2 secure. ElGamal is a classic example.

4.5 El-Gamal Encryption

IND-CPA security proof sketch. Suppose \( \mathcal{A} \) wins the IND-CPA game with non-negligible advantage. We construct a DDH distinguisher: given a DDH tuple \( (g, g^a, g^b, Z) \) (where \( Z = g^{ab} \) or \( Z = g^c \)), simulate the El-Gamal challenger with \( h = g^a \) and challenge ciphertext \( c^* = (g^b, Z \cdot m_b) \). If \( Z = g^{ab} \), this is a valid El-Gamal encryption, and \( \mathcal{A} \) wins with non-negligible advantage. If \( Z = g^c \) is random, then \( c^* \) is a one-time pad on \( m_b \), perfectly hiding \( b \). So \( \mathcal{A} \)’s advantage equals the DDH distinguisher’s advantage, contradicting DDH hardness.

Malleability. Given \( (A, B) = (g^b, g^{ab} m) \), one can form \( (A, B \cdot m') = (g^b, g^{ab} \cdot m \cdot m') \), which decrypts to \( mm' \). This homomorphic property is useful in some protocols but makes El-Gamal not IND-CCA2 secure.

4.6 Fujisaki-Okamoto Transform

The FO transform is a powerful generic construction that converts an IND-CPA scheme into an IND-CCA2 KEM (Key Encapsulation Mechanism) in the random oracle model.

The re-encryption check is critical: it prevents the adversary from submitting malformed ciphertexts that would reveal information about the secret key. In the random oracle model, the FO transform is tightly secure if the underlying scheme is \( \delta \)-correct (decryption failure probability \( \delta \)) and IND-CPA. The Kyber/ML-KEM standard applies precisely this transform.

4.7 Zero-Knowledge Proofs and Sigma Protocols

A zero-knowledge proof allows a prover to convince a verifier of a statement’s truth without revealing anything beyond the truth of the statement.

Sigma (\( \Sigma \)) protocols are a particularly elegant class of 3-round honest-verifier zero-knowledge proofs: (1) prover sends a commitment, (2) verifier sends a random challenge, (3) prover sends a response. They are simple to analyze and widely deployed.

4.8 Schnorr Identification Protocol

Honest-verifier zero-knowledge. The simulator, knowing \( c \) in advance, samples \( z \leftarrow \mathbb{Z}_q \) uniformly, computes \( R = g^z X^{-c} \), and outputs \( (R, c, z) \). This is identically distributed to an honest transcript because in both cases \( z \) is uniform in \( \mathbb{Z}_q \) and \( R = g^z X^{-c} \).

Special soundness. Given two accepting transcripts \( (R, c, z) \) and \( (R, c', z') \) with \( c \neq c' \) (same commitment, different challenges), one can extract \( x = (z - z')/(c - c') \pmod{q} \). This means a prover who can answer two different challenges for the same \( R \) must know the witness.

4.9 Fiat-Shamir Transform

The Fiat-Shamir transform removes interaction from a \( \Sigma \)-protocol by replacing the verifier’s challenge with a hash of the transcript so far.

In the random oracle model, Fiat-Shamir produces signatures that are existentially unforgeable under chosen-message attacks (EUF-CMA) via the forking lemma (see below).

4.10 Digital Signatures: Schnorr and ECDSA

Schnorr signatures. Applying Fiat-Shamir to Schnorr ID:

• Sign\( (x, m) \): Sample \( r \leftarrow \mathbb{Z}_q \); compute \( R = g^r \), \( c = H(R, m) \), \( z = r - cx \pmod{q} \). Output \( (z, c) \).
• Verify\( (X, m, (z,c)) \): Accept iff \( H(g^z X^c, m) = c \).

ECDSA. In ECDSA (used in Bitcoin, TLS), the signing procedure is:

• Sample ephemeral key \( k \leftarrow \mathbb{Z}_q \); compute \( R = kG \), \( r = x(R) \bmod q \) (\( x \)-coordinate).
• Compute \( s = k^{-1}(H(m) + rx) \bmod q \); output \( (r, s) \).
• Verify: \( u_1 = s^{-1}H(m) \), \( u_2 = s^{-1}r \); check \( x(u_1 G + u_2 X) \equiv r \pmod{q} \).

ECDSA’s security is harder to analyze formally than Schnorr’s because the \( r = x(R) \bmod q \) step introduces an irregular structure. Schnorr signatures have a tight EUF-CMA proof in the ROM via the forking lemma: any forger can be rewound to produce two signatures with the same \( R \) but different challenges, enabling extraction of the secret key. ECDSA reuses \( k \) only implicitly, and a single nonce reuse \( (k_1 = k_2) \) immediately leaks the private key \( x = (z_1 H(m_2) - z_2 H(m_1)) / (r(z_2 - z_1)) \) — a catastrophic failure exploited against the PlayStation 3 in 2010.

Chapter 5: Learning with Errors and Lattices

The constructions in Chapters 1–4 — Diffie-Hellman, ElGamal, Schnorr, ECDSA — all rest on a common foundation: the hardness of the discrete logarithm problem in a group where the group operation is fast. This foundation is elegant and well-studied, but it carries a structural vulnerability: every DLOG-based scheme is broken in polynomial time by Shor’s algorithm (Chapter 7), which reduces order-finding in any finite abelian group to quantum phase estimation. Elliptic-curve groups enjoy no special protection — Shor’s algorithm extracts the group periodicity regardless of the ambient geometry. RSA (Chapter 6) falls by the same algorithm via the integer factoring reduction. If large-scale quantum computers are built, the entire algebraic paradigm collapses simultaneously.

This motivates the search for hard problems whose structure is fundamentally different. Two desiderata guide the choice: first, no known quantum algorithm should provide more than a modest (square-root) speedup; second, and more subtly, the problem should admit a worst-case to average-case reduction — if SVP (Shortest Vector Problem) on an arbitrary lattice is hard in the worst case, then the specific random instances used in cryptography are also hard. This second property is remarkable. DLOG and factoring have no such reduction; their hardness on random instances is an assumption with no worst-case backing. Lattice problems, by contrast, do: Regev’s landmark 2005 paper showed that solving random LWE samples is as hard as solving worst-case lattice problems. This reduction provides a qualitatively different level of confidence than anything achievable in the DLOG world.

5.1 The Learning With Errors Problem

The Learning With Errors (LWE) problem, introduced by Regev (2005), is the central hardness assumption for post-quantum cryptography. The intuition is elementary: if \( \mathbf{s} \in \mathbb{Z}_q^n \) is a secret vector and you are given many linear equations \( b_i = \mathbf{a}_i^\top \mathbf{s} \pmod{q} \) over a finite field with no noise, solving for \( \mathbf{s} \) by Gaussian elimination is trivial. But add a small random error \( e_i \) to each right-hand side: the system becomes overdetermined and inconsistent, Gaussian elimination fails catastrophically, and even distinguishing such noisy samples from purely random \( (\mathbf{a}_i, b_i) \) pairs appears to require exponential time — and provably so, via the lattice reduction in Regev’s theorem.

The error \( e \) is small (magnitude \( \ll q/2 \)), so \( b \approx \mathbf{a}^\top \mathbf{s} \) but with enough noise to prevent lattice attacks from easily recovering \( \mathbf{s} \).

5.2 Hardness and Parameter Taxonomy

Error distribution. The standard choice is a discrete Gaussian \( \chi_e = D_{\mathbb{Z},\sigma} \), truncated to \( \mathbb{Z}_q \). Larger \( \sigma \) means more noise and (intuitively) harder LWE. Gaussian errors are theoretically “hardest” in the sense that average-case LWE with Gaussian errors is as hard as worst-case lattice problems (via Regev’s reduction).

Secret distribution. The secret \( \mathbf{s} \) may be uniform over \( \mathbb{Z}_q^n \) (standard secret) or drawn from \( \chi_s = \chi_e \) (normal form secret). Both are believed equally hard; the normal form simplifies security proofs.

Normal form equivalence. Tall LWE has \( m > n \) samples with a uniform secret. Normal form LWE has \( m = n \) samples with secret from \( \chi_e \). The equivalence proof (sketch): Given tall LWE samples \( (\mathbf{A}, \mathbf{b}) \) with \( \mathbf{A} \in \mathbb{Z}_q^{m \times n} \) and \( m > n \), split \( \mathbf{A} = \begin{pmatrix} \mathbf{A}_0 \\ \mathbf{A}_1 \end{pmatrix} \) where \( \mathbf{A}_0 \in \mathbb{Z}_q^{n \times n} \) is invertible (happens with high probability). Compute \( \mathbf{A}_1 \mathbf{A}_0^{-1} \mathbf{b}_0 - \mathbf{b}_1 = \mathbf{A}_1 \mathbf{A}_0^{-1}(\mathbf{A}_0 \mathbf{s} + \mathbf{e}_0) - (\mathbf{A}_1 \mathbf{s} + \mathbf{e}_1) = \mathbf{A}_1 \mathbf{A}_0^{-1}\mathbf{e}_0 - \mathbf{e}_1 \), which is a normal-form LWE sample.

Search–Decision reduction. Search-LWE reduces to \( O(nq) \) calls to a decision-LWE oracle via a hybrid argument: guess each coordinate of \( \mathbf{s} \) by checking consistency of modified samples with the oracle. This means that if decision-LWE is hard, so is search-LWE (over the same parameters).

5.3 Lattices and Lattice Problems

This is a fundamental existence theorem: any lattice must contain a non-zero vector of length at most \( \sqrt{n} \cdot \det(\mathcal{L})^{1/n} \). Algorithms for finding such short vectors — lattice reduction — are the main tools for attacking LWE.

The geometric picture deserves emphasis. A lattice is like a multidimensional periodic grid, but the grid need not align with coordinate axes and its basis vectors can be highly skewed — long, nearly parallel, far from orthogonal. Given such a bad basis, the lattice appears intractable: computing an integer combination that lands on a particular short vector is like navigating a tilted, oblique grid without a compass. A good basis — short, nearly orthogonal vectors — makes many computations easy. Lattice reduction is the algorithmic challenge of transforming any given basis into a nearly-good one. The LLL algorithm (Lenstra-Lenstra-Lovász, 1982) achieves polynomial-time reduction but only produces a moderately good basis, sufficient to break small parameters. BKZ-\(\beta\) achieves progressively better reduction at exponential cost \( \sim 2^{0.292\beta} \), and concrete LWE parameters are chosen so that even BKZ-\(\beta\) at optimal \( \beta \) falls short.

Key lattice problems:

• SVP (Shortest Vector Problem): Find a non-zero \( \mathbf{v} \in \mathcal{L} \) with \( \|\mathbf{v}\| = \lambda_1(\mathcal{L}) \).
• CVP (Closest Vector Problem): Given target \( \mathbf{t} \notin \mathcal{L} \), find \( \mathbf{v} \in \mathcal{L} \) minimizing \( \|\mathbf{t} - \mathbf{v}\| \).
• BDD (Bounded Distance Decoding): As CVP, but promised that \( \min_{\mathbf{v} \in \mathcal{L}} \|\mathbf{t} - \mathbf{v}\| < \lambda_1(\mathcal{L})/2 \).

Kannan’s embedding. BDD reduces to SVP: given target \( \mathbf{t} \) and lattice \( \mathcal{L} \), form the augmented lattice \( \mathcal{L}' \) with basis \( \begin{pmatrix} B & 0 \\ \mathbf{t}^\top & \varepsilon \end{pmatrix} \). The closest lattice point to \( \mathbf{t} \) corresponds to a short vector in \( \mathcal{L}' \).

LWE as BDD. An LWE sample \( (\mathbf{A}, \mathbf{b}) \) with \( \mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e} \) and small \( \mathbf{e} \) defines a BDD instance: \( \mathbf{b} \) is close to the lattice point \( \mathbf{A}\mathbf{s} \) in the \( q \)-ary lattice \( \mathcal{L}_q(\mathbf{A}) = \{\mathbf{y} \in \mathbb{Z}^m : \mathbf{y} = \mathbf{A}\mathbf{s} \pmod{q},\, \mathbf{s} \in \mathbb{Z}_q^n\} \). The error \( \mathbf{e} \) is the deviation from the lattice. Solving BDD on this lattice recovers \( \mathbf{s} \).

Best known attack: BKZ. The BKZ (Block Korkine-Zolotarev) lattice reduction algorithm interpolates between LLL (polynomial time, weak reduction quality) and full SVP. BKZ-\( \beta \) uses an SVP oracle in dimension \( \beta \) as a subroutine, running in time roughly \( 2^{0.292\beta} \) (heuristically). Concrete LWE security estimates use the lattice estimator (Albrecht et al.) which optimizes over all BKZ-based attacks.

5.4 Ring-LWE and Module-LWE

Standard LWE requires matrices \( \mathbf{A} \in \mathbb{Z}_q^{m \times n} \), which have key sizes quadratic in the dimension. Ring-LWE and Module-LWE reduce key sizes dramatically by replacing \( \mathbb{Z}_q^n \) with polynomial rings.

Polynomial multiplication in \( R_q \) can be viewed as multiplication by a circulant matrix — specifically, the companion (negacyclic) matrix of \( x^d + 1 \). This allows applying fast algorithms. The Number Theoretic Transform (NTT) is a finite-field analogue of the FFT: when \( d \mid q-1 \), one can find all \( d \)-th roots of unity in \( \mathbb{Z}_q \) and evaluate polynomials at these roots in \( O(d \log d) \) operations, reducing polynomial multiplication to componentwise multiplication in the NTT domain. NTT is the key algorithmic ingredient making lattice-based schemes practical.

The efficiency advantage over plain LWE is dramatic. In standard LWE with dimension \( n \), a public key consists of a matrix \( \mathbf{A} \in \mathbb{Z}_q^{m \times n} \), costing \( O(n^2) \) ring elements. In Ring-LWE, a single polynomial \( a \in R_q \) plays the role of the entire matrix — polynomial multiplication by \( a \) acts as the “random linear map,” and the ring structure forces all the algebraic relationships that the full matrix would carry. This drops the key size from \( O(n^2) \) to \( O(n) \) elements, which at \( n = 256 \) and \( q = 3329 \) translates to public keys of roughly 1 KB rather than 1 MB.

Module-LWE. Generalizes Ring-LWE to small matrices over \( R_q \):

Module-LWE interpolates between standard LWE (large \( k = n, \ell = 1 \)) and Ring-LWE (\( k = \ell = 1 \)). Kyber uses small \( k, \ell \in \{2,3,4\} \), giving compact keys (hundreds of bytes) while relying on a well-studied hardness assumption.

The proof reduces an IND-CPA distinguisher to an MLWE distinguisher by a hybrid argument over the rows of \( \mathbf{A} \) and the components of the ciphertext.

5.5 Kyber KEM (ML-KEM)

Kyber (CRYSTALS-Kyber) was selected by NIST in 2022 as the primary post-quantum KEM standard, now called ML-KEM (FIPS 203).

Correctness. The noise in \( w \) is \( e_2 + \mathbf{e}_1^\top \mathbf{r} - \mathbf{s}^\top \mathbf{e}_1 + (\text{cross terms}) \), all small. As long as the total noise magnitude is less than \( q/4 \), rounding correctly recovers \( m \). This holds with overwhelming probability for the chosen parameters.

The Fujisaki-Okamoto transform is applied to produce the IND-CCA2 KEM: the message \( m \) is sampled as \( m = H_1(\text{random seed}) \), the encapsulation recomputes from \( m \), and decapsulation re-encrypts to verify. The shared key is \( K = H_2(m, H(\mathbf{u}, v)) \).

Concrete parameters:

5.6 Dilithium Signatures (ML-DSA)

CRYSTALS-Dilithium (now ML-DSA, FIPS 204) is the primary NIST-standardized post-quantum signature scheme. It combines module-LWE with the Short Integer Solution (SIS) hardness assumption.

The signature scheme follows a “Fiat-Shamir with aborts” paradigm:

The rejection sampling step (abort if \( \|\mathbf{z}\|_\infty \) is too large) ensures that the distribution of \( \mathbf{z} = \mathbf{y} + c\mathbf{s}_1 \) is independent of the secret \( \mathbf{s}_1 \): by choosing \( \gamma_1 \gg \|c\mathbf{s}_1\|_\infty \), the rejection probability is bounded, and the accepted \( \mathbf{z} \) is statistically close to uniform. This is the key privacy property (analogous to the Schnorr ZK simulator).

Security rests on the module-LWE problem (for key recovery) and the module-SIS problem (for forgery): producing \( (\mathbf{z}, c) \) satisfying verification without knowing \( \mathbf{s}_1, \mathbf{s}_2 \) requires finding a short vector in a module lattice.

5.7 NTRU Cryptosystem

NTRU (Hoffstein–Pipher–Silverman, 1998) is one of the oldest lattice-based cryptosystems and remains deployed in production systems today. Its hardness rests on the difficulty of recovering short vectors in an NTRU lattice, a structured 2\( n \)-dimensional lattice. Unlike LWE-based systems, NTRU does not have a known worst-case hardness reduction, but it has withstood more than 25 years of cryptanalysis and is the basis of FALCON (FN-DSA), one of the four NIST-standardized schemes.

The central algebraic setting is the polynomial ring \( R = \mathbb{Z}[x]/(x^n - 1) \) (or the negacyclic version \( \mathbb{Z}[x]/(x^n+1) \) in FALCON). NTRU’s security rests on the observation that, in a polynomial ring, dividing by a “small” polynomial modulo two different moduli \( p \) and \( q \) hides the numerator: if \( f \) is small and \( g \) is small, the quotient \( h = g \cdot f^{-1} \pmod{q} \) looks like a uniformly random polynomial modulo \( q \), yet carries hidden short-vector structure that enables efficient decryption.

The centering step — lifting \( a \bmod q \) to the symmetric interval \( (-q/2, q/2] \) — is the analogue of the rounding step in LWE decryption, and fails if the noise polynomial \( p \cdot r \cdot g + f \cdot m \) has any coefficient outside that interval. Choosing \( q \gg p \cdot n \cdot \|r\|_\infty \cdot \|g\|_\infty \) ensures correctness with overwhelming probability.

Chapter 6: RSA (Brief Treatment)

RSA predates elliptic curves and lattice-based cryptography by decades — it was invented in 1977, more than a quarter-century before Regev’s LWE. It appears in these notes after Chapter 5 for a deliberate pedagogical reason: having seen what makes lattice hardness quantum-resistant, you can now understand precisely what RSA lacks. RSA’s hardness rests on integer factoring, a problem with rich algebraic structure inside \( (\mathbb{Z}/n\mathbb{Z})^* \), and Shor’s algorithm exploits that structure directly. The contrast with LWE is clarifying: lattice problems resist Shor because they have no exploitable abelian periodicity; RSA falls because its core structure is an abelian group on which order-finding is exactly what phase estimation computes.

Beyond the quantum vulnerability, RSA’s catalogue of implementation attacks — PKCS#1 v1.5 padding oracles (Bleichenbacher 1998), small exponent attacks, CRT fault attacks (Bellcore attack), timing side channels (Kocher 1996) — provides an invaluable cautionary template. Many of these attack patterns recur in subtle forms in lattice-based schemes, making a thorough understanding of RSA attacks a prerequisite for auditing post-quantum implementations.

6.1 Setup and Key Generation

RSA (Rivest-Shamir-Adleman, 1977) was the first practical public-key cryptosystem. Its security rests on the presumed hardness of factoring large integers and computing \( e \)-th roots modulo a composite.

Textbook RSA. Encryption: \( c = m^e \bmod n \). Decryption: \( m = c^d \bmod n \). Correctness follows from Euler’s theorem: \( c^d = m^{ed} = m^{1 + k\phi(n)} = m \cdot (m^{\phi(n)})^k \equiv m \pmod{n} \) (for \( \gcd(m,n)=1 \)).

6.2 Security Issues with Textbook RSA

Textbook RSA is insecure in multiple ways:

1. Deterministic: Encrypting the same \( m \) always gives the same \( c \), violating IND-CPA. An adversary can simply encrypt \( m_0 \) and compare with \( c^* \).
2. Multiplicative homomorphism: \( (m_1^e)(m_2^e) = (m_1 m_2)^e \bmod n \), so a ciphertext for \( m_1 m_2 \) is the product of ciphertexts. An adversary can transform a challenge ciphertext \( c^* = m_b^e \) to \( c^* \cdot 2^e \) (which decrypts to \( 2m_b \)), query decryption (in CCA model), and determine \( b \).
3. Small exponent attack: If \( e = 3 \) and \( m \) is small, \( m^3 < n \), so \( c = m^3 \) exactly over the integers; compute \( m = c^{1/3} \) via integer cube root with no modular arithmetic needed.

6.3 OAEP and RSA-PSS

RSA-OAEP (Optimal Asymmetric Encryption Padding, Bellare-Rogaway 1994) is the standard for RSA-based encryption. It uses two hash functions to create a randomized, “full-domain” encoding of the message before exponentiation. In the random oracle model, RSA-OAEP achieves IND-CCA2 security assuming RSA is a one-way permutation. PKCS#1 v2.1 and v2.2 mandate OAEP.

RSA-PSS (Probabilistic Signature Scheme, Bellare-Rogaway 1996) applies a similar randomized hash encoding for signatures. RSA-PSS has a tight security proof in the ROM: any EUF-CMA adversary breaks RSA. This is in contrast to PKCS#1 v1.5 signatures (still widely used in TLS certificates) which lack a clean security proof.

6.4 Factoring Algorithms

The security of RSA ultimately depends on the hardness of factoring \( n = pq \). Known factoring algorithms:

Here \( L_n[\alpha, c] = \exp(c(\log n)^\alpha (\log \log n)^{1-\alpha}) \). NFS is sub-exponential (between polynomial and exponential) and is the best known classical algorithm. For 2048-bit RSA, NFS requires roughly \( 2^{112} \) operations, giving roughly 112-bit classical security; NIST recommends 2048-bit RSA as the minimum and 3072-bit for long-term security beyond 2030.

6.5 CRT-RSA and Side Channels

CRT speedup. Rather than computing \( c^d \bmod n \) directly (expensive for large \( n, d \)), compute \( c^{d_p} \bmod p \) and \( c^{d_q} \bmod q \) separately, where \( d_p = d \bmod (p-1) \) and \( d_q = d \bmod (q-1) \). By Fermat’s little theorem, \( c^d \equiv c^{d_p} \pmod{p} \). Combine the two results using CRT. Exponents \( d_p, d_q \) are about half the bit-length of \( d \), and the moduli are half the bit-length of \( n \), giving approximately a \( 4\times \) speedup.

Side-channel attacks. Kocher (1996) showed that timing measurements of modular exponentiation can reveal the secret key bit by bit. The fix is exponent blinding: replace \( d \) by \( d + r\phi(n) \) for a random \( r \), so timing depends on a different exponent each run. Montgomery ladder provides a similar countermeasure for ECC.

6.6 RSA vs. ECC: Security Comparison

The ratio grows as security level increases, because index calculus for DH/RSA scales as \( L_n[1/3] \) (faster than exponential) while ECC Pollard rho scales as \( O(2^{n/2}) \) (fully exponential in key size \( n \)).

Chapter 7: Quantum Algorithms and Post-Quantum Cryptography

The emergence of quantum computing does not merely threaten one or two cryptographic constructions — it threatens the entire algebraic paradigm that underlies public-key cryptography as it has been practised since Diffie-Hellman (1976). Shor’s algorithm (1994) reduces both integer factorization and discrete logarithm — in finite fields and on elliptic curves — to a single abstract problem solvable in quantum polynomial time. Grover’s algorithm (1996) halves the bit-security of every symmetric key and hash function. Simon’s algorithm (1994) breaks a surprising number of symmetric constructions outright when an adversary can query them quantumly. Understanding these algorithms at a mathematical level is now a core competency for anyone who designs or deploys cryptographic systems.

7.1 Quantum Computing Model

A classical bit holds either 0 or 1. A qubit is a unit vector in \( \mathbb{C}^2 \):

Measuring in the computational basis yields \( |0\rangle \) with probability \( |\alpha|^2 \) and \( |1\rangle \) with probability \( |\beta|^2 \), collapsing the superposition. An \( n \)-qubit register lives in \( \mathbb{C}^{2^n} \):

Entanglement arises when the joint state of two qubits cannot be written as a tensor product of individual qubit states. The Bell state \( \frac{1}{\sqrt{2}}(|00\rangle + |11\rangle) \) is the canonical example: measuring the first qubit instantly determines the second, regardless of physical separation.

Quantum gates are unitary matrices acting on the Hilbert space. Unitarity ensures reversibility and preserves the normalization constraint. Key single-qubit gates:

The quantum circuit model composes unitary gates in sequence. A circuit on \( n \) qubits using \( g \) gates runs in time \( O(g) \); efficiency is measured in gate count as a function of input size. The BQP complexity class contains all decision problems solvable by polynomial-size quantum circuits with bounded error. BQP is known to contain BPP (classical randomized polynomial time) and to be contained in PSPACE; its relationship to NP is unknown, but factoring (believed outside BPP) lies in BQP.

Quantum parallelism alone is not magic: applying a circuit \( U_f \) to a superposition \( \frac{1}{\sqrt{N}}\sum_x |x\rangle|0\rangle \) yields \( \frac{1}{\sqrt{N}}\sum_x|x\rangle|f(x)\rangle \), encoding \( f \) evaluated at all inputs simultaneously. But measuring this state collapses it to a single \( (x, f(x)) \) pair, no better than random sampling. The genuine power comes from quantum interference: careful sequences of gates cancel amplitudes at wrong answers and reinforce amplitudes at right answers. Both Shor and Grover exploit interference in sophisticated ways.

7.2 Quantum Fourier Transform

The Quantum Fourier Transform (QFT) is the engine of Shor’s algorithm. It is the quantum analogue of the Discrete Fourier Transform (DFT).

The classical FFT computes the DFT of \( N \) numbers in \( O(N \log N) \) operations. The QFT achieves the same transformation of the \( N \) amplitudes using only \( O(n^2) = O((\log N)^2) \) quantum gates — an exponential reduction. This is not because the QFT reads out all \( N \) Fourier coefficients simultaneously (measuring collapses the state to one), but because the amplitude vector becomes the DFT, which can then be measured with interference-guided amplification.

Circuit decomposition. Writing \( j \) in binary as \( j = j_1 2^{n-1} + \cdots + j_n 2^0 \), the QFT has a product representation:

Each factor \( |0\rangle + e^{2\pi i j/2^l}|1\rangle \) depends only on \( j \bmod 2^l \), i.e., on the last \( l \) bits of \( j \). This enables a recursive circuit: apply Hadamard to qubit \( l \), then apply controlled-\( R_k \) gates from qubits \( l+1, \ldots, n \) to add the fractional phases, then finish with a bit-reversal swap. The total gate count is \( \sum_{l=1}^n l = n(n+1)/2 = O(n^2) \).

What QFT finds. If the input state has period \( r \) — that is, \( a_j = a_{j+r} \) for all \( j \) — then the QFT concentrates amplitude at multiples of \( N/r \). Measuring yields \( \approx s \cdot N/r \) for a random integer \( s \), and the ratio \( s/r \) can be recovered via continued fractions. This period-finding power is the core of Shor’s algorithm.

7.3 Quantum Phase Estimation

Phase estimation is the central subroutine in Shor’s algorithm, generalizing period-finding to arbitrary unitary operators.

Circuit. Use two registers: \( t \) ancilla qubits initialized to \( |0\rangle \), and the eigenvector register initialized to \( |u\rangle \).

1. Apply \( H^{\otimes t} \) to the ancilla register: \( \frac{1}{\sqrt{2^t}}\sum_{j=0}^{2^t-1}|j\rangle \otimes |u\rangle \).
2. Apply controlled-\( U^{2^k} \) gates for \( k = 0, 1, \ldots, t-1 \), where the \( k \)-th ancilla qubit controls \( U^{2^k} \) on the eigenvalue register. Because \( U^{2^k}|u\rangle = e^{2\pi i \cdot 2^k \theta}|u\rangle \), the ancilla register accumulates: \[ \frac{1}{\sqrt{2^t}}\sum_{j=0}^{2^t-1} e^{2\pi i j\theta}|j\rangle \otimes |u\rangle. \]
3. Apply \( \text{QFT}^{-1}_{2^t} \) to the ancilla register. If \( \theta = s/2^t \) exactly, the state collapses to \( |s\rangle \), recovering \( \theta \) perfectly. If \( \theta \) is not an exact \( t \)-bit fraction, measuring gives the closest \( t \)-bit approximation with probability \( \geq 4/\pi^2 \approx 0.405 \).

The \( t \) controlled-\( U^{2^k} \) operations each require one call to \( U^{2^k} \) (implemented by repeated squaring, \( O(t) \) multiplications each). Total cost: \( O(t^2) \) controlled-\( U \) applications plus \( O(t^2) \) QFT gates.

7.4 Shor’s Algorithm

Shor’s algorithm reduces integer factorization and discrete logarithm to order-finding, which is solved by phase estimation.

Reduction: Factoring to Order-Finding

Given \( N = pq \) (odd, composite, not a prime power), pick random \( a \) with \( \gcd(a, N) = 1 \). Define the function \( f(x) = a^x \bmod N \); it is periodic with period \( r = \text{ord}_N(a) \). If \( r \) is even and \( a^{r/2} \not\equiv -1 \pmod{N} \) (which holds with probability \( \geq 1/2 \) over random \( a \)), then:

Since \( a^{r/2} \not\equiv \pm 1 \pmod{N} \), neither factor is divisible by \( N \) alone, so \( \gcd(a^{r/2}-1, N) \) and \( \gcd(a^{r/2}+1, N) \) are both non-trivial factors. Repeat with fresh \( a \) until a non-trivial factor is found; expected \( O(1) \) repetitions.

Order-Finding via Phase Estimation

The unitary \( U_a : |x\rangle \mapsto |ax \bmod N\rangle \) acts on \( \lceil \log_2 N \rceil \)-qubit registers. Its eigenvectors are:

with eigenvalues \( e^{2\pi i s/r} \). Observe that \( \frac{1}{\sqrt{r}}\sum_{s=0}^{r-1}|u_s\rangle = |1\rangle \), so starting from \( |1\rangle \) in the second register (which we can prepare easily) gives an equal superposition of all eigenvectors.

Phase estimation on \( U_a \) with input \( |1\rangle \) yields a random \( s/r \) (for random \( s \)), to \( t \) bits of precision, after which:

Complexity. Modular exponentiation \( U_a^{2^k} \) needs \( O((\log N)^2) \) quantum gates via schoolbook multiplication (or \( O(\log N \cdot (\log\log N)^2) \) with FFT-based multiplication). Phase estimation with \( t = 2\lceil \log_2 N \rceil + O(1) \) precision bits requires \( O(\log N) \) controlled applications. Total quantum gate count: \( O((\log N)^3) \), polynomial in the bit-length of \( N \). Compare to the classical NFS running time \( \exp(O((\log N)^{1/3}(\log\log N)^{2/3})) \).

Discrete Logarithm

Shor also solves DLP: given \( g, h \in G \) with \( h = g^x \), find \( x \). Define unitaries \( U_g : |j\rangle \mapsto |g^j \bmod N\rangle \) and \( U_h \). Phase estimation on the two-register state \( U_g^a U_h^{-b} \) for random \( a, b \) allows recovery of \( x = \log_g h \). The algorithm works in any group where the group operation is efficient as a quantum circuit — in particular, in \( (\mathbb{Z}/p\mathbb{Z})^* \) and on elliptic curves over finite fields. The latter is critical: ECC was designed to resist classical DLP attacks (no subexponential algorithm), but Shor’s algorithm breaks it in \( O((\log p)^3) \) quantum gate operations.

Abelian Hidden Subgroup Problem

Both factoring and DLP are instances of the Abelian Hidden Subgroup Problem (HSP):

QFT over the abelian group \( G \) solves HSP in quantum polynomial time. Factoring corresponds to \( G = \mathbb{Z}_{N-1} \) (order of the multiplicative group), DLP to \( G = \mathbb{Z}_q \times \mathbb{Z}_q \). For non-abelian groups — such as the symmetric group \( S_n \) (relevant for Graph Isomorphism) — QFT-based approaches work only partially; no polynomial-time quantum algorithm is known for the non-abelian HSP in general, which is why lattice problems (which lack exploitable abelian structure) resist Shor-style attacks.

Resource Estimates and Gate Complexity

Exact gate count. For an \( n \)-bit integer \( N \) (so \( n = \log_2 N \)):

• Phase estimation requires \( t = 2n + O(1) \) ancilla qubits for sufficient precision.
• Each controlled-\( U_a^{2^k} \) application is a controlled modular exponentiation: \( U_a^{2^k} \) computes \( a^{2^k} \bmod N \), which requires \( O(n^2) \) Toffoli gates by schoolbook multiplication (each of \( O(n) \) multiply steps costs \( O(n) \) gates). Total across \( 2n \) steps: \( O(n^3) \) Toffoli gates.
• The QFT inverse uses \( O(n^2) \) gates.
• Total: \( O(n^3) \) gates, which for RSA-2048 (\( n = 2048 \)) is \( O(2048^3) \approx 8.6 \times 10^9 \) Toffoli gates.

Breaking RSA-2048 requires approximately 4,000 logical qubits with full quantum error correction. Each logical qubit requires roughly 1,000 physical qubits under the surface code (assumed error rate \( p \approx 10^{-3} \)). Total physical qubit count: \( \sim 4 \times 10^6 \). Runtime: a few hours at a clock rate of 1 MHz logical operations. As of 2025, the best superconducting quantum processors (Google Willow, IBM Heron) have \( \sim 10^3 \) physical qubits with error rates around \( 10^{-3} \), still far from the fault-tolerant regime needed for Shor at cryptographic scale. The gap is at least one order of magnitude in qubit count and likely more in quality; however, quantum error correction overhead may decrease significantly with improved hardware, making the timeline deeply uncertain.

7.5 Simon’s Algorithm and Symmetric Cryptography Attacks

Simon’s algorithm (1994) predates Shor and was the first to demonstrate an exponential quantum speedup. It has surprising consequences for symmetric cryptography.

Algorithm. Prepare \( \frac{1}{\sqrt{2^n}}\sum_x|x\rangle|0\rangle \). Apply the oracle: \( \frac{1}{\sqrt{2^n}}\sum_x|x\rangle|f(x)\rangle \). Measure the second register; this collapses the first to an equal superposition \( \frac{1}{\sqrt{2}}(|x_0\rangle + |x_0 \oplus s\rangle) \) for a random \( x_0 \). Apply Hadamard to the first register; the resulting state has support only on \( \{y : y \cdot s = 0\pmod{2}\} \). Collect \( O(n) \) such vectors \( y \) and solve the resulting linear system over \( \mathbb{F}_2 \) to recover \( s \).

Application to symmetric cryptography. Consider the Even-Mansour construction \( E_{k_1,k_2}(x) = P(x \oplus k_1) \oplus k_2 \), where \( P \) is a public random permutation. Classically, Even-Mansour has \( 2^n \) key security. Quantumly, Simon’s algorithm recovers \( k_1 \oplus k_2 \) in \( O(n) \) queries to a quantum oracle for \( E \), because \( E(x) \oplus E(x \oplus k_1) = P(x \oplus k_1) \oplus k_2 \oplus P(x) \oplus k_2 = P(x) \oplus P(x\oplus k_1) \) has Simon’s hidden-shift structure. More generally:

• CBC-MAC and PMAC are broken in \( O(n) \) quantum queries (Kaplan–Leurent–Leverrier–Naya-Plasencia, 2016).
• GHASH (used in AES-GCM) is vulnerable to polynomial evaluation attacks lifted to quantum.
• Any construction with an XOR-periodic internal function is potentially vulnerable.

These attacks require a quantum adversary — one who can query the cipher on a superposition of inputs, which is not a standard threat model. In the Q1 model (classical queries, quantum computation), Even-Mansour and AES-GCM retain their classical security. In the Q2 model (quantum queries), many symmetric constructions require redesign. The NIST symmetric standards (AES, SHA-3) are believed secure in Q1; their Q2 security is an active research topic.

7.6 Grover’s Algorithm

Grover’s algorithm solves unstructured search quadratically faster than any classical algorithm.

Geometric interpretation. Let \( |\alpha\rangle = \frac{1}{\sqrt{N-M}}\sum_{f(x)=0}|x\rangle \) (non-solutions) and \( |\beta\rangle = \frac{1}{\sqrt{M}}\sum_{f(x)=1}|x\rangle \) (solutions). The initial state \( H^{\otimes n}|0\rangle = \sqrt{\frac{N-M}{N}}|\alpha\rangle + \sqrt{\frac{M}{N}}|\beta\rangle \) lies at angle \( \theta/2 \) from \( |\alpha\rangle \), where \( \sin(\theta/2) = \sqrt{M/N} \).

Each Grover iteration — oracle phase flip \( O_f \) followed by inversion-about-mean \( 2H|0\rangle\langle 0|H - I \) — rotates the state by angle \( \theta \) in the 2D plane spanned by \( |\alpha\rangle \) and \( |\beta\rangle \). After \( k \) iterations, the amplitude at \( |\beta\rangle \) is \( \sin\!\left((2k+1)\theta/2\right) \). This is maximized at \( k \approx \frac{\pi}{4}\sqrt{N/M} \) iterations, at which point measurement yields a solution with probability \( \geq 1 - O(M/N) \).

Optimality. Bennett, Bernstein, Brassard, and Vazirani (1997) proved that any quantum algorithm requires \( \Omega(\sqrt{N/M}) \) oracle queries. Grover’s algorithm is therefore optimal.

Multiple solutions. When \( M \) is unknown, run Grover with geometrically increasing iteration counts \( 1, 2, 4, \ldots \) until a solution is found; expected total queries \( O(\sqrt{N/M}) \).

Amplitude amplification. Grover’s iteration generalizes to any quantum algorithm \( \mathcal{A} \) that finds a solution with probability \( p \): the amplified algorithm solves the problem in \( O(1/\sqrt{p}) \) applications of \( \mathcal{A} \), regardless of the structure of the search space. This makes Grover applicable as an inner loop in more complex quantum algorithms.

7.7 Impact on Cryptographic Security Levels

Grover’s algorithm halves the bit-security of every primitive that relies on exhaustive search.

Block ciphers. An \( n \)-bit key has classical security \( 2^n \) (exhaustive key search). Grover gives a quantum key search in \( O(2^{n/2}) \) evaluations. Consequence:

Hash functions. Preimage resistance: Grover finds a preimage of an \( n \)-bit hash in \( O(2^{n/2}) \) queries. Collision resistance: the Brassard-Høyer-Tapp (BHT) algorithm finds collisions in \( O(2^{n/3}) \) quantum queries (using quantum walk on a Johnson graph with QRAM), better than Grover’s \( O(2^{n/2}) \).

NIST symmetric recommendations: Use AES-256 and SHA-384 (or SHA3-256 for collision resistance under \( 2^{85} \)-bound models; SHA3-384 for stronger margin) in post-quantum deployments. The KEM/signature schemes standardized by NIST already build on SHA3-256 with explicit quantum security analysis.

7.8 Why Lattice Problems Resist Quantum Algorithms

The abelian group structure of \( (\mathbb{Z}/N\mathbb{Z})^* \) and elliptic curve groups is precisely what Shor’s algorithm exploits. Lattice problems have no known exploitable group structure.

HSP obstruction. SVP and CVP are not known to reduce to any HSP. The closest structural problem is the dihedral hidden subgroup problem (relevant for ideal lattices), for which no efficient quantum algorithm is known despite decades of effort. The best known quantum algorithm for dihedral HSP (Kuperberg 2005) runs in \( 2^{O(\sqrt{\log N})} \) time — subexponential but not polynomial.

Quantum speedups for lattice algorithms. The best classical lattice algorithm for \( n \)-dimensional SVP is the BKZ-\(\beta\) algorithm with sieving subroutine, running in time \( \sim 2^{0.292\beta} \) per BKZ tour. Quantum speedups:

1. Grover speedup on classical sieving: The inner sieve can use Grover search, reducing the exponent from \( 0.292 \) to \( 0.265 \). This is only a modest constant-factor improvement in the exponent, not exponential.
2. Quantum walk speedup on sieving: Laarhoven (2016) showed quantum walks can reduce sieving to \( \sim 2^{0.2653n} \). Again only a constant improvement.
3. No known exponential speedup exists for lattice sieving or enumeration. The best quantum attack on LWE remains classical BKZ with minor Grover enhancement.

Concrete numbers. For Kyber-768 (\( n = 768 \), \( q = 3329 \)):

• Classical core-SVP hardness: \( \approx 2^{183} \)
• Quantum core-SVP hardness: \( \approx 2^{166} \)
• NIST target: 128-bit quantum security (Category 3)

The gap between 166 and 128 provides a healthy security margin. This is the strongest current evidence that lattice cryptography is post-quantum secure.

7.9 The NIST PQC Standardization Process

NIST initiated its Post-Quantum Cryptography Standardization in 2016, receiving 69 complete submissions. After four public rounds and extensive cryptanalysis:

Why four schemes? Kyber and Dilithium share the same mathematical assumption (Module-LWE/SIS); a breakthrough against one likely breaks the other. SPHINCS+ provides an independent safety net based only on hash function security — if all lattice assumptions fail, SPHINCS+ still stands, at the cost of larger signatures (8 KB for SPHINCS+-128s). FALCON offers smaller signatures than Dilithium (about 666 bytes vs 2.4 KB at NIST Level 1) but requires precise Gaussian sampling over lattices, making it harder to implement without side-channel leakage.

SIKE breach (2022). The Supersingular Isogeny Key Encapsulation (SIKE) scheme was a round-4 alternate candidate. In July 2022, Castryck and Decru published a polynomial-time classical attack exploiting the additional structure of SIDH’s auxiliary torsion points via isogeny computations on higher-dimensional abelian varieties. SIKE was completely broken in under one hour on a laptop. This episode is a cautionary tale: SIDH had been studied for nearly a decade before a fatal flaw was discovered. NIST’s conservative multi-assumption approach is directly vindicated by SIKE’s failure.

7.10 Hybrid Cryptography and Post-Quantum Migration

The uncertainty in quantum computing timelines, combined with the long lifespan of encrypted archives, creates a case for immediate action.

“Harvest now, decrypt later.” A well-resourced adversary intercepting TLS handshakes today can store the classical RSA/ECDH ciphertexts and decrypt them retroactively once a large-scale quantum computer becomes available. Secrets with long lifespans — diplomatic communications, financial records, health data, intellectual property — are at risk even before any quantum computer is built.

Hybrid key exchange. During the transition period, NIST recommends combining a classical scheme with a post-quantum scheme:

X25519Kyber768 (now standardized as ML-KEM-768 + X25519 in RFC 9497) is deployed in Chrome 116+, Firefox 132+, and Cloudflare’s TLS termination infrastructure.

Migration checklist for cryptographic engineers:

• Replace RSA and ECDH with ML-KEM-768 or ML-KEM-1024 for key exchange.
• Replace ECDSA and RSA signatures with ML-DSA-65 or FN-DSA-512 for authentication.
• Replace AES-128 with AES-256; replace SHA-256 with SHA-384 for integrity.
• Audit protocols for Simon-vulnerable constructions (CBC-MAC, counter-mode with short tags) if quantum oracle access is a concern in the future threat model.
• Deploy hybrid schemes during transition to retain classical security until post-quantum deployment is complete.

Chapter 8: Pairing-Based Cryptography and Advanced Topics

8.1 Bilinear Pairings

Pairing-based cryptography derives additional functionality — identity-based encryption, short signatures, non-interactive zero knowledge — from special bilinear maps between elliptic curve groups.

The standard examples are the Weil pairing and Tate pairing on supersingular or pairing-friendly elliptic curves. The Weil pairing \( e_n(P, Q) \) for \( n \)-torsion points \( P, Q \in E[n] \) is defined via rational functions (Weil’s \( f_P \) functions), evaluated at divisors supported outside the torsion points.

Bilinearity is the key property: \( e(aP, bQ) = e(P, Q)^{ab} \), so the pairing collapses two separate DH-style computations into one group target element.

Weil pairing intuition. For an elliptic curve \( E \) over \( \mathbb{F}_q \) and integer \( n \) with \( \gcd(n, q) = 1 \), the \( n \)-torsion subgroup \( E[n] \cong (\mathbb{Z}/n\mathbb{Z})^2 \) over the algebraic closure. For each \( P \in E[n] \), there exists a rational function \( f_P \) on the curve with divisor \( n(P) - n(\mathcal{O}) \). The Weil pairing is:

where \( D_P, D_Q \) are divisors of degree 0 supported away from each other’s support, linearly equivalent to \( (P) - (\mathcal{O}) \) and \( (Q) - (\mathcal{O}) \) respectively. Miller’s algorithm (1986) computes \( f_P(D_Q) \) in \( O(\log n) \) steps by a double-and-add procedure on the function values, making pairing computation practical. The bilinearity \( e_n(aP, Q) = e_n(P, Q)^a \) follows from the theory of divisors and Weil reciprocity.

8.2 Decisional Bilinear Diffie-Hellman (DBDH)

The security of pairing-based schemes typically relies on the DBDH assumption: given \( (g, g^a, g^b, g^c, T) \in G_1^4 \times G_T \), distinguish \( T = e(g,g)^{abc} \) from \( T = e(g,g)^r \) with \( r \) random. This assumption does not follow from standard CDH/DDH in \( G_1 \), making it an independent hardness assumption.

Pairings destroy DDH hardness in \( G_1 \): if \( G_1 \) has a pairing, then given \( (g, g^a, g^b, Z) \), compute \( e(g^a, g^b) \) and compare to \( e(g, Z) \); they are equal iff \( Z = g^{ab} \). So DDH in \( G_1 \) is easy with a pairing, which means El-Gamal in pairing groups is not IND-CPA under DDH. Pairing-based schemes instead build security on the separate DBDH or BDH assumptions.

8.3 Boneh-Franklin Identity-Based Encryption

The most famous application of pairings is Identity-Based Encryption (IBE), where a party’s public key is simply their identity string (email address, name, employee ID). A trusted Private Key Generator (PKG) issues private keys corresponding to identities.

Security is proven in the random oracle model under the BDH assumption. IBE enables powerful applications: timed-release encryption (identity = “2030-01-01”), revocation via key expiry, and hierarchical key delegation.

8.4 BLS Short Signatures

The Boneh-Lynn-Shacham (BLS) signature scheme uses pairings to achieve extremely short signatures (about 48 bytes at the 128-bit security level, compared to ECDSA’s 64 bytes and Schnorr’s 64 bytes), with a particularly clean algebraic structure.

BLS signatures are aggregatable: \( n \) signatures \( \sigma_1, \ldots, \sigma_n \) on messages \( m_1, \ldots, m_n \) under keys \( pk_1, \ldots, pk_n \) aggregate to a single signature \( \sigma = \sum_i \sigma_i \), verifiable as \( e(\sigma, P) = \prod_i e(H(m_i), pk_i) \). This enables blockchain applications (Ethereum 2.0 uses BLS for validator signatures) where thousands of signatures must be aggregated.

8.5 Post-Quantum Status of Pairing-Based Cryptography

Pairings operate in elliptic curve groups \( G_1, G_2 \) and the multiplicative group \( G_T \) of a finite field extension. Shor’s algorithm breaks DLP in all of these groups (both elliptic curve and finite field). Consequently, all current pairing-based schemes are broken by quantum computers. There is active research on post-quantum analogues (e.g., isogeny-based pairings), but no standard post-quantum pairing scheme exists as of 2025.

This means that IBE, BLS aggregation, and other pairing-based applications will require entirely new post-quantum constructions — likely based on lattices or other quantum-resistant assumptions. Lattice-based IBE and signatures exist but tend to have larger keys and signatures than pairing-based counterparts.

8.6 Key Encapsulation and Hybrid Encryption Summary

All practical public-key cryptography uses a KEM-DEM (Key Encapsulation Mechanism / Data Encapsulation Mechanism) hybrid:

1. KEM: Encapsulate a symmetric key \( K \) using the recipient’s public key; produces ciphertext \( c_1 \).
2. DEM: Encrypt the actual message \( M \) under \( K \) using an authenticated symmetric cipher (AES-GCM, ChaCha20-Poly1305); produces ciphertext \( c_2 \).
3. Send \( (c_1, c_2) \).

This architecture separates the algebraic public-key operation (performed once) from the bulk data encryption (symmetric, fast, provably secure). Security of the hybrid scheme follows from IND-CCA2 security of the KEM combined with authenticated encryption security of the DEM.

For post-quantum transition:

• Replace the classical KEM (X25519, RSA-OAEP) with ML-KEM (Kyber).
• The DEM (AES-GCM with 256-bit key) is already quantum-safe.
• This is the minimal change needed for post-quantum security in practice.

Chapter 9: Hash-Based Signatures

Hash-based signature schemes occupy a unique position in post-quantum cryptography: their security rests on nothing more than the collision resistance (and one-wayness) of the underlying hash function, with no algebraic structure whatsoever. This makes them the most conservative post-quantum assumption available. If SHA-256 or SHA3-256 remains secure — a proposition that the entire security community has been trying to falsify for decades — then hash-based signatures are secure. No lattice assumption, no isogeny assumption, no number-theoretic assumption is needed. This conservatism comes at a cost: signatures are larger than algebraic schemes, and most constructions are either one-time (Lamport, Winternitz) or require careful state management (XMSS). SPHINCS+ (SLH-DSA) eliminates the statefulness at the cost of somewhat larger signatures, and was standardized by NIST in 2024 as FIPS 205.

9.1 Lamport One-Time Signatures

The Lamport signature scheme (1979) is conceptually the simplest public-key signature scheme imaginable. Its security reduces directly and tightly to one-way functions — no collision resistance is needed.

The signing procedure reveals exactly one preimage per bit — the preimage corresponding to the actual message bit. This is the fundamental limitation: if the signer uses the same key pair to sign two different messages \( m \ne m' \), the adversary can combine the two signatures to forge a signature on any message whose bit string is a componentwise “mix” of \( d = H(m) \) and \( d' = H(m') \), since both preimages for differing bits have been revealed. Hence Lamport is a one-time signature: one key pair, one message, never reuse.

Winternitz improvement. The Winternitz One-Time Signature (W-OTS) reduces key and signature sizes by signing \( w \) bits at once using a hash chain of length \( 2^w \). Instead of revealing one of two preimages per bit, the signer reveals a link in a chain \( x \to f(x) \to f(f(x)) \to \cdots \to f^{2^w-1}(x) \), with the chain length encoding the message bits. Choosing \( w = 4 \) or \( w = 16 \) reduces signature size by a factor of \( w / (w+1) \) at the cost of \( O(2^w) \) hash evaluations per coefficient during signing and \( O(2^w) \) during verification.

9.2 Merkle Tree Signatures (Many-Time)

Lamport solves the one-message problem. To sign many messages, Merkle (1979) introduced a construction using a binary hash tree to authenticate an entire family of Lamport public keys with a single short root value. The signer generates \( 2^h \) Lamport key pairs for tree height \( h \), arranges them as leaves, and builds a binary tree by hashing pairs upward.

The Merkle root binds all \( 2^h \) leaf keys. Forging a signature on the \( i \)-th message would require forging the Lamport signature (breaks one-wayness of \( f \)) or forging the authentication path (breaks collision resistance of \( H \)). The authentication path has exactly \( h \) hash values, so the signature overhead is \( h \cdot \lambda \) bits plus the Lamport signature.

9.3 XMSS and SPHINCS+

XMSS (eXtended Merkle Signature Scheme, RFC 8391). Extends MSS with the Winternitz W-OTS+ one-time signature and adds a Merkle tree of trees (hypertree) for increased capacity. XMSS is stateful: the signer must maintain a counter of which leaf index has been used and must never repeat an index. If the state is lost or duplicated (as can happen on a restored backup), security is catastrophically violated — any two signatures under the same Lamport key leak both secret preimages, enabling forgeries. XMSS was standardized by NIST as SP 800-208 (2020) and is appropriate for settings with reliable state management (e.g., hardware security modules).

Chapter 10: NIST PQC Standardization — Scheme-by-Scheme Analysis

The four schemes standardized by NIST in 2024 each embody different mathematical tradeoffs. Understanding them individually — not just as names — equips a cryptographic engineer to make informed deployment decisions.

The table below summarizes the standardized schemes:

The multi-scheme approach is deliberate: no single mathematical assumption should be a single point of failure for global cryptographic infrastructure. If a breakthrough against Module-LWE emerges, ML-KEM and ML-DSA would both be broken simultaneously, but SLH-DSA would stand. If hash functions (SHA-256, SHAKE-256) are weakened, SLH-DSA would be affected but all lattice schemes would remain secure. This complementarity mirrors the defense-in-depth principle applied at the algorithmic level.