多元加密方案如何工作？
我最近一直在研究後量子密碼學的多元密碼學，但我很難理解這些簽名方案是如何工作的。只要我看到有 UOV 方案，然後 Rainbow 是 UOV 方案的一種概括，還有一種叫做 HFEv- 的東西。
但是這些簽名方案是如何工作的呢？我的意思是我們使用一些多元多項式，大多數時候多項式是二次的。但是我們如何真正簽署和驗證消息（假設是一個玩具消息，例如
011101101）？有沒有什麼地方可以逐步找到算法的工作原理，以及它們在玩具範例中的應用，以了解它們是如何工作的？
UOV
關於 UOV，您需要了解的第一件事是輸入變數被劃分為醋變數 $ x_1, \ldots, x_v $ 和石油變數 $ x_{v+1}, \ldots, x_{v+o} $ . 醋變數的數量大約是油變數數量的兩倍： $ v = 2o $ . 油和醋的名稱來自於油變數不與秘密多項式中的其他油變數混合的事實。實際上，密鑰的每個多項式都可以描述為二次形式。例如，讓 $ v=4 $ 和 $ o=2 $ 和 $ \mathbf{x}^\mathsf{T} = (x_1 , x_2 , x_3 , x_4 , x_5 , x_6) $ . 那麼每個秘密多項式都可以描述為：
$$ f_i(\mathbf{x}) = \mathbf{x}^\mathsf{T} \left( \begin{matrix}
- & * & * & * & * & * \
- & * & * & * & * & * \
- & * & * & * & * & * \
- & * & * & * & * & * \
- & * & * & * & & \
- & * & * & * & & \ \end{matrix} \right) \mathbf{x} \enspace . $$ 在哪裡 $ * $ 表示隨機選擇的元素，但空格表示零。石油變數， $ x_5 $ 和 $ x_6 $ 不與自己或彼此混合。 現在，同樣重要的是要知道 $ o $ 秘密多項式。其分量為的向量函式 $ f_i $ 表示為 $ \mathcal{F} $ :
$$ \mathcal{F}(\mathbf{x}) = \left( \begin{matrix} f_1(\mathbf{x}) \ \vdots \ f_o(\mathbf{x}) \end{matrix} \right) \enspace . $$ （在我們的範例中，只有兩個組件 $ \mathcal{F} $ .) 公鑰 $ \mathcal{P} $ 產生於 $ \mathcal{F} $ 通過用隨機可逆線性變換組合它 $ S \in \mathsf{GL}_{o+v}(\mathbb{F}_q) $ ，它實際上是一個逆存在的方陣： $ S \in \mathbb{F}_q^{(v+o)\times(v+o)} $ . 那麼公鑰就是
$$ \mathcal{P} = \mathcal{F} \circ S \enspace . $$ 為了簽署文件 $ d $ 帶雜湊 $ \mathbf{h} = \mathsf{H}(d) $ ，簽名者執行以下操作。首先，選擇醋變數的隨機分配 $ x_1, \ldots, x_v $ . 那麼多項式方程組 $ \mathcal{F}(x_{v+1},\ldots,x_{v+o}) = \mathbf{h} $ 是線性的 $ o \times o $ 系統。求解得到 $ x_{v+1}, \ldots, x_{v+o} $ 此時簽名者擁有整個向量 $ \mathbf{x} $ . 接下來，計算簽名 $ \mathbf{y} $ 作為 $ \mathbf{y} = S^{-1}\mathbf{x} $ .
為了驗證簽名 $ \mathbf{y} $ ，驗證者評估公鑰 $ \mathbf{y} $ ，並檢查結果是否等於文件的雜湊值， 即
$$ \mathcal{P}(\mathbf{y}) \stackrel{?}{=} \mathsf{H}(d) \enspace . $$ 注意 UOV 如何使用線性 $ o \times o $ 系統作為生成簽名的一個步驟，但是這個步驟如何推廣到任何可以有效地找到逆的二次（！）系統。例如，您可以遞歸調平並在那裡放置另一個 UOV 系統。這種多層方法稱為 Rainbow。
HFE、HFE- 和 HFEv-
HFE 型系統非常不同。您應該了解的第一件事是它們在擴展欄位上使用單變數多項式。所以 $ \mathbb{F}_q $ 是基本欄位（如在 UOV 的情況下）。然後選擇任何不可約多項式 $ f(z) \in \mathbb{F}_q[z] $ 學位 $ n $ ，然後你可以辨識多項式的集合 $ \mathbb{F}q[z] / \langle f(z) \rangle $ 程度小於 $ n $ 作為一個新領域，擴展領域 $ \mathbb{F}{q^n} $ ，其運算是多項式加法和多項式乘法模 $ f(z) $ . 每當你有一個向量 $ n $ 基礎欄位上的值，比如說 $ \mathbf{a} \in \mathbb{F}q^n $ ，您可以使用規範嵌入將此值嵌入到擴展欄位中 $ \varphi : \mathbb{F}q^n \rightarrow \mathbb{F}{q^n} : \mathbf{a} \mapsto A = \sum{i=1}^na_iz^{i-1} $ . 特別是，您可以使用變數向量來執行此操作： $ \varphi(\mathbf{x}) = X $ 然後你有一個變數 $ X $ 在擴展欄位上。任何列表 $ n $ 多元多項式 $ \mathbf{x} $ 在基域上映射到一個單變數多項式 $ X $ 在擴展欄位上，反之亦然。
為了生成 HFE 密鑰，請在擴展欄位上選擇一個隨機單變數多項式 $ \mathcal{F}(X) \in \mathbb{F}_{q^n}[X] $ 最多有學位 $ D $ 和形式
$$ \mathcal{F}(X) = \sum_{i} \sum_{j} \alpha_{i,j} X^{q^i + q^j} \enspace . $$ 換句話說，選擇係數 $ \alpha_{i,j} $ 均勻隨機地從 $ \mathbb{F}{q^n} $ 只要 $ q^i+q^j \leq D $ , 並設置 $ \alpha{i,j}=0 $ 否則。按照這個結構 $ \mathcal{F} $ 將保證它映射到基域上的多元二次方程列表。在過去，他們推薦 $ D \approx 1000 $ 但現在我們明白瞭如何用更小的設備來保證 HFE 的安全 $ D $ ，例如 $ D \approx 10 $ ——這只會使計劃更快！接下來，選擇兩個隨機可逆線性變換 $ T, S \in \mathsf{GL}_n(\mathbb{F}_q) $ 它們又是真正的可逆方陣 $ \mathbb{F}_q^{n \times n} $ . 密鑰包括 $ (\varphi, \mathcal{F}, T, S) $ . 公鑰是通過組合這些變換找到的： $$ \mathcal{P} = T \circ \varphi^{-1} \circ \mathcal{F} \circ \varphi \circ S \enspace . $$ 為了簽署文件 $ d $ 帶雜湊 $ \mathbf{h} = \mathsf{H}(d) $ ，簽名者進行如下。首先，他計算 $ Y = \varphi(T^{-1}\mathbf{h}) $ . 然後他使用 Berlekamp 算法分解多項式 $ \mathcal{F}(X)-Y $ 並找到根源 $ {X_i} $ 這使它為零。他選擇這些根之一作為 $ X $ 並繼續計算簽名 $ \mathbf{z} = S^{-1}\varphi^{-1}(X) $ .
為了驗證簽名，驗證者評估公鑰 $ \mathcal{P} $ 在 $ \mathbf{z} $ 並檢查他是否獲得了雜湊 $ \mathbf{h} $ 文件：
$$ \mathcal{P}(\mathbf{z}) \stackrel{?}{=} \mathsf{H}(d) \enspace . $$ 不幸的是，直到這裡描述的 HFE 被證明是不安全的。特別是，它容易受到涉及有效 Gröbner 基算法的直接代數攻擊。這就是為什麼您至少需要一個修飾符 - （減號）或 v（醋）。兩者都使用是有意義的。一個好的右手定則是 $ a + v + \mathsf{log}_2 D \geq 15 $ .
減號意味著從公鑰中刪除了一些多項式。特別是，分解現在涉及一個健忘的運算符 $ \pi : \mathbb{F}_q^n \rightarrow \mathbb{F}_q^{n-a} $ 留下第一個 $ n-a $ 組件完好無損，但其餘部分掉落 $ a $ 那些：
$$ \mathcal{P} = \pi \circ T \circ \varphi^{-1} \circ \mathcal{F} \circ \varphi \circ S \enspace . $$ 為了生成簽名，簽名者必須選擇缺失多項式的值。這沒有問題，因為隨機選擇就足夠了。 醋包括添加 $ v $ 醋變數。在簽名生成過程中，這些醋變數的值也是隨機選擇的，之後剩下要做的就是反轉正常的 HFE 系統。而不是找到線性的解決方案 $ o \times o $ 系統（如 UOV 的情況），現在必須通過分解 HFE 多項式來找到原像。
閱讀材料
在無障礙閱讀材料方面，我可以推薦兩件事。一、丁陽在2009年出版的《後量子密碼學》一書中有一章。二、Ding、Gower 和 Schmidt 有一本書叫《Multivariate Public Key Cryptosystems》。除此之外，相關論文讀起來很好，因為它們包含所有必要的資訊，例如估計安全性。另一方面，它們的密度要大得多。