Learning Lattice Cryptography

The paper saysA faithful restatement of the paper, with the exact source in grey, e.g. §2.3, Eq. (6). Conditions and the direction of every “if” are kept exactly as the paper states them.

The paper says

The road to the NIST standards

Modern lattice cryptography starts with two works from the mid 1990s. Ajtai [Ajt96] showed that solving a random instance of the Small Integer Solution (SIS) problem is as hard as solving some believed-to-be-difficult problem for every lattice. NTRU [HPS98] was an efficient public-key cryptosystem based on a new, potentially-hard problem over polynomial rings. Ajtai's line had strong guarantees but impractical instantiations; NTRU was practical but lacked a theoretical underpinning, and several NTRU-style constructions were later weakened or broken.

The two threads were woven together in the next decade: [Mic02, PR06, LM06] distilled the algebraic structure that gives lattice primitives NTRU-like efficiency with Ajtai-like guarantees, and Regev [Reg05] introduced the Learning with Errors (LWE) problem and showed that random LWE is as hard as (quantumly) solving worst-case lattice problems. The first fully-homomorphic encryption scheme [Gen09] and the threat of quantum computers [Sho97] added momentum; by the start of the NIST post-quantum process in 2017, lattice schemes were among the fastest and most compact quantum-resistant primitives. §1, p. 2

Scope and audience

The tutorial covers the mathematical concepts and design decisions behind the two main NIST lattice standards: the KEM / encryption scheme CRYSTALS-Kyber (ML-KEM) and the signature scheme CRYSTALS-Dilithium (ML-DSA), plus the ideas behind Frodo and NTRU. It assumes familiarity with indistinguishability, the hybrid argument, CPA-secure encryption, random oracles and the Fiat–Shamir transform; keeping ElGamal and Schnorr in mind helps. §1, pp. 2–3

Lattice cryptography is “messy”: security depends on several parameters, and there are many optimization tricks (dropping low-order bits, rounding). But it needs very few “deep” mathematical concepts. The advice is to work through the details with pencil and paper once, then keep the high-level ideas. §1, p. 3

Not covered: advanced constructions beyond encryption and signatures, precise cryptanalysis, the geometric side needed for FALCON and trapdoor sampling [GPV08, Pei10, MP12], and quantum aspects (the ROM versus the QROM). §1, pp. 3–4

Outline

§2 builds encryption over $\mathbb{Z}_q$ from LWE, plus compression tricks; §3 introduces lattices and connects LWE and SIS to the hardness of lattice problems; §4 moves to polynomial rings and ends with Kyber and the NTT; §5 builds a lattice analogue of Schnorr signatures, ending with Dilithium. §1, p. 4

The paper says

We start with a CPA-secure public-key encryption scheme: three algorithms (key generation, encryption, decryption), and CPA security means that for any two messages of the adversary's choosing, their encryptions are computationally indistinguishable. Generic transformations such as Fujisaki–Okamoto [FO99] later turn CPA security into CCA security (§4.8).

Unlike discrete-log and factoring schemes, lattice schemes are most efficient when they allow decryption errors: even when everything is run correctly, a ciphertext may, with very small probability, decrypt wrongly. An error around $2^{-150}$ does not appear to hurt practical security, as long as the transformations' proofs account for it. §2, p. 5; footnote 5

The paper says

All operations are in the ring $(\mathbb{Z}_q, +, \times)$. $a \leftarrow S$ means $a$ is chosen uniformly from the set $S$. For a positive integer $\beta$,

$$[\beta] = \{-\beta, \ldots, -1, 0, 1, \ldots, \beta\}. \qquad (1)$$

$[\beta]^{n\times m}$ is an $n\times m$ matrix with coefficients in $[\beta]$; vectors are column vectors; $\mathbf{v} \in [\beta]^m$ can also be written $\|\mathbf{v}\|_\infty \le \beta$. $\lceil x \rfloor$ is the closest integer to $x$, with ties broken upwards. For polynomials $a = \sum a_i X^i$, $a \leftarrow [\beta]$ means every coefficient is uniform in $[\beta]$; a distribution $\psi$ can replace $[\beta]$. §2.1, Eq. (1)

The paper says

Pretend that for $n \ge m$ and $\beta \ll q$ the distributions $(\mathbf{A}, \mathbf{A}\mathbf{s})$ with $\mathbf{A} \leftarrow \mathbb{Z}_q^{n\times m}$, $\mathbf{s} \leftarrow [\beta]^m$, and $(\mathbf{A}, \mathbf{u})$ with $\mathbf{u} \leftarrow \mathbb{Z}_q^n$, are indistinguishable. This assumption is clearly false: Gaussian elimination inverts $\mathbf{A}$ (or an $m\times m$ sub-matrix) and checks whether some $\mathbf{s} \in [\beta]^m$ satisfies $\mathbf{A}\mathbf{s} = \mathbf{u}$. But it gives an ElGamal-like scheme: §2.2

$$\mathsf{sk}: \mathbf{s} \leftarrow [\beta]^m,\quad \mathsf{pk}: (\mathbf{A} \leftarrow \mathbb{Z}_q^{m\times m},\; \mathbf{t} = \mathbf{A}\mathbf{s}) \qquad (2)$$ $$(\mathbf{u}^T = \mathbf{r}^T\mathbf{A},\; v = \mathbf{r}^T\mathbf{t} + \mu), \quad \mathbf{r} \leftarrow [\beta]^m \qquad (3)$$ $$v - \mathbf{u}^T\mathbf{s} = \mathbf{r}^T\mathbf{A}\mathbf{s} + \mu - \mathbf{r}^T\mathbf{A}\mathbf{s} = \mu. \qquad (4),(5)$$

Security would follow from the assumption used twice: once for the public key, once (with $n$ and $m$ swapped) for $(\mathbf{A}', \mathbf{r}^T\mathbf{A}')$ with $\mathbf{A}' = [\mathbf{A} \mid \mathbf{t}]$. If $m \gg n$ the public key could be statistically uniform (§2.5.5), but the ciphertext would still need the assumption. §2.2, Eqs. (2)–(5)

The paper says

The error $\mathbf{e}$ is what makes Gaussian elimination inapplicable. The problem becomes harder as $m$ and $\beta/q$ grow; $n$ has no known large impact unless it is as large as about $m^{2\beta+1}$ (linearization [AG11]), so we often write $\mathsf{LWE}_{m,q,\beta}$. §2.3, Definition 1

Uniform errors are for illustration: Regev's worst-case reductions [Reg09, Pei09] used rounded Gaussians, but this is not strictly necessary [DM13, MP13], and Kyber uses a binomial distribution because it is faster to sample. Definition 2 ($\mathsf{LWE}_{n,m,q,\psi}$) replaces $[\beta]$ by any distribution $\psi$. Some parameters make LWE trivially hard but useless (if $n < m$ and $\beta$ is large, $(\mathbf{A}, \mathbf{A}\mathbf{s}+\mathbf{e})$ can be statistically close to uniform), and some make it easy (if $m = 1$ it is not difficult to see whether $\mathbf{A}\mathbf{s}+\mathbf{e}$ is close to a multiple of the vector $\mathbf{A}$). Taking $\mathbf{s}$ from the same distribution as $\mathbf{e}$ gives an essentially equally hard problem [ACPS09]. §2.3, Definition 2, p. 7

