3.8. Các hệ mật mã khóa công khai dựa trên lý thuyết code

3.8.1. Hệ mật mã McEliece

Hệ mật mã McEliece được phát triển bởi R. J. McEliece vào năm 1978 trong [13].

3.8.1.1. Ý tưởng xây dựng

Đặt \(\bm{G}\) là ma trận sinh của linear code \([n, k]_q\) \(\mathcal{C}\) nào đó, sửa được \(t\) lỗi.

3.8.1.2. Tham số

  • \(\mathcal{C} = \{ \mathcal{C}_\lambda \}_{\lambda \in \Lambda}\) là một họ các linear code trên trường \(\mathbb{F}_q\) sao cho với mỗi code \(\bm{C} \in \mathcal{C}\) có một thuật toán decode hiệu quả là \(\mathsf{Decode}\) sửa được \(t\) lỗi. Ở đây \(\Lambda \subseteq \{ 0, 1 \}^\star\) là tập các giá trị của tham số code trong họ.

  • \(\mathsf{Sample}(1^\lambda)\) là thuật toán xác suất hiệu quả sao cho với giá trị tham số \(\lambda \in \Lambda\) cho ra ma trận sinh \(\bm{G}\) của code \(\mathcal{C}_\lambda\), số lượng lỗi \(t\) và thuật toán \(\mathsf{Decode}\), giải được bài toán decode trên linear code \([n, k]_q\) với ma trận sinh \(\bm{G}\) và kênh truyền có \(t\) lỗi. Kí hiệu \(\mathcal{G} = \{ \bm{G}_\lambda \}_{\lambda \in \Lambda}\) là tập tất cả ma trận sinh cho ra thuật toán \(\mathsf{Sample}(1^\lambda)\) cho mọi trường hợp tham số \(\lambda \in \Lambda\).

3.8.1.3. Thuật toán sinh khóa (Gen)

Private key gồm:

  1. Ma trận \(\bm{M} \in \mathrm{GL}_q(k)\) không suy biến cỡ \(k \times k\) trên \(\mathbb{F}_q\).

  2. \(\bm{G} \in V_{k \times n}(q)\) là ma trận sinh của \([n, k]_q\) code \(\mathcal{C}_\lambda\).

  3. \(\bm{P} \in \mathcal{S}_n\) là hoán vị trên tập \(\{ 1, \ldots, n \}\).

  4. \(\mathsf{Decode}\) là thuật toán decode trên mã \(\mathcal{C}_\lambda\).

Public key gồm:

  1. \(\bm{G}_{pub} = \bm{M} \cdot \bm{G} \cdot \bm{P} \in V_{k \times n}(q)\) là ma trận sinh của code tương đương với code \(\mathcal{C}_\lambda\).

  2. \(t \in \mathbb{N}\) là số lỗi được decode bởi \(\mathsf{Decode}\).

3.8.1.4. Thuật toán mã hóa (Enc)

Thuật toán mã hóa nhận đầu vào là thông điệp \(\bm{m} \in V_k(q)\) và trả về ciphertext \(\bm{c} \in V_n(q)\).

Để mã hóa, chọn ngẫu nhiên vector \(\bm{e} \in V_n(q)\) độ dài \(n\) và có trọng số Hamming bằng \(t\). Khi đó ta tính ciphertext:

\[\bm{c} = \bm{m} \cdot \bm{G}_{pub} + \bm{e}.\]

3.8.1.5. Thuật toán giải mã (Dec)

  1. Tính \(\bm{b} \gets \bm{c} \cdot \bm{P}^{-1}\).

  2. Tính \(\bm{u} \gets \mathsf{Decode}(\bm{b})\).

  3. Tính \(\bm{m} \gets \bm{u} \cdot \bm{M}^{-1}\).

Khi đó \(\bm{m}\) là plaintext ban đầu.

3.8.2. Hệ mật mã Niederreiter

