Post-Quantum Cryptography

Every public-key scheme in Chapters 2 and 3 rests on one asymmetry: multiplying two large primes is fast, while recovering the primes from their product is beyond every known classical polynomial-time algorithm, the best known method running in subexponential time. The discrete logarithm and its bilinear variants have the same shape. Provable security is conditional on the asymmetry holding: each scheme reduces breaking it to inverting one of these problems, so the reduction is only as good as the hardness of the problem.

In 1994 Shor broke the asymmetry for quantum machines. His algorithm solves both factoring and the discrete logarithm in polynomial time on a quantum Turing machine. The period-finding core exploits superposition to extract the period of $x \mapsto a^{x} \bmod N$ from exponentially many values at once. The period yields a factor of $N$ or a logarithm base $g$. The relevant threshold is a cryptographically relevant quantum computer, one with enough logical qubits and gate fidelity to run such circuits. Factoring a $1024$-bit integer is estimated at roughly $2050$ logical qubits and a circuit of billions of quantum gates, and present devices have factored only tiny numbers such as $15$ and $21$. No cryptographer expects a break this year.

Common mistake. "Quantum computers can already break RSA-2048." Shor's algorithm needs millions of physical qubits: Gidney and Ekerå estimated in 2019 that factoring RSA-2048 in eight hours takes about 20 million noisy qubits. Current machines hold roughly a thousand.

The migration still cannot wait for the machines, and harvest-now-decrypt-later is the reason. An adversary can record today's ciphertexts and decrypt them years later, when the quantum machine exists, so any traffic that must stay secret for a decade is already exposed. Signatures raise the same problem from the other side: once RSA or ECDSA keys are broken, signatures made under them today can be forged retroactively, which invalidates long-lived certificates and archived contracts. Migration time adds urgency. Replacing cryptographic primitives across protocols, libraries, hardware and standards takes ten to twenty years, as the TLS 1.3 rollout shows, so starting after the threat materializes is starting too late.

Symmetric cryptography survives with longer keys. Grover's algorithm searches an unstructured key space quadratically faster, which halves the security level, and doubling the key length restores it. An AES-256 key keeps $128$ bits of security against a quantum attacker. Public-key cryptography has no such fix, because Shor's speedup is exponential. The assumptions of Chapters 2 and 3 must be abandoned.

Common mistake. "Grover's algorithm destroys symmetric cryptography." The speedup is only quadratic: a $128$-bit key drops from about $2^{128}$ classical trials to about $2^{64}$ sequential quantum operations, which stays infeasible. Doubling to AES-256 restores the margin.

Post-quantum cryptography is one of two responses to the threat. The two are often confused. PQC replaces the hard problem. It keeps classical algorithms on ordinary hardware and rests their security on problems no known quantum algorithm speeds up. Quantum key distribution distributes keys over quantum channels, using physics in place of computation. QKD needs dedicated hardware on every link and does not by itself authenticate the endpoints or replace signatures, so this chapter is about PQC alone.

The migration has a concrete cost in bytes. Lattice keys, ciphertexts and signatures run one to two orders of magnitude larger than the elliptic-curve primitives they replace, and the code-based McEliece scheme, one of the longest-standing candidates, carries a public key near $1$ MB.

Worked number. ML-KEM-768 uses a $1184$-byte encapsulation key and $1088$-byte ciphertexts, against $32$ bytes for an X25519 elliptic-curve key and $256$ bytes for RSA-2048. A handshake that once carried tens of bytes of key material now carries kilobytes.

The replacement assumptions are lattice problems, so the first task is geometric. A lattice is the simplest infinite set that still has enough structure to do algebra on: points in $\R^{n}$ arranged periodically.

The same lattice has many bases. Permuting the vectors, negating one or adding an integer multiple of one vector to another all preserve the generated set. Every basis change of this kind is captured by one statement.

This freedom in the description is the source of both the algorithms and the hardness. Even when every basis vector is long, the lattice may contain short vectors. A bad basis hides them. The animation below makes this visible in two dimensions. Deployed schemes run in dimensions too high to draw, so treat every picture in this section as intuition.

