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 works only when $q$ is large enough relative to $n$ that the secret vector becomes shorter than the Gaussian heuristic in a subfield projection of the lattice. This is the “overstretched” regime. Ducas and van Woerden 2021 place the fatigue point for ternary NTRU at $q \approx 0.004 \, n^{2.484}$ (Ducas & van Woerden, 2021). At $n = 512$ that is around $q \approx 2 \times 10^4$, about $2^{14.4}$. So $q = 2^{40}$ sits far past it, while $q = 3329 \approx 2^{11.7}$ sits below it by a factor of about six at this $n$ (at ML-KEM’s own $n = 256$ the point is near $3800$, as the chapter notes). 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 maps the lattice into a subfield of the cyclotomic by a norm or trace map. It is not modulus switching, which is a dual-attack refinement and belongs to a different family. Second, and this is the substantive point, the attack is a statement about the NTRU key distribution, where the secret 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 Fluhrer 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

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