Lattice

發表於 2026-02-02 更新於 2026-02-02 lattice LLL GSO SVP

Before reading

先了解下列內容：

  • vector (linear combination, span, subspace, basis, dimension, linearly independent, rank, basis matrix, determinant)
  • inner product (norm, distance, length, orthogonality, pairwise orthogonal, orthonormal basis, projection, Triangle Inequality, Cauchy–Schwarz inequality, Gram matrix)
  • orthogonalization (Gram–Schmidt process, QR decomposition, least squares)

Definition

Definition (Lattice). Let $b_1, \dots, b_m \in \mathbb{R}^n$ be linearly independent vectors. The (full-rank in its span) lattice generated by $b_1, \dots, b_m$ is the set $$ L = \left\{ \sum_{i=1}^{m} a_i b_i : a_i \in \mathbb{Z} \right\} \subseteq \mathbb{R}^n. $$ Equivalently, if $B = [ \, b_1 \ \cdots \ b_m \, ] \in \mathbb{R}^{n \times m}$ is the matrix whose columns are the basis vectors, then $$ L = \{ \, B a : a \in \mathbb{Z}^m \, \}. $$ The set $\{ b_1, \dots, b_m \}$ is called a basis of $L$ and $B$ is called a basis matrix.
Example. 考慮由兩個向量生成的格點集合 $L \subseteq \mathbb{R}^2$： $$ b_1 = \begin{pmatrix} 2 \\ 0 \end{pmatrix}, \qquad b_2 = \begin{pmatrix} 1 \\ 1 \end{pmatrix}. $$ 依照 lattice 的定義，$L$ 中的每個點都必須是 $b_1, b_2$ 的「整數線性組合」： $$ L = \{ x b_1 + y b_2 : x, y \in \mathbb{Z} \}. $$ 把整數係數 $x, y$ 展開來算： $$ x \begin{pmatrix} 2 \\ 0 \end{pmatrix} + y \begin{pmatrix} 1 \\ 1 \end{pmatrix} = \begin{pmatrix} 2 x + y \\ y \end{pmatrix} $$ 所以這個 lattice 就是所有形如 $$ \begin{pmatrix}2x+y\\y\end{pmatrix}\quad (x,y\in\mathbb{Z}) $$ 的平面點集合。 直觀上，只能用整數倍數去「走」$b_1$ 和 $b_2$，因此得到的是一個離散的點陣；把這些點畫在平面上，會看到它們規律地排列成一個 2-dimensional lattice。

continuous vs. discrete

Lattice 可以視為 vector subspace 的 discrete 版本。

  • vector subspace is continuous：在任意兩個點之間永遠存在無限多個點
  • lattice 由 basis vectors 的 integer linear combinations 所生成，因此只會落在一組分散且規律排列的 points 上（形成點陣結構）

discreteness 帶來一個關鍵差異：在 lattice 中，除了 zero vector 以外，存在 shortest non-zero vector。

  • 在 continuous space 裡，向量長度可以無限逼近 0，因此通常不存在真正的 minimum
  • 但 lattice 是離散集合，從原點到 non-zero points 的距離集合不會出現「嚴格遞減且下界為 0」卻永遠取不到的情況，因此 shortest non-zero vector is well-defined

high dimension hard, low dimension easy

許多計算問題（尤其在 cryptography 中）常可歸結為：在給定的 lattice 中找出 shortest non-zero vector；典型代表是 Shortest Vector Problem (SVP)。

一般而言，對 high-dimensional lattice 求解 SVP 被普遍認為是困難的，這也是 lattice-based cryptography 安全性的核心安全來源之一。

相對地，在 low dimension 時，這類問題往往較容易處理：維度小時可以依靠幾何直觀，搭配較直接的 search 或 reduction 方法有效求解。

Changing a Lattice Basis

給定一個 lattice $L$ 的 basis matrix $B$，進一步會想找「更好」的 basis（例如向量更短、更接近正交）。 但 lattice 的換基底不能像 vector space 一樣用任意實數線性變換，否則會改變由整數線性組合生成的點集。

lattice 允許的換基底形式是

\[B' = B U,\]

其中 $U$ 必須是 unimodular integer matrix，也就是 $U$ 的元素皆為整數且

\[\det(U) = \pm 1.\]

這確保新基底仍然生成同一個 lattice（只是重新排列/重組基底向量）。

Determinant as an Invariant

由於

\[\det(B') = \det(B) \det(U),\]

且 $\det(U) = \pm 1$，因此

\[|\det(B')| = |\det(B)|.\]

basis matrix 的 determinant 的絕對值不依賴於選擇哪一組 basis，是 lattice 的一個 invariant。

Discriminant of a Lattice

對一般情況（$B$ 不一定是 square matrix），定義 lattice 的 discriminant 為

\[\Delta = \left | \det(B^T B) \right | ^{1/2}.\]

這個量只依賴 lattice 本身，不會因為換基底而改變。

Full-Rank Case

若 $L$ 是 full-rank lattice（等價於 $B$ 是 square matrix），則

\[\det(B^T B) = \det(B^T) \det(B) = (\det(B))^2,\]

因此，在 full-rank 的情況下，discriminant 就等於 basis matrix determinant 的絕對值。

\[\Delta = | \det(B) |.\]

Orthogonal Bases in Lattices

給定一個 lattice $L$，直覺上會想問：是否存在一組 orthogonal basis？答案是否定的。

原因在於 lattice 的換基底必須維持「整數線性組合所生成的點集」不變。lattice 的 basis change 只能使用整數係數（對應到 unimodular integer matrix），因此不能任意做含有非整數係數的線性變換。

Why Gram–Schmidt Does Not Preserve the Lattice

Gram–Schmidt process 可以把一組向量正交化，得到新的向量系統。 但在過程中會出現投影係數 $\mu_{i,j}$，即使起始的 basis vectors 都是整數向量，$\mu_{i,j}$ 幾乎都會是非整數。

  • Gram–Schmidt 產生的向量仍然張成同一個 vector subspace
  • 但通常不再生成同一個 lattice

它保留了「線性空間」但破壞了「整數結構」，因為 lattice 不允許用 non-integer coefficients 來做換基底。

Aim for “Nearly Orthogonal” Bases

雖然一般不存在真正的 orthogonal lattice basis，但可以追求「接近正交」的基底。 一個常見的目標是讓 Gram–Schmidt 的係數滿足

\[|\mu_{i,j}| \le \frac{1}{2} \quad \text{for } 1 \le j < i \le n.\]

這表示每個基底向量在先前基底方向上的投影不會過大，使得基底不會過度傾斜，幾何上更「接近正交」。

References

  • Nigel P. Smart, Cryptography: An Introduction (3rd ed.), Chapter 17. PDF
↑