Cryptography needs problems that are hard on the instances it actually generates. Lattice theory supplies them in two layers: worst-case geometric problems, which are conjecturally hard but inconvenient to sample, and average-case algebraic problems, SIS and LWE, whose random instances are provably as hard as the worst case.

The worst-case layer, first. For an approximation factor $\gamma \ge 1$:

• $\mathsf{SVP}_{\gamma}$ (shortest vector problem) asks, given $B$, for a lattice vector of length at most $\gamma \cdot \lambda_1(\mathcal{L}(B))$.
• $\mathsf{GapSVP}_{\gamma}$ (decisional shortest vector problem) asks to decide whether $\lambda_1 \le 1$ or $\lambda_1 \ge \gamma$.
• $\mathsf{SIVP}_{\gamma}$ (shortest independent vectors problem) asks for $n$ linearly independent vectors within $\gamma \cdot \lambda_n$.
• $\mathsf{CVP}_{\gamma}$ (closest vector problem) asks, given $B$ and a target $v$, for a lattice point within $\gamma$ times the distance of the closest one.
• $\mathsf{BDD}$ (bounded distance decoding) is CVP with the promise that $v$ is already close.

Solving $\mathsf{CVP}$ solves $\mathsf{SVP}$. Exact algorithms cost $2^{\Theta(n)}$ time, polynomial algorithms exist only for very large $\gamma$ and NP-hardness is known only for small approximation factors. For the polynomial factors cryptography uses, $\gamma = \Omega(n)$, the problems are believed hard without being NP-hard. No better quantum algorithm is known, which is the property section 1 needs.

Common mistake. "Learning with errors is proven NP-hard." The schemes rest on average-case hardness tied by reductions to worst-case lattice problems. No NP-hardness proof is known. The gap problems in the used regime lie in NP intersect coNP, which makes NP-hardness unlikely.

SIS is a lattice problem in disguise: the solutions form the $q$-ary lattice $\Lambda^{\perp}(A) = \{z \in \Z^{m} : A^{\top} z = 0 \bmod q\}$. The task is to find a short vector in it. Ajtai's theorem is the bridge from average case to worst case.

LWE is a system of linear equations with noise added to every row. The noise is the whole difficulty.

Worked number. Take modulus $q = 13$ and secret $s = 4$. For $a = 7$ the sender computes $7 \cdot 4 = 28 = 2 \bmod 13$, adds error $e = 1$ and publishes $(7, 3)$. With errors in $\{-1, 0, 1\}$ several secrets fit, so the attacker cannot single out $s$.

LWE is BDD in disguise: the samples live near the lattice $\Lambda(A) = \{z \in \Z^{m} : z \equiv s^{\top} A \bmod q \text{ for some } s\}$, and recovering $s$ means finding the lattice point close to $b$.

The attacker in both problems is any polynomial-time algorithm, classical or quantum. The reductions above make success on random instances imply success on worst-case geometry. No quantum algorithm improves on the best classical attacks there.

Common mistake. "Shor's algorithm also cracks lattice schemes." Shor extracts the period of a repeating pattern, the structure hidden inside factoring and discrete logarithms. Lattice problems show no such periodic structure, so the algorithm gives no speedup.

Several elementary properties of LWE are used constantly later.

• A candidate secret $t$ is checked by testing whether all residuals $b_i - \langle t, a_i \rangle$ are small; for $t \neq s$ the residuals are well spread in $\Zq$.
• The secret can be shifted by any $r$, since the map $(a, b) \mapsto (a, b + \langle r, a \rangle)$ turns a sample for $s$ into one for $s + r$, a random self-reduction that amplifies success probabilities.
• Several secrets $s_1, \dots, s_k$ under one $A$ remain indistinguishable from random.
• Search reduces to decision by shifting: to test whether $s_1 = 0$, feed the distinguisher samples shifted by random multiples of the first coordinate and sweep all $q$ values.
• LWE stays hard when the secret itself is drawn from the error distribution $\chi$ (Micciancio; Applebaum, Cash, Peikert and Sahai), a fact the efficient schemes of section 9 rely on.

