Appendix D: Solutions for Chapter 13

This page collects solutions and editorial notes for the exercises in Chapter 13: Lattice cryptanalysis. Compute and derivation exercises have worked solutions; open-ended exercises have an editorial note describing what a strong answer addresses.

The fuller versions of these routines are in the cryptanalysis package under solutions/ch13-lattice-cryptanalysis. From a clone of the companion repository, pytest tests/ch13 runs its suite. Appendix C has the setup.

Exercise 1

The classical core-SVP cost is $0.292 \beta$ bits and the quantum cost is $0.265 \beta$ bits. Both scale linearly in $\beta$, so monotonicity is automatic. ML-KEM-768’s $\beta = 626$ falls between the rows for $\beta = 600$ and $\beta = 800$. Floor the products rather than rounding them, which is what the Kyber security script does: it prints int(floor(...)), and the chapter’s core_svp_classical uses int() for the same reason. At $\beta = 626$ the rounded exponents give $\lfloor 0.292 \cdot 626 \rfloor = 182$ classical and $\lfloor 0.265 \cdot 626 \rfloor = 165$ quantum. Table 4 prints $183$ and $166$, which flooring the unrounded $0.29248$ and $0.26526$ reproduces; so does rounding the headline products to nearest, so the reproduction does not settle which arithmetic the table used. Either way it is the one-bit effect the chapter’s estimator section walks. Either way the figure sits well below the $207$-bit classical floor the NIST Call for Proposals sets for category 3. The Kyber Round 3 submission argues that core-SVP conservatism covers the gap, and its refined gate count of $215.1$ bits is what clears the floor (Avanzi et al., 2021).

for beta in (100, 200, 400, 600, 626, 800, 1000):
    print(beta, int(0.292 * beta), int(0.265 * beta))
# ==> 100 29 26
# ==> 200 58 53
# ==> 400 116 106
# ==> 600 175 159
# ==> 626 182 165
# ==> 800 233 212
# ==> 1000 292 265

Exercise 2

The sweep gives the following, with the last row landing on ML-KEM-768’s own block size:

import math


def delta_beta(beta):
    numerator = ((math.pi * beta) ** (1.0 / beta)) * beta
    return (numerator / (2.0 * math.pi * math.e)) ** (1.0 / (2.0 * (beta - 1)))


def primal_succeeds(beta, d, q, m, sigma):
    log_lhs = math.log(sigma * math.sqrt(beta))
    log_rhs = (2 * beta - d - 1) * math.log(delta_beta(beta)) + (m / d) * math.log(q)
    return log_lhs <= log_rhs


def smallest_beta(n_unknowns, q=3329, sigma=1.0):
    for beta in range(50, 1200):
        for m in range(1, 2 * n_unknowns + 1):
            if primal_succeeds(beta, m + n_unknowns + 1, q, m, sigma):
                return beta
    raise AssertionError("no beta in range")


for n_unknowns in (50, 100, 200, 300, 400, 512, 640, 768):
    print(n_unknowns, smallest_beta(n_unknowns))
# ==> 50 50
# ==> 100 50
# ==> 200 105
# ==> 300 191
# ==> 400 280
# ==> 512 382
# ==> 640 502
# ==> 768 624

The block size climbs steadily with the number of unknowns once the instance is large enough to be interesting, and the final row reproduces the $\beta = 624$ the chapter’s free search returns for ML-KEM-768. The two equal rows are the point of the exercise. At $n = 50$ and $n = 100$ the search returns $50$ because $50$ is where it starts, not because the condition first becomes satisfiable there.

Searching below $\beta = 50$ would not repair that, and this is the part worth writing down. The closed form for $\delta(\beta)$ is an asymptotic approximation that the chapter states is valid for $\beta \gtrsim 50$. Run it at $\beta = 2$ and the condition is satisfied at a single sample, which is not a security estimate but a formula evaluated outside its range. So the honest answer for these two instances is that the model cannot express how weak they are, only that they are weaker than anything it covers. That is a property of the estimator, not of the instances, and it is the reason the chapter’s core_svp_beta starts its sweep at $50$ rather than at $2$.

Toy parameter sets are pedagogically useful and offer no cryptographic strength. What the sweep shows is that the estimator has a floor beneath which it stops distinguishing between degrees of broken.

Exercise 3

The Albrecht-Bai-Ducas attack norms the NTRU key down to a subfield. The paper calls the large-modulus NTRU it attacks overstretched (Albrecht et al., 2016, sec. 1), and expects the attack to fail unless the normed-down key is unusually short in the subfield lattice, which a small enough modulus rules out (Albrecht et al., 2016, sec. 6). Its Table 2 experiment runs LLL at degree $256$ with a degree-$64$ subfield. The normed-down key is longer than the Gaussian-heuristic estimate at $q \approx 2^{24}$ and shorter from $q \approx 2^{28}$, but LLL in the subfield first succeeds at $q \approx 2^{32}$ (Table 2 in Albrecht et al., 2016, sec. 5.2). Both crossovers belong to the experiment, not to the attack.

