2.1. Nhập môn mật mã dựa trên lattice¶

Kí hiệu. Vector hàng được kí hiệu bởi chữ thường in đậm, ví dụ \(\bm{x}\), \(\bm{y}\), \(\bm{v}\). Ma trận được kí hiệu bởi chữ hoa in đậm, ví dụ \(\bm{A}\), \(\bm{B}\).

Định nghĩa 2.1 (Lattice)

Xét tập hợp các vector độc lập tuyến tính \(\bm{v}_1\), \(\bm{v}_2\), ..., \(\bm{v}_d\) trên \(\mathbb{R}^n\). Ta nói lattice (hay lưới) \(\mathcal{L} \subset \mathbb{R}^n\) được sinh bởi các vector \(\bm{v}_1\), \(\bm{v}_2\), ..., \(\bm{v}_d\) nếu

\[\mathcal{L} = \{ a_1 \bm{v}_1 + a_2 \bm{v}_2 + \ldots + a_d \bm{v}_d : a_i \in \mathbb{Z} \}.\]

Nói cách khác, lattice là không gian vector được sinh bởi tổ hợp tuyến tính với hệ số nguyên.

Tập các vector

\[\{ \bm{v}_1, \bm{v}_2, \ldots, \bm{v}_d \}\]

được gọi là tập sinh hay cơ sở (basis) của lattice \(\mathcal{L}\).

Số lượng vector trong cơ sở được gọi là số chiều của lattice và kí hiệu là \(d = \dim(\mathcal{L})\).

Lattice được gọi là full-rank nếu \(\dim(\mathcal{L}) = n\).

Xét ma trận \(\bm{V}\) có các hàng là các vector \(\bm{v}_1\), ..., \(\bm{v}_d\), nghĩa là \(\bm{V} \in \mathbb{R}^{d \times n}\).

Định nghĩa 2.2 (Định thức của lattice)

Định thức của lattice \(\mathcal{L}\) được xác định bởi công thức \(\displaystyle{\det(\mathcal{L}) = \sqrt{\det\left(\bm{V} \bm{V}^\top \right)}}\).

Nếu lattice full-rank thì \(\det(\mathcal{L}) = \lvert\det(\bm{V})\rvert\).

Chú ý 2.1 (Tính bất biến của số chiều)

Cơ sở của một lưới không là duy nhất nhưng số lượng vector trong mỗi cơ sở là như nhau và bằng số chiều của lattice.

Nếu \(\bm{V}\) và \(\bm{W}\) là hai ma trận cơ sở của cùng lattice \(\mathcal{L}\) thì tồn tại ma trận unimodular \(\bm{A} \in \mathbb{Z}^{d \times d}\) có định thức \(\pm 1\) sao cho \(\bm{W} = \bm{A} \cdot \bm{V}\).

Giả sử \(\{ \bm{v}_1, \bm{v}_2, \ldots, \bm{v}_d \}\) là một cơ sở của \(\mathcal{L}\). Tương tự, \(\{ \bm{w}_1, \bm{w}_2, \ldots, \bm{w}_d \}\) là một cơ sở khác của \(\mathcal{L}\).

Chứng minh

Ta có thể viết mỗi \(\bm{w}_i\) là tổ hợp tuyến tính của các vector \(\bm{v}\) như sau

\[\begin{split}\bm{w}_1 & = a_{11} \bm{v}_1 + a_{12} \bm{v}_2 + \ldots + a_{1d} \bm{v}_d \\ \bm{w}_2 & = a_{21} \bm{v}_1 + a_{22} \bm{v}_2 + \ldots + a_{2d} \bm{v}_d \\ \vdots & \\ \bm{w}_d & = a_{d1} \bm{v}_1 + a_{d2} \bm{v}_2 + \ldots + a_{dd} \bm{v}_d\end{split}\]

Khi đó, nếu viết các vector \(\bm{w}_i\) thành hàng của ma trận \(\bm{W}\) và \(\bm{v}_j\) thành hàng của ma trận \(\bm{V}\) thì biểu diễn trên tương đương với:

\[\begin{split}\bm{W} = \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1d} \\ a_{21} & a_{22} & \cdots & a_{2d} \\ \vdots & \vdots & \ddots & \vdots \\ a_{d1} & a_{d2} & \cdots & a_{dd} \end{pmatrix} \cdot \bm{V}.\end{split}\]

Đặt

\[\begin{split}\bm{A} = \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1d} \\ a_{21} & a_{22} & \cdots & a_{2d} \\ \vdots & \vdots & \ddots & \vdots \\ a_{d1} & a_{d2} & \cdots & a_{dd} \end{pmatrix}.\end{split}\]

Do \(\bm{W}\) và \(\bm{V}\) là các cơ sở của \(\mathcal{L}\) nên nếu các vector \(\bm{w}_i\) có thể biểu diễn qua các vector \(\bm{v}_j\) thì ngược lại, các vector \(\bm{v}_j\) cũng có thể được biểu diễn qua các vector \(\bm{w}_i\). Suy ra ma trận \(\bm{A}\) là ma trận khả nghịch. Do \(a_{ij} \in \mathbb{Z}\) theo định nghĩa lattice, \(\det(\bm{A}) \in \mathbb{Z}\).

Hơn nữa, vì:

\[I = \bm{A} \cdot \bm{A}^{-1} \Rightarrow 1 = \det (\bm{A}) \cdot \det (\bm{A}^{-1})\]

nên \(\det(\bm{A}) = \pm 1\).

Mỗi lattice \(\mathcal{L}\) có một lattice đối ngẫu (dual lattice), kí hiệu là