SIS and LWE are related. SIS has many solutions while LWE has one, an SIS oracle solves LWE by returning $z$ with $A^{\top} z = 0$ and testing whether $\langle b, z \rangle = \langle e, z \rangle$ is small. The converse direction is known only under quantum reductions.

Plain LWE has a cost problem. Producing one pseudorandom scalar $b_i = \langle s, a_i \rangle + e_i \bmod q$ takes an $n$-dimensional inner product, so each output element costs $O(n)$ field operations, public keys carry the whole matrix $A$ and encrypting an $n$-bit message costs $\Omega(n^{2})$ time. The columns of $A$ can be amortized over many secrets, yet the per-scalar cost remains. The question is whether one cheap algebraic product can yield many pseudorandom scalars at once.

The answer is to replace the scalar ring $\Zq$ with a polynomial ring. Let $R = \Z[X]/(X^{d} + 1)$ for $d$ a power of two and $R_q = R / qR$, whose elements are polynomials of degree below $d$ with coefficients modulo $q$. Define the product $\star$ as multiplication in $R_q$. One product $s \star a + e = b$ then expands into $d$ related scalar equations on a secret of dimension $n = d \cdot k$. The multiplication itself runs in $O(d \log d)$ operations by FFT-style algorithms. The coefficient-wise product would be insecure for small errors, so the ring structure is essential.

The case for lattices as the post-quantum foundation rests on four properties: provable security, worst-case security, quantum resistance and efficiency.

• Breaking the schemes reduces to solving stated mathematical problems, a connection some classical deployments lack.
• A break implies solving every instance of the lattice problem, whereas factoring and discrete logarithms guarantee only average-case hardness.
• After decades of study, no quantum algorithm improves on the best classical ones for these problems, although this is an empirical record, monitored for instance in the 2024 analysis of eprint report 2024/555.
• The operations are additions and multiplications of small integers, with no modular exponentiation anywhere, which is what makes the schemes of sections 7 to 11 competitive with the classical ones they replace.

What went wrong. Fluhrer's 2016 key-reuse attack on a Ring-LWE key exchange recovered the secret when one ephemeral key served several sessions. Protocols must enforce fresh keys.

SIS alone yields the two most basic primitives in cryptography, a one-way function and a collision-resistant hash, plus commitments. The proofs introduce the leftover hash lemma that the rest of the chapter keeps reusing.

The lemma recurs throughout the chapter's security proofs. Regev encryption in section 9 hides its message because the ciphertext preamble $Ar$ is statistically uniform, and GSW in section 11 hides its plaintext by the same argument over the columns of its randomness matrix.

One-way functions alone do not provide encryption or signatures. Lattice schemes add a geometric trapdoor, together with a sampling method that conceals it.

Recall the two faces of the Small Integer Solution (SIS) and Learning with Errors (LWE) function family. The surjective face is $f_A(x) = A^{\top} x \bmod q$ for short $x$, many preimages per output. The injective face is $f_A(s, e) = s^{\top} A + e \bmod q$ for small $e$, one preimage per output. Inverting means, in the first case, sampling a random preimage $x \getsr f_A^{-1}(u)$ with probability proportional to the Gaussian weight $\exp(-\abs{x}^{2}/s^{2})$, and in the second, recovering the unique small pair $(s, e)$. Both tasks are easy given the right auxiliary information: a short basis of $\Lambda^{\perp}(A)$. The lab below shows why. With a short, nearly orthogonal basis, Babai's nearest-plane algorithm rounds coordinate by coordinate and lands on (or very near) the closest lattice point; with a long skewed basis of the same lattice the same rounding misses. The quality parameter of a Gaussian sampler is the length of the basis it works with. The line of work from Babai (1986) through Klein, Gentry-Peikert-Vaikuntanathan and others is a history of tightening that trade-off.

Generating a random $A$ together with a short basis for $\Lambda^{\perp}(A)$ is possible but slow. The older inversion algorithms trade sampling quality against running time. Micciancio and Peikert (2012) replaced the basis with a different kind of trapdoor that is simpler, faster and just as powerful.