Distinguishing $(\mathbf{A}, \mathbf{s}^T\mathbf{A} + \mathbf{e}^T)$ is also LWE, with $n$ and $m$ interchanged; by a hybrid argument, many samples $\mathbf{A}\mathbf{s}_i + \mathbf{e}_i$ and $\mathbf{s}_j'^T\mathbf{A} + \mathbf{e}_j'^T$ are indistinguishable from uniform, losing a factor of at most $(t + t')$. §2.3, p. 8

The paper says

The message becomes a bit $\mu \in \{0,1\}$, and every product gets an error term:

$$\mathsf{sk}: \mathbf{s} \leftarrow [\beta]^m,\quad \mathsf{pk}: (\mathbf{A} \leftarrow \mathbb{Z}_q^{m\times m},\; \mathbf{t} = \mathbf{A}\mathbf{s} + \mathbf{e}_1),\; \mathbf{e}_1 \leftarrow [\beta]^m \qquad (6)$$ $$\Bigl(\mathbf{u}^T = \mathbf{r}^T\mathbf{A} + \mathbf{e}_2^T,\;\; v = \mathbf{r}^T\mathbf{t} + e_3 + \bigl\lceil \tfrac q2 \bigr\rfloor \mu\Bigr),\quad \mathbf{r}, \mathbf{e}_2 \leftarrow [\beta]^m,\; e_3 \leftarrow [\beta] \qquad (7)$$

$\lceil q/2 \rfloor$ is the element of $\mathbb{Z}_q$ closest to the rational $q/2$ (e.g. if $q = 13$, then $\lceil q/2 \rfloor = 7$). Security: $(\mathbf{A}, \mathbf{t})$ is indistinguishable from uniform by $\mathsf{LWE}_{m,q,\beta}$; then, with $\mathbf{A}' = [\mathbf{A} \mid \mathbf{t}]$, so is $(\mathbf{A}', \mathbf{r}^T\mathbf{A}' + [\mathbf{e}_2^T \mid e_3])$. LWE is used twice, with $m$ as the number of columns and then as the number of rows. §2.3.1, Eqs. (6)–(7)

$$v - \mathbf{u}^T\mathbf{s} = \mathbf{r}^T\mathbf{e}_1 + e_3 + \tfrac q2\mu - \mathbf{e}_2^T\mathbf{s} \qquad (8),(9)$$

The error terms have coefficients bounded by $\pm\beta$, so $\mathbf{r}^T\mathbf{e}_1$ and $\mathbf{e}_2^T\mathbf{s}$ each consist of $m$ terms of magnitude at most $\beta^2$: the error lies in $[2m\beta^2 + \beta]$. If $2m\beta^2 + \beta < q/4$, the decryptor recovers $\mu$ by checking whether $v - \mathbf{u}^T\mathbf{s}$ is closer to $0$ or to $q/2$. §2.3.1, p. 9

The paper says

$2m\beta^2 + \beta$ is an upper bound, but the coefficients are random and centred, so the error is closer to $O(\sqrt m\,\beta^2)$. We want a bound that holds with very high probability (say $1 - 2^{-150}$), and for concrete parameters we can compute exactly §2.3.2

$$\Pr_{\mathbf{s},\mathbf{r},\mathbf{e}_1,\mathbf{e}_2 \leftarrow [\beta]^m,\, e_3 \leftarrow [\beta]}\bigl[\mathbf{r}^T\mathbf{e}_1 + e_3 - \mathbf{e}_2^T\mathbf{s} \in [\alpha]\bigr] \qquad (10)$$

using the fact that distributions of sums of independent random variables are products of polynomials: with $A(X) = \sum A_i X^i$, $B(X) = \sum B_i X^i$ and $C(X) = A(X)B(X) = \sum C_i X^i$,

$$\Pr[A + B = i] = C_i, \qquad \Pr[A+B \in [\alpha]] = \sum_{i=-\alpha}^{\alpha} C_i. \qquad (11),(12)$$

$\mathbf{r}^T\mathbf{e}_1 - \mathbf{e}_2^T\mathbf{s}$ is a sum of $2m$ independent variables with $A_i = \Pr_{x,y \leftarrow [\beta]}[xy = i]$, and $e_3$ is uniform over $[\beta]$. For $\beta = 2$: $A_{\pm4} = \frac{2}{25}$, $A_{\pm2} = \frac{4}{25}$, $A_{\pm1} = \frac{2}{25}$, $A_0 = \frac{9}{25}$. Setting $\alpha = q/4 - 1$ gives the exact probability of correct decryption. §2.3.2, pp. 9–10

The paper says

$\mathbf{A}$ is uniform, so it can be expanded from a 256-bit seed $\rho$ by a PRF (e.g. SHAKE); the public key costs $256 + m\log q$ bits. The ciphertext $(\mathbf{u}, v)$ costs $(m+1)\log q$ bits; secure parameters need $m \approx 700$ and $q \approx 2^{13}$, which is a lot for one bit. To amortize [PVW08, MR09, BCD⁺16], encrypt $N = k\ell$ bits arranged in $\mathbf{M} \in \{0,1\}^{k\times\ell}$: §2.4

$$\mathsf{sk}: \mathbf{S} \leftarrow [\beta]^{m\times\ell},\quad \mathsf{pk}: (\mathbf{A} \leftarrow \mathbb{Z}_q^{m\times m},\; \mathbf{T} = \mathbf{A}\mathbf{S} + \mathbf{E}_1) \qquad (13)$$ $$\Bigl(\mathbf{U} = \mathbf{R}\mathbf{A} + \mathbf{E}_2,\;\; \mathbf{V} = \mathbf{R}\mathbf{T} + \mathbf{E}_3 + \tfrac q2\mathbf{M}\Bigr) \qquad (14)$$

The public key grows to $256 + \ell m\log q$ bits; the ciphertext is $km\log q + k\ell\log q$ bits. For the minimum combined size set $k \approx \ell \approx \sqrt N$: about $256 + 2\sqrt N m\log q + N\log q$ bits, dominated by $2\sqrt N m\log q$ (one rarely needs more than $N = 256$). Security follows from $\mathsf{LWE}_{m,q,\beta}$ with a hybrid argument, losing $\log\ell$ bits (footnote 7: it is not clear in this case whether the loss is real). Each coefficient of $\mathbf{V} - \mathbf{U}\mathbf{S} = \mathbf{R}\mathbf{E}_1 + \mathbf{E}_3 + \frac q2\mathbf{M} - \mathbf{E}_2\mathbf{S}$ has exactly the single-bit noise (Eqs. (16)–(17)); a union bound over coefficients gives the total error (footnote 8). §2.4, Eqs. (13)–(17)

The paper says

The scheme above is a general framework; when instantiating it there are several optimizations. It is not easy to know which to use and how to set parameters optimally without actually trying some possibilities. §2.5

The paper says

Send only $\kappa$ bits per coefficient of $\mathbf{V}$. Pick $\mathcal{S} \subset \mathbb{Z}_q$ of size $2^\kappa$ with neighbouring points as evenly spaced as possible ($q/2^\kappa$ is the best one can hope for): §2.5.1

$$\mathcal{S} = \bigl\{\lceil i\cdot q/2^\kappa \rfloor : 0 \le i < 2^\kappa\bigr\}. \qquad (18)$$

Every $v \in \mathbb{Z}_q$ is within $\lceil q/2^{\kappa+1}\rceil$ of $\mathcal{S}$. $\mathrm{HIGH}_\mathcal{S}(v)$ is the closest element of $\mathcal{S}$ and $\mathrm{LOW}_\mathcal{S}(v) = v - \mathrm{HIGH}_\mathcal{S}(v)$. Sending $\mathbf{V}' = \mathrm{HIGH}_\mathcal{S}(\mathbf{V})$ adds one term $\mathbf{E}' = \mathrm{LOW}_\mathcal{S}(\mathbf{V})$:

$$\mathbf{V}' - \mathbf{U}\mathbf{S} = \mathbf{R}\mathbf{E}_1 + \mathbf{E}_3 - \mathbf{E}' + \tfrac q2\mathbf{M} - \mathbf{E}_2\mathbf{S}. \qquad (19)$$

$\mathbf{E}'$ has limited effect because the other terms are inner products with much larger coefficients; $\kappa$ can usually be 3 or 4. Compressing $\mathbf{U}$ is harder: its error is multiplied by $\mathbf{S}$ (a term $\mathbf{E}''\mathbf{S}$), so one balances error against size by trial and error. §2.5.1, Figure 1, Eq. (19)

The paper says

With $2^\kappa = p$, $\mathcal{S} = \{\lceil x\rfloor_{p\to q} : x \in \mathbb{Z}_p\}$, $\mathrm{HIGH}_\mathcal{S}(x) = \lceil\lceil x\rfloor_{q\to p}\rfloor_{p\to q}$, Lemma 1 proves $\mathrm{LOW}_\mathcal{S}(x) \in [\lceil q/2p\rceil]$. One transmits $\lceil x\rfloor_{q\to p} \in \mathbb{Z}_p$, not $\mathrm{HIGH}_\mathcal{S}(x)$. Decryption itself is compression to one bit: $\mu = \lceil v - \mathbf{u}^T\mathbf{s}\rfloor_{q\to2}$ (20). Other $\mathcal{S}$ can be equally good, e.g. $p = 4$, $q = 33$, $\mathcal{S} = \{0, 8, 16, 24\}$, needing only reductions and divisions mod 8. Kyber ($q$ small) uses the generic $\mathcal{S}$; Dilithium ($q$ larger) gets a nice $\mathcal{S}$ and fast multiplication. §2.5.2, Definition 3, Lemma 1, Eq. (20)

The paper says

By LWE, $(\mathbf{A}, \mathrm{HIGH}_\mathcal{S}(\mathbf{A}\mathbf{s} + \mathbf{e}))$ is indistinguishable from $(\mathbf{A}, \mathrm{HIGH}_\mathcal{S}(\mathbf{u}))$. But $\mathbf{e}$ may not change the rounded value at all: $\mathrm{HIGH}_\mathcal{S}(\mathbf{A}\mathbf{s}+\mathbf{e}) = \mathrm{HIGH}_\mathcal{S}(\mathbf{A}\mathbf{s})$ with probability about $\bigl(1 - \frac{\beta|\mathcal{S}|}{2q}\bigr)^n$, because a coefficient changes only if $\mathbf{A}\mathbf{s}$ is within $\beta$ of a midpoint; per coefficient

$$\frac{2|\mathcal{S}|}{q}\sum_{i=1}^{\beta}\frac{i}{2\beta+1} \approx \frac{\beta|\mathcal{S}|}{2q}.$$

Distinguishing $(\mathbf{A}, \mathrm{HIGH}_\mathcal{S}(\mathbf{A}\mathbf{s}))$ from $(\mathbf{A}, \mathrm{HIGH}_\mathcal{S}(\mathbf{u}))$ is the Learning with Rounding (LWR) problem, at least as hard as LWE whenever adding $\mathbf{e}$ does not affect the rounded output [BPR12, AKPW13, BGM⁺16]. It is sometimes used even when $q$ is too small for a reduction, as a separate assumption. The best attacks treat it as LWE with implicit noise $\mathbf{e} = -\mathrm{LOW}_\mathcal{S}(\mathbf{A}\mathbf{s})$, which is larger than the reduction's noise. Under LWR, rounding does two jobs: in (19), $\mathbf{E}'$ may make $\mathbf{E}_3$ unnecessary, and rounding $\mathbf{U}$ may make $\mathbf{E}_2$ unnecessary. §2.5.3, pp. 14–15

The paper says

Pack the $N$ bits into $\mathbf{M} \in \{0, \ldots, 2^b-1\}^{(k/\sqrt b)\times(\ell/\sqrt b)}$ and use $\frac{q}{2^b}\mathbf{M}$ instead of $\frac q2\mathbf{M}$. The other error terms in (17) must then lie in $[q/2^{b+1}]$ instead of $[q/4]$. The trivial fix is to increase $q$ by about $2^{b-1}$. That can still shrink the public key: if $\ell$ halves, $256 + \ell m\log q$ becomes $256 + \frac{\ell m}{2}(\log q + b - 1)$, smaller if $b - 1 < \log q$. But a larger $q$ with everything else fixed lowers security (the problem gets harder as $\beta/q$ grows), so one must increase $\beta$ or $m$ — best found by a script. §2.5.4

The paper says

The leftover hash lemma [IZ89, IN96], roughly: if $\mathbf{A} \leftarrow \mathbb{Z}_q^{n\times m}$ ($q$ prime), $\mathbf{s} \leftarrow [\beta]^m$ and $(2\beta+1)^m \gg q^n$, then $(\mathbf{A}, \mathbf{A}\mathbf{s})$ is statistically close to $(\mathbf{A}, \mathbf{u})$. For a uniform public key, replace (13) by

$$\mathsf{sk}: \mathbf{S} \leftarrow [\beta']^{m\times\ell},\quad \mathsf{pk}: (\mathbf{A} \leftarrow \mathbb{Z}_q^{n\times m},\; \mathbf{T} = \mathbf{A}\mathbf{S}),\quad (2\beta'+1)^m > q^n. \qquad (21)$$

LWE is not used twice any more, so $\beta'$ need not equal $\beta$. Encryption and decryption stay as in (14) and (17), but $\mathbf{E}_2\mathbf{S}$ grows (larger $m$ and/or $\beta'$) and $\mathbf{R}\mathbf{E}_1 = 0$. A uniform ciphertext works the same way: choose $\mathbf{A}$'s dimension and $\mathbf{R}$'s distribution so that $([\mathbf{A}\mid\mathbf{T}], \mathbf{R}[\mathbf{A}\mid\mathbf{T}])$ is indistinguishable from $([\mathbf{A}\mid\mathbf{T}], [\mathbf{U}\mid\mathbf{V}])$. Applications: identity-based encryption [GPV08], where $\mathbf{t}_x = \mathcal{H}(x)$ is uniform and a trapdoor lets the authority find a short $\mathbf{s}_x$ with $\mathbf{A}\mathbf{s}_x = \mathbf{t}_x$ (the secret key is created after the public key); and leakage of $\mathbf{r}$ [AGV09]. §2.5.5, Eq. (21)

The paper says

Take $\mathbf{r}, \mathbf{s} \leftarrow \psi_1$ and $\mathbf{e}_1, \mathbf{e}_2 \leftarrow \psi_2$ [ZYF⁺20]. Against the best known algorithms, hardness depends on the norm of $(\mathbf{s}, \mathbf{e}_1)$ (§3.3), while decryption wants $\mathbf{r}^T\mathbf{e}_1 + \mathbf{e}_2^T\mathbf{s}$ (22) small. With normal distributions ($\|\mathbf{v}\| \approx \sigma\sqrt n$ for $\mathbf{v} \leftarrow \mathcal{N}_\sigma^n$; $\langle\mathbf{s},\mathbf{v}\rangle \sim \mathcal{N}_{\sigma\|\mathbf{v}\|}$), $\mathbf{s},\mathbf{r} \leftarrow \mathcal{N}_{\sigma_1}$ and $\mathbf{e}_1, \mathbf{e}_2 \leftarrow \mathcal{N}_{\sigma_2}$ give (22) $\sim \mathcal{N}_{\sigma_1\sigma_2\sqrt{2n}}$ and $\|(\mathbf{s},\mathbf{e}_1)\| \approx \sqrt{\sigma_1^2+\sigma_2^2}\sqrt n$. §2.5.6, Eqs. (22)–(24)