\[\mathcal{L}^* = \{ \bm{w} \in \mathbb{R}^n : \langle \bm{w}, \bm{x} \rangle \in \mathbb{Z} \ \text{với mọi} \ \bm{x} \in \mathcal{L} \}.\]

Định nghĩa 2.3 (Fundamental domain)

Cho lattice \(\mathcal{L}\) có số chiều là \(d\) với cơ sở gồm các vector \(\{ \bm{v}_1, \bm{v}_2, \ldots, \bm{v}_d \}\). Ta gọi fundamental domain (hay fundamental parallelepiped) của \(\mathcal{L}\) ứng với cơ sở trên là tập

\[\mathcal{F} (\bm{v}_1, \ldots, \bm{v}_d) = \{ t_1 \bm{v}_1 + \ldots + t_d \bm{v}_d : 0 \leqslant t_i < 1 \}.\]

Trong mặt phẳng \(Oxy\) với hai vector \(\bm{u}\) và \(\bm{v}\) không cùng phương thì fundamental domain là hình bình hành tạo bởi hai vector đó.

Chú ý 2.2 (Phân hoạch bởi fundamental domain)

Gọi \(\mathcal{L} \subset \mathbb{R}^n\) là lattice với số chiều là \(n\) và gọi \(\mathcal{F}\) là fundamental domain của \(\mathcal{L}\). Khi đó mọi vetor \(\bm{w} \in \mathbb{R}^n\) đều có thể viết dưới dạng

\[\bm{w} = \bm{t} + \bm{v}\]

với \(\bm{t}\) duy nhất thuộc \(\mathcal{F}\) và \(\bm{v}\) duy nhất thuộc \(\mathcal{L}\).

Một cách tương đương, hợp của các fundamental domains

\[\mathcal{F} + \bm{v} = \{ \bm{t} + \bm{v} : \bm{t} \in \mathcal{F} \}\]

với \(\bm{v}\) là các vector trong \(\mathcal{L}\), sẽ bao phủ hết \(\mathbb{R}^n\).

Chứng minh

Để chứng minh nhận xét trên, giả sử \(\{ \bm{v}_i : 1 \leqslant i \leqslant n \}\) là cơ sở của \(\mathcal{L}\). Khi đó các \(\bm{v}_i\) độc lập tuyến tính nên cũng là cơ sở của \(\mathbb{R}^n\).

Ta viết các vector \(\bm{w} \in \mathbb{R}^n\) dưới dạng tổ hợp tuyến tính của \(\bm{v}_i\) và tách hệ số trước mỗi vector thành phần nguyên và phần lẻ. Phần nguyên cho vector trong \(\mathcal{L}\) và phần lẻ cho vector trong \(\mathcal{F}\).

Để chứng minh tính duy nhất của tổ hợp, xét hai cách biểu diễn khác nhau của \(\bm{w}\) và chứng minh hai cách đó là một.

Định lý 2.1 (Bất đẳng thức Hadamard)

Cho lattice \(\mathcal{L}\), lấy cơ sở bất kỳ của \(\mathcal{L}\) là các vector \(\bm{v}_1\), ..., \(\bm{v}_n\) và gọi \(\mathcal{F}\) là fundamental domain cho \(\mathcal{L}\). Khi đó

\[\det L = \text{Vol} (\mathcal{F}) \leqslant \lVert \bm{v}_1 \rVert \cdot \lVert \bm{v}_2 \rVert \cdots \lVert \bm{v}_n \rVert.\]

Cơ sở càng gần với trực giao thì bất đẳng thức Hadamard trên càng trở thành đẳng thức.

Định nghĩa 2.4 (Đa thức cyclotomic)

Với mỗi số nguyên dương \(N\), đa thức cyclotomic thứ \(N\) là đa thức tối giản \(\Phi_N\) duy nhất trong \(\mathbb{Z}[x]\) sao cho \(x^N - 1\) chia hết cho \(\Phi_N\) nhưng \(x^k - 1\) không chia hết cho \(\Phi_N\) với mọi \(k < N\).

Ví dụ 2.1 (Đa thức cyclotomic thứ ba)

Ví dụ, xét \(x^3 - 1 = (x - 1)(x^2 + x + 1)\):

với \(k = 1\), ta có \((x^2 + x + 1) \nmid (x - 1)\);
với \(k = 2\), ta có \((x^2 + x + 1) \nmid (x^2 - 1)\);
với \(k = 3\), theo phân tích nhân tử trên thì \((x^2 + x + 1) \mid (x^3 - 1)\).

Như vậy \(\Phi_3 = x^2 + x + 1\).

Chú ý 2.3 (Trường hợp chỉ số nguyên tố)

Nếu \(d\) là số nguyên tố thì \(\Phi_d = 1 + x + x^2 + \ldots + x^{d-1}\).

Chú ý 2.4 (Phân tích đa thức \(x^N-1\))

Các đa thức tối giản không chỉ đối với \(\mathbb{Z}\) mà còn đối với \(\mathbb{Q}\). Ta cũng có thể chứng minh được rằng:

\[x^N - 1 = \prod_{d \mid N} \Phi_d(x).\]

Định nghĩa 2.5 (Các cực tiểu liên tiếp)

Với \(i = 1, \ldots, n\), định nghĩa \(\lambda_i(\mathcal{L})\) là \(\lambda\) nhỏ nhất sao cho \(\mathcal{L}\) chứa ít nhất \(i\) vector độc lập tuyến tính có chuẩn Euclid không vượt quá \(\lambda\). Cụ thể, \(\lambda_1(\mathcal{L})\) là độ dài vector khác không ngắn nhất trong \(\mathcal{L}\).