One subtlety remains. Sampling preimages as $x = \binom{R}{I} z$ leaks the covariance $\Sigma = \mathbb{E}[x x^{\top}] \approx R R^{\top}$, which reveals information about the trapdoor. The fix is the perturbation method of Peikert (2010): first draw a perturbation $p$ with covariance $s^{2} I - R R^{\top}$ (positive exactly when the target Gaussian width $s$ exceeds the trapdoor quality), then sample a spherical $z$ with $G^{\top} z = u - A^{\top} p$, then output $x = p + \binom{R}{I} z$. The sum has the target spherical covariance. The equation $A^{\top} x = u$ still holds while the output distribution is independent of $R$. This is the sampler Falcon and the identification schemes of section 8 build on.

A signature scheme needs a one-way function that only the signer can invert. Section 6 supplied one: a surjective SIS function with a trapdoor. Falcon applies that construction directly.

The security argument is short because the machinery of sections 3 and 6 does the work. Forging a signature on a fresh message $\mu^{*}$ requires producing a short $x^{*}$ with $A^{\top} x^{*} = \Hash(\mu^{*})$, which is the inhomogeneous SIS problem, hard by Ajtai's theorem. Signing queries do not help the forger, classical or quantum, because the Gaussian sampler reveals nothing about the trapdoor: the distribution of each signature depends on $A$ and $\Hash(\mu)$ alone. The perturbation method of section 6 is what makes that statement true. A sampler that leaked the covariance of $T$ would hand the forger a growing set of linear measurements of the secret basis, and several early lattice signature schemes failed after their samplers leaked in this way.

Falcon itself instantiates this blueprint over NTRU lattices, the ring-structured lattices of Hoffstein, Pipher and Silverman, where keys and signatures are polynomials in $\Z[X]/(X^{d}+1)$ and polynomial arithmetic replaces vector arithmetic. The ring structure makes Falcon's signatures the most compact in the NIST portfolio, at the cost of a delicate implementation: the sampler is a fast Fourier orthogonalization over floating-point trees, and side-channel resistance requires care. NIST selected Falcon in 2022 alongside Crystals-Dilithium; the two are the lattice signature standards, with Falcon favored where bandwidth is scarce and Crystals-Dilithium where implementation simplicity is.

What went wrong. Coppersmith and Shamir used lattice reduction against early NTRU in 1997. Reduction algorithms keep improving, so parameter sets need generous safety margins.

The second route to signatures goes through identification. A canonical identification scheme is a three-move protocol: the prover sends a commitment $\alpha$, the verifier replies with a random challenge $\beta$ and the prover answers with $\gamma$. Two properties matter. Completeness: an honest prover convinces an honest verifier with overwhelming probability. Passive security: no efficient prover knowing only $\mathit{pk}$ can convince the verifier, even after seeing many honest transcripts.

Two sufficient criteria make passive security checkable. Special soundness: from any two accepting transcripts $(\alpha, \beta, \gamma)$ and $(\alpha, \beta', \gamma')$ with $\beta \neq \beta'$, one can extract the secret key in polynomial time. This implies the protocol is a proof of knowledge: rewind a successful prover after $\alpha$, feed it a second challenge $\beta'$ and apply the extractor. Honest-verifier zero-knowledge (HVZK): honest transcripts can be simulated from $\mathit{pk}$ alone, so whatever the verifier learns, it could have computed by talking to itself.

The template is the discrete-log scheme (Schnorr): with $\mathit{pk} = x = g^{w}$, send $\alpha = g^{a}$ for fresh $a$, answer $\gamma = \beta w + a$ and verify $g^{\gamma} = x^{\beta} \alpha$. Special soundness extracts $w = (\gamma - \gamma')(\beta - \beta')^{-1}$; the simulator picks $\beta, \gamma$ first and sets $\alpha = g^{\gamma} / x^{\beta}$. Copying the shape onto lattices, with $\mathit{pk} = (A, t = As)$, gives $\alpha = Au$, $\gamma = \beta s + u$ and the check $A^{\top} \gamma = \beta t + \alpha$. The extraction is identical: $s = (\gamma - \gamma')(\beta - \beta')^{-1}$. The problems are all lattice-specific.

