Lattice-based Post-Quantum Cryptography - Hệ mật mã hậu lượng tử trên dàn

Giới thiệu về Lattice

Về cơ bản, lattice là một cấu trúc rời rạc trong không gian \(n\) chiều, được xây dựng từ các tổ hợp tuyến tính nguyên của một tập hợp các vector cơ sở. Để dễ hình dung, hãy tưởng tượng một mạng lưới các điểm đều đặn trong không gian, giống như các giao điểm trên một tờ giấy kẻ ô vuông, nhưng có thể "nghiêng" hoặc "kéo giãn" theo các chiều khác nhau.

Điều làm cho lưới trở thành một nền tảng mạnh mẽ cho mật mã học là sự tồn tại của một số bài toán khó trên lưới (Hard Lattice Problems). Đây là những bài toán mà cho đến nay, chưa có thuật toán hiệu quả nào (cả cổ điển hay lượng tử) có thể giải được trong thời gian đa thức khi kích thước của lưới (số chiều) đủ lớn. Hai trong số các bài toán quan trọng nhất là:

• Bài toán vector ngắn nhất (Shortest Vector Problem - SVP): Tìm một vector khác không có độ dài nhỏ nhất trong lưới.

• Bài toán vector gần nhất (Closest Vector Problem - CVP): Cho một điểm bất kỳ không nằm trong lưới, tìm điểm lưới gần nhất với nó.

Hầu hết các sơ đồ mật mã dựa trên lưới đều xây dựng tính bảo mật của chúng dựa trên độ khó của các biến thể xấp xỉ của SVP và CVP, hoặc các bài toán liên quan như Learning With Errors (LWE) và Ring-LWE (RLWE).

Định nghĩa toán học

Một lattice \(L\) trong không gian \(\mathbb R^n\) được định nghĩa là tập hợp tất cả các tổ hợp tuyến tính nguyên của một tập hợp \(m\) vector độc lập truyến tính \(\mathbf b_1, \mathbf b_2,\ldots, \mathbf b_m \in \mathbb R^n\), với \(m \le n\). Các vector này được gọi là base vectors (vector cơ sở) của lưới. Cụ thể, \(L\) được định nghĩa như sau:

$$L = \left \{ \sum_{i=1}^m c_i\mathbf b_i | c_i \in \mathbb Z \right\}$$

Tập hợp \(\{\mathbf b_1,\mathbf b_2,\ldots, \mathbf b_m\}\) được gọi là một basis (cơ sở) của \(L\). Nếu \(m=n\), ta gọi đó là một full-rank lattice.

Ví dụ: Trong \(\mathbb R^2\), xét các vector cơ sở \(\mathbf b_1 = (1,0)\) và \(\mathbf b_1 = (0,1)\) của dàn \(L\). \(L\) được tạo thành bởi tập hợp tất cả các điểm có tọa độ nguyên \((x,y)\) với \(x,y \in \mathbb Z\). \(L\) sẽ có thể hiện như một lưới hình vuông đơn giản.

Ý tưởng cở bản về mã hóa trên lattice

Ý tưởng này khai thác sự khác biệt giữa việc tính toán với một cơ sở "tốt" (dễ dàng) và một cơ sở "xấu" (khó khăn).

Tạo khóa

• Bên nhận tạo ra một cơ sở "tốt" (good basis) để làm secret key. Cơ sở này bao gồm các vector ngắn và gần vuông góc, giúp bên nhận dễ dàng thực hiện các phép toán phức tạp trên lưới một cách hiệu quả.

• Từ cơ sở "tốt", bên nhận lại tiếp tục tạo ra một cơ sở "xấu" (bad basis) (hoặc một mô tả tương đương của lưới mà không tiết lộ cơ sở tốt) để làm public key. Cơ sở này trông "lộn xộn" và không thể dễ dàng sử dụng để giải các bài toán khó trên lưới.

• Ý tưởng cốt lõi: Public key ẩn đi cấu trúc "dễ dàng" của lưới, khiến việc giải các bài toán trên đó trở nên cực kỳ khó khăn đối với bất kỳ ai không có secret key (cơ sở tốt)

Mã hóa

• Người gửi sử dụng public key (bad basis) để tạo ra một điểm trong không gian. Điểm này gần với một điểm của lattice nhưng không nằm chính xác trên lattice.

• Thông điệp được mã hóa bằng cách thêm một lượng nhiễu nhỏ có kiểm soát vào điểm này. Lượng nhiễu này đủ nhỏ để không làm thay đổi đáng kể "độ gần" của điểm tới điểm lưới ban đầu, nhưng đủ lớn để kẻ tấn công không thể dễ dàng suy luận ra thông điệp mà không biết secret key.

• Ý tưởng cốt lõi: Bản mã là một điểm trong không gian mà "dường như" ngẫu nhiên khi nhìn qua bad basis (public key). Tuy nhiên, nó có một mối liên hệ ẩn với lưới và thông điệp gốc, được tạo ra bởi nhiễu có chủ đích.

Giải mã

Thực chất là tìm lại thông điệp nhờ good basis (secret key)

• Bên nhận sử dụng secret key để "tìm lại" điểm lưới gần nhất với bản mã nhận được. Nhờ có cơ sở tốt, việc này trở nên dễ dàng.

• Sau khi tìm được điểm lưới gần nhất, bên nhận loại bỏ (trừ ra) nó khỏi bản mã. Phần còn lại chính là lượng nhiễu nhỏ mà người gửi đã thêm vào.

