Goppa code được sử dụng trong thuật toán Classic McEliece,
là một thuật toán mã hóa khóa công khai thuộc post-quantum
cryptography. Phần này mình sử dụng slide bài giảng .
2.9.1. Thiết lập Goppa Code
Đầu tiên ta chọn số nguyên \(m \geqslant 1\) và
số nguyên tố \(q \geqslant 2\) nhằm xác định
trường \(\mathbb{F}_{q^m}\).
Chọn tập
\[L = \{ \alpha_1, \ldots, \alpha_n \}\]
sao cho \(\alpha_i \in \mathbb{F}_{q^m}\) đôi một
khác nhau và \(n \leqslant q^m\).
Ta chọn đa thức \(g(x)\) bậc không quá \(t\)
với hệ số trong \(\mathbb{F}_{q^m}\), sao cho
\(g(x)\) không có nghiệm bội và \(g(\alpha_i) \neq 0\)
với mọi \(i = 1, \ldots, n\).
Khi đó Goppa code \(\mathcal{C}\) với độ dài \(n\) là:
\[\mathcal{C} = \Gamma(L, g) = \left\{
\bm{c} = (c_1, \ldots, c_n) \in \mathbb{F}_q^n :
\sum_{i=1}^n \frac{c_i}{x - \alpha_i} = 0 \bmod{g(x)}
\right\},\]
nghĩa là Goppa code \(\mathcal{C}\) gồm các vector
\(\bm{c} \in \mathbb{F}_q^n\) sao cho tổng
\[\frac{c_1}{x - \alpha_1} + \frac{c_2}{x - \alpha_2} + \cdots + \frac{c_n}{x - \alpha_n} = 0 \bmod{g(x)}.\]
Dễ thấy khi biến đổi tương đương ta có
\[\dfrac{1}{x - \alpha_i} = -\dfrac{g(x) - g(\alpha_i)}{x - \alpha_i} \cdot g^{-1}(\alpha_i) \bmod{g(x)}.\]
Trong Classic McEliece thì \(q = 2\)
và \(g(x)\) là đa thức monic và tối giản.
2.9.1.1. Tìm ma trận parity-check
Giả sử
\[g(x) = g_0 + g_1 x + \cdots + g_t x^t = \sum_{i=0}^t g_t x^t\]
với \(g_i \in \mathbb{F}_{q^m}\).
Ta có
\[\begin{split}\frac{g(x) - g(\alpha_i)}{x - \alpha_i}
& = \frac{g_t(x^t - \alpha_i^t) + \cdots + g_1(x - \alpha_i) + g_0 \cdot 0}{x - \alpha_i} \\
& = g_t(x^{t-1} + x^{t-2} \alpha_i + x^{t-3} \alpha_i^2 + \cdots + \alpha_i^{t-1}) \\
& \ + g_{t-1}(x^{t-2} + x^{t-3} \alpha_i + x^{t-4} \alpha_i^2 + \cdots + \alpha_i^{t-2}) \\
& \ + \cdots + g_2(x + \alpha_i) + g_1 \\
& = g_t x^{t-1} + (g_t \alpha_i + g_{t-1}) x^{t-2} \\
& \ + (g_t \alpha_i^2 + g_{t-1} \alpha_i + g_{t-2}) x^{t-3} \\
& \ + \cdots \\
& \ + (g_t \alpha_i^{t-1} + g_{t-1} \alpha_i^{t-2} + \cdots + g_2 \alpha_i + g_1).\end{split}\]
Như vậy, hệ số trước \(x^j\) của codeword
\[\sum_{i=1}^n c_i \cdot \frac{g(x) - g(\alpha_i)}{x - \alpha_i} \cdot g^{-1}(\alpha_i)\]
lần lượt là
\[\begin{split}\begin{array}{ccc}
x^{t-1} & : & g_t g^{-1}(\alpha_1) c_1 + \cdots + g_t g^{-1}(\alpha_n) c_n \\
x^{t-2} & : & (g_t \alpha_1 + g_{t-1}) g^{-1}(\alpha_1) c_1 + \cdots + (g_t \alpha_n + g_{t-1}) g^{-1}(\alpha_n) c_n \\
\vdots \\
x^0 & : & \substack{(g_t \alpha_1^{t-1} + g_{t-1} \alpha_1^{t-2} + \cdots + g_2 \alpha_1 + g_1) c_1 + (g_t \alpha_2^{t-1} + g_{t-1} \alpha_2^{t-2} + \cdots + g_2\alpha_2 + g_1) c_2 \\ + \cdots + (g_t \alpha_n^{t-1} + g_{t-1} \alpha_n^{t-2} + \cdots + g_2\alpha_n + g_1) c_n}
\end{array}.\end{split}\]
Khi đó, \(\bm{c} \in \Gamma(L, g)\) khi và chỉ khi
tất cả hệ số trước \(x^j\) bằng \(0\). Điều này
tương đương với \(\overline{\bm{H}} \bm{c}^\intercal = 0\)
với \(\overline{\bm{H}} \in \mathbb{F}_{q^m}^{t \times n}\).
Ở đây
\[\begin{split}\overline{H} & = \begin{pmatrix}
g_t \cdot g^{-1}(\alpha_1) & \cdots & g_t \cdot g^{-1}(\alpha_n) \\
(g_t \alpha_1 + g_{t-1}) \cdot g^{-1}(\alpha_1) & \cdots & (g_t \alpha_n + g_{t-1}) \cdot g^{-1}(\alpha_n) \\
\vdots & \ddots & \vdots \\
(g_t \alpha_1^{t-1} + g_{t-1} \alpha_1^{t-2} + \cdots + g_2 \alpha_1 + g_1) \cdot g^{-1}(\alpha_1) & \cdots & (g_t \alpha_n^{t-1} + g_{t-1} \alpha_n^{t-2} + \cdots + g_2 \alpha_n + g_1) \cdot g^{-1}(\alpha_n)
\end{pmatrix} \\
& = \underbrace{\begin{pmatrix}
g_t & 0 & \cdots & 0 \\ g_{t-1} & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ g_1 & g_2 & \cdots & g_t
\end{pmatrix}}_{\bm{G}} \cdot \underbrace{\begin{pmatrix}
1 & 1 & \cdots & 1 \\ \alpha_1 & \alpha_2 & \cdots & \alpha_n \\ \vdots & \vdots & \ddots & \vdots \\ \alpha_1^{t-1} & \alpha_2^{t-1} & \cdots & \alpha_n^{t-1}
\end{pmatrix}}_{\bm{X}} \cdot \underbrace{\begin{pmatrix}
g^{-1}(\alpha_1) & 0 & \cdots & 0 \\ 0 & g^{-1}(\alpha_2) & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & g^{-1}(\alpha_n)
\end{pmatrix}}_{\bm{Y}}.\end{split}\]
Ma trận \(\bm{G}\) khả nghịch, đặt
\[\begin{split}\bm{H} = \bm{G}^{-1} \overline{\bm{H}} = \begin{pmatrix}
g^{-1}(\alpha_1) & \cdots & g^{-1}(\alpha_n) \\
\alpha_1 g^{-1}(\alpha_1) & \cdots & \alpha_n g^{-1}(\alpha_n) \\
\vdots & \ddots & \vdots \\
\alpha_1^{t-1} g^{-1}(\alpha_1) & \cdots & \alpha_n^{t-1} g^{-1}(\alpha_n)
\end{pmatrix} \in \mathbb{F}_{q^m}^{t \times n}.\end{split}\]
Ta sẽ thu được ma trận trên \(\mathbb{F}_{q^m}^{tm \times n}\)
bằng việc xét song ánh \(\mathbb{F}_{q^m}^{t \times n} \to \mathbb{F}_{q^m}^{tm \times n}\)
với một cơ sở cố định.
2.9.2. Decode với Goppa code
Khoảng cách tối thiểu (minimal distance) của \(\Gamma(L, g)\)
là \(d \geqslant t + 1\). Đặc biệt, khi \(q = 2\) và \(g\)
là separable (tức là \(g\) có đủ \(t\) nghiệm phân biệt
trên một trường mở rộng nào đó của \(\mathbb{F}_{q^m}\))
thì \(d \geqslant 2t + 1\) (bài tập).
Giả sử ta nhận được vector qua kênh truyền là
\[\bm{y} = (y_1, \ldots, y_n) = \underbrace{(c_1, \ldots, c_n)}_{\bm{c}} + \underbrace{(e_1, \ldots, e_n)}_{\bm{e}},\]
trong đó \(\bm{e}\) là lỗi. Khi đó
\(\mathrm{wt}(\bm{e}) \leqslant \left\lfloor\dfrac{d-1}{2}\right\rfloor\)
với \(\mathrm{wt}(\bm{e})\) là trọng số
của vector \(\bm{e}\).
Đặt \(\mathcal{B} = \{ i : e_i \neq 0 \}\) là tập
các vị trí xảy ra lỗi. Khi đó \(\lvert \mathcal{B} \rvert = \mathrm{wt}(\bm{e})\).
Đặt
\[s(x) = \sum_{i=1}^n \frac{y_i}{x - \alpha_i} = \sum_{i=1}^n \frac{e_i}{x - \alpha_i} \bmod{g(x)}\]
thì đây là syndrome của \(\bm{y}\) và chúng ta
sẽ decode dựa trên \(s(x)\).
Ta cần hai đa thức bổ trợ nữa là
\[\sigma(x) = \prod_{i \in \mathcal{B}} (x - \alpha_i)\]
gọi là đa thức định vị lỗi (error locator polynomial),
và đa thức
\[w(x) = \prod_{i \in \mathcal{B}} e_i \prod_{j \in \mathcal{B}, j \neq i} (x - \alpha_j).\]
Khi đó ta suy ra
\[e_k = \frac{w(\alpha_k)}{\sigma'(\alpha_k)}\]
với mọi \(k \in \mathcal{B}\).
Ta cũng suy ra
\[\sigma(x) \cdot s(x) = w(x) \bmod{g(x)}.\]
Khi đó
\[\deg \sigma(x) = \lvert \mathcal{B} \rvert, \quad \deg w(x) = \mathrm{wt}(\bm{e}) - 1.\]
Lúc này ta có \(\deg g = t\) phương trình,
trong đó có \(2\mathrm{wt}(\bm{e}) - 1\) phương trình
chưa biết.
Vì \(\mathrm{wt}(\bm{e}) < (t - 1) / 2\) nên
ta có thể giải hệ và tìm lại được các \(e_k\).
2.9.3. Ví dụ
Xét \(q = 2\) và \(m = 3\), \(\FF_{2^3} = \FF_2[x] / (x^3 + x + 1)\).
Đặt
\[L = \FF_2^3 = \{ 0, 1, \alpha, \alpha^2, \alpha + 1, \alpha^2 + \alpha, \alpha^2 + \alpha + 1, \alpha^2 + 1 \}\]
với \(\alpha^3 + \alpha + 1 = 0\).
Khi đó
\[\begin{split}\overline{\bm{H}} = \left(\begin{array}{cccccccc}
1 & 1 & \alpha^2 & \alpha^4 & \alpha^2 & \alpha & \alpha & \alpha^4 \\
0 & 1 & \alpha^3 & \alpha^6 & \alpha^5 & \alpha^5 & \alpha^6 & \alpha^2
\end{array}\right) \ \text{trên} \ \FF_{2^3},\end{split}\]
\[\begin{split}\bm{H} = \left(\begin{array}{cccccccc}
1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\
0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 \\
\hline
0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 \\
0 & 0 & 0 & 1 & 1 & 1 & 1 & 0
\end{array}\right).\end{split}\]
Giả sử ta gửi đi codeword
\[\begin{split}\bm{c} & = (1, 0, 1, 0, 1, 1, 1, 0) \\
& = \frac{1}{x - 0} + \frac{0}{x - 1} + \frac{1}{x - \alpha} + \frac{0}{x - \alpha^2} + \frac{1}{x - (\alpha + 1)} + \frac{1}{x - (\alpha^2 + \alpha)} \\
& + \frac{1}{x - (\alpha^2 + \alpha + 1)} + \frac{0}{x - (\alpha^2 + 1)} \bmod{(x^3 + x + 1)}.\end{split}\]
Đặt \(g(x) = x^2 + x + 1\). Ta có
\[\begin{split}g(0) & = 1 \Longrightarrow g^{-1}(0) = 1, \frac{1}{x - 0} = x + 1 \\
g(\alpha) & = a^2 + \alpha + 1 \Longrightarrow g^{-1}(\alpha) = a^2, \frac{1}{x - \alpha} = \alpha^2 x + (\alpha^2 + \alpha + 1) \\
g(\alpha + 1) & = \alpha^2 + \alpha + 1 \Longrightarrow g^{-1}(\alpha + 1) = \alpha^2, \frac{1}{x - (\alpha + 1)} = \alpha^2 x + (\alpha + 1) \\
g(\alpha^2 + \alpha) & = \alpha^2 + 1 \Longrightarrow g^{-1}(\alpha^2 + \alpha) = \alpha + 1, \frac{1}{x - (\alpha^2 + \alpha)} = (\alpha + 1) x + \alpha \\
g(\alpha^2 + \alpha + 1) & = \alpha^2 + 1 \Longrightarrow g^{-1}(\alpha^2 + \alpha + 1) = \alpha, \frac{1}{x - (\alpha^2 + \alpha + 1)} = \alpha x + (\alpha^2 + \alpha + 1)\end{split}\]
Thay các \(g\) trên vào \(\bm{c}\) thì ta có
\[\begin{split}\bm{c} & = c(x) = (x + 1) + \left(\alpha^2 x + (\alpha^2 + \alpha + 1)\right) + \left(\alpha^2 x + (\alpha + 1)\right) \\
& + \left((\alpha + 1) x + \alpha\right) + \left(\alpha x + (\alpha^2 + \alpha + 1)\right) \\
& = \left(1 + \alpha^2 + \alpha^2 + (\alpha + 1) + \alpha\right) x \\
& + \left(1 + (\alpha^2 + \alpha + 1) + (\alpha + 1) + \alpha + (\alpha^2 + \alpha + 1)\right) = 0.\end{split}\]
Như vậy \(\bm{c}\) là một codeword.
Giả sử ở bên nhận ta nhận được vector
\[\bm{y} = (1, 1, 1, 0, 1, 1, 1, 0).\]
Bằng trực quan ta thấy \(\bm{y}\) đã sai bit thứ hai so với \(\bm{c}\). Sau đây ta sẽ sử dụng phương pháp sửa lỗi của Goppa code để tìm ra vị trí lỗi (trên điều kiện là không biết \(\bm{c}\)).
Ta tính
\[\begin{split}\bm{y} & = (1, 1, 1, 0, 1, 1, 1, 0) \\
& = \frac{1}{x - 0} + \frac{1}{x - 1} + \frac{1}{x - \alpha} + \frac{0}{x - \alpha^2} + \frac{1}{x - (\alpha + 1)} + \frac{1}{x - (\alpha^2 + \alpha)} \\
& + \frac{1}{x - (\alpha^2 + \alpha + 1)} + \frac{0}{x - (\alpha^2 + 1)} \bmod{(x^3 + x + 1)} \\
& = x \Longrightarrow s(x) = x.\end{split}\]
Ta tìm các đa thức \(\sigma(x) \cdot s(x) \equiv w(x) \bmod{g(x)}\), tương đương với tìm các đa thức \(\sigma(x)\) và \(u(x)\) sao cho
\[\sigma(x) \cdot s(x) + u(x) \cdot g(x) = w(x).\]
Sử dụng thuật toán Euclide ta có
\[u(x) = 1 \ \text{và} \ \sigma(x) = x + 1, w(x) = 1.\]
Như vậy, vì
\[\sigma(x) = x + 1 = x - 1 = \prod_{i \in \{ 1 \}} (x - \alpha_1),\]
nên lỗi xảy ra ở vị trí \(1\) (chỉ số dãy \(\alpha_i\) bắt đầu từ \(0\)).