The repair is rejection sampling. Widen the mask: draw $u$ with coefficients in $\{0, \dots, b - 1\}$ for $b$ much larger than the coefficient range of $s$. Then $\gamma_i = s_i + u_i$ leaks only at the two extremes, $0$ and $b$. Every middle value occurs with probability exactly $1/b$ regardless of $s_i$. The prover therefore sends $\gamma$ only when every coefficient falls in the safe middle range, and aborts otherwise. The probability a coefficient survives is $1 - 1/b$, and with $b = mk$ tuned to the total number of coefficients, an execution completes with probability about $1/e$, a constant expected number of restarts. A final refinement commits to the whole first round: the verifier receives $\alpha = \Hash(\alpha_1, \dots, \alpha_k)$ and checks each reconstructed $\alpha_j$ on top of the linear equations, which lets the HVZK simulator produce transcripts even for aborted runs.

The protocol that emerges from these repairs, moved to polynomial rings so that one shot suffices for approximate proofs, is the core of Crystals-Dilithium, selected by NIST in 2022 and standardized in 2024 as ML-DSA (FIPS 204). Its structure is the one above: a module-SIS key pair $(A, t = As + e)$, Fiat-Shamir with aborts and rejection sampling to keep transcripts independent of the secret. The size cost is concrete. The smallest ML-DSA parameter set publishes a $1312$-byte public key and produces $2420$-byte signatures, against $32$ and $65$ bytes for the 256-bit elliptic-curve equivalents.

Encryption from Learning with Errors (LWE) follows the same pattern as the one-way function of section 5, with the injective face of $f_A$ carrying the message. The scheme is due to Regev (2005). It is the ancestor of every lattice encryption scheme that followed, including GSW in section 11 and Kyber in section 10.

The dual variant (Gentry, Peikert, Vaikuntanathan 2008) transposes the roles. The public key is $(A, u)$ with $u = A^{\top} r$ for a short $r \in \{0,1\}^{m}$. The secret key is $r$. Encryption draws a fresh LWE secret per ciphertext: the preamble is $c_0 = A s' + e'$ and the payload is $c_1 = \langle s', u \rangle + e'' + x \lfloor q/2 \rceil$, and Bob outputs $c_1 - \langle c_0, r \rangle$. In the primal scheme the public key is pseudorandom with a unique secret and each ciphertext admits many coin choices; in the dual scheme the public key is statistically random with many possible secrets and each ciphertext has unique coins. Both security proofs run the same two hybrids in opposite order. A practical bonus of the dual form is that the matrix $A$ can be shared across users.

The most efficient version (Lyubashevsky and Peikert 2011) takes a square matrix $A \in \Zq^{n \times n}$ and draws both the secret and the encryption randomness from the error distribution $\chi$: $\mathit{pk} = (A, u = A^{\top} s + e)$, preamble $c_0 = A r + e'$, payload $c_1 = \langle u, r \rangle + e'' + x \lfloor q/2 \rceil$. Its security uses LWE with short secrets, the theorem of section 3, to replace $(A, u)$ with uniform. This is essentially the shape Crystals-Kyber encrypts in, before the Fujisaki-Okamoto transform of the next section wraps it into a Key Encapsulation Mechanism (KEM).

Regev's scheme is Chosen-Plaintext Attack (CPA) secure. That is the strongest notion its randomization buys. Deployed key transport faces active adversaries, classical or quantum, who submit ciphertexts of their own and watch the reactions, so the target is Chosen-Ciphertext Attack (CCA) security. The Fujisaki-Okamoto transform (1999, refined 2013) converts any passively secure public-key scheme into an actively secure one, at the cost of two hash functions modeled as random oracles. The result is best read as a key encapsulation mechanism: Alice runs $\mathsf{Encaps}$ under $\mathit{pk}$ to obtain a key $k$ and a ciphertext $c$, Bob runs $\mathsf{Decaps}(\mathit{sk}, c)$ to recover the same $k$ and the pair then uses $k$ with a symmetric scheme.