$$\sigma_1 = \sigma_2 = \sigma:\;\; \|(\mathbf{s},\mathbf{e}_1)\| \approx \sigma\sqrt{2n},\; (22) \sim \mathcal{N}_{\sigma^2\sqrt{2n}} \qquad (23)$$ $$\sigma_1 = \tfrac43\sigma,\; \sigma_2 = \tfrac{\sqrt2}{3}\sigma:\;\; \|(\mathbf{s},\mathbf{e}_1)\| \approx \sigma\sqrt{2n},\; (22) \sim \mathcal{N}_{\frac{4\sqrt2}{9}\sigma^2\sqrt{2n}} \qquad (24)$$

Same norms, smaller decryption noise. Whether to do this depends on believing the two LWE problems (Definition 2 and the one with different distributions) are equally hard. §2.5.6

The paper says

Encryption gives a passively-secure key transport: party 1 sends a public key (13), party 2 encrypts an AES key as $\mathbf{M}$ (14). But party 2 must wait for party 1; in Diffie–Hellman either party can send $g^{x_i}$ first. An LWE protocol with that property exists but is much less efficient. For one shared bit: public random $\mathbf{A} \in \mathbb{Z}_q^{m\times m}$ trusted by everyone (e.g. expanded by SHAKE from seed 0); party $i$ picks $\mathbf{s}_i, \mathbf{e}_i \leftarrow [\beta]^m$; party 1 sends $\mathbf{u}_1^T = \mathbf{s}_1^T\mathbf{A} + \mathbf{e}_1^T$, party 2 sends $\mathbf{u}_2 = \mathbf{A}\mathbf{s}_2 + \mathbf{e}_2$. Each sets its bit to 1 if its value is between $q/4$ and $3q/4$: §2.6

$$\mathbf{s}_1^T\mathbf{u}_2 = \mathbf{s}_1^T\mathbf{A}\mathbf{s}_2 + \mathbf{s}_1^T\mathbf{e}_2, \qquad \mathbf{u}_1^T\mathbf{s}_2 = \mathbf{s}_1^T\mathbf{A}\mathbf{s}_2 + \mathbf{e}_1^T\mathbf{s}_2. \qquad (25),(26)$$

The errors have magnitude at most $m\beta^2$, so $b_1 \ne b_2$ only if $\mathbf{s}_1^T\mathbf{A}\mathbf{s}_2$ falls within $m\beta^2$ of $q/4$ or $3q/4$ (27). That value is uniform, so the probability is at most $4m\beta^2/q$. The techniques of §2.3.2 still leave $\Omega(\beta^2\sqrt m/q)$ — unlike encryption, where the error can be made exponentially small. A negligible mismatch needs a very large $q$ [GdKQ⁺24], and this may be intrinsic to using LWE in the natural way [GKRS22]. §2.6, Eqs. (25)–(27)

The paper says

Section 3 gives a geometric view of the LWE problem. The connection is not really necessary for understanding how most cryptographic constructions work, but it is crucial for understanding their security. §3, p. 19

The paper says

An $m$-dimensional integer lattice $\Lambda$ is a subgroup of $(\mathbb{Z}^m, +)$. It can be described by a (full-rank) basis $\mathbf{B} \in \mathbb{Z}^{m\times m}$: $$\Lambda = \mathcal{L}(\mathbf{B}) = \{\mathbf{v} \in \mathbb{Z}^m : \exists\, \mathbf{z} \in \mathbb{Z}^m \text{ s.t. } \mathbf{B}\mathbf{z} = \mathbf{v}\}. \qquad (28)$$ The paper restricts to $q$-ary lattices, which are the ones used in cryptography and which, asymptotically, make solving random instances as hard as solving some problem on any lattice (the worst-case to average-case line of work [Ajt96, Reg09]). For $\mathbf{A} \in \mathbb{Z}_q^{n\times m}$: $$\Lambda = \mathcal{L}_q^\perp(\mathbf{A}) = \{\mathbf{v} \in \mathbb{Z}^m : \mathbf{A}\mathbf{v} \equiv \mathbf{0} \pmod q\}. \qquad (29)$$ The two definitions are like describing a linear code by a generating matrix (28) or a parity-check matrix (29). The lattices used from now on are $$\Lambda = \mathcal{L}_q^\perp([\mathbf{A} \mid \mathbf{I}_n]), \qquad (30)$$ which is "not much of a restriction": if $\mathbf{A} = [\mathbf{A}_1 \mid \mathbf{A}_2]$ with $\mathbf{A}_2 \in \mathbb{Z}_q^{n\times n}$ invertible, then $\mathcal{L}_q^\perp(\mathbf{A}) = \mathcal{L}_q^\perp(\mathbf{A}_2^{-1}\mathbf{A}) = \mathcal{L}_q^\perp([\mathbf{A}_2^{-1}\mathbf{A}_1 \mid \mathbf{I}])$. For such lattices it is easy to switch between the two representations: $$\mathcal{L}_q^\perp([\mathbf{A} \mid \mathbf{I}_n]) = \mathcal{L}\left(\begin{bmatrix}-\mathbf{I}_m & \mathbf{0}\\ \mathbf{A} & q\mathbf{I}_n\end{bmatrix}\right). \qquad (31)$$ §3.1, Eqs. (28)–(32), p. 19

The paper says

The determinant of a full-rank lattice $\Lambda \subseteq \mathbb{Z}^m$ is the inverse of its density: with $S_r = \{\mathbf{z} \in \mathbb{Z}^m : \|\mathbf{z}\| < r\}$, $$\det(\Lambda) = \lim_{r\to\infty}\frac{|S_r|}{|\Lambda \cap S_r|}.$$ If $\Lambda = \mathcal{L}(\mathbf{B})$ for a full-rank $\mathbf{B} \in \mathbb{Z}^{m\times m}$, then $\det(\Lambda) = |\det(\mathbf{B})|$; for the $(n+m)$-dimensional lattice in (31) this is $q^n$. Equivalently, $\det(\Lambda)$ is the size of the quotient group $\mathbb{Z}^m/\Lambda$. The parity-check form makes cosets easy to test: for $\Lambda = \mathcal{L}_q^\perp(\mathbf{A})$, $\mathbf{z}_1, \mathbf{z}_2$ are in the same coset iff $\mathbf{A}\mathbf{z}_1 \equiv \mathbf{A}\mathbf{z}_2 \pmod q$; for $\Lambda = \mathcal{L}_q^\perp([\mathbf{A} \mid \mathbf{I}_n])$ there are exactly $q^n$ cosets, consistent with $\det = q^n$. §3.1.1, pp. 19–20

The paper says

For an $m$-dimensional lattice and any $\mathbf{r} \in \mathbb{Z}^m$, the $\ell_p$ distance to the lattice is $$\Delta_p(\mathbf{r}, \Lambda) = \min_{\mathbf{v}\in\Lambda}\|\mathbf{v} - \mathbf{r}\|_p. \qquad (33)$$ All members of a coset have the same distance, so for $\Lambda = \mathcal{L}_q^\perp(\mathbf{A})$ and $\mathbf{t} \equiv \mathbf{A}\mathbf{z} \pmod q$ one writes $\Delta_p^C(\mathbf{t}, \Lambda) = \Delta_p(\mathbf{z}, \Lambda)$. The lemmas below are proved for prime $q$ only, for simplicity ("with more care, one can prove similar statements for all $q$"). §3.1.2, p. 20

The boundary is sharp: at $\beta = q^{n/(n+m)}$ a vector with coefficients in $[\beta]$ always exists (Lemma 4), while for $\beta < \tfrac14 q^{n/(n+m)}$ the probability that one exists is less than $2^{-(n+m)}$ (Lemma 3). §3.1.2, p. 21

The paper says

Lemma 4 guarantees a non-zero $\mathbf{z} \in [q^{n/(n+m)}]^{n+m}$ with $[\mathbf{A} \mid \mathbf{I}_n]\mathbf{z} \equiv \mathbf{0}$, but all known (quantum) algorithms for finding such vectors for uniformly random $\mathbf{A}$ take $2^{\Omega(m+n)}$ time [AKS01, ADRS15, AS18]. The problem gets easier as $\beta$ grows; at $\beta = q/2$ it is trivial (set the coefficients multiplied by $\mathbf{I}_n$ to the target). All modern (i.e. polynomial-time) algorithms are descendants of LLL [LLL82], which guarantees a vector at most $2^{O(n+m)}$ times longer than the shortest; in practice the factor is exponential but with a small base. Experiments [GN08, MR09] show that one can find non-trivial vectors of length approximately $$\det(\Lambda)^{1/(n+m)}\cdot\delta^{n+m} = q^{n/(n+m)}\cdot\delta^{n+m}, \qquad (34)$$ where $\delta$ depends on the running time. "As a very rough rule of thumb, $\delta = 1.01$ is considered within reach, whereas $\delta = 1.005$ may never be achieved for lattices of high-enough dimension (e.g. more than 500)." Since one may drop columns of $\mathbf{A}$, it is optimal to use a lattice of dimension $$\sqrt{n\log q/\log\delta}, \qquad (35)$$ which yields a found vector of $\ell_2$-norm $$2^{2\sqrt{n\log q\log\delta}}. \qquad (36)$$ §3.2, Eqs. (34)–(36), pp. 21–22

By Lemma 3, SIS is vacuously hard when $\beta \ll \frac12 q^{n/(n+m)}$, and by (36) it gets easier as $\beta$ grows. Once $m > \sqrt{n\log q/\log\delta}$, $m$ has no impact on hardness, so one writes $\mathrm{SIS}_{n,q,\beta}$. SIS is defined in the $\ell_\infty$ norm (natural for Dilithium, which avoids complicated operations; all its sampling is uniform, footnote 11), while (36) is an $\ell_2$ norm: finding a vector of $\ell_\infty$ norm $\beta$ requires at least finding one of $\ell_2$ norm (36) multiplied by the square root of the dimension. Footnote 10: [MR09] only state the bound when the found vector is shorter than $q$. §3.2, p. 22

The paper says

Outputting $(\mathbf{A}, \mathbf{t} = \mathbf{A}\mathbf{s} + \mathbf{e})$ with $\mathbf{s} \leftarrow [\beta]^m$, $\mathbf{e} \leftarrow [\beta]^n$ is the same as outputting a lattice $\Lambda = \mathcal{L}_q^\perp([\mathbf{A} \mid \mathbf{I}_n])$ and a coset $\mathbf{t}$ with $\Delta^C_\infty(\mathbf{t}, \Lambda) \le \beta$; a uniform $\mathbf{u}$ is a random coset. So $\mathrm{LWE}_{n,m,q,\beta}$ is distinguishing cosets close to the lattice from random cosets. The encryption scheme had $m = n$ and needed $\beta^2 = O(q/\sqrt m)$ for correctness, so $\beta \ll \sqrt q$; by Corollary 1 random cosets are then further than $\beta$ from the lattice.

