1.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 1.64 (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 1.65 (Đị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{\lvert \det\left(\bm{V} \bm{V}^\top \right)\rvert}}$.

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

Nhận xét 1.16

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 $\bm{A}$ với hệ số nguyên (tức $\bm{A} \in \mathbb{Z}^{d \times d}$) có định thức bằng $1$ sao cho $\bm{W} = \bm{A} \cdot \bm{V}$. Chúng ta có thể dễ dàng chứng minh điều này khi biểu diễn các vector trong $\bm{W}$ thành tổ hợp tuyến tính các vector trong $\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 1.66 (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 đó.

Nhận xét 1.17

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í 1.17 (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 1.67 (Đ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ụ 1.35

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$.

Nhận xét 1.18

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

Nhận xét 1.19

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 1.68

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 của chuẩn Euclid (Euclidean norm) tại hầu hết $\lambda$. Cụ thể $\lambda_1(\mathcal{L})$ là độ dài vector khác không ngắn nhất trong $\mathcal{L}$.