Post-Quantum Cryptography Explained

This article has three layers:

1. The intuition: what quantum computers actually threaten, why we must switch now, and the intuition behind lattice cryptography
2. Real-world use: NIST standards, real deployments in browsers, Signal, iMessage and SSH, migration timelines, blockchains
3. The mathematics: lattices and SVP/CVP, LWE, Ring/Module-LWE, the full Kyber flow, NTT and CRT, hash-based signatures and worked examples

Layer 1: The Intuition

1.1 What today's cryptography rests on

Nearly every case of "strangers establishing a secure connection" relies on public-key cryptography:

The security of public-key algorithms rests on one sentence: "This math problem would take a classical computer until the end of the universe." For example, factoring a 2048-bit number $N = pq$ back into $p$ and $q$ with the best known classical algorithm (the number field sieve) takes roughly

$$\exp\!\Big(c\,(\ln N)^{1/3}(\ln\ln N)^{2/3}\Big),$$

which is completely infeasible for RSA-2048.

1.2 Shor's algorithm: RSA and ECC would be broken completely

In 1994, Peter Shor proved: a quantum computer can factor integers and solve discrete logarithms in polynomial time.

The intuition goes like this. Factoring $N$ reduces to finding the period of a function: take any $a$ and see how often

$$f(k) = a^k \bmod N$$

repeats. Let the period be $r$, so $a^r \equiv 1 \pmod N$. If $r$ is even, then

$$(a^{r/2}-1)(a^{r/2}+1) \equiv 0 \pmod N,$$

so $\gcd(a^{r/2}-1,\,N)$ is very likely a proper factor of $N$.

A classical computer can only find the period by trying values one by one; a quantum computer can put all $k$ in "superposition" and apply a quantum Fourier transform, and the period emerges like fringes from a diffraction grating. The elliptic curve discrete logarithm is also a "hidden period" problem, falls the same way, and needs even fewer qubits than RSA.

1.3 Grover's algorithm: AES is only weakened

Symmetric ciphers (AES) and hashes (SHA-256) have no algebraic structure for Shor to exploit, leaving a quantum computer with "unstructured search". Grover's algorithm reduces the time to find an answer among $N$ candidates from $N$ to about $\sqrt{N}$:

$$2^{128} \;\longrightarrow\; \sqrt{2^{128}} = 2^{64}.$$

So under quantum attack AES-128 "nominally" has only 64 bits of security left. But this is only a quadratic speedup:

• Doubling the key cancels it: AES-256 still has strength of about $2^{128}$ under quantum attack.
• Grover must run serially, and is hard to parallelize across thousands of machines the way classical brute force is, so in practice even AES-128 isn't in so much danger.

The conclusion: what really must be replaced is public-key cryptography, namely key exchange and digital signatures.

1.4 "Harvest now, decrypt later": why we must switch now

Quantum computers haven't been built yet, so why the rush to switch in 2024? Because one attack is already happening today:

A classic inequality (Mosca's inequality) measures the danger. Let

• $x$: how many years your data must stay secret,
• $y$: how many years migrating the whole system to post-quantum algorithms takes,
• $z$: how many years until quantum computers can break RSA.

If

$$x + y > z,$$

then you are already late. Medical records, state secrets and genomic data easily have $x$ of several decades, and large institutions often need $y$ of ten years, so even $z$ of 15 years isn't safe.

Note that the two uses differ in urgency:

• Encryption / key exchange: threatened by "harvest now, decrypt later" and the most urgent, so it is what the big companies switched first.
• Signatures: a signature only has to be secure at the moment of verification. Signatures made before quantum computers appear were trustworthy when verified, so these can switch a little later. It is a different story if, as with Bitcoin, public keys stay exposed on-chain for a long time (see 2.5).

1.5 The intuition of lattice cryptography: finding the nearest point in a high-dimensional grid

Post-quantum cryptography has several schools (lattices, hashes, codes, multivariate, isogenies), and lattice cryptography is by far the mainstay.

A lattice is a neatly arranged array of points in space. In the plane, take two vectors $b_1, b_2$. All their integer combinations

$$\{\, a_1 b_1 + a_2 b_2 \;:\; a_1, a_2 \in \mathbb{Z} \,\}$$

form a lattice, which looks like a sheet of slanted graph paper.

A lattice can be generated by many different "bases":

• Good basis: two short, nearly perpendicular vectors, giving a neat grid.
• Bad basis: two long, nearly parallel vectors, generating the same lattice but looking like a mess.

The closest vector problem (CVP): given any point in space, find the lattice point nearest to it.

• With a good basis: round the point's coordinates to the nearest integer combination, and you are basically right.
• With a bad basis: rounding lands you far away.

In two dimensions you can do it by eye, but raise the dimension to 500 or 1000, and no one knows how to do it efficiently. The best known algorithms (classical or quantum) all need exponential time.

Why can't quantum computers help? Shor's algorithm relies on algebraic structure like a "hidden period", and lattice problems have no period to exploit directly. People have looked for quantum lattice algorithms for decades, and the best give only constant-factor improvements. This is also why NIST chose lattices as the mainstay.

Layer 2: Real-World Use

2.1 The results of NIST standardization

The US National Institute of Standards and Technology (NIST) began publicly soliciting post-quantum algorithms in 2016, received 82 proposals, and after more than three rounds of public analysis published the first three official standards on August 13, 2024:

Where each algorithm fits:

• ML-KEM: general key exchange. Nearly all deployments use it, most often with the ML-KEM-768 parameters.
• ML-DSA: general signatures, fast and simple to implement.
• SLH-DSA: secure as long as hash functions aren't broken, with the fewest assumptions and the most conservative stance. The cost is very large signatures and slow signing. It suits uses like root certificates and firmware signing, "signed rarely and kept a long time".
• FN-DSA (Falcon): signatures and public keys are much smaller than ML-DSA's, but signing requires discrete Gaussian sampling over floating-point numbers, which is hard to make constant-time and side-channel-resistant, so its standard has lagged. It was still a draft as of October 2026.
• HQC: chosen by NIST in March 2025 as a backup to ML-KEM. It is based on error-correcting codes rather than lattices, so if lattices ever fall, a mathematically completely different scheme is available. The standard is planned to be finalized in 2027.

Size comparison (in bytes):

2.2 Why "hybrid"

Nearly all real deployments don't simply replace X25519 with ML-KEM, but use both together:

$$K = \mathrm{KDF}\big(K_{\text{X25519}} \,\|\, K_{\text{ML-KEM}}\big).$$

An attacker must break both at once to get $K$:

• If quantum computers arrive and X25519 falls, ML-KEM still holds.
• If ML-KEM turns out to have a mathematical or implementation flaw, X25519 at least guarantees things are no worse than today.

This caution has been earned: in 2022, the NIST round-4 candidate SIKE (isogeny cryptography) was broken by an ordinary laptop within an hour, and the signature candidate Rainbow (multivariate) was also broken that year. New mathematical problems need time to prove themselves.

2.3 Real deployments

Browsers and TLS (HTTPS)

• Chrome: Chrome 124 in April 2024 enabled X25519+Kyber768 hybrid key exchange by default on desktop; Chrome 131 in November 2024 switched to the standardized X25519MLKEM768. Firefox and Edge followed, and Apple added hybrid ML-KEM to TLS in its 2025 system updates.
• Cloudflare: has supported post-quantum handshakes on the server side since 2022. By the end of October 2025, more than half of human traffic on Cloudflare used post-quantum key exchange; according to reports from April 2026, the share had passed 65%. Cloudflare's goal is to make authentication (signatures) fully post-quantum by 2029 as well.

Signal

• PQXDH (September 2023): adds Kyber-1024 to the initial X3DH handshake, protecting session setup.
• SPQR / the triple ratchet (released October 2, 2025): Signal's original Double Ratchet keeps updating keys as a chat goes on. SPQR (Sparse Post-Quantum Ratchet) adds another ratchet based on ML-KEM-768, and the keys from both feed into a KDF. Post-quantum protection thus covers the whole conversation, not just the start.
  • A related detail: ML-KEM data runs over a thousand bytes, so Signal splits it into chunks protected by erasure coding, and it can recover even if some messages are lost, on the same principle as Reed–Solomon codes.

Apple iMessage PQ3 (February 2024, iOS 17.4)

• The initial handshake mixes Kyber-1024 and ECC, and afterwards it periodically rekeys with Kyber-768. Even if a key leaks at some moment, later messages automatically recover their security. Apple calls this "Level 3" security.

OpenSSH

• OpenSSH 9.0 (April 2022) already used sntrup761x25519-sha512 (NTRU Prime + X25519 hybrid) by default.
• OpenSSH 10.0 (April 2025) changed the default key exchange to mlkem768x25519-sha256. Version 10.1 also warns when a connection doesn't use post-quantum key exchange.
• But host keys and user keys (Ed25519, RSA) are still classical signatures, because a post-quantum signature standard for SSH is still under discussion at the IETF. This again shows: switch key exchange first, signatures later.

2.4 Migration timelines

In short, 2035 is the nearly universal deadline for "retiring RSA/ECC".

2.5 The threat to blockchains

Blockchains are especially sensitive to quantum attacks, because signatures are ownership, and historical data is public forever.

Bitcoin

• It uses ECDSA / Schnorr signatures on secp256k1, and Shor's algorithm can compute the private key directly from the public key.
• An address is usually a hash of the public key, and hashes face only Grover, so addresses that "have only received and never spent" are relatively safe.
• The danger is in coins whose public keys are already exposed:
  • Early P2PK outputs wrote the public key directly on-chain, including about a million coins believed to belong to Satoshi Nakamoto;
  • Reused addresses (once spent from, the public key is public);
  • Taproot (P2TR) outputs contain the public key directly.
• Even with an unexposed address, the public key is public during the few minutes between a transaction's broadcast and its confirmation, and a fast enough quantum computer could compute the private key first and issue a conflicting transaction.
• The community is discussing post-quantum address proposals such as BIP-360, but also faces a social problem: what about old coins that never migrate? Freeze them, or let "quantum miners" take them?

Ethereum

• Externally owned accounts (EOAs) are also based on secp256k1, and after one transaction the public key can be recovered from the signature.
• Account abstraction lets wallets switch to any signature algorithm, one of the main paths for Ethereum's post-quantum migration.
• At the zero-knowledge proof layer: pairing-based SNARKs (Groth16, KZG commitments) rely on the elliptic curve discrete logarithm and would be broken by Shor, while hash-based STARKs (with the FRI and Reed–Solomon codes inside them) are post-quantum secure.

Proof of work itself (SHA-256 mining) faces only Grover's quadratic speedup, and the clock speed of quantum computers is far below ASIC miners, so it isn't a problem in the short term.

Layer 3: The Mathematics

3.1 Lattices, SVP and CVP

In algebraic language, a lattice is a discrete additive subgroup of rank $n$ in $\mathbb{R}^n$, isomorphic to $\mathbb{Z}^n$ as a $\mathbb{Z}$-module.

The same lattice has many bases: $B$ and $B'$ generate the same lattice if and only if there is $U \in GL_n(\mathbb{Z})$ (an integer matrix with determinant $\pm 1$) with $B' = BU$. So $|\det B|$ doesn't depend on the choice of basis; it is the lattice's "fundamental region volume".

Two core hard problems:

• The shortest vector problem (SVP): find the shortest nonzero vector in the lattice, whose length is written $$\lambda_1(\mathcal{L}) = \min_{v \in \mathcal{L}\setminus\{0\}} \|v\|.$$
• The closest vector problem (CVP): given a target point $t \in \mathbb{R}^n$, find $v \in \mathcal{L}$ minimizing $\|t - v\|$.

Known results:

• The LLL algorithm (1982) finds a vector of length at most $2^{O(n)}\lambda_1$ in polynomial time. The approximation factor is exponential, which is useless for cryptography.
• The BKZ algorithm can trade off the approximation factor against running time, but a polynomial approximation factor still takes $2^{\Theta(n)}$ time.
• Exact SVP is NP-hard under randomized reductions. No quantum algorithm currently approximates SVP to a polynomial factor in polynomial time.

What cryptography actually relies on is the hardness of SVP with polynomial approximation factors (GapSVP, SIVP).

3.2 LWE: learning with errors

Building cryptosystems directly from lattice bases (GGH, early NTRU variants) is rather inconvenient. In 2005 Oded Regev proposed an "algebraized" version: Learning With Errors (LWE).

Why is $e$ the key? Without $e$, $b = As$ is a system of linear equations, solved for $s$ in a few steps by Gaussian elimination over $\mathbb{Z}_q$ (a field when $q$ is prime). With a little noise added:

• Gaussian elimination amplifies the errors: each row operation multiplies them by coefficients and piles them up, quickly drowning the signal.
• From the lattice viewpoint, $\{\,Ax \bmod q : x\in\mathbb{Z}_q^n\,\}$ plus $q\mathbb{Z}^m$ forms a lattice, and $b$ is a point very close to some lattice point. Solving LWE is solving CVP on this lattice.

This "worst-case to average-case" reduction is very strong: breaking a randomly generated LWE instance means being able to solve hard problems on all lattices. RSA has no such guarantee.

From LWE to public-key encryption (Regev's scheme, encrypting one bit):

• Private key: $s \in \mathbb{Z}_q^n$.
• Public key: $(A,\, b = As + e)$.
• Encrypt a bit $\mu \in \{0,1\}$: randomly choose $r \in \{0,1\}^m$ and compute $$u = A^{\mathsf T} r, \qquad v = b^{\mathsf T} r + \mu \cdot \left\lfloor \tfrac{q}{2} \right\rfloor .$$ The ciphertext is $(u, v)$.
• Decrypt: compute $$d = v - u^{\mathsf T} s = (As+e)^{\mathsf T} r + \mu\lfloor q/2\rfloor - r^{\mathsf T} A s = e^{\mathsf T} r + \mu \left\lfloor \tfrac{q}{2} \right\rfloor .$$ Because $e^{\mathsf T} r$ is small, output $0$ if $d$ is close to $0$, and $1$ if close to $q/2$.
• Correctness condition: $|e^{\mathsf T} r| < q/4$.

3.3 A worked example: toy LWE encrypting one bit

Step 1: generate the public key. First compute $As$:

$$As = \begin{pmatrix} 3\cdot 2 + 7\cdot 5 \\ 5\cdot 2 + 1\cdot 5 \\ 11\cdot 2 + 4\cdot 5 \\ 2\cdot 2 + 9\cdot 5 \end{pmatrix} = \begin{pmatrix} 41 \\ 15 \\ 42 \\ 49 \end{pmatrix} \equiv \begin{pmatrix} 7 \\ 15 \\ 8 \\ 15 \end{pmatrix} \pmod{17}.$$

Then add the errors:

$$b = As + e \equiv \begin{pmatrix} 7+1 \\ 15-1 \\ 8+0 \\ 15+1 \end{pmatrix} = \begin{pmatrix} 8 \\ 14 \\ 8 \\ 16 \end{pmatrix} \pmod{17}.$$

Publish $(A, b)$ and keep $s$ secret.

Step 2: encrypt the bit $\mu = 1$. Randomly choose $r = (1, 0, 1, 1)^{\mathsf T}$, which adds samples 1, 3 and 4:

$$u = A^{\mathsf T} r = \begin{pmatrix} 3 + 11 + 2 \\ 7 + 4 + 9 \end{pmatrix} = \begin{pmatrix} 16 \\ 20 \end{pmatrix} \equiv \begin{pmatrix} 16 \\ 3 \end{pmatrix} \pmod{17},$$

$$v = b^{\mathsf T} r + 8 = (8 + 8 + 16) + 8 = 40 \equiv 6 \pmod{17}.$$

The ciphertext is $(u, v) = \big((16, 3)^{\mathsf T},\; 6\big)$.

Step 3: decrypt. With the private key, compute

$$u^{\mathsf T} s = 16\cdot 2 + 3 \cdot 5 = 47 \equiv 13 \pmod{17},$$

$$d = v - u^{\mathsf T} s = 6 - 13 = -7 \equiv 10 \pmod{17}.$$

The decision rule: in $\mathbb{Z}_{17}$, the values close to $0$ are $\{13,\dots,16, 0, 1, \dots, 4\}$, and those close to $8$ are $\{5, \dots, 12\}$. $d = 10$ is only $2$ from $8$, so it decrypts to $1$ ✓.

Checking the theory: $e^{\mathsf T} r = 1 + 0 + 1 = 2$, and indeed

$$d = e^{\mathsf T} r + 8 = 2 + 8 = 10.$$

For comparison: encrypt $\mu = 0$. With the same $r$, $u$ is unchanged and $v = 32 \equiv 15$, so $d = 15 - 13 = 2$, close to $0$, which decrypts to $0$ ✓.

Why is it always correct? The absolute values of the components of $e$ sum to $3$, so for any $r \in \{0,1\}^4$ we have $|e^{\mathsf T} r| \le 3 < 17/4$, and decryption never fails. (Verified with Python by enumerating all $2^4$ values of $r$ and both bits.)

3.4 Ring-LWE and Module-LWE

Plain LWE has a big problem: the public key is too large. The matrix $A$ has $m \times n$ elements, hundreds of thousands of numbers at $n = 768$, for a public key of hundreds of KB.

The idea of Ring-LWE: give $A$ structure, replacing the whole matrix with one polynomial.

Take the quotient ring

$$R_q = \mathbb{Z}_q[x] / (x^n + 1),$$

whose elements are polynomials of degree $< n$ with coefficients in $\mathbb{Z}_q$, simplified after multiplication with $x^n = -1$. In the language of abstract algebra, $R_q$ is the quotient of $\mathbb{Z}[x]$ by the ideal $(q,\; x^n+1)$:

$$R_q \;\cong\; \mathbb{Z}[x] / (q,\; x^n + 1).$$

In $R_q$, "multiplying by $a(x)$" is a $\mathbb{Z}_q$-linear map, corresponding to an $n\times n$ matrix:

$$a(x) \cdot s(x) \quad\longleftrightarrow\quad \begin{pmatrix} a_0 & -a_{n-1} & \cdots & -a_1 \\ a_1 & a_0 & \cdots & -a_2 \\ \vdots & \vdots & \ddots & \vdots \\ a_{n-1} & a_{n-2} & \cdots & a_0 \end{pmatrix} \begin{pmatrix} s_0 \\ s_1 \\ \vdots \\ s_{n-1} \end{pmatrix}.$$

This is called a negacyclic matrix: each column is the previous one "rotated down by one", with the element wrapping to the top changing sign, because $x \cdot x^{n-1} = x^n = -1$. The whole matrix is determined by $n$ numbers, so storage drops from $n^2$ to $n$.

Why $x^n + 1$? Take $n = 2^k$. Then

$$x^n + 1 = \Phi_{2n}(x)$$

is the $2n$-th cyclotomic polynomial (its complex roots are exactly all the primitive $2n$-th roots of unity $e^{\pi i (2j+1)/n}$). There are several reasons to choose it:

1. It is irreducible over $\mathbb{Q}$ (for $\Phi_{2^{k+1}}$, apply Eisenstein's criterion to $f(x+1)$ with $p=2$). So $\mathbb{Z}[x]/(x^n+1)$ is the ring of integers of the cyclotomic field $\mathbb{Q}(\zeta_{2n})$. Lyubashevsky, Peikert and Regev (2010) used exactly this algebraic number theory structure to reduce the hardness of Ring-LWE to worst-case hard problems on ideal lattices.
2. Irreducibility matters. A counterexample: with $x^n - 1 = (x-1)(\cdots)$, there is a ring homomorphism $$\mathbb{Z}_q[x]/(x^n - 1) \to \mathbb{Z}_q, \qquad f(x) \mapsto f(1).$$ Substituting $x = 1$ into both sides of $b = as + e$ gives $b(1) = a(1)s(1) + e(1)$. This is a small problem with just 1 unknown, and $e(1)$ is fairly small, leaking enough information to mount an attack.
3. Reduction is cheap: with $x^n \equiv -1$, modular reduction just flips the sign of high-degree terms and adds them back to low-degree ones. Coefficients also don't swell during reduction (the "expansion factor" is small), keeping errors small.
4. It suits the NTT: when $q \equiv 1 \pmod{2n}$ (or $\pmod n$), $x^n+1$ factors over $\mathbb{Z}_q$, and multiplication can be accelerated with the NTT (see 3.6).

Module-LWE: between the two. Ring-LWE's structure is too "full", and Module-LWE steps back a little, using a $k \times k$ matrix of ring elements

$$\mathbf{A} \in R_q^{k\times k}, \qquad \mathbf{s}, \mathbf{e} \in R_q^{k}, \qquad \mathbf{t} = \mathbf{A}\mathbf{s} + \mathbf{e}.$$

This is LWE on the $R_q$-module $R_q^k$, hence the name. The benefits:

• The ring $R_q$ is fixed at $n = 256$, so changing only $k$ adjusts the security level, with the same NTT code throughout.
• Compared with Ring-LWE it has less algebraic structure, so in theory it is less exposed to structure-targeting attacks.

All three use $n = 256$ and $q = 3329$.

3.5 The flow of Kyber (ML-KEM)

Notation: $R_q = \mathbb{Z}_q[x]/(x^{256}+1)$ and $q = 3329$. The coefficients of "small" polynomials are sampled from a centered binomial distribution $\beta_\eta$, with values in $\{-\eta, \dots, \eta\}$; ML-KEM-768 has $\eta = 2$.

The derivation uses only $\mathbf{t} = \mathbf{A}\mathbf{s}+\mathbf{e}$ and the commutativity of $R_q$:

$$\mathbf{t}^{\mathsf T}\mathbf{r} - \mathbf{s}^{\mathsf T}\mathbf{A}^{\mathsf T}\mathbf{r} = (\mathbf{A}\mathbf{s})^{\mathsf T}\mathbf{r} + \mathbf{e}^{\mathsf T}\mathbf{r} - \mathbf{s}^{\mathsf T}\mathbf{A}^{\mathsf T}\mathbf{r} = \mathbf{e}^{\mathsf T}\mathbf{r}.$$

This has exactly the same structure as the toy example in 3.3, with "integers" replaced by "polynomials in $R_q$", encrypting 256 bits at once instead of 1.

3.6 NTT: accelerating multiplication with the Chinese Remainder Theorem

The main computation in Kyber is polynomial multiplication in $R_q$. Direct multiplication needs $256^2 = 65536$ coefficient multiplications, and the NTT (number theoretic transform) reduces this to the order of $O(n\log n)$. The NTT is the FFT over a finite field, and the mathematics behind it is the Chinese Remainder Theorem from abstract algebra.

The key point: multiplication on the right side of the isomorphism is componentwise. So to compute $g \cdot h$, you can:

1. Map $g, h$ to the right side (forward NTT);
2. Multiply componentwise (cheap);
3. Map back to the left side (inverse NTT).

Steps 1 and 3 can recursively split in half like the FFT, using $x^{2m} - c^2 = (x^m - c)(x^m + c)$, in $\log n$ levels in all.

First, a small example: $\mathbb{Z}_{17}[x]/(x^4+1)$.

Because $17 \equiv 1 \pmod 8$, $\mathbb{Z}_{17}^\times$ (a cyclic group of order $16$) contains primitive 8th roots of unity, so $x^4 + 1$ factors completely over $\mathbb{Z}_{17}$. Its four roots are $2, 8, 9, 15$ (for example $2^4 = 16 \equiv -1$). So

$$\mathbb{Z}_{17}[x]/(x^4+1) \;\cong\; \mathbb{Z}_{17}[x]/(x-2) \times \mathbb{Z}_{17}[x]/(x-8) \times \mathbb{Z}_{17}[x]/(x-9) \times \mathbb{Z}_{17}[x]/(x-15) \;\cong\; \mathbb{Z}_{17}^4,$$

and the isomorphism is evaluation, $g \mapsto \big(g(2), g(8), g(9), g(15)\big)$.

Take $f = 1 + 2x + x^3$ and $g = 3 + x^2$. Computing directly (with $x^4 = -1$, $x^5 = -x$):

$$fg = 3 + 6x + x^2 + 5x^3 + x^5 = 3 + 5x + x^2 + 5x^3.$$

Verifying by evaluation:

A perfect match. Note in passing that $f(9) = 0$: $f$ isn't the zero polynomial yet vanishes on one component, so $f$ is a zero divisor in this ring. This shows $R_q$ isn't an integral domain, which is the same fact as "$x^4+1$ is reducible over $\mathbb{Z}_{17}$".

Back to Kyber: $q = 3329$ and $q - 1 = 3328 = 2^8 \cdot 13$.

• $\mathbb{Z}_{3329}^\times$ is a cyclic group of order $3328$ containing primitive $256$th roots of unity, and Kyber takes $\zeta = 17$ (you can verify that $17$ has order exactly $256$ and $17^{128} \equiv -1$).
• But $512 \nmid 3328$, so there is no primitive 512th root of unity, and $x^{256}+1$ can't factor completely into linear factors, only into 128 quadratic ones:

$$x^{256} + 1 = \prod_{i=0}^{127} \big(x^2 - \zeta_i\big), \qquad \zeta_i = \zeta^{\,2\,\mathrm{br}_7(i)+1},$$

where $\mathrm{br}_7(i)$ reverses the 7-bit binary representation of $i$ (just for the order of the FFT recursion). These 128 values $\zeta_i$ are exactly all the roots of $y^{128} = -1$. By the CRT:

$$R_q = \mathbb{Z}_q[x]/(x^{256}+1) \;\cong\; \prod_{i=0}^{127} \mathbb{Z}_q[x]/(x^2 - \zeta_i).$$

Going further: $x^2 - \zeta_i$ is irreducible over $\mathbb{Z}_q$. If $\zeta_i = y^2$, then $y$ would have order $512$, and no such element exists. So each factor is a field $\mathbb{F}_{q^2}$, and

$$R_q \;\cong\; \underbrace{\mathbb{F}_{q^2} \times \cdots \times \mathbb{F}_{q^2}}_{128\text{ copies}}.$$

In the NTT domain, multiplying two polynomials becomes 128 "linear polynomial multiplications modulo $x^2 - \zeta_i$":

$$(a_0 + a_1 x)(b_0 + b_1 x) \equiv (a_0 b_0 + \zeta_i\, a_1 b_1) + (a_0 b_1 + a_1 b_0)\, x \pmod{x^2 - \zeta_i}.$$

3.7 The signature idea of ML-DSA (briefly)

ML-DSA (Dilithium) uses "Fiat–Shamir with aborts":

1. Commit: randomly choose a small $\mathbf{y}$ and compute the high bits $\mathbf{w}_1$ of $\mathbf{w} = \mathbf{A}\mathbf{y}$.
2. Challenge: $c = H(\text{message} \,\|\, \mathbf{w}_1)$, a sparse polynomial with only a few coefficients of $\pm 1$.
3. Respond: $\mathbf{z} = \mathbf{y} + c\,\mathbf{s}_1$.
4. Abort check: if the coefficients of $\mathbf{z}$ are too large (which might leak information about $\mathbf{s}_1$), discard and retry. By rejection sampling, the distribution of $\mathbf{z}$ is independent of the private key.

The verifier checks that the high bits of $\mathbf{A}\mathbf{z} - c\,\mathbf{t}$ equal $\mathbf{w}_1$, and that $\mathbf{z}$ is small enough. Security rests on Module-LWE and Module-SIS (finding a short vector $\mathbf{x}$ with $\mathbf{A}\mathbf{x} = 0$).

3.8 Hash-based signatures: from Lamport to SPHINCS+

The security of hash-based signatures depends only on the one-wayness and collision resistance of a hash function, with no algebraic structure at all. It is the most conservative approach.

Lamport one-time signatures (1979): let $H$ output 256 bits.

• Private key: $512$ random strings $x_{i,0}, x_{i,1}$, for $i = 1, \dots, 256$.
• Public key: their hashes $y_{i,b} = H(x_{i,b})$.
• Sign a message $M$: let $h = H(M) = h_1 h_2 \cdots h_{256}$, and for each bit reveal $x_{i,h_i}$.
• Verify: check $H(\text{signature}_i) = y_{i,h_i}$ for all $i$.

Forging a signature requires a hash preimage of some $y_{i,b}$. But each key can be used only once: signing two messages exposes parts of both sides of the private key, and an attacker can assemble a new signature.

The line of improvements:

• Winternitz (WOTS): handles $w$ bits at a time, using a hash chain $x \to H(x) \to H(H(x)) \to \cdots$ to represent $0$ to $2^w - 1$, greatly shortening signatures.

• Merkle trees: take $2^h$ one-time public keys as leaves and build a hash tree, whose root is the overall public key. A signature = a one-time signature + the authentication path from leaf to root ($h$ hash values). The drawback is that the signer must remember which leaves were used (it is stateful); XMSS and LMS (NIST SP 800-208) are of this kind. If the state ever goes wrong (say a virtual machine snapshot is rolled back), a leaf may be reused, leaking the private key.

• SPHINCS+ (SLH-DSA):

  • Uses a hypertree (stacked layers of Merkle trees) to provide a vast number of leaves, such as $2^{63}$ or more;
  • Uses a hash of the message to pick a leaf pseudorandomly, with so many leaves that collisions are nearly impossible;
  • Uses FORS (a few-time signature) rather than a one-time signature at the leaves, so even an occasional collision on one leaf is still safe.

  So no state needs tracking. The cost is signatures from 7.8 KB to about 50 KB, and signing much slower than ML-DSA.

Summary