To distinguish, find short $\mathbf{r}_1, \mathbf{r}_2$ with $$\mathbf{r}_1^T\mathbf{A} + \mathbf{r}_2^T = \mathbf{0}. \qquad (37)$$ If $\mathbf{t}$ is uniform, $\mathbf{r}_1^T\mathbf{t}$ is random in $\mathbb{Z}_q$; if $\mathbf{t} = \mathbf{A}\mathbf{s} + \mathbf{e}$, $$\mathbf{r}_1^T\mathbf{t} = \mathbf{r}_1^T\mathbf{A}\mathbf{s} + \mathbf{r}_1^T\mathbf{e} = -\mathbf{r}_2^T\mathbf{s} + \mathbf{r}_1^T\mathbf{e}, \qquad (38)$$ which is small. Finding $\mathbf{r}_1, \mathbf{r}_2$ is finding a short vector in $\mathcal{L}_q^\perp([\mathbf{A}^T \mid \mathbf{I}_m])$; by (36) (with $n$ replaced by $m$, because $\mathbf{A}^T$ is used) its norm is about $2^{2\sqrt{m\log q\log\delta}}$. A coefficient uniform in $[\beta]$ has variance $$\frac{1}{2\beta+1}\sum_{i=-\beta}^{\beta} i^2 = \frac{\beta(\beta+1)}{3}, \qquad (39)$$ and, treating coefficients as normal (justified asymptotically by the CLT, "already a very good approximation"), $-\mathbf{r}_2^T\mathbf{s} + \mathbf{r}_1^T\mathbf{e}$ is normal with standard deviation $$\|(\mathbf{r}_1, \mathbf{r}_2)\|\cdot\sqrt{\tfrac{\beta(\beta+1)}{3}} \approx 2^{2\sqrt{m\log q\log\delta}}\cdot\sqrt{\tfrac{\beta(\beta+1)}{3}}. \qquad (40)$$ A normal variable with standard deviation greater than $\sqrt3\cdot q$, reduced mod $q$, is within $\approx 2^{-80}$ of uniform [MR07]. So $\mathrm{LWE}_{n,m,q,\beta}$ is secure "at least against this attack, which seems to be as good as any other known approach" whenever $$\sqrt{\beta(\beta+1)} > 3\cdot q\cdot 2^{-2\sqrt{m\log q\log\delta}}. \qquad (41)$$ §3.3, Eqs. (37)–(41), pp. 23–24

The paper says

Table 1 lists sample $\mathrm{LWE}_{m,q,\beta}$ parameters similar to those used in Kyber (ML-KEM, §4.7); the signature scheme of §5 depends on both SIS and LWE, and Table 2 gives parameters resembling Dilithium (ML-DSA). The tables are set from the best currently-known lattice-reduction algorithms (cf. the Lattice Estimator [APS15]). §3.4, Tables 1–2, pp. 24–25

Looking at Figure 2, LWE hardness increases monotonically in $\beta$, without jumps: if $q/\beta = 2^{m/k}$ with $1 \le k \le m$, the best known algorithm takes time about $2^k$ (ignoring polynomial factors). But a sudden jump is not out of the realm of possibility: it is exactly what happens for short vectors in lattices corresponding to an ideal of some algebraic ring [CGS14, BS16, CDPR16, CDW17]. When $q/\beta > 2^{\sqrt m}$ (i.e. $k < \sqrt m$) that problem can be solved in quantum polynomial time, but as soon as $k > \sqrt m$ the hardness jumps back to $2^k$. Some not-yet-invented (quantum) algorithm might do much better on a particular range of $q/\beta$, so "it may therefore be prudent" to build cryptography on LWE with $q/\beta$ as small as possible. §3.4, pp. 24–25

The paper says

The LWE scheme of Section 2.3 needs a ciphertext of $(m+1)\log q$ bits for one message bit: its expansion is linear in the security parameter. The scheme of Section 2.4 reduced this to a square-root expansion, at the price of blowing up the public key by the same factor. Section 4 removes the square-root blow-up by doing LWE not over $\mathbb{Z}_q$ but over higher-degree polynomial rings. §4, p. 26

The paper says

$\mathbb{Z}[X]$ is the ring of polynomials $a = \sum_i a_i X^i$ with integer coefficients. $\deg(a)$ is the largest $i$ with $a_i \neq 0$; $a$ is monic if $a_{\deg(a)} = 1$; $a$ is irreducible if it cannot be written as $a = bc$ with $\deg(b), \deg(c) < \deg(a)$. §4.1

For a monic $f \in \mathbb{Z}[X]$ of degree $d$, the ring $\mathcal{R}_f$ (often written $\mathbb{Z}[X]/(f(X))$, footnote 12) consists of the polynomials $a = \sum_{i=0}^{d-1} a_i X^i$. Addition is coefficient-wise, so $\mathcal{R}_f$ under addition is $\mathbb{Z}^d$. Multiplication is ordinary multiplication followed by reduction modulo $f$: every $a$ can be written uniquely as $a = bf + r$ with $\deg(r) < d$, and $a \bmod f = r$. The usual $\mathbb{Z}$ is the special case $f = X$ (or $f = X - \alpha$). §4.1, p. 26–27

The paper says

Multiplication modulo $f$ is a matrix times a vector (Eq. (42)): $$ab \bmod f = a\cdot\Big(\sum_{i=0}^{d-1} b_iX^i\Big) \bmod f = \sum_{i=0}^{d-1}(aX^i \bmod f)\,b_i.$$ With $\mathcal{V}_a = (a_0,\dots,a_{d-1})^T \in \mathbb{Z}^d$ and $\mathcal{M}_a = [\,\mathcal{V}_a \;\; \mathcal{V}_{aX \bmod f} \;\cdots\; \mathcal{V}_{aX^{d-1} \bmod f}\,] \in \mathbb{Z}^{d\times d}$ (Eq. (44)) we get $\mathcal{M}_a\mathcal{V}_b = \mathcal{V}_{ab}$. For $\mathbf{A} \in \mathcal{R}_f^{n\times m}$ and $\mathbf{b} \in \mathcal{R}_f^m$, stacking blocks gives $\mathcal{M}_\mathbf{A}\cdot\mathcal{V}_\mathbf{b} = \mathcal{V}_{\mathbf{A}\mathbf{b}} \in \mathbb{Z}^{dn}$ (Eqs. (45)–(46)). Example (Eq. (43)): $(2X^2-1)(X^2-X+2) \bmod X^3-X+1 = 5X^2 - 3X$. §4.1.1, Eqs. (42)–(46)

The paper says

Since $ab = \mathcal{M}_a\mathcal{V}_b$, a simple bound on the largest coefficient is $d\,\|\mathcal{M}_a\|_\infty\cdot\|\mathcal{V}_b\|_\infty$ (better $\ell_2$ bounds use the largest singular value of $\mathcal{M}_a$). The best we could hope for is $\|\mathcal{M}_a\|_\infty = \|\mathcal{V}_a\|_\infty$; the only $f$ with this property are $X^d \pm 1$. For $X^d \pm X^{d/2} + 1$ and $\sum_{i=0}^{d} X^i$, $\|\mathcal{M}_a\|_\infty \le 2\|\mathcal{V}_a\|_\infty$ (Eqs. (47)–(50) show $d = 4$). Some $f$ with small coefficients, e.g. $X^d + 2X^{d-1} + 1$, give $\mathcal{M}_a$ with exponentially larger coefficients than $a$; such $f$ are not useful for cryptography. We prefer a ratio of 1 or 2. §4.1.2, p. 28

The paper says

$\mathcal{R}_{q,f}$ is like $\mathcal{R}_f$ but with coefficients in $\mathbb{Z}_q$ (written $\mathbb{Z}_q[X]/(f(X))$ in the literature). §4.2

As before, $n$ has no known effect on hardness unless it is large, so one writes $\mathcal{R}_{q,f}$-$\mathsf{LWE}_{m,\beta}$. The definition and the cryptosystem follow [LPR10, BV11, LPR13b, LS15]; SIS is generalized following [PR06, LM06, LS15]. In the literature these are called Ring-LWE / Ring-SIS or Module-LWE / Module-SIS; in ML-KEM and ML-DSA, "ML" stands for "Module Lattice". §4.2, Definitions 5–6

The paper says

The scheme is virtually identical to Section 2.3.1 with $\mathbb{Z}$ replaced by $\mathcal{R}_f$; its main advantage is that $\mu \in \mathcal{R}_f$ packs $d$ bits. §4.3, Eqs. (51)–(55)

Security based on $\mathcal{R}_{q,f}$-$\mathsf{LWE}_{m,\beta}$ is identical to the proof for $\mathsf{LWE}_{m,q,\beta}$. The decryption noise is $\mathcal{M}_{\mathbf{r}^T}\mathcal{V}_{\mathbf{e}_1} + \mathcal{V}_{e_3} - \mathcal{M}_{\mathbf{e}_2^T}\mathcal{V}_\mathbf{s}$ (55), handled with the techniques of Section 2.3.2. For $f = X^d \pm 1$ each coefficient is computed exactly as over the integers, because each row of $\mathcal{M}_{\mathbf{r}^T}$ and $\mathcal{M}_{\mathbf{e}_2^T}$ has independent coefficients (see (47) and (48)); a union bound over the $d$ coefficients finishes. For other $f$ the technique still applies if the product can be rewritten as a sum of independent random variables.

The paper says

One no longer needs to enlarge the public key (as in Section 2.4) to encrypt a longer message: a degree-$d$ ring carries $d$ bits, so with $d \ge 256$ — the length of an AES key — the public key is optimally small. There is no need to pack several bits per coefficient (Section 2.5.4). The compression of Section 2.5.1 still applies, and LWR (2.5.3) and the NIKE (2.6) are defined analogously over $\mathcal{R}_f$. §4.3.1

The paper says

By (46), distinguishing $(\mathbf{A}, \mathbf{t} = \mathbf{A}\mathbf{s} + \mathbf{e})$ from uniform over $\mathcal{R}_{q,f}$ is distinguishing $(\mathcal{M}_\mathbf{A}, \mathcal{V}_\mathbf{t} = \mathcal{M}_\mathbf{A}\mathcal{V}_\mathbf{s} + \mathcal{V}_\mathbf{e})$ from $(\mathcal{M}_\mathbf{A}, \mathcal{V}_\mathbf{u})$ — a problem over $\mathbb{Z}_q$, attacked (as in Section 3.3, lattice (56) $\mathcal{L}_q^\perp([\mathbf{A}^T \mid \mathbf{I}_m])$) by finding short vectors in $\mathcal{L}_q^\perp([\mathcal{M}_\mathbf{A}^T \mid \mathbf{I}_{dm}])$, a lattice of dimension $d(m+n)$. If $\mathcal{R}_f$'s algebraic structure has no weaknesses (Section 4.5), this is as hard as the $\mathsf{LWE}_{n',m',q,\beta}$ lattice with $n' = dn$, $m' = dm$. So for $\mathcal{R}_{q,f}$-$\mathsf{LWE}_{n,m,\beta}$ the important value is $dm$ (degree of $f$ × columns of $\mathbf{A}$); for $\mathcal{R}_{q,f}$-$\mathsf{SIS}_{n,m,\beta}$ it is $dn$ (degree × rows). §4.3.2, Eq. (56)

The paper says

NTRU [HPS98] was the first truly efficient lattice-based encryption scheme and the first to use polynomial rings — specifically $\mathcal{R}_{q,X^d-1}$. It was proposed as a trapdoor one-way function, which can be seen as a OW-CPA cryptosystem (footnote 13: an attacker holding the public key cannot recover the message of a ciphertext of a randomly chosen message). A simple modification gives CPA security [SS11], but usually the one-way function suffices, since there are black-box transformations to CCA-secure encryption (cf. [Den02]). §4.4, p. 30

