1.5. Thuật toán rút gọn lattice

1.5.1. Thuật toán rút gọn lattice Gauss

Gọi \(L \subset \mathbb{R}^2\) là lattice \(2\) chiều với các vector cơ sở là \(\bm{v}_1\) và \(\bm{v}_2\). Thuật toán rút gọn lattice Gauss (Gaussian Lattice Reduction) hoạt động như sau.

Thuật toán 1.2 (Thuật toán rút gọn lattice Gauss)

  1. Loop

    1. Nếu \(\lVert \bm{v}_2 \rVert < \lVert \bm{v}_1 \rVert\) thì đổi chỗ \(\bm{v}_1\) và \(\bm{v}_2\) (swap).

    2. Tính \(m = \left\lfloor\dfrac{\bm{v}_1 \cdot \bm{v}_2}{\lVert \bm{v}_1 \rVert^2}\right\rceil\).

    3. Nếu \(m = 0\) thì trả về cơ sở mới gồm các vector \(\bm{v}_1\) và \(\bm{v}_2\).

    4. Thay \(\bm{v}_2\) thành \(\bm{v}_2 - m \bm{v}_1\).

  2. Tiếp tục loop :)))

Sau khi thuật toán kết thúc thì \(\bm{v}_1\) là vector khác không ngắn nhất trong \(L\), và do đó bài toán \(\texttt{SVP}\) được giải quyết. Hơn nữa góc \(\theta\) giữa \(\bm{v}_1\) và \(\bm{v}_2\) thỏa mãn

\[\lvert\cos\theta\rvert \leqslant \lVert\bm{v}_1\rVert / 2\lVert\bm{v}_2\rVert,\]

cụ thể là \(\dfrac{\pi}{3} \leqslant \theta \leqslant \dfrac{2\pi}{3}\).

Chứng minh

Đầu tiên ta chứng minh \(\bm{v}_1\) là vector khác không ngắn nhất trong \(L\).

Giả sử thuật toán kết thúc và trả về hai vector \(\bm{v}_1\) và \(\bm{v}_2\). Bước 1 của vòng lặp đảm bảo rằng \(\lVert \bm{v}_2 \rVert \geqslant \lVert \bm{v}_1 \rVert\) và

(1.4)\[\frac{\lvert \bm{v}_1 \cdot \bm{v}_2 \rvert}{\lVert \bm{v}_1\rVert^2} \leqslant \frac{1}{2}\]

vì đây là điều kiện để làm tròn \(\dfrac{\bm{v}_1 \cdot \bm{v}_2}{\lVert \bm{v}_1 \rVert^2}\) thành \(0\) và thỏa bước 3.

Mỗi vector \(\bm{v}\) khác không trong \(L\) đều biểu diễn được dưới dạng

\[\bm{v} = a_1 \bm{v}_1 + a_2 \bm{v}_2, \quad a_1, a_2 \in \mathbb{Z}.\]

Sử dụng (1.4) và bất đẳng thức quen thuộc \(\lvert x \rvert \geqslant -x\) với mọi \(x \in \mathbb{R}\) ta có

\[\begin{split}\lVert \bm{v} \rVert^2 & = \lVert a_1 \bm{v}_1 + a_2 \bm{v}_2 \rVert^2 \\ & = a_1^2 \lVert\bm{v}_1\rVert^2 + 2 a_1 a_2 \cdot \bm{v}_1 \cdot \bm{v}_2 + a_2^2 \lVert\bm{v}_2\rVert^2 \\ & \geqslant a_1^2\lVert\bm{v}_1\rVert^2 - 2 \lvert a_1 a_2 \rvert \cdot \bm{v}_1 \cdot \bm{v}_2 + a_2^2 \lVert\bm{v}_2\rVert^2 \\ & \geqslant a_1^2\lVert\bm{v}_1\rVert^2 - 2\lvert a_1 a_2 \rvert \cdot \lVert\bm{v}_1\rVert^2 + a_2^2\lVert\bm{v}_2\rVert^2 \\ & \geqslant a_1^2\lVert\bm{v}_1\rVert^2 - 2\lvert a_1 a_2\rVert \cdot \lVert\bm{v}_1\rVert^2 + a_2^2 \lVert\bm{v}_1\rVert^2 \quad (\text{vì} \ \lVert\bm{v}_2\rVert \geqslant \lVert\bm{v}_1\rVert) \\ & = (a_1^2 - 2\lvert a_1 \rvert \cdot \lvert a_2\rvert + a_2^2) \lVert\bm{v}_1\rVert^2.\end{split}\]

Ta sử dụng bất đẳng thức quen thuộc: với mọi \(t_1, t_2 \in \mathbb{R}\) thì

\[t_1^2 - 2 t_1 t_2 + t_2^2 = \left(t_1 - \frac{t_2}{2}\right)^2 + \frac{3}{4} \cdot t_2^2 = \frac{3}{4} \cdot t_1^2 + \left(\frac{t_1}{2} - t_2\right)^2 \geqslant 0.\]

Biểu thức bằng \(0\) khi và chỉ khi \(t_1 = t_2 = 0\). Vì \(a_1\) và \(a_2\) là các số nguyên không đồng thời bằng \(0\) nên có thể suy ra \(\lVert\bm{v}\rVert^2 \geqslant \lVert\bm{v}_1\rVert^2\) với mọi vector \(\bm{v}\) khác không trong \(L\). Nói cách khác, \(\bm{v}_1\) là vector khác không ngắn nhất trong \(L\) và bài toán \(\texttt{SVP}\) được giải xong.

