Cấu trúc dữ liệu và Giải thuật Bài 147: Thuật toán Giảm cơ sở lưới LLL (Lenstra-Lenstra-Lovász Lattice Basis Reduction) - Nền tảng mật mã học hậu lượng tử và hình học của các con số.

Trong hình học của các con số (Geometry of Numbers) do Hermann Minkowski khởi xướng, một lưới (Lattice) là tập hợp vô hạn các điểm rời rạc trong không gian vector được sinh ra bởi các tổ hợp tuyến tính nguyên của một hệ cơ sở. Cùng một lưới có thể được biểu diễn bởi vô số cơ sở khác nhau. Một cơ sở "xấu" bao gồm các vector rất dài và gần như song song với nhau; ngược lại, một cơ sở "tốt" bao gồm các vector ngắn và gần như trực giao (orthogonal) với nhau.

Bài toán tìm vector khác không ngắn nhất trong lưới (Shortest Vector Problem - SVP) là một bài toán NP-hard dưới các phép quy nạp ngẫu nhiên hóa và là nền tảng an toàn của toàn bộ nền Mật mã học hậu lượng tử (Post-Quantum Cryptography - PQC) hiện đại.

Năm 1982, ba nhà toán học Arjen Lenstra, Hendrik Lenstra và László Lovász đã công bố Thuật toán LLL (Lenstra-Lenstra-Lovász Lattice Basis Reduction). Thuật toán này không giải chính xác bài toán SVP trong thời gian hàm mũ, mà giải bài toán xấp xỉ SVP: tìm ra một cơ sở gồm các vector ngắn có độ dài bị chặn trong phạm vi hệ số hàm mũ $2^{(d-1)/2}$ so với vector ngắn nhất tuyệt đối trong thời gian đa thức. Đây là một trong những thuật toán toán học có ảnh hưởng sâu rộng nhất thế kỷ 20, ứng dụng từ việc phân tích đa thức hệ số hữu tỉ, giải quy hoạch nguyên, phá vỡ hệ mật mã knapsack và RSA, cho đến phân tích độ an toàn của các thuật toán mã hóa kháng lượng tử chuẩn NIST như Kyber hay Dilithium.

1. Cơ sở Lý thuyết: Khái niệm Lưới và Hình học Minkowski

Cho $d$ vector độc lập tuyến tính $b_1, b_2, \dots, b_d \in \mathbb{R}^n$ ($d \le n$).

Lưới $\Lambda$ sinh bởi hệ cơ sở $B = \{b_1, b_2, \dots, b_d\}$ là tập hợp tất cả các tổ hợp tuyến tính với hệ số nguyên:

$$\Lambda = \mathcal{L}(B) = \left\{ \sum_{i=1}^d z_i b_i \;\middle\vert{}\; z_i \in \mathbb{Z} \right\}$$

• $d$ được gọi là hạng (rank) của lưới. Nếu $d = n$, lưới được gọi là toàn hạng (full-rank).

• Định thức của lưới (Determinant / Volume): Đại lượng đo lường thể tích của hình hộp cơ bản (fundamental parallelepiped) sinh bởi $B$:

  $$\det(\Lambda) = \sqrt{\det(B^T B)}$$

  Định thức là một bất biến hình học: mọi cơ sở hợp lệ của cùng một lưới $\Lambda$ đều có chung một định thức $\det(\Lambda)$.

   Cơ sở "xấu" (Vector dài, góc hẹp):         Cơ sở "tốt" (Vector ngắn, gần trực giao):
             b2                                         b2
            /                                           ^
           /                                            |
          /                                             |
         o--------> b1                                  o--------> b1
      (Rất khó giải bài toán)                      (Đạt chuẩn LLL-reduced)

Các bài toán tính toán cơ bản trên Lưới

1. Shortest Vector Problem (SVP): Tìm vector $v \in \Lambda \setminus \{0\}$ sao cho độ dài Euclidean $\Vert{}v\Vert{}$ đạt cực tiểu:

   $$\lambda_1(\Lambda) = \min_{v \in \Lambda \setminus \{0\}} \Vert{}v\Vert{}$$