The paper says

Search Generalized-LWE: given $(a, as + e)$ with $a \leftarrow \mathcal{R}_{q,f}$, $s, e \leftarrow [\beta]$, find $e$ (if $a$ is invertible this also gives $s$). NTRU is the same problem (with $n = m = 1$) except $a = pg_1g_2^{-1}$ for small $g_1, g_2 \leftarrow [\beta]$ and $p = 2\beta + 1$ relatively prime to $q$ ($\beta = 1$ is popular). §4.4.1

Trapdoor function: public key $a = pg_1g_2^{-1}$ (57), secret key $g_2$; evaluate $b = as + e \in \mathcal{R}_{q,f}$ (58); invert via $g_2b \bmod p = pg_1s + g_2e \bmod p = g_2e \bmod p$ (59), then $(g_2b \bmod p)g_2^{-1} \bmod p = e$ (60) and $(b - e)a^{-1} = s$ (61). It suffices to recover $s, e$ modulo $p$, since elements of $[\beta]$ and residues mod $p = 2\beta+1$ correspond one-to-one. The paper urges first-time readers to appreciate that (59) holds despite using two relatively prime moduli, "which is very rarely an idea that leads to any meaningful results". §4.4.1, Eqs. (57)–(61)

The paper says

Ignoring the special form of $a$, recovering $s, e$ from (58) is the Generalized-LWE key attack: a short vector in $\mathcal{L}_q^\perp([\mathcal{M}_a \mid \mathcal{V}_b \mid \mathbf{I}_d])$ (62). One can also try to recover $g_1, g_2$ (or related short polynomials) from $a$ via $\mathcal{L}_q^\perp([\mathcal{M}_{p^{-1}a} \mid \mathbf{I}_d])$ (63). The two lattices differ only by the extra vector $\mathcal{V}_b$, yet when $q$ is significantly larger than $\beta$ (but not so large that generic reduction clearly works), finding short vectors in (63) was found to be significantly easier than in (62) [ABD16, CJL16, KF17]. This does not affect NTRU's parameters, but rules the NTRU assumption out of advanced primitives (e.g. FHE) needing large moduli and small noise; there, Generalized-LWE (security resting essentially on (62)) is used. §4.4.2, Eqs. (62)–(63)

The paper says

Over $\mathcal{R}_{q,f}$ with $f = X^d - 1$, since $X - 1$ divides $f$ there is a ring homomorphism to $\mathcal{R}_{q,X-1} = \mathbb{Z}_q$: $a = \sum a_iX^i \mapsto a' = \sum a_i$. If $a$'s coefficients are small, so is $a'$ (at most a factor $d$ larger). Attack (adapted from [PR06, LM06]): map $\mathbf{A}, \mathbf{t}$ to $\mathbf{A}' \in \mathbb{Z}_q^{n\times m}$, $\mathbf{t}' \in \mathbb{Z}_q^n$. If $\mathbf{s} \in [\beta]^m$, $\mathbf{e} \in [\beta]^n$ with $\mathbf{A}\mathbf{s} + \mathbf{e} = \mathbf{t}$ exist, then $\mathbf{s}' \in [d\beta]^m$, $\mathbf{e}' \in [d\beta]^n$ satisfy $\mathbf{A}'\mathbf{s}' + \mathbf{e}' = \mathbf{t}'$ — a small-dimensional LWE problem, solvable as in Section 3.3. If $f$ had a factor like $X - 2$ instead, the image $\sum a_i2^i$ would be exponentially large in $d$. Interestingly, the worst-case to average-case reductions [PR06, LM06, LPR13a, LS15, PRS17] only need $f$ irreducible (or, for SIS, with a large-degree irreducible factor) over $\mathbb{Z}[X]$, not over $\mathbb{Z}_q[X]$ — and many low-degree factors in $\mathbb{Z}_q[X]$ are good for efficiency. §4.5, p. 32

The paper says

Schoolbook multiplication of degree-$d$ polynomials takes $O(d^2)$ operations; Karatsuba and Toom–Cook take approximately $O(d^{1.5})$. The Number Theoretic Transform needs as few as $O(d\log d)$ operations over $\mathbb{Z}_q$: it is the FFT over $\mathbb{Z}_q$. It was first used for lattice primitives in SWIFFT [LMPR08], and is now standard in encryption [ADPS16, BDK⁺18] and signatures [DKL⁺18, PFH⁺17]. §4.6, p. 32–33

Over $\mathbb{Z}_q[X]/(X^d + \alpha)$, $d$ a power of 2, if $-\alpha$ has a square root $r$: $X^d + \alpha \equiv (X^{d/2} - r)(X^{d/2} + r)$, and by the CRT one computes $ab$ by reducing $a, b$ modulo both factors (64)–(65), multiplying component-wise (66), and reconstructing. Eqs. (64)–(66)

Proof: $b_i = a_i + r\,a_{i+n/2}$, $c_i = a_i - r\,a_{i+n/2}$; in reverse $2a_i = b_i + c_i$, $2a_{i+n/2} = r^{-1}(b_i - c_i)$. Computing $2\phi^{-1}$ instead of $\phi^{-1}$ saves multiplications: the factor 2 accumulates to $2^{\log d} = d$ and is removed once, by multiplying by $d^{-1}$ at the end. Recurrence (67): $T(d) = 2T(d/2) + 2dA + dM$; solution (68): $T(d) = dT(1) + 2d\log d\cdot A + d\log d\cdot M$ with $T(1) = M$. Splitting $X^d + 1$ down to linear factors needs a $2d$-th root of unity in $\mathbb{Z}_q^*$, which exists for primes $q \equiv 1 \pmod{2d}$ (Lemma 7). If only $q \equiv 1 \pmod d$, the recursion stops at quadratic factors $X^2 - r_i$, whose base multiplication costs a small constant (5 multiplications and 2 additions); the total is virtually identical. Lemma 5, Eqs. (67)–(68), footnotes 14–16

The paper says