Tiếp theo, với \(\cos\theta\), ta có

\[\lvert\cos\theta\rvert = \left|\frac{\bm{v}_1 \cdot \bm{v}_2}{\lVert\bm{v}_1\rVert \cdot \lVert\bm{v}_2\rvert}\right| = \frac{\bm{v}_1 \cdot \bm{v}_2}{\lVert\bm{v}_1\rVert^2} \cdot \frac{\lVert\bm{v}_1\rVert}{\lVert\bm{v}_2\rVert} \leqslant \frac{1}{2} \cdot \frac{\lVert\bm{v}_1\rVert}{\lVert\bm{v}_2\rVert}.\]

Hơn nữa \(\lVert \bm{v}_2 \rVert \geqslant \lVert \bm{v}_1 \rVert\) nên suy ra

\[\lvert\cos\theta\rvert \leqslant \frac{1}{2} \cdot \frac{\lVert\bm{v}_1\rVert}{\lVert\bm{v}_2\rVert} \leqslant \frac{1}{2} \Longleftrightarrow -\frac{1}{2} \leqslant \cos\theta \leqslant \frac{1}{2} \Longleftrightarrow \frac{\pi}{3} \leqslant \theta \leqslant \frac{2\pi}{3}.\]

Mình sẽ ví dụ thuật toán trên qua việc phá mã congruential public key cryptosystem với số liệu đã trình bày trong bài viết.

Số nguyên tố \(q = 3973659461\) là public parameter.

Ta đã chọn \(f = 36624\) và \(g = 33577\) làm private key. Ở đây \(f\) và \(g\) điều kiện

\[f < \sqrt{q/2}, \quad \sqrt{q/4} < g < \sqrt{q/2}, \quad \gcd(f, qg) = 1.\]

Lúc này public key là

\[h \equiv f^{-1} g \equiv 3540857813 \pmod q.\]

Để ý rằng \(h = f^{-1} g \pmod q\), tương đương \(fh + kq = g\) với \(k \in \mathbb{Z}\).

Ta thấy rằng \(f \cdot (h, 1) + k \cdot (q, 0) = (g, f)\). Như vậy cơ sở của lattice gồm hai vector

\[\{ (h, 1), (q, 0) \}.\]

Điều kiện của \(f\) và \(g\) cho ta tính chất quan trọng: vector \((g, f)\) ngắn trong lattice. Do đó thuật toán rút gọn lattice Gauss sẽ hoạt động trong trường hợp này (số chiều bằng \(2\)).

Đặt \(\bm{v}_1 = (h, 1) = (3540857813, 1)\) và \(\bm{v}_2 = (q, 0) = (3973659461, 0)\).

Bước 1, ta có

\[\lVert\bm{v}_1\rVert = \sqrt{12537674051883142970} > \lVert\bm{v}_2\rVert = 3973659461\]

nên ta giữ nguyên \(\bm{v}_1\) và \(\bm{v}_2\).

Tiếp theo ta tính

\[m = \left\lfloor\frac{\bm{v}_1 \cdot \bm{v}_2}{\lVert\bm{v}_1\rVert^2}\right\rceil = \left\lfloor\frac{14070163148683218793}{12537674051883142970}\right\rceil = 1 \neq 0\]

nên ta thay \(\bm{v}_2\) bởi \(\bm{v}_2 - m \bm{v}_1\) thì

\[\bm{v}_2 = (432801648, -1).\]

Bước 2, hiện tại

\[\bm{v}_1 = (3540857813, 1), \ \bm{v}_2 = (432801648, -1)\]

nên

\[\lVert\bm{v}_1\rVert < \lVert\bm{v}_2\rVert,\]

đổi chỗ \(\bm{v}_1\) và \(\bm{v}_2\) ta được

\[\bm{v}_1 = (432801648, -1), \bm{v}_2 = (3540857813, 1).\]

Tiếp theo ta tính

\[m = \left\lfloor\frac{\bm{v}_1 \cdot \bm{v}_2}{\lVert\bm{v}_1\rVert^2}\right\rceil = \left\lfloor\frac{1532489096800075823}{187317266511515905}\right\rceil = 8 \neq 0\]

nên ta thay \(\bm{v}_2\) bởi \(\bm{v}_2 - m \bm{v}_1\) thì

\[\bm{v}_2 = (78444629, 9).\]

Cứ tiếp tục như vậy, vector \(\bm{v}_1\), \(\bm{v}_2\) và giá trị \(m\) sau bước 3 ở mỗi vòng lặp sẽ được thể hiện ở bảng sau.

Loop

\(\bm{v}_1\)

\(\bm{v}_2\)

\(m\)

1

\((3540857813, 1)\)

\((3973659461, 0)\)

\(1\)

2

\((432801648, -1)\)

\((3540857813, 1)\)

\(8\)

3

\((78444629, 9)\)

\((432801648, -1)\)

\(6\)

4

\((-37866126, -55)\)

\((78444629, 9)\)

\(-2\)

5

\((2712377, -101)\)

\((-37866126, -55)\)

\(-14\)

6

\((107152, -1469)\)

\((2712377, -101)\)

\(25\)

7

\((33577, 36624)\)

\((107152, -1469)\)

\(1\)

8

\((33577, 36624)\)

\((73575, -38093)\)

\(0\)

Vector \(\bm{v}_1\) ở bước cuối chính xác là \((g, f)\) bên trên.