2. Closest Vector Problem (CVP): Cho một điểm đích $t \in \mathbb{R}^n$, tìm vector $v \in \Lambda$ gần $t$ nhất:

   $$\text{dist}(t, \Lambda) = \min_{v \in \Lambda} \Vert{}t - v\Vert{}$$

Định lý thứ nhất của Minkowski (Minkowski's First Theorem)

Minkowski chứng minh rằng trong bất kỳ lưới toàn hạng $\Lambda \subset \mathbb{R}^d$ nào, luôn tồn tại một vector khác không có độ dài bị chặn trên bởi:

$$\lambda_1(\Lambda) \le \sqrt{d} \cdot (\det(\Lambda))^{1/d}$$

Tuy nhiên, định lý Minkowski chỉ mang tính chất tồn tại thuần túy, không cung cấp phương pháp tìm ra vector đó trong thời gian đa thức.

2. Trực chuẩn hóa Gram-Schmidt (GSO) và Cơ sở LLL-Reduced

Để đánh giá mức độ trực giao của một cơ sở, công cụ đại số then chốt là Quá trình Trực giao hóa Gram-Schmidt (Gram-Schmidt Orthogonalization - GSO).

Biểu diễn Gram-Schmidt

Cho cơ sở $b_1, \dots, b_d \in \mathbb{R}^n$, các vector trực giao tương ứng $b_1^*, \dots, b_d^*$ được xác định:

$$b_i^* = b_i - \sum_{j=1}^{i-1} \mu_{i, j} b_j^* \quad \text{với} \quad \mu_{i, j} = \frac{\langle b_i, b_j^* \rangle}{\Vert{}b_j^*\Vert{}^2}$$

• Các vector $b_i^*$ tạo thành hệ trực giao trong $\mathbb{R}^n$: $\langle b_i^*, b_j^* \rangle = 0$ với mọi $i \neq j$.

• Định thức của lưới liên hệ trực tiếp với GSO: $\det(\Lambda) = \prod_{i=1}^d \Vert{}b_i^*\Vert{}$.

• Lưu ý cốt tử: Các vector $b_i^*$ nói chung không thuộc lưới $\Lambda$ vì các hệ số $\mu_{i, j}$ là số thực, không phải số nguyên.

Định nghĩa Cơ sở Giảm LLL (LLL-Reduced Basis)

Một cơ sở $B = (b_1, \dots, b_d)$ được gọi là LLL-reduced với tham số $\delta \in (1/4, 1]$ (thường chọn $\delta = 3/4$ hoặc $\delta = 0.99$) nếu thỏa mãn đồng thời hai điều kiện:

1. Điều kiện Giảm kích thước (Size-Reduced Condition)

$$\vert{}\mu_{i, j}\vert{} \le \frac{1}{2} \quad \text{với mọi } 1 \le j < i \le d$$

Ý nghĩa: Hình chiếu của vector $b_i$ lên các vector trực giao trước đó $b_j^*$ có độ dài không vượt quá một nửa độ dài của $b_j^*$. Điều này đảm bảo các vector cơ sở không bị "nghiêng" quá mức về phía các vector đi trước.

2. Điều kiện Lovász (Lovász Condition)

$$\delta \Vert{}b_{k-1}^*\Vert{}^2 \le \Vert{}b_k^* + \mu_{k, k-1} b_{k-1}^*\Vert{}^2 = \Vert{}b_k^*\Vert{}^2 + \mu_{k, k-1}^2 \Vert{}b_{k-1}^*\Vert{}^2$$

hay tương đương:

$$\Vert{}b_k^*\Vert{}^2 \ge \left( \delta - \mu_{k, k-1}^2 \right) \Vert{}b_{k-1}^*\Vert{}^2$$

Ý nghĩa: Đảm bảo độ dài của các vector trực giao $b_i^*$ không bị suy giảm quá nhanh khi chỉ số $i$ tăng dần. Nếu điều kiện này bị vi phạm, việc hoán đổi hai vector $b_{k-1}$ và $b_k$ sẽ giúp vector đứng trước ngắn hơn đáng kể.

3. Các bước Thực thi của Thuật toán LLL

Thuật toán LLL liên tục thực hiện hai thao tác cơ bản:

1. Size Reduction: Trừ đi các bội số nguyên của các vector trước đó để thu nhỏ hệ số $\vert{}\mu_{i, j}\vert{} \le 1/2$.

2. Lovász Swap: Hoán đổi hai vector kề nhau khi điều kiện Lovász bị vi phạm, làm giảm thế năng của cơ sở.

                  Bắt đầu với k = 1
                          |
                          v
         +---> [Size-Reduce: b_k theo b_{k-1}]
         |                |
         |                v
         |     [Kiểm tra Điều kiện Lovász]
         |       /                     \
   (Vi phạm)   /                         \ (Thỏa mãn)
             v                             v
    [Hoán đổi b_{k-1} và b_k]    [Size-Reduce: b_k theo b_{k-2} ... b_0]
    [Cập nhật lại GSO]                     |
    [k = max(k - 1, 1)]                    v
             |                         [k = k + 1]
             +-----------------------------+
                          |
               (Dừng khi k == d)

Chứng minh Tính hữu hạn (Potential Function Argument)

Tại sao thuật toán LLL chắc chắn dừng lại trong thời gian đa thức mà không bị lặp vô hạn?

Lenstra, Lenstra và Lovász định nghĩa hàm thế năng (Potential function) $D$:

$$D = \prod_{i=1}^{d-1} d_i \quad \text{với} \quad d_i = \det(\mathcal{L}(b_1, \dots, b_i))^2 = \prod_{j=1}^i \Vert{}b_j^*\Vert{}^2$$

• Mỗi khi thực hiện phép hoán đổi giữa $b_{k-1}$ và $b_k$ vi phạm điều kiện Lovász, chỉ có định thức con $d_{k-1}$ bị thay đổi.

• Giá trị mới $d_{k-1}'$ giảm ít nhất một hệ số hằng số: $d_{k-1}' \le \delta \cdot d_{k-1}$ (với $\delta < 1$).

• Các định thức con $d_i$ khác ($i \neq k-1$) hoàn toàn không đổi.

• Do đó, thế năng toàn cục $D$ giảm ít nhất một hệ số $\delta$ sau mỗi phép hoán đổi.

• Vì các vector có tọa độ nguyên, $d_i$ luôn là các số nguyên dương $\ge 1$, chặn dưới giá trị của $D \ge 1$. Do đó, số phép hoán đổi tối đa bị chặn trên bởi $O(d^2 \log B)$, chứng minh thuật toán kết thúc sau một số đa thức các bước.

4. Hiện thực hóa Thuật toán LLL bằng Golang

Chương trình Golang dưới đây cài đặt hoàn chỉnh:

• Hàm tính toán Gram-Schmidt Orthogonalization (GSO) và ma trận hệ số $\mu$.

• Thủ tục Size-Reduction trừ bội số nguyên.

• Bước kiểm tra điều kiện Lovász và cập nhật hoán đổi vector.

• Kiểm thử trên cơ sở lưới chiều cao để tìm vector ngắn.

Go

package main

import (
	"fmt"
	"math"
)

type LLLReducer struct {
	d     int         // Số lượng vector cơ sở (hạng)
	n     int         // Số chiều của không gian
	b     [][]float64 // Cơ sở hiện tại (d x n)
	bStar [][]float64 // Các vector trực giao Gram-Schmidt (d x n)
	mu    [][]float64 // Ma trận hệ số GSO (d x d)
	gamma []float64   // gamma[i] = ||bStar[i]||^2
	delta float64     // Tham số Lovasz (thường chọn 0.75)
}

func NewLLLReducer(basis [][]float64, delta float64) *LLLReducer {
	d := len(basis)
	n := len(basis[0])

	bCopy := make([][]float64, d)
	for i := 0; i < d; i++ {
		bCopy[i] = make([]float64, n)
		copy(bCopy[i], basis[i])
	}

	bStar := make([][]float64, d)
	mu := make([][]float64, d)
	for i := 0; i < d; i++ {
		bStar[i] = make([]float64, n)
		mu[i] = make([]float64, d)
	}

	return &LLLReducer{
		d:     d,
		n:     n,
		b:     bCopy,
		bStar: bStar,
		mu:    mu,
		gamma: make([]float64, d),
		delta: delta,
	}
}

func dot(u, v []float64) float64 {
	var sum float64
	for i := range u {
		sum += u[i] * v[i]
	}
	return sum
}

// Cập nhật biểu diễn Gram-Schmidt toàn bộ
func (lll *LLLReducer) updateGSO() {
	for i := 0; i < lll.d; i++ {
		// bStar[i] = b[i]
		copy(lll.bStar[i], lll.b[i])

		for j := 0; j < i; j++ {
			if lll.gamma[j] > 1e-12 {
				lll.mu[i][j] = dot(lll.b[i], lll.bStar[j]) / lll.gamma[j]
			} else {
				lll.mu[i][j] = 0
			}
			for k := 0; k < lll.n; k++ {
				lll.bStar[i][k] -= lll.mu[i][j] * lll.bStar[j][k]
			}
		}
		lll.mu[i][i] = 1.0
		lll.gamma[i] = dot(lll.bStar[i], lll.bStar[i])
	}
}

// Giảm kích thước b[k] theo b[j]
func (lll *LLLReducer) sizeReduce(k, j int) {
	if math.Abs(lll.mu[k][j]) > 0.5 {
		q := math.Round(lll.mu[k][j])
		for i := 0; i < lll.n; i++ {
			lll.b[k][i] -= q * lll.b[j][i]
		}
		// Cập nhật lại các hệ số mu sau khi trừ
		lll.mu[k][j] -= q
		for i := 0; i < j; i++ {
			lll.mu[k][i] -= q * lll.mu[j][i]
		}
	}
}

// Thuật toán LLL chính thức
func (lll *LLLReducer) Reduce() [][]float64 {
	lll.updateGSO()
	k := 1

	for k < lll.d {
		// 1. Giảm kích thước b[k] đối với b[k-1]
		lll.sizeReduce(k, k-1)

		// 2. Kiểm tra điều kiện Lovasz:
		// gamma[k] >= (delta - mu[k][k-1]^2) * gamma[k-1]
		lovaszBound := (lll.delta - lll.mu[k][k-1]*lll.mu[k][k-1]) * lll.gamma[k-1]

		if lll.gamma[k] < lovaszBound {
			// Điều kiện Lovasz bị vi phạm -> Hoán đổi b[k] và b[k-1]
			lll.b[k], lll.b[k-1] = lll.b[k-1], lll.b[k]

			// Cập nhật lại GSO và lùi k
			lll.updateGSO()
			if k > 1 {
				k--
			}
		} else {
			// Thỏa mãn Lovasz -> Giảm kích thước b[k] đối với tất cả các b[j] còn lại (j = k-2 lùi về 0)
			for j := k - 2; j >= 0; j-- {
				lll.sizeReduce(k, j)
			}
			k++
		}
	}

	return lll.b
}

func norm(v []float64) float64 {
	return math.Sqrt(dot(v, v))
}

func main() {
	// Khởi tạo một cơ sở 4 chiều rất "xấu" (các vector dài và gần như thẳng hàng)
	// sinh ra một mạng lưới số nguyên
	initialBasis := [][]float64{
		{1, 1, 1, 1},
		{-1, 0, 2, 1},
		{3, 5, 6, 8},
		{0, 1, -1, 0},
	}

	fmt.Println("=== CƠ SỞ BAN ĐẦU (Chưa giảm) ===")
	for i, v := range initialBasis {
		fmt.Printf("b_%d = %v (Độ dài: %.3f)\n", i, v, norm(v))
	}

	// Chạy thuật toán LLL với delta = 0.75
	reducer := NewLLLReducer(initialBasis, 0.75)
	reducedBasis := reducer.Reduce()

	fmt.Println("\n=== CƠ SỞ SAU KHI GIẢM BẰNG THUẬT TOÁN LLL (delta = 0.75) ===")
	for i, v := range reducedBasis {
		// Làm tròn nhẹ hiển thị để loại bỏ sai số số thực float64
		roundedV := make([]int64, len(v))
		for j := range v {
			roundedV[j] = int64(math.Round(v[j]))
		}
		fmt.Printf("b_%d = %v (Độ dài: %.3f)\n", i, roundedV, norm(v))
	}

	fmt.Printf("\nVector ngắn nhất tìm được bởi LLL (b_0): %.3f\n", norm(reducedBasis[0]))
}

5. Các Chặn Đánh giá Chất lượng và Phân tích Độ phức tạp

Các Chặn Đánh giá Lý thuyết của Cơ sở LLL

Gọi $B = (b_1, \dots, b_d)$ là cơ sở đã được LLL-reduced với tham số $\delta = 3/4$:

1. Chặn độ dài vector đầu tiên so với nghiệm tối ưu SVP:

   $$\Vert{}b_1\Vert{} \le 2^{(d-1)/2} \cdot \lambda_1(\Lambda)$$

   Ý nghĩa: Vector đầu tiên $b_1$ đảm bảo xấp xỉ vector ngắn nhất tuyệt đối trong phạm vi hệ số mũ $2^{(d-1)/2}$.

2. Chặn so với Định thức của Lưới:

   $$\Vert{}b_1\Vert{} \le 2^{(d-1)/4} \cdot (\det(\Lambda))^{1/d}$$

3. Tính trực giao tổng thể (Hadamard Ratio Bound):

   $$\prod_{i=1}^d \Vert{}b_i\Vert{} \le 2^{d(d-1)/4} \cdot \det(\Lambda)$$

   (Tích độ dài các vector LLL-reduced tiệm cận gần với thể tích hình hộp cơ sở, chứng minh tính gần trực giao).

Phân tích Độ phức tạp Thời gian

Gọi $B_{\max} = \max_i \Vert{}b_i\Vert{}$ là độ dài lớn nhất của các vector cơ sở đầu vào.

Để áp dụng trong thực tế mật mã học với số chiều lớn ($d > 100$), các thư viện chuẩn (như NTL hay fplll) sử dụng kỹ thuật Floating-Point LLL kết hợp kiểm soát sai số động để đạt tốc độ cao mà không làm mất tính đúng đắn của đại số.

6. Ứng dụng Thực tế và Tầm ảnh hưởng trong Mật mã học

• Mật mã học Hậu Lượng tử (Post-Quantum Cryptography - PQC):

  • Các thuật toán chữ ký số và mã hóa khóa công khai chuẩn hóa bởi Viện Tiêu chuẩn và Kỹ thuật Quốc gia Hoa Kỳ (NIST) như CRYSTALS-Kyber (ML-KEM) và CRYSTALS-Dilithium (ML-DSA) dựa trên bài toán Module Learning With Errors (M-LWE).

  • LLL và biến thể khối mở rộng của nó — Thuật toán BKZ (Block Korkine-Zolotarev) — là công cụ chuẩn mực số 1 được sử dụng để đánh giá độ an toàn bit thực tế (Concrete Hardness) của các hệ mật mã kháng lượng tử trước các cuộc tấn công thu hẹp lưới (Lattice Reduction Attacks).

• Định lý Coppersmith & Tấn công Hệ mật RSA:

  • Năm 1996, Don Coppersmith sử dụng LLL để tìm nghiệm nguyên nhỏ của đa thức một biến theo modulo $N$. Kỹ thuật này phá vỡ hoàn toàn các triển khai RSA khi số mũ công khai nhỏ ($e = 3$) trong các kịch bản lộ một phần khóa bí mật, chia sẻ bản rõ, hoặc tấn công Franklin-Reiter Related Message.

• Tấn công Hệ mật Knapsack (Merkle-Hellman Knapsack Cryptosystem):

  • Hệ mật Merkle-Hellman từng được coi là giải pháp thay thế RSA. Năm 1985, Andrew Odlyzko và Ernest Brickell sử dụng LLL quy bài toán Subset-Sum về bài toán tìm vector ngắn trong lưới đa chiều, bẻ gãy hệ mật này trong thời gian đa thức.

• Phân tích Đa thức Thành Nhân tử (Factoring Polynomials over $\mathbb{Q}$):

  • Động lực ban đầu của Lenstra, Lenstra và Lovász năm 1982 là giải bài toán phân tích một đa thức bậc $d$ với hệ số hữu tỉ thành các nhân tử bất khả quy trong thời gian đa thức — một vấn đề toán học mở suốt nhiều thế kỷ.