# 後量子密碼學08 簡介多元二次密碼學
此篇文章來簡介「多元二次密碼學」，包括數學難題與一些實際密碼建構方法。
## 數學描述
多元二次多項式系統是形如以下的多項式系統：
\begin{aligned}
& p^{(1)}\left(x_1, x_2, \ldots, x_n\right)= \sum_{i=1}^n \sum_{j=i}^n p_{i j}^{(1)} x_i x_j+\sum_{i=1}^n p_i^{(1)} x_i+p_0^{(1)} \\
& p^{(2)}\left(x_1, x_2, \ldots, x_n\right)= \sum_{i=1}^n \sum_{j=i}^n p_{i j}^{(2)} x_i x_j+\sum_{i=1}^n p_i^{(2)} x_i+p_0^{(2)} \\
& \vdots \\
& p^{(m)}\left(x_1, x_2, \ldots, x_n\right)=\sum_{i=1}^n \sum_{j=i}^n p_{i j}^{(m)} x_i x_j+\sum_{i=1}^n p_i^{(m)} x_i+p_0^{(m)}
\end{aligned}
這裡，每個多項式 $p^{(k)}(x_1, x_2, \ldots, x_n)$ 都是變量 $x_1, x_2, \ldots, x_n$ 的二次多項式。每個多項式由二次項、一次項和常數項組成。讓我們來看一個具體的例子
假設我們有兩個變量 $x_1$ 和 $x_2$，以及兩個多項式 $p^{(1)}$ 和 $p^{(2)}$，構成的多變量二次多項式系統可以表示如下：
\begin{aligned}
& p^{(1)}\left(x_1, x_2\right)=3 x_1^2+2 x_1 x_2+x_2^2+4 x_1+5 x_2+6 \\
& p^{(2)}\left(x_1, x_2\right)=x_1^2+3 x_1 x_2+2 x_2^2+x_1+2 x_2+3
\end{aligned}
在這個例子中，我們可以看到每個多項式都包含了二次項（如 $3x_1^2$）、一次項（如 $4x_1$）和常數項（如 $6$）。這些多項式可以用來構造多變量加密系統。
## 困難問題
假設我們把上面這個例子記做 $\mathcal{F}$
\begin{align}
\mathcal{F}(x_{1},x_{2}) = (p^{(1)}(x_{1},x_{2}),p^{(1)}(x_{1},x_{2}))
\end{align}
那我們可以很快速的求到函數值
\begin{align}
\mathcal{F}(1,2) = (31,23)
\end{align}
可是如果反過來，要找到某組 $(x_1, x_2)$ 滿足
\begin{align}
\mathcal{F}(x_{1},x_{2})=(27,1)
\end{align}
那這個問題是，蠻複雜的。因此，對於一個多元二次方程組來說
$$
\mathcal{F = }
\left\{
\begin{aligned}
& p^{(1)}\left(x_1, x_2, \ldots, x_n\right)= \sum_{i=1}^n \sum_{j=i}^n p_{i j}^{(1)} x_i x_j+\sum_{i=1}^n p_i^{(1)} x_i+p_0^{(1)} \\
& p^{(2)}\left(x_1, x_2, \ldots, x_n\right)= \sum_{i=1}^n \sum_{j=i}^n p_{i j}^{(2)} x_i x_j+\sum_{i=1}^n p_i^{(2)} x_i+p_0^{(2)} \\
& \vdots \\
& p^{(m)}\left(x_1, x_2, \ldots, x_n\right)=\sum_{i=1}^n \sum_{j=i}^n p_{i j}^{(m)} x_i x_j+\sum_{i=1}^n p_i^{(m)} x_i+p_0^{(m)}
\end{aligned}\right.
$$
要計算 $\mathcal{F}$ 的反函數，是非常困難的。也因為這樣的困難度（hardness）我們可以把它設計成密碼協議
## 雙極構造法
**「容易求反函數」的中心映射 $\mathcal{F}$**
在多元二次密碼系統中，往往先設計一個「容易求逆」的多元二次映射 $\mathcal{F}$。一旦給出輸出，就能相對容易地透過私鑰推回輸入。這樣的映射稱為「中心映射」。
**兩個可逆的仿射變換 $\mathcal{T}$, $\mathcal{S}$**
- $\mathcal{T}$ 定義在輸入空間（$nn$ 維度）上，為一個可逆仿射變換：
\begin{align}
\mathcal{T}(\mathbf{x})=A_{\mathcal{T}} \cdot \mathbf{x}+\mathbf{b}_{\mathcal{T}} .
\end{align}
- $\mathcal{S}$ 定義在輸出空間（$mm$ 維度）上，為另一個可逆仿射變換：
\begin{align}
\mathcal{S}(\mathbf{y})=A_{\mathcal{S}} \cdot \mathbf{y}+\mathbf{b}_{\mathcal{S}} .
\end{align}
**整體公鑰函數**
綜合上述三個部分，形成
\begin{align}
P(\mathbf{x})=\mathcal{S}(\mathcal{F}(\mathcal{T}(\mathbf{x}))) .
\end{align}
- **公鑰**：最後得到的多元二次系統 $P(\mathbf{x})$。
- **私鑰**：$\mathcal{T}$,$\mathcal{T}$, $\mathcal{F}$ 的詳細結構與參數。
當攻擊者只看到 $P$ 時，難以有效反推；但私鑰持有者可依序使用 $\mathcal{T}$, $\mathcal{F}$, $\mathcal{T}$ 的反函數，求得 $x$
## 兩種經典的多元二次密碼系統
在雙極構造法的脈絡之下，下個問題就是：「很好算反函數的」F 該怎麼被構造？這裡簡要介紹 Matsimoto-Imai 與 UOV（不平衡油醋）協議：
### Matsumoto–Imai (MI)
Matsumoto–Imai 系統在「中心映射」F 的設計上，採用多項式商環 $\mathbb{Z}_q[x] /\langle g(x)\rangle$ 及「取次方」的策略。簡言之，令
\begin{align}
\mathcal{F}(X)=X^{q^\theta+1}
\end{align}
並藉由費馬小定理推得反函數，從而保證了整個系統的可逆性。在實作時，再結合「雙極構造法」外層包裝以增強安全性。
並藉由費馬小定理（或其擴充）推得反函數 F−1F−1，從而保證了整個系統的可逆性。在實作時，再結合「雙極構造法」外層包裝以增強安全性。
延伸學習請見看此[教學](https://ithelp.ithome.com.tw/articles/10356425)
### UOV（不平衡油醋）
UOV 透過將變量拆分成「油」與「醋」兩部分，使得部分變量（醋）一旦固定，另一部分變量（油）可透過線性方式迅速解出。因此「中心映射」FF 的反函數在運算量上相對較小，更適合於在低資源環境中快速簽章與驗證。搭配雙極構造法後，整體公鑰看起來依舊是一組「混亂」的多元二次方程，但持有私鑰者可輕鬆解密或生成簽章。
延伸學習請看此[教學](https://ithelp.ithome.com.tw/articles/10358954)