Proof: $X^d + 1 = \frac{X^{2d}-1}{X^d-1} = \prod_{k \mid 2d,\ k \nmid d}\Phi_k(X)$. If $d = 2^\ell$ this is $\Phi_{2d}$, irreducible; if $d = 2^\ell d'$ with $d' > 1$ odd, $\Phi_{2d}$ and $\Phi_{2d/d'}$ are distinct factors.

Proof: take $r$ of order $2k$ (so $r^k \equiv -1$); the $r^{2i+1}$ for $i \in \{0,\dots,k-1\}$ are distinct roots of $X^k + 1$; substitute $X^{d/k}$ for $X$.

§4.6.1, Lemmas 6–8, footnote 17

The paper says

Kyber, standardized by NIST as ML-KEM, is based on generalized LWE over $\mathcal{R}_{3329,X^{256}+1}$ with secrets from the binomial distribution, mainly because it is easier to sample. §4.7, p. 36–37

The paper says — Figure 3 (Kyber CPA encryption)

Public parameters $k, \eta_1, \eta_2, d_u, d_v \in \mathbb{Z}^+$. Figure 3

$k$ is the main parameter varied between security levels; $d_u, d_v$ give the log of the size of the set $\mathcal{S}$ (Figure 1, (18)) the ciphertext parts are rounded to, and determine ciphertext size and decryption error. Key generation is (51) with binomial secrets; encryption computes (52) and compresses it (Sections 2.5.1–2.5.2); decryption is (54) with compression recovering the 0/1 coefficients as in (20).

Table 3 — parameters for the three instantiations; their security is supposedly, in practice, no worse than AES-128, AES-192 and AES-256. Table 3

The paper says

With $e'$, $\mathbf{e}''$ the compression errors (coefficients as the $\eta$ of Lemma 1), and $\mathbf{t} = \mathbf{A}\mathbf{s} + \mathbf{e}$: $$\lceil v' - \mathbf{u}'^T\mathbf{s}\rfloor_{q\to2} = \Big\lceil \mathbf{r}^T\mathbf{e} + e_2 + \tfrac{q-1}{2}m + e' - (\mathbf{e}_1 + \mathbf{e}'')^T\mathbf{s}\Big\rfloor_{q\to 2}\quad(70)$$ which is $m$ if every coefficient of $\mathbf{r}^T\mathbf{e} + e_2 + e' - (\mathbf{e}_1 + \mathbf{e}'')^T\mathbf{s}$ (71) is less than $q/4$ in magnitude. Compute this as in Section 2.3.2 (adapted to rings via (55)), assuming the compressed values are uniform so that $e'$ is distributed as $\lceil\lceil x\rfloor_{q\to2^{d_v}}\rfloor_{2^{d_v}\to q} - x$ for random $x \in \mathbb{Z}_q$ (resp. $d_u$); then multiply the one-coefficient probability by 256 (union bound). Eqs. (70)–(71)

The paper says

Security is based on $\mathcal{R}_{3329,X^{256}+1}$-$\mathsf{LWE}_{k,\psi_2}$, with the proof of Sections 2.3.1 and 4.3. In Kyber-512, $\eta_1 = 3$ but $\eta_2 = 2$: the public key rests on $\mathcal{R}$-$\mathsf{LWE}_{k,\psi_3}$, while the ciphertext rests on a "hybrid" distribution ($\mathbf{r}$ from $\psi_3$, $\mathbf{e}_1, e_2$ from $\psi_2$), at least as hard as $\mathcal{R}$-$\mathsf{LWE}_{k,\psi_2}$. But the output is the rounded $\lceil\mathbf{r}^T\mathbf{A} + \mathbf{e}_1^T\rfloor_{q\to 2^{d_u}}$, adding error as in LWR (Section 2.5.3); $\psi_2$ plus compression from 3329 to $2^{d_u} = 1024$ values is somewhat larger than $\psi_3$, so in practice one gets a few extra bits of heuristic security. The price of $\psi_3$ is a larger decryption error. §4.7 Security

The paper says

Store a 256-bit seed $\rho$ and create $\mathbf{A} = \mathcal{H}(\rho)$ (e.g. SHAKE); the public key is $(\rho, \mathbf{t})$. $3329 \equiv 1 \pmod{256}$, so (Lemma 7) $X^{256} + 1$ splits into 128 quadratics $X^2 - r_i$; the NTT representation is $\hat a = (a \bmod X^2 - r_1, \dots, a \bmod X^2 - r_{128})$ (72), and converting $a \leftrightarrow \hat a$ takes $O(d\log d)$. No prime of similar size splits $X^{256} + 1$ into linear factors (that needs $q \equiv 1 \bmod 512$, footnote 18), and there is virtually no computational difference. Since the NTT is a bijection, sample $\mathbf{A}$ directly in NTT form, and store $\mathbf{t}$ in NTT form (needed anyway for $\mathbf{r}^T\mathbf{t}$) — a double win that avoids $k^2$ NTT computations. $\mathbf{s}, \mathbf{e}, \mathbf{r}, \mathbf{e}_1, e$ cannot be sampled in NTT form (not uniform), and compression cannot be done in NTT form. §4.7, Eq. (72), footnote 18

The paper says

A KEM has KEM-KeyGen, KEM-Encaps (public key → shared key + ciphertext) and KEM-Decaps (ciphertext + secret key → the same shared key). CPA-secure: the adversary cannot distinguish the shared key from uniform given public key and ciphertext; any CPA-secure encryption gives one by encrypting a random message (footnote 19: for slightly more advanced notions output a hash of it with the public key, as in Figure 4). CCA-secure: this remains true even with a decapsulation oracle usable on anything but the given ciphertext. The Fujisaki–Okamoto transform makes the decapsulation oracle "useless": it outputs non-$\perp$ only on ciphertexts whose message the adversary already knows — by making the encryption randomness depend on the message (encryption becomes deterministic, harmless since messages are random, footnote 20) and having decapsulation decrypt, re-encrypt, and output $\perp$ if the ciphertexts differ. §4.8, Figure 4

$\mathcal{H}$ and $\mathcal{G}$ are modelled as random oracles; $\rho \in \{0,1\}^{256}$ is the random coins of CPA-Encrypt (used to generate $(\mathbf{r}, \mathbf{e}_1, e_2)$). The Decaps inputs $h, z$ belong to the ML-KEM modifications below.

The paper says — modifications in ML-KEM

Pre-hashing the public key. Lattice public keys are large ($\approx$ 1 KB) and NTT operations are fast compared with exponentiation or elliptic-curve operations, so hashing $pk$ in Encaps/Decaps is noticeable — between 30 and 50 percent of the running time with AVX-2. Since in many practical scenarios decapsulation runs more often than key generation, compute $h = \mathcal{G}(pk)$ in KeyGen, store it, and use $h$ instead of $pk$ as input to $\mathcal{H}$ in Decaps (nothing is saved in Encaps; Decaps hashes 32 bytes instead of $\approx$ 1 KB). Implicit rejection. Kyber never outputs $\perp$: on a mismatch it outputs a random key computed as a hash of the input ciphertext and a secret random value created at key generation. The reasoning is "somewhat technical, and it is not really clear whether this adds any security in practice". §4.8, p. 40

The paper says

The goal is a lattice signature whose high-level structure is like Schnorr's [Sch89]. In a Schnorr signature the public key is $g, h$ and the signature is a non-interactive zero-knowledge proof of knowledge (ZKPoK) of $x$ with $g^x = h$. It is built in two steps: (1) a 3-move interactive Σ-protocol that is an honest-verifier ZKPoK of $x$; (2) the Fiat–Shamir transform, which makes it non-interactive. Section 5 follows the same road map with $\mathcal{R}_{q,f}$-LWE and $\mathcal{R}_{q,f}$-SIS, and ends with Dilithium (ML-DSA). §5, p. 41

The paper says

Start from an $\mathcal{R}_{q,f}$-$\mathrm{LWE}_{n,m,\beta}$ instance: $\mathbf{A} \leftarrow \mathcal{R}_{q,f}^{n\times m}$, $\mathbf{s}_1 \leftarrow [\beta]^m$, $\mathbf{s}_2 \leftarrow [\beta]^n$, $\mathbf{t} = \mathbf{A}\mathbf{s}_1 + \mathbf{s}_2$. The public key is $(\mathbf{A}, \mathbf{t})$; we want to prove knowledge of $\mathbf{s}_1, \mathbf{s}_2$ in the right range. This is harder than for discrete log: besides the algebraic relation we must also prove that the coefficients are small (ideally in $[\beta]$, but $[\bar\beta]$ for some $\bar\beta$ a little larger is fine).

The most efficient signatures do not prove knowledge of small $\mathbf{s}_1, \mathbf{s}_2$ with $\mathbf{A}\mathbf{s}_1 + \mathbf{s}_2 = \mathbf{t}$ (Eq. (73)), but of a relaxed solution: $\bar{\mathbf{s}}_1, \bar{\mathbf{s}}_2$ with coefficients in a somewhat larger interval and a small $\bar c$ with

$$\mathbf{A}\bar{\mathbf{s}}_1 + \bar{\mathbf{s}}_2 = \bar c\,\mathbf{t}. \qquad (74)$$

§5.1, Eqs. (73)–(74), Lemma 9, p. 41

The paper says

The coefficients of $\bar c$ (and of $\bar{\mathbf{s}}_1, \bar{\mathbf{s}}_2$) depend on the challenge space, so we want challenges with small norms. Over $\mathcal{R}_f$ with $\deg f = d$, let $\eta$ be the smallest integer with $2^\eta\binom{d}{\eta} > 2^{256}$ (assuming $d$ is large enough). Define

$$\mathcal{C} = \{c \in [1] : \|c\|_1 = \eta\}, \qquad \bar{\mathcal{C}} = \{\bar c = c_1 - c_2 : c_1 \neq c_2 \in \mathcal{C}\}. \qquad (75),(76)$$

So $\mathcal{C}$ contains the polynomials with exactly $\eta$ non-zero coefficients from $\{-1, 1\}$, and $|\mathcal{C}| = 2^\eta\binom{d}{\eta}$. Allowing fewer non-zero coefficients would complicate sampling without increasing the size by much. Footnote 22: to sample, start from a length-$d$ vector with $\eta$ ones, shuffle it (e.g. Fisher–Yates), then randomly negate each $1$. §5.1.1, Eqs. (75)–(76), p. 42

The paper says

An unusual feature: the protocol does not have perfect completeness. To keep the output small and independent of the secret, the last round uses rejection sampling. Here it is simply a check that all coefficients lie in a range. Discrete-Gaussian rejection gives slightly smaller outputs [Lyu12, DDLL13], but it is more complex: a slightly incorrect implementation may leak the secret key, and it may be harder to defend against side channels. As a result, the signer's running time is a random variable, but one independent of $\mathbf{s}_1, \mathbf{s}_2$. Sending a hash of the first message is a common compaction trick, and with rejection it would also let one simulate aborting transcripts. It is unnecessary for signature security, because the signer's aborted attempts are never seen. So the paper proves zero-knowledge only for non-aborting transcripts. §5.2, Figure 5, pp. 42–43

The paper says

Proof idea. Look at one integer coefficient. For $z$ to equal a target $\nu_z \in [\bar\beta]$ when the secret coefficient is $\nu_s \in [\gamma]$, the mask must be exactly $\nu_y = \nu_z - \nu_s$. That value lies in $[\bar\beta + \gamma]$, the very range $\nu_y$ is drawn from, so it happens with probability exactly $\frac{1}{2(\bar\beta+\gamma)+1}$ whatever $\nu_s$ is (Eq. (79)). Summing over the $(2\bar\beta+1)^{d(m+n)}$ valid outputs gives (77); dividing gives (78). §5.2.1, Lemma 10, Eqs. (77)–(79), pp. 43–44

The paper says

The probability of not aborting is (Eq. (80))

$$\left(\frac{2\bar\beta+1}{2(\bar\beta+\gamma)+1}\right)^{d(m+n)} > \left(\frac{\bar\beta}{\bar\beta+\gamma}\right)^{d(m+n)} = \left(1+\frac{\gamma}{\bar\beta}\right)^{-d(m+n)} \approx e^{-\gamma d(m+n)/\bar\beta},$$

so setting $\bar\beta = \gamma d(m+n)$ needs an expected $e$ repetitions before a non-$\perp$ value is sent. A smaller $\bar\beta$ is possible at the cost of more repetitions. §5.2.1, Eq. (80), p. 44

The paper says

The simulator. Choose $\mathbf{z}_1 \leftarrow [\bar\beta]^m$, $\mathbf{z}_2 \leftarrow [\bar\beta]^n$, $c \leftarrow \mathcal C$, set $\mathbf{w} := \mathbf{A}\mathbf{z}_1 + \mathbf{z}_2 - c\mathbf{t}$, and output $(\mathbf{w}, c, \mathbf{z}_1, \mathbf{z}_2)$. This perfectly simulates a non-aborting transcript: $c$ is uniform, by Lemma 10 $(\mathbf{z}_1, \mathbf{z}_2)$ is uniform for any $c$, and $\mathbf{w}$ is determined by the other values. So Figure 5 is HVZK when $\perp$ is not sent. Also, the probability of sending $\perp$ is independent of the secret. A running time that depended on the secret would enable side-channel attacks; the protocol is immune to that particular attack. §5.2.1, p. 44

The paper says

Use the usual rewinding argument (Figure 6): after the prover sends $\mathbf{w}$, get answers to two challenges $c \neq c'$. If both transcripts $(\mathbf{w}, c, \mathbf{z}_1, \mathbf{z}_2)$ and $(\mathbf{w}, c', \mathbf{z}_1', \mathbf{z}_2')$ verify, then $\mathbf{A}\mathbf{z}_1 + \mathbf{z}_2 - c\mathbf{t} = \mathbf{A}\mathbf{z}_1' + \mathbf{z}_2' - c'\mathbf{t}$, which simplifies to