• Bằng cách phân tích lượng nhiễu này, bên nhận có thể giải mã được thông điệp gốc.

• Ý tưởng cốt lõi: Khóa bí mật cho phép bên nhận "nhìn xuyên qua" nhiễu và định vị chính xác vị trí của bản mã trong mối quan hệ với lưới, từ đó loại bỏ nhiễu và trích xuất thông điệp. Kẻ tấn công không có cơ sở tốt sẽ không thể làm được điều này.

Tại sao lại phức tạp như vậy?

Sự phức tạp này là cần thiết để đảm bảo tính bảo mật trước các máy tính lượng tử. Các máy tính lượng tử có thể giải quyết các bài toán về phân tích nhân tố (RSA) và logarit rời rạc (ECC) rất hiệu quả. Tuy nhiên, việc phân biệt giữa một điểm lưới chính xác và một điểm lưới bị thêm nhiễu ngẫu nhiên, khi không có "cơ sở tốt", vẫn là một bài toán khó ngay cả đối với chúng.

Mã hóa sử dụng Learning With Errors (LWE)

LWE là nền tảng của hầu hết các mật mã lattice thực tế hiện nay và dựa trên ý tưởng trên. Chúng ta cùng xem xét một ví dụ cụ thể đơn giản như sau: (nhờ các bạn tự tính toán và kiểm tra lại các kết quả ở dưới bằng tay nhé!!!)

Giả định:

• Áp dụng trên một trường hữ hạn \(\mathbb Z_q\) với \(q\) là số nguyên tố

• Thông điệp \(M\) chỉ dài 1 bit \(M \in \{0,1\}\)

Các tham số hệ thống (công khai)

• Chọn \(q=101\)

• Số chiều của vector \(n=3\)

• Các giá trị nhiễu \(\{-1,0,1\}\)

Tạo khóa (Người nhận Alice)

• Alice chọn một vector cột \(\mathbf s \in \mathbb Z_q^n\), ví dụ: \(\mathbf s = \begin{bmatrix} 1 \\ 2 \\ 1 \end{bmatrix}\) làm secret key \(sk\).

• Alice tạo public key \(pk\): Ma trận ngẫu nhiên \(\mathbf A \in \mathbb Z_q^{m \times n}\) và vector \(\mathbf b\) với các phần tử chọn ngẫu nhiên từ \(\mathbb Z_q\).
  Ví dụ: với \(m=5\)
  \(\mathbf A = \begin{bmatrix}5 & 10 &2 \\ 3 & 7 & 1 \\ 12 & 4 & 9 \\ 8 & 15 & 6 \\ 1 & 9 & 11 \end{bmatrix} (\bmod 101)\)

• Alice tính \(\mathbf b = \mathbf A . \mathbf s + e\) với \(e\) là môt vector nhiễu. Giả sử \(e=\begin{bmatrix}1\\-1\\0\\1\\0\end{bmatrix}\) vậy \(\mathbf b =\begin{bmatrix}5 & 10 &2 \\ 3 & 7 & 1 \\ 12 & 4 & 9 \\ 8 & 15 & 6 \\ 1 & 9 & 11 \end{bmatrix} \begin{bmatrix} 1 \\ 2 \\ 1 \end{bmatrix} +\begin{bmatrix}1\\-1\\0\\1\\0\end{bmatrix} =\begin{bmatrix}28\\17\\29\\45\\30\end{bmatrix} (\bmod 101)\)

• Secret key \(sk\) là \(\mathbf s\)

• Public key \(pk\) là \((\mathbf A, \mathbf b)\)

Mã hóa (Người gửi Bob)

• Bob chọn vector nhị phân ngẫu nhiên \(\mathbf u \in \mathbb Z^m\). Ví dụ \(\mathbf u = \begin{bmatrix}1\\0\\1\\0\\1\end{bmatrix}\)

• Tính hai phần của bản mã \((c_1, c_2)\):

  • \(c_1 = u^T. \mathbf A\) → một vector hàng \(1 \times n\)

  • \(c_2 = u^T.b + \lfloor q/2 \rfloor . M\) → một giá trị vô hướng

  • Giả sử Bob muốn mã hóa \(M=1\) thì \(\lfloor q/2 \rfloor . M = 50\)

    • \(c_1 = (18 \quad 23 \quad 22) (\bmod 101)\)

    • \(c_2 = 36\)

• Vậy bản mã Bob gửi Alice là \((c_1,c_2) = ( (18 \quad 23 \quad 22), 36)\)

Giải mã

• Alice nhận được \((c_1, c_2)\)

• Tính giá trị \(v = c_2-c_1. \mathbf s = 51 (\bmod 101)\)

• Tính \(v\) làm gì?

  • Vì \(v = c_2-c_1. \mathbf s = (u^T.\mathbf b + \lfloor q/2\rfloor. M) - (u^T.\mathbf A).\mathbf s = u^Te + \lfloor q/2\rfloor. M\)

  • Vì \(u\) là vector nhị phân và \(e\) là vector nhiễu nhỏ, do đó \(u^Te\) là giá trị rất nhỏ, theo như cách chọn giá trị của ví dụ này thì \(u^Te = 1\)

• Kiểm tra giá trị \(v\) để suy ra thong điệp gốc \(M\):

  • Nếu \(v \in (-q/4,q/4)\) → thông điệp gốc là \(0\)

  • Nếu \(v \in (q/4, 3q/4)\) → thông điệp gốc là \(1\)

  • Như vậy khi \(v=51\), ta giải ra được \(M=1\) (chính xác)

Demo