The paper’s own criterion for perfect immunity sits far lower. The paper takes it at the smallest relative degree, $2$, which at degree $256$ means a subfield of degree $n' = 128$. Perfect immunity then holds when the normed-down key is longer than the Gaussian-heuristic estimate, $\sqrt{2}\,\sigma^2 n' > \sqrt{n' q / (\pi e)}$, where $\sigma^2$ is the variance of the key’s coefficients (Albrecht et al., 2016, sec. 6). Solving for the modulus gives $q < 2 \pi e \, \sigma^4 n'$, so the bound depends on the key distribution. For uniform ternary coefficients, of variance $2/3$, it is $q < 971.6$.

Ducas and van Woerden 2021 locate where the overstretched regime begins for ternary NTRU, the fatigue point, at $q \approx 0.004 \, n^{2.484}$. Above it, lattice reduction on the full NTRU lattice finds the dense sublattice before the key, which is why the subfield attack is not needed there (Ducas & van Woerden, 2021). At $n = 256$, which is also ML-KEM’s degree, the formula puts the fatigue point near $q \approx 3800$, as the chapter notes. The constant the paper fits with that exponent before rounding, $0.0038$, puts it near $3650$ (Ducas & van Woerden, 2021, sec. 5.3). So a modulus just above $2^{40}$ lies above all three thresholds. ML-KEM’s $q = 3329 \approx 2^{11.7}$ sits 9 to 13 percent under the fatigue point and above the immunity bound, so at this degree the modulus alone would not make an NTRU key with uniform ternary coefficients perfectly immune. The two moduli differ by a factor of roughly $2^{28}$.

Two things carry more weight than the modulus, though, and a strong answer says both. First, the attack norms the public key $h = g/f$ down to a subfield. The norm is multiplicative, so the normed-down key is again a ratio of two short elements, and its authors expect the large modulus this needs to confine the attack to the NTRU setting (Albrecht et al., 2016, sec. 1). Second, and this is the substantive point, the attack is a statement about the NTRU key distribution, where the public key is a ratio of two short ring elements, and not about the Module-LWE public key ML-KEM publishes.

Langlois and Stehlé 2015 is the worst-case to average-case foundation of the Module-LWE family (Langlois & Stehlé, 2015, sec. 4.1). It is a reduction with hypotheses, not a statement about overstretched parameters: it is stated for an elliptical Gaussian error family and, for its direct search-to-decision route, for a prime modulus that splits completely, with a modulus-switching route (Theorem 4.8) that reaches other moduli at enlarged Gaussian noise, so on either route it certifies the family rather than ML-KEM’s centered-binomial instance at $q = 3329$. Carrying the NTRU threshold across to ML-KEM is the error the exercise is testing for, and so is reading the reduction as a certificate for the standardized parameters.

Exercise 4

The decoder-boundary attack picks $\tau$ to push the decryption sum into the boundary between bit 0 and bit 1, where the noise margin is exactly the size $|s_j \cdot \tau|$. The two queries probe the boundary from above and below. The $+\tau \mathbf{u}_j$ query gives $v = \lfloor q/4 \rfloor - \tau s_j$, so it crosses into bit $1$ exactly when $s_j = -1$. The $-\tau \mathbf{u}_j$ query gives $v = \lfloor q/4 \rfloor + \tau s_j$ and crosses exactly when $s_j = +1$. The pair $(b^+, b^-)$ is therefore $(0, 0)$ if $s_j = 0$, $(1, 0)$ if $s_j = -1$, and $(0, 1)$ if $s_j = +1$. That identifies $s_j$ uniquely. The fourth case $(1, 1)$ does not occur for $|s_j| \le 1$. Total oracle calls is $2 n = 8$ for the small-secret toy at Chapter 10’s parameters. The attack scales as $O(n)$ in the absence of an FO transform, which is why every lattice- and code-based KEM in this book wraps its PKE in one.

References

Albrecht, M. R., Bai, S., & Ducas, L. (2016). A subfield lattice attack on overstretched NTRU assumptions: Cryptanalysis of some FHE and graded encoding schemes. IACR Cryptology ePrint Archive, Report 2016/127, full version of the CRYPTO 2016 paper. https://eprint.iacr.org/2016/127

Avanzi, R., Bos, J., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schanck, J. M., Schwabe, P., Seiler, G., & Stehlé, D. (2021). CRYSTALS-Kyber Algorithm Specifications and Supporting Documentation (Version 3.02). NIST Post-Quantum Cryptography Project, Round 3 submission package. https://pq-crystals.org/kyber/data/kyber-specification-round3-20210804.pdf

Ducas, L., & van Woerden, W. (2021). NTRU Fatigue: How Stretched is Overstretched? Advances in Cryptology – ASIACRYPT 2021; IACR ePrint 2021/999. https://eprint.iacr.org/2021/999

Langlois, A., & Stehlé, D. (2015). Worst-case to average-case reductions for module lattices. Designs, Codes and Cryptography, 75(3), 565–599. https://doi.org/10.1007/s10623-014-9938-4