The transform is cleaner in two halves, with an intermediate notion. One-Wayness under Chosen-Plaintext Attack (OW-CPA) says an attacker given $\mathit{pk}$ and a challenge ciphertext for a uniform unknown message cannot guess the message; One-Wayness under Plaintext-Checking Attack (OW-PCA) adds a plaintext-checking oracle that answers whether $\Dec(\mathit{sk}, c) = m$ for queried pairs.

Each mechanism blocks a specific abuse. The re-encryption check defeats the decryption oracle: a modified ciphertext decrypts to some $m'$ whose re-encryption almost surely differs from the query, so the answer is rejection regardless of the challenge message, and the plaintext-checking capability the attacker was hoping for never materializes. Explicit rejection matters for timing and for the proof, since the decapsulation output must depend only on the hash of whatever came out, valid or invalid. Skipping either ingredient admits a chosen-ciphertext attack, as exercise 4 works out.

Crystals-Kyber is the instantiation: the LP11-style Module-LWE encryption of section 9, over the ring $\Zq[X]/(X^{d}+1)$ with module rank $k$, wrapped in this transform. NIST selected it in 2022 and published it in 2024 as ML-KEM (FIPS 203). The parameter sets are named for their target security: ML-KEM-512, ML-KEM-768 and ML-KEM-1024 match AES-128, AES-192 and AES-256. At the smallest set the public key is $800$ bytes, the ciphertext $768$ bytes and the secret key $1632$ bytes. ML-KEM is the first post-quantum key encapsulation in broad deployment, and current practice runs it in hybrid mode, combined with an elliptic-curve exchange so that a break of either component still leaves the session key intact.

What went wrong. KyberSlash (2024) showed timing side channels in Kyber implementations: secret-dependent divisions leaked secret keys. Constant-time code matters as much as the mathematics.

Encryption so far has protected data at rest and in transit while destroying its utility, since a server holding $\Enc(\mathit{pk}, x)$ cannot compute $f(x)$. The motivating scenario is outsourced computation: a client uploads private $x$ to an untrusted server, the server evaluates $f$ and the client decrypts $f(x)$, with the server learning nothing. Computing on encrypted data subsumes so many other tasks that a general solution yields most of private computation.

An apparent paradox motivates the randomized requirement. Consider $f(x_1, x_2, x_3) = x_2$ if $x_1 = 0$ and $x_3$ if $x_1 = 1$. A server evaluating $f$ on three ciphertexts returns either $\Enc(\mathit{pk}, x_2)$ or $\Enc(\mathit{pk}, x_3)$. The identity of the returned object reveals $x_1$. The resolution is that encryption is randomized: the output of $\mathsf{Eval}$ is computationally indistinguishable from a fresh encryption of $f(x)$, so the server cannot tell which branch it computed. A trivial construction shows the definition is otherwise easy to satisfy: set $\mathsf{Eval}(\mathit{pk}, \Gamma, c) = (\Gamma, c)$ and let $\Dec'$ run $\Gamma$ on the decrypted input. It is correct and private, and useless, because decryption now costs as much as the circuit. Real FHE keeps the evaluation structure while keeping decryption cheap.

Homomorphism follows the invariant. Addition is matrix addition: $C_{+} = C_1 + C_2$ carries plaintext $x_1 + x_2$ and noise $e_1 + e_2$. Multiplication uses gadget decomposition to control the blow-up: $C_{\times} = C_1 \cdot G^{-1}(C_2)$, and expanding the invariant gives plaintext $x_1 x_2$ with noise $e_{\times} = e_1 G^{-1}(C_2) + x_1 e_2$, bounded by about $(N + 1) \cdot \max(\abs{e_1}, \abs{e_2})$ where $N$ is the gadget width. Without the gadget the noise would square at every multiplication; with it, growth is linear per level. After multiplicative depth $\tau$ the noise is at most $(N + 1)^{\tau - 1} \cdot m \cdot \alpha q$. Correctness requires $n \cdot m \cdot (N + 1)^{\tau - 1} < q/4$. Choosing parameters for a target depth gives levelled FHE. The ciphertext size stays polynomial in the security parameter and $\tau$, which is weak compactness. Security is the Regev argument again: LWE makes $A$ uniform-looking, the leftover hash lemma makes each column of $AR$ statistically uniform and the ciphertext hides the plaintext computationally under LWE.