$$\mathbf{A}(\mathbf{z}_1 - \mathbf{z}_1') + (\mathbf{z}_2 - \mathbf{z}_2') = (c - c')\mathbf{t}, \qquad (81)$$

exactly the statement (74) with $\bar{\mathbf{s}}_1 \in [2\bar\beta]^m$, $\bar{\mathbf{s}}_2 \in [2\bar\beta]^n$, $\bar c \in [2]$. §5.2.2, Figure 6, Eq. (81), p. 44

The paper says

HVZK means an adversary learns nothing from non-aborted transcripts. Proof of knowledge means an adversary who can impersonate the prover can produce a solution to (74), which by Lemma 9 solves Ring-LWE or Ring-SIS. Together, assuming Ring-SIS and Ring-LWE are hard, an adversary cannot impersonate the prover even after observing valid interactions. Fiat–Shamir then yields a signature scheme secure in the random oracle model, based on the hardness of Ring-SIS and Ring-LWE. §5.2.3, pp. 44–45

The paper says

Extraction gives $\bar{\mathbf{s}}_1, \bar{\mathbf{s}}_2$ with coefficients in $[2\bar\beta]$ and $\|\bar c\|_1 \le 2\eta$. By Lemma 9, if $\mathcal{R}_{q,f}$-$\mathrm{LWE}_{n,m,\beta}$ is hard, this implies solving an $\mathcal{R}_{q,f}$-SIS problem with $m+1$ columns. The optimal setting makes the two problems equally hard, i.e. on the same vertical line in Figure 2. $\bar\beta$ is dictated by Lemma 10: by (80) it should be around $\gamma d(m+n)$, and with $\|c\|_1 \le \eta$, $\gamma = \eta\beta$. So $\bar\beta$ is roughly a factor $\eta d(m+n)$ larger than $\beta$. §5.2.4, p. 45

The paper says

This section is not needed for the sequel (footnote 24). By changing only $\beta$ (and the derived $\bar\beta$), the lattice protocol mimics three discrete-log schemes with different security properties. The Schnorr-like variant, with $\beta$ unconstrained, is the most efficient. The common blueprint: a homomorphic one-way function family $\mathcal F$; the public key is $f, f(x)$; the prover sends $w = f(y)$ for a random mask $y$ and answers $c$ with $z = y + xc$. Different properties come from changing the relation between the domain and range sizes of $f$. §5.3, p. 45–46

The paper says

Public key $g$, $h = g^x$. The prover sends $w = g^y$ and answers $c$ with $z = y + xc$; the verifier checks $g^z = h^c\cdot w$. To reduce from discrete log, use the challenge $(g, h)$ as the public key. Without $x$, simulate by picking random $z, c$ and setting $w = g^z/h^c$. If the adversary impersonates, rewinding gives $g^{\bar z} = h^{\bar c}$ with $\bar z = z - z'$, $\bar c = c - c'$, and the discrete log is $\bar z/\bar c$. The lattice analogue (Figure 5) extracts (74) and applies Lemma 9 to $[\mathbf{A} \mid \mathbf{t}]$. One difference: Schnorr's public key $(g, g^x)$ is random, while in lattices Ring-LWE is needed to argue the key looks random. §5.3, p. 46

The paper says

Okamoto [Oka92] can be proven secure against active adversaries, who choose challenges maliciously. This is not really needed for signatures, since Fiat–Shamir only needs HVZK (footnote 25: there is no reduction from discrete log or DDH to actively secure Schnorr, though it can be proven under “knowledge assumptions” [BP02]). The public key is $(g_1, g_2)$, $h = g_1^{x_1}g_2^{x_2}$. The prover sends $w = g_1^{y_1}g_2^{y_2}$ and answers with $z_i = y_i + cx_i$; the verifier checks $g_1^{z_1}g_2^{z_2} = h^c w$.

The reduction picks its own valid secret key and runs the protocol honestly, with no simulation. Rewinding an impersonator gives $h^{\bar c} = g_1^{\bar z_1}g_2^{\bar z_2}$, i.e. $1 = g_1^{\bar z_1 - x_1\bar c}g_2^{\bar z_2 - x_2\bar c}$ (Eqs. (82)–(83)). This yields $\log_{g_1} g_2$ unless both exponents are $0$. Many secret keys are consistent with $h$, and the transcripts are identically distributed for all of them (footnote 26), even with adversarial $c$. So even an unbounded impersonator hits exactly $\bar z_i = x_i\bar c$ only with small probability. (This fails for Schnorr: $h = g^x$ has only one secret key.)

Lattice analogue: choose $\beta$ so large that the public key does not determine the secret. If $(2\beta+1)^{n+m} > q^n\cdot 2^{128/d}$, any algorithm recovers the exact $(\mathbf{s}_1, \mathbf{s}_2)$ with probability only $2^{-128}$ (footnote 27). Lemma 10 shows the transcripts leak nothing about the $\mathbf{s}_i$. But, as with Okamoto versus Schnorr, the requirement on $\beta$ makes it less efficient. §5.3, Eqs. (82)–(83), pp. 46–47

The paper says

Katz–Wang [KW03, Section 3] rests entirely on DDH and needs no rewinding, which gives a tighter reduction (footnote 28). Tightness matters more in the quantum random oracle model, where adversaries cannot be straightforwardly rewound. But it does not seem to affect actual security, so Okamoto, Katz–Wang and their lattice versions “remain mostly of only theoretical interest.” The public key is $(g_1, g_2)$, $(h_1 = g_1^x, h_2 = g_2^x)$. The prover sends $w_i = g_i^y$ and answers with $z = y + cx$; the verifier checks $g_i^z = h_i^c w_i$.

Given a DDH instance, publish it as the key and simulate as for Schnorr. If the tuple is random ($h_i = g_i^{x_i}$, $x_1 \neq x_2$, $w_i = g_i^{r_i}$), a valid $z$ needs $z = x_1c + r_1 = x_2c + r_2$, which happens with probability $1/|\mathcal C|$ over $c$. So the adversary's success decides DDH.

Lattice analogue: make $\bar\beta$ so small that, for a uniformly random key $(\mathbf{A}, \mathbf{t})$, valid responses do not exist information-theoretically. Two accepting challenges for one $\mathbf{w}$ would give $\mathbf{A}\bar{\mathbf{z}}_1 + \bar{\mathbf{z}}_2 = \mathbf{t}\bar c$ (Eq. (84)), and a Lemma-2-style argument shows such $\bar{\mathbf{z}}_i \in [2\bar\beta]$ do not exist for random $(\mathbf{A}, \mathbf{t})$ with high probability (footnote 30: this needs the polynomials in $[2\bar\beta]$ to be invertible [LS18, Corollary 1.2]). This forces $\bar\beta$ somewhat below $q^{n/(n+m)}$, and $\beta$ even smaller. §5.3, Eq. (84), pp. 47–49

The paper says

In Figure 2, LWE gets harder and SIS easier as $\beta$ grows, and they cross near $q^{n/(n+m)}$. The optimal Schnorr-like setting puts $\beta$ and $\bar\beta$ on different sides of the crossing. Okamoto-like needs $\beta > q^{n/(n+m)}$, putting both on the same side. Katz–Wang-like needs $\bar\beta < q^{n/(n+m)}$, again putting both on the same side. Figure 7 sketches the intuition: the Okamoto and Katz–Wang constraints produce less hard Ring-SIS/Ring-LWE instances, which require increasing $n$ and $m$. §5.3, Figure 7, p. 49

The paper says

In Figure 5 the verifier can recompute $\mathbf{z}_2 = \mathbf{w} - \mathbf{A}\mathbf{z}_1 + c\mathbf{t}$, so $\mathbf{z}_2$ need not be sent. But this is incompatible with using the protocol efficiently or turning it into a signature with Fiat–Shamir (§5.6). There one sends the short hash $\rho = \mathcal{H}(\mathbf{w})$ instead of $\mathbf{w}$ (the verifier checks $\mathcal{H}(\mathbf{A}\mathbf{z}_1 + \mathbf{z}_2 - c\mathbf{t}) = \rho$), and then $\mathbf{z}_2$ can no longer be recomputed. Not sending $\mathbf{w}$ essentially halves the signature size. So at first glance the prover must send either $\mathbf{w}$ or $\mathbf{z}_2$.

The insight. $\mathbf{z}_2$ is small, so with good probability it does not affect the high-order bits of $\mathbf{w}$. Likewise $\mathbf{y}_2$ does not affect the high bits of $\mathbf{A}\mathbf{y}_1 + \mathbf{y}_2$. So define $\mathbf{w}$ as the high bits of $\mathbf{A}\mathbf{y}_1$, and let the verifier check that the high bits of $\mathbf{A}\mathbf{z}_1 - c\mathbf{t}$ equal $\mathbf{w}$. Then neither $\mathbf{z}_2$ nor $\mathbf{w}$ needs to be sent. The prover still needs $\mathbf{s}_2$ to keep the protocol zero-knowledge. The idea is from [GLP12, BG14]; Figure 8 is due to [BG14].

Notation. As in §2.5.1, $\mathcal S \subset \mathbb{Z}_q$ has size $2^\kappa$ with neighbours $\approx q/2^\kappa$ apart, and $w = \mathrm{HIGH}_\mathcal{S}(w) + \mathrm{LOW}_\mathcal{S}(w)$ with $\mathrm{LOW}_\mathcal{S}(w) \in [q/2^{\kappa+1}]$. $\delta_\mathcal{S}$ is the largest integer such that the sets $s_i + [\delta_\mathcal{S}]$ are disjoint; for equidistant points, $\delta_\mathcal{S} \approx q/2^{\kappa+1}$. For all positive $\gamma < \delta_\mathcal{S}$ and $s \in [\gamma]$:

$$\mathrm{LOW}_\mathcal{S}(w) \in [\delta_\mathcal{S} - \gamma] \implies \mathrm{HIGH}_\mathcal{S}(w) = \mathrm{HIGH}_\mathcal{S}(w + s). \qquad (85)$$

§5.4, Figure 8, Eq. (85), pp. 49–51

The paper says

If $\mathbf{z} \neq \perp$ we need $\mathrm{HIGH}_\mathcal{S}(\mathbf{A}\mathbf{y}) = \mathrm{HIGH}_\mathcal{S}(\mathbf{A}\mathbf{z} - c\mathbf{t})$. Now

$$\mathbf{A}\mathbf{z} - c\mathbf{t} = \mathbf{A}(c\mathbf{s}_1 + \mathbf{y}) - c(\mathbf{A}\mathbf{s}_1 + \mathbf{s}_2) = \mathbf{A}\mathbf{y} - c\mathbf{s}_2. \qquad (86)$$

The prover only continues if $\mathrm{LOW}_\mathcal{S}(\mathbf{A}\mathbf{y} - c\mathbf{s}_2) \in [\delta_\mathcal{S} - \gamma]^n$. By (85) this implies $\mathrm{HIGH}_\mathcal{S}(\mathbf{A}\mathbf{y}) = \mathrm{HIGH}_\mathcal{S}(\mathbf{A}\mathbf{y} - c\mathbf{s}_2)$, so $\mathbf{w} = \mathrm{HIGH}_\mathcal{S}(\mathbf{A}\mathbf{z} - c\mathbf{t})$. §5.4.1, Eq. (86), p. 51

The paper says

By Lemma 10, conditioned on $\mathbf{z} \in [\bar\beta]^m$, $\mathbf{z}$ is uniform. The simulator picks $\mathbf{z} \leftarrow [\bar\beta]^m$ and $c \leftarrow \mathcal C$, and checks whether $\mathrm{LOW}_\mathcal{S}(\mathbf{A}\mathbf{z} - c\mathbf{t}) \in [\delta_\mathcal{S} - \gamma]^n$, resampling if not. It then sets $\mathbf{w} := \mathrm{HIGH}_\mathcal{S}(\mathbf{A}\mathbf{z} - c\mathbf{t})$ and outputs $(\mathbf{w}, c, \mathbf{z})$. It is crucial that the simulator can perfectly simulate the prover's check

$$\mathrm{LOW}_\mathcal{S}(\mathbf{A}\mathbf{y} - c\mathbf{s}_2) \in [\delta_\mathcal{S} - \gamma]^n. \qquad (87)$$

That is why this check, rather than a different and possibly less restrictive one, is performed. The scheme would still be complete if the prover directly checked that the verifier will accept, $\mathbf{w} = \mathrm{HIGH}_\mathcal{S}(\mathbf{A}\mathbf{z} - c\mathbf{t})$. But the simulator cannot perform that check, because it sets $\mathbf{w}$ only after fixing $\mathbf{z}$ and checking (87), so the scheme would lose its ZK property. Check (87) is needed to ensure correctness and simulatability. §5.4.2, Eq. (87), p. 51

The paper says

As in Lemma 10, $\Pr_\mathbf{y}[\mathbf{z} \in [\bar\beta]^m] = \bigl(\frac{2\bar\beta+1}{2(\bar\beta+\gamma)+1}\bigr)^{dm} \approx e^{-\gamma dm/\bar\beta}$. For the second check, make the heuristic assumption that $\mathbf{A}\mathbf{y} - c\mathbf{s}_2$ is uniform, so its LOW part is uniform in $[\delta_\mathcal{S}]^n$:

$$\left(\frac{2(\delta_\mathcal{S}-\gamma)+1}{2\delta_\mathcal{S}+1}\right)^{dn} > \left(1 - \frac{\gamma}{\delta_\mathcal{S}}\right)^{dn} \approx e^{-\gamma dn/\delta_\mathcal{S}}, \qquad (88)$$ $$\Pr_\mathbf{y}[\mathbf{z} \neq \perp] \approx e^{-\gamma d(m/\bar\beta + n/\delta_\mathcal{S})}. \qquad (89)$$

Larger $\bar\beta$ and $\delta_\mathcal{S}$ increase the correctness probability, but also the size of the extracted $\bar{\mathbf{s}}_1, \bar{\mathbf{s}}_2$. The heuristic is only used to compute the probability; independence of the abort from the secret needs none, because $\mathbf{z}$ is independent of the secret and $\mathrm{LOW}_\mathcal{S}(\mathbf{A}\mathbf{y} - c\mathbf{s}_2) = \mathrm{LOW}_\mathcal{S}(\mathbf{A}\mathbf{z} - c\mathbf{t})$. §5.4.3, Eqs. (88)–(89), pp. 51–52

The paper says

Rewinding gives $(\mathbf{w}, c, \mathbf{z})$ and $(\mathbf{w}, c', \mathbf{z}')$ with $\mathrm{HIGH}_\mathcal{S}(\mathbf{A}\mathbf{z} - c\mathbf{t}) = \mathrm{HIGH}_\mathcal{S}(\mathbf{A}\mathbf{z}' - c'\mathbf{t})$. Write each side as HIGH + LOW, with the LOW parts in $[q/2^{\kappa+1}]^n \approx [\delta_\mathcal{S}]^n$, and subtract:

$$\mathbf{A}(\mathbf{z} - \mathbf{z}') - (c - c')\mathbf{t} = \mathrm{LOW}_\mathcal{S}(\mathbf{A}\mathbf{z} - c\mathbf{t}) - \mathrm{LOW}_\mathcal{S}(\mathbf{A}\mathbf{z}' - c'\mathbf{t}) \in [q/2^\kappa]^n \approx [2\delta_\mathcal{S}]^n. \qquad (90)$$

This is (74), with $\bar{\mathbf{s}}_2$ set to the difference of the two LOW parts. §5.4.4, Eq. (90), p. 52

The paper says

Write $\mathbf{t} = \mathrm{HIGH}_\mathcal{T}(\mathbf{t}) + \mathrm{LOW}_\mathcal{T}(\mathbf{t})$ for a set $\mathcal T \subset \mathbb{Z}_q$ of $2^\ell$ elements about $q/2^\ell$ apart. Since $\mathbf{A}\mathbf{z}_1 \approx c\mathbf{t} \approx c\cdot\mathrm{HIGH}_\mathcal{T}(\mathbf{t})$, the verifier does not need the low bits of $\mathbf{t}$ to verify approximately. So publish only $\mathbf{t}_1 = \mathrm{HIGH}_\mathcal{T}(\mathbf{t})$, which takes $nd\ell$ bits instead of $nd\log q$; here $\mathbf{t} = \mathbf{t}_1 + \mathbf{t}_0$. The techniques are from [DKL⁺18]. The verifier can only compute $\mathbf{A}\mathbf{z} - c\mathbf{t}_1 = \mathbf{A}\mathbf{z} - c\mathbf{t} + c\mathbf{t}_0$, and would need

$$\mathrm{HIGH}_\mathcal{S}(\mathbf{A}\mathbf{z} - c\mathbf{t}) = \mathrm{HIGH}_\mathcal{S}(\mathbf{A}\mathbf{z} - c\mathbf{t} + c\mathbf{t}_0). \qquad (91)$$

Forcing $c\mathbf{t}_0$ to be tiny and reusing (85) would be wasteful. We bounded $c\mathbf{s}_2$ by $\gamma$ only because $\mathbf{s}_2$ must stay secret, whereas $\mathbf{t}_0$ need not be secret, only unnecessary for verification. The key observation: if $c\mathbf{t}_0 \in [\delta_\mathcal{S}]^n$, the verifier needs just one extra bit per coefficient. If $v$ lies between $s_i$ and $s_{i+1}$ and $v' \in [\delta_\mathcal{S}]$, the closest point to $v + v'$ can only be $s_i$ or $s_{i+1}$, and the prover tells the verifier which. $\mathrm{HINT}(\mathbf{A}\mathbf{z} - c\mathbf{t}_1, c\mathbf{t}_0) = \mathbf{h} \in \{0,1\}^{dn}$. $\mathrm{USEHINT}(\mathbf{v}, \mathbf{h})$ outputs, for each coefficient of $\mathbf{v}$, the closer neighbouring point if the hint bit is 0 and the farther one if it is 1. For every $\mathbf{v}$ and $\mathbf{h}$,

$$\mathbf{v} - \mathrm{USEHINT}(\mathbf{v}, \mathbf{h}) \in [q/2^\kappa]^n \approx [2\delta_\mathcal{S}]^n. \qquad (92)$$

Usually the hint bit is 0, so $\mathbf{h}$ can be represented by the positions where it is 1. Figure 9 is Figure 8 plus: restart if $c\mathbf{t}_0 \notin [\delta_\mathcal{S}]^n$; send $(\mathbf{z}, \mathbf{h})$; the verifier accepts iff $\mathbf{z} \in [\bar\beta]^m$ and $\mathrm{USEHINT}(\mathbf{A}\mathbf{z} - c\mathbf{t}_1, \mathbf{h}) = \mathbf{w}$. It proves knowledge of $\bar{\mathbf{s}}_1 \in [2\bar\beta]^m$, $\bar{\mathbf{s}}_2 \in [q/2^{\kappa-1}]^n$, $\bar c \in \bar{\mathcal C}$ with

$$\mathbf{A}\bar{\mathbf{s}}_1 + \bar{\mathbf{s}}_2 = \bar c\,\mathbf{t}_1. \qquad (93)$$

Substituting $\mathbf{t}_1 = \mathbf{t} - \mathbf{t}_0$ gives $\mathbf{A}\bar{\mathbf{s}}_1 + (\bar{\mathbf{s}}_2 + \bar c\mathbf{t}_0) = \bar c\mathbf{t}$, i.e. (74) with $\bar{\mathbf{s}}_2$ grown by the largest $\bar c\mathbf{t}_0$. §5.5, Figure 9, Eqs. (91)–(93), pp. 52–54

The paper says

Although the verifier does not need $\mathbf{t}_0$, it should not be considered secret, because the hint $\mathbf{h}$ leaks information about it. Think of it as: the verifier knows all of $\mathbf{t}$ but only uses $\mathbf{t}_1$. ZK follows from Figure 8 (§5.4.2), since the only new output $\mathbf{h}$ can be computed from $\mathbf{z}$ and $\mathbf{t}$. Correctness holds whenever $c\mathbf{t}_0 \in [\delta_\mathcal{S}]^n$. If this sometimes fails, security is unaffected; the prover just restarts more often. Footnote 31: a 1-bit hint in fact works when $c\mathbf{t}_0 \in [2\delta_\mathcal{S} - 1]$. This was observed independently by Jonathan Katz and in [BDL24]; it compresses the public key further at a small cost in signature size, and it came after ML-DSA was standardized. §5.5.1, footnote 31, p. 54

The paper says

Rewinding gives $\mathrm{USEHINT}(\mathbf{A}\mathbf{z} - c\mathbf{t}_1, \mathbf{h}) = \mathrm{USEHINT}(\mathbf{A}\mathbf{z}' - c'\mathbf{t}_1, \mathbf{h}')$ (Eq. (94)). By (92), each argument is within $[q/2^\kappa]^n$ of this common value, so

$$\mathbf{A}(\mathbf{z} - \mathbf{z}') - (c - c')\mathbf{t}_1 \in [q/2^{\kappa-1}]^n \approx [4\delta_\mathcal{S}]^n, \qquad (95)$$

which is knowledge of $\bar{\mathbf{s}}_1, \bar{\mathbf{s}}_2, \bar c$ as in (93). §5.5.2, Eqs. (94)–(95), pp. 54–55

The paper says

This is the Fiat–Shamir transform of Figure 9, with secrets chosen uniformly from their domains. Because the protocol is no longer interactive, the signer never sends $\perp$: it keeps restarting until rejection sampling succeeds. That is why ZK was only needed for non-aborting transcripts. Correctness and simulatability follow from Figure 9 and the random-oracle heuristic, and the generic properties of Fiat–Shamir extract from a successful forger the same $\bar{\mathbf{s}}_1, \bar{\mathbf{s}}_2, \bar c$ as in (93). By Lemma 9, that is as hard as Ring-LWE or Ring-SIS. §5.6, Figure 10, p. 55

The paper says

A sample instantiation very much resembling [DKL⁺18], (conservatively) with 192 bits of security (NIST Level 3), over $\mathcal{R}_{q,f}$ with $f = X^{256}+1$ and $q = 2^{23} - 2^{13} + 1$. Since $q \equiv 1 \pmod{512}$, this $q$ allows efficient NTT (§4.6).

Every point of $\mathbb{Z}_q$ is at most $(q-1)/32 + 1$ from $\mathcal S$. The coefficients of $\mathbf{t}_0$ lie in $[2^{12}]$, and $c\mathbf{t}_0 \in [\delta_\mathcal{S}]^6$ with high probability. Footnote 32: in fact always, since $\|\mathbf{t}_0\|_\infty \le 2^{12}$ and $\|c\|_1 = 49$ give $\|c\mathbf{t}_0\|_\infty \le 49\cdot 2^{12} < \delta_\mathcal{S}$. From (89), a signing attempt succeeds with probability about $e^{-196\cdot256\cdot(5/2^{19} + 6\cdot32/(q-1))} \approx 0.2$, so about 5 attempts are needed. Signing is noticeably slower than verification, but optimized implementations still run in well under a millisecond on a standard PC. The public key is a 256-bit seed $\rho$ plus $\mathbf{t}_1$ at 10 bits per coefficient, i.e. $6\cdot256\cdot10$ bits: 1952 bytes. The signature is $\mathbf{z}_1$ at 20 bits per coefficient ($256\cdot5\cdot20$ bits), $c$ (about 256 bits) and $\mathbf{h}$ (at most $256\cdot6$ bits): around 3424 bytes. §5.7, Table 4, footnote 32, p. 56

The paper says

• Hash the message once. If $\mu'$ is long, recomputing $\mathcal H(\mathrm{HIGH}_\mathcal{S}(\mathbf{A}\mathbf{y}), \mu, \mathbf{A}, \mathbf{t})$ after every restart is wasteful. First hash $\mu'$ with SHA-512, together with the public key, into a 512-bit digest $\mu$.
• Power-of-two masking range. $[\gamma + \bar\beta] = [2^{19} - 1]$ has $2^{20} - 1$ values; sampling instead from $\{-(2^{19}-1), \ldots, 2^{19}-1, 2^{19}\}$ uses exactly 20 random bits.
• Compact hint. With high probability $\mathbf{h}$ has at most 55 ones. Send their positions (8 bits each, $8\cdot55$ bits) plus the boundaries between the 6 polynomials ($5\cdot6 = 30$ bits): 470 bits instead of 1536. The signature drops to about 3290 bytes. The signer restarts if there are more than 55 ones, which is experimentally very rare.

§5.7, p. 57

The paper says

By §5.5, Lemma 9 and (93), security relies on $\mathcal{R}_{q,f}$-$\mathrm{LWE}_{n,m,\beta}$ (the public key $(\mathbf{A}, \mathbf{t})$ looks uniform) and $\mathcal{R}_{q,f}$-$\mathrm{SIS}_{n,m+1,2\bar\beta}$ (a forger would solve (93) with $\bar{\mathbf{s}}_1 \in [2\bar\beta]$, $\bar{\mathbf{s}}_2 \in [4\delta_\mathcal{S}]$ by (95), both approximately $[2^{20}]$). This corresponds to the middle row of Table 2, where the required $\delta$ is roughly the same for both problems. §5.7, p. 57