3.8.2.1. Tham số

  • \(\mathcal{C} = \{ \mathcal{C}_\lambda \}_{\lambda \in \Lambda}\) là một họ các linear code trên trường \(\mathbb{F}_q\) sao cho với mỗi code \(C \in \mathcal{C}\) có một thuật toán decode hiệu quả là \(\mathsf{Decode}\) sửa được \(t\) lỗi. Ở đây \(\Lambda \subseteq \{ 0, 1 \}^\star\) là tập các giá trị của tham số code trong họ.

  • \(\mathsf{Sample}(1^\lambda)\) là thuật toán xác suất hiệu quả sao cho với giá trị tham số \(\lambda \in \Lambda\) cho ra ma trận parity-check \(\bm{H}\) của code \(\mathcal{C}_\lambda\), số lượng lỗi \(t\) và thuật toán \(\mathsf{SDecode}\), giải được bài toán syndrome decode trên linear code \([n, k]_q\) với ma trận parity-check \(\bm{H}\) và kênh truyền có \(t\) lỗi. Kí hiệu \(\mathcal{H} = \{ \bm{H}_\lambda \}_{\lambda \in \Lambda}\) là tập tất cả ma trận parity-check cho ra thuật toán \(\mathsf{Sample}(1^\lambda)\) cho mọi trường hợp tham số \(\lambda \in \Lambda\).

3.8.2.2. Thuật toán sinh khóa (Gen)

Private key gồm:

  1. Ma trận \(\bm{M} \in \mathrm{GL}_q(r)\) cỡ \(r \times r\) trên \(\mathbb{F}_q\), với \(r = n - k\) là số kí tự kiểm tra của \([n, k]_q\) code \(\mathcal{C}_\lambda\).

  2. \(\bm{H} \in V_{r \times n}(q)\) là ma trận parity-check của \([n, k]_q\) code \(\mathcal{C}_\lambda\).

  3. \(\bm{P} \in \mathcal{S}_n\) là hoán vị trên \(\{ 1, \ldots, n \}\).

  4. \(\mathsf{SDecode}\) là thuật toán syndrome decode trên code \(\mathcal{C}_\lambda\).

Public key gồm:

  1. \(\bm{H}_{pub} = \bm{M} \cdot \bm{H} \cdot \bm{P} \in V_{r \times n}(q)\) là ma trận parity-check của code mới tương đương với code \(\mathcal{C}_\lambda\).

  2. \(t \in \mathbb{N}\) là số lượng lỗi có thể sửa bởi \(\mathsf{SDecode}\).

3.8.2.3. Thuật toán mã hóa (Enc)

Plaintext được biểu diễn thành vector \(\bm{m} \in V_l(q)\) với \(l = \lfloor \log_q ((q - 1)^t \binom{n}{t}) \rfloor\). Ciphertext là vector \(\bm{c} \in V_r(q)\).

Ta cần ánh xạ \(\varphi_{n, t, q} : V_l(q) \to V_n(q)\) là đơn ánh, với mỗi \(\bm{m} \in V_l(q)\) cho ra vector \(\bm{e} \in V_n(q)\) có trọng số Hamming là \(t\).

  1. \(\bm{e} \gets \varphi_{n, t, q}(\bm{m})\)

  2. \(\bm{c} \gets \bm{e} \cdot \bm{H}_{pub}^\top\)

3.8.2.4. Thuật toán giải mã (Dec)

Để giải mã ta cần ánh xạ \(\varphi_{n, t, q}^{-1}\) là ánh xạ ngược của \(\varphi_{n, t, q}\).

  1. \(\bm{s} \gets \bm{M}^{-\top} \bm{c}^\top\).

  2. \(\bm{e}' \gets \mathsf{SDecode}(\bm{s})\).

  3. \(\bm{e} \gets \bm{e}' \cdot \bm{P}\).

  4. \(\bm{m} \gets \varphi^{-1}_{n, t, q}(\bm{e})\).

Thật vậy, nếu \(\bm{e}'=\bm{e}\bm{P}^{\top}\) thì \(\bm{c}^{\top}=\bm{M}\bm{H}(\bm{e}')^{\top}\) và do đó \(\bm{s}=\bm{H}(\bm{e}')^{\top}\) là syndrome đối với mã bí mật.

3.8.3. Cơ sở an toàn

Khóa công khai che giấu mã có cấu trúc bằng phép đổi cơ sở \(\bm{M}\) và hoán vị tọa độ \(\bm{P}\). Một kẻ tấn công có thể thử giải trực tiếp bài toán decoding/syndrome decoding trên ma trận công khai bằng information-set decoding, hoặc cố khôi phục cấu trúc của mã bí mật. Vì vậy họ mã được chọn phải vừa có decoder hiệu quả cho người giữ khóa, vừa không để lộ cấu trúc qua khóa công khai. Classic McEliece dùng mã Goppa nhị phân cho mục đích này.