Levelled schemes have a hard limit. Parameters grow with the depth. No evaluation is possible once the noise crosses $q/4$. Gentry's trick removes the limit. Bootstrapping refreshes a ciphertext by homomorphically evaluating the scheme's own decryption circuit: given an encryption of the secret key under a fresh key, $\mathsf{Eval}$ runs $\Dec$ inside the encryption, producing a fresh ciphertext of the same plaintext with noise reset to the fresh level. Key switching chains the levels, so a few operations per key suffice. The construction assumes circular security: $\Enc(\mathit{pk}, 0) \approx_c \Enc(\mathit{pk}, 1)$ must hold even given an encryption of $\mathit{sk}$ under $\mathit{pk}$. GSW is conjectured to have this property. No proof is known.

Chapter 2 built identity-based encryption from pairings, whose security falls with the discrete logarithm under Shor's algorithm. The lattice construction preserves the interface while replacing the algebra. It also leads to attribute-based encryption. Key escrow remains: the authority that issues private keys can read every message.

The same skeleton generalizes from identities to predicates. Inner-product encryption (Katz, Sahai, Waters 2008; Agrawal, Freeman, Vaikuntanathan 2011): Alice encrypts with an attribute vector $a = (a_1, \dots, a_k)$, Bob holds a key $\mathit{sk}_b$ for a vector $b$ and decryption recovers $x$ if and only if $\langle a, b \rangle = 0$. The AFV construction publishes $(A, A_1, \dots, A_k, G, u)$, gives Bob a short $s_b$ with $F_b^{\top} s_b = u$ for $F_b = [A \,\|\, \sum_i b_i A_i]$. The ciphertext components along the $A_i$ are masked so that $a$ itself stays hidden, which is the attribute-privacy variant. Attribute-based encryption (Sahai and Waters 2004) replaces the inner product with a general predicate: decryption succeeds if and only if $f(a) = 0$, with no attribute privacy required. The lattice realization (Garg, Gentry, Halevi and collaborators 2014) handles the missing operation, multiplication, by gadget algebra: from ciphertext pieces for $a_1$ and $a_2$ one forms a piece for the product with matrix $A_{a_1 a_2} = A_1 A_2 + a_1 a_2 G$, combining $c_{a_1}^{\top} G^{-1}(-A_2)$ and $c_{a_2}^{\top} a_1$, where the small terms keep the noise under control. Additions compose trivially, so every boolean circuit of attributes is reachable, which is why ABE is the standard tool for privacy-preserving data mining and fine-grained access control on encrypted data.

• NIST Post-Quantum Cryptography project. The authoritative hub for FIPS 203 ML-KEM, FIPS 204 ML-DSA, FIPS 205 SLH-DSA and the migration timeline.
• What Is Post-Quantum Cryptography? (NIST FAQ). A plain-language account of why factoring falls to quantum computers, harvest-now-decrypt-later and the difference between PQC and QKD.
• CRYSTALS. The designers' introduction to Kyber and Dilithium, covering module lattices, parameter sets, key and ciphertext sizes and benchmarks.
• Wikipedia: Post-quantum cryptography. The six candidate families with the status of their security reductions and a size-comparison table.
• Wikipedia: Learning with errors. The formal LWE definition and Regev's construction.
• The Joy of Cryptography, chapter 20. A classroom-grade PQC chapter in the provable-security style used here.
• IACR Cryptology ePrint Archive. Primary sources for advanced students.
• CrypTool-Online Kyber app. An in-browser ML-KEM demo.

Further reading: Katz and Lindell (2015), Introduction to Modern Cryptography, the standard reference for the provable-security style used throughout this chapter.