Appendix D: Solutions for Chapter 7

This page collects solutions and editorial notes for the exercises in Chapter 7: Lattices for programmers. 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 lattices package under solutions/ch07-lattices. From a clone of the companion repository, pytest tests/ch07 runs its suite. Appendix C has the setup.

Exercise 1: unimodular change of basis

For the chapter’s running example, $B_1 = \begin{pmatrix} 3 & 1 \\ 1 & 2 \end{pmatrix}$ and $B_2 = \begin{pmatrix} 3 & 4 \\ 1 & 3 \end{pmatrix}$. Since $\det B_1 = 5$, the inverse is $B_1^{-1} = \tfrac{1}{5} \begin{pmatrix} 2 & -1 \\ -1 & 3 \end{pmatrix}$, and

$$U = B_1^{-1} B_2 = \frac{1}{5} \begin{pmatrix} 5 & 5 \\ 0 & 5 \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}.$$

Every entry is an integer, and $\det U = 1 \cdot 1 - 1 \cdot 0 = 1$. The second construction reads the same matrix off the columns of $B_2$. Writing $b'_1 = (3, 1) = 1 \cdot b_1 + 0 \cdot b_2$ gives the first column $(1, 0)^T$; writing $b'_2 = (4, 3) = 1 \cdot b_1 + 1 \cdot b_2$ gives the second, $(1, 1)^T$. The two constructions agree, and the rest of this solution says why they always do.

In general, let $B_1, B_2$ be two bases of the same lattice $L$. The defining property of “same lattice” is that every column of $B_2$ is an integer combination of columns of $B_1$, and vice versa. Writing this column by column gives a matrix $U$ with integer entries such that $B_2 = B_1 U$, and a matrix $V$ with integer entries such that $B_1 = B_2 V$. Substituting one into the other gives $B_1 = B_1 U V$, so $U V = I_n$ (since $B_1$ has full column rank as a matrix over $\mathbb{Q}$). Both $U$ and $V$ have integer entries, so $\det U$ and $\det V$ are integers, and their product is $\det(I_n) = 1$. Two integers that multiply to 1 must each be $\pm 1$, so $\det U = \pm 1$ and $U$ is unimodular.

The two constructions in the exercise both produce $U$:

• $U = B_1^{-1} B_2$ as matrices over $\mathbb{Q}$. Because $B_1$ and $B_2$ generate the same lattice, this rational matrix has integer entries.
• $U$ as the matrix whose $j$-th column is the integer-coefficient vector expressing the $j$-th column of $B_2$ in the basis $B_1$. This is just the column-by-column expansion of $B_1^{-1} B_2$.

The two constructions are the same calculation written from different starting points, so they must agree. The exercise is the canonical check that two bases generate the same lattice: the change-of-basis matrix between them is integer with determinant $\pm 1$.

Exercise 2

The dual-of-dual identity is $(B^{-T})^{-T} = B$. Floating-point error means np.allclose(D2, B) is true but D2 == B may not hold exactly. The dual basis $D$ has rational entries in general because $\det B$ enters denominators (here $\det B = 25$, so $D$‘s entries are multiples of $1/25$). Only when $|\det B| = 1$ is $D$ guaranteed integer.

import numpy as np
B = np.array([[2, 0, 1], [1, 3, 0], [0, 1, 4]], dtype=float)
D = np.linalg.inv(B).T
D2 = np.linalg.inv(D).T
print(np.allclose(D2, B))
# ==> True

Exercise 3

$\det(L) = 2 \cdot 3 \cdot 5 \cdot 7 = 210$. Minkowski’s bound is $\sqrt{4} \cdot 210^{1/4} \approx 2 \cdot 3.807 \approx 7.614$. The first basis vector $b_1 = (2, 0, 0, 0)$ has Euclidean norm $2$, which is below the bound. In the given basis its coefficient vector is $(1, 0, 0, 0)$.

import math
det_L = 2 * 3 * 5 * 7
bound = math.sqrt(4) * det_L ** 0.25
print(det_L, round(bound, 3))
# ==> 210 7.614

Exercise 4

A reference statement to compare against your own version:

• SVP. Input: a basis $B$ of a lattice $L \subset \mathbb{R}^n$. Output: a nonzero lattice vector $v \in L$ with $\lVert v \rVert = \lambda_1(L)$ (the minimum nonzero norm).
• CVP. Input: a basis $B$ of $L$ and a target $t \in \mathbb{R}^n$. Output: a lattice vector $v \in L$ minimizing $\lVert v - t \rVert$.
• $\mathrm{SVP}_\gamma$ (approximate, search). Input: a basis $B$ and a slack factor $\gamma \geq 1$. Output: a nonzero $v \in L$ with $\lVert v \rVert \leq \gamma \lambda_1(L)$.
• $\mathrm{CVP}_\gamma$ (approximate, search). Input: $(B, t)$ and $\gamma \geq 1$. Output: $v \in L$ with $\lVert v - t \rVert \leq \gamma \cdot \mathrm{dist}(t, L)$.
• $\mathrm{GapSVP}_\gamma$ (promise decision). Input: $(B, d)$. Decide whether $\lambda_1(L) \leq d$ or $\lambda_1(L) > \gamma d$, promised that one of the two cases holds.
• $\mathrm{GapCVP}_\gamma$ (promise decision). Input: $(B, t, d)$. Decide whether $\mathrm{dist}(t, L) \leq d$ or $\mathrm{dist}(t, L) > \gamma d$, under the same promise.

Keep the search and decision versions apart: $\mathrm{SVP}_\gamma$ returns a vector, while $\mathrm{GapSVP}_\gamma$ returns one bit. The lattice cryptography literature works with the approximate and promise versions rather than exact SVP or CVP. That is what the worst-case-to-average-case reductions in (Ajtai, 1996) and (Regev, 2009) target: Regev’s Theorem 1.1 reduces from $\mathrm{GapSVP}$ and $\mathrm{SIVP}$ at an approximation factor $\tilde{O}(n/\alpha)$, where $\alpha$ is the LWE noise rate (Regev, 2009).

References

Ajtai, M. (1996). Generating hard instances of lattice problems (extended abstract). Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC), 99–108. https://doi.org/10.1145/237814.237838

Regev, O. (2009). On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM, 56(6), 34:1-34:40. https://doi.org/10.1145/1568318.1568324