UOV簽名方案，仿射變換是如何工作的？核心圖和仿射圖的組合產生什麼？
我在理解 UOV 方案的一部分時遇到了困難，我知道它是如何工作的，除了使用仿射變換 T 組合核心映射 F 時，我理解它是一個可逆的方陣？我理解 F 由 o 個油醋多項式組成，其中 o 是油變數的數量。那麼這是否意味著核心映射 F 中的每個多元方程都乘以表示仿射映射 T 的方陣？這個乘法的乘積究竟是什麼？每個多元油醋方程是否被視為 1x1 矩陣並與 T 相乘？我知道映射 T 用於更改系統的基礎，但公鑰應該是一個多元方程系統，所以有人可以幫助澄清核心映射 F 和仿射映射 T 的組成實際上產生了什麼? 如果可能的話，也許舉個小例子？例如，在 o = 2 的情況下，如果我說核心映射 F 由下式給出
$ F = [3x_0^2 - 4x_0x_1 - 4x_1^2 + 8x_0x_2 + 11x_2^2 - 2x_0x_3 - x_1x_3 + 9x_2x_3 + 12x_3^2 + 7x_0x_4 - 11x_1x_4 - 9x_2x_4 - 2x_3x_4 + 3x_0x_5 + 5x_1x_5 + 14x_2x_5 - 11x_3x_5] $
$ [-6x_0^2 + 10x_0x_1 + 10x_1^2 + 13x_0x_2 + 4x_1x_2 + 7x_2^2 - 7x_0x_3 - x_1x_3 - 13x_2x_3 + 4x_3^2 + 6x_0x_4 + 15x_1x_4 - 11x_2x_4 - 12x_3x_4 - 12x_0x_5 + 7x_1x_5 - 13x_2x_5 - 9x_3x_5] $
和仿射變換 $ T $ 給出：
$ \begin{bmatrix} 18 & 23 & 14 & 1 & 6 & 21 \ 24 & 3 & 3 & 0 & 2 & 0 \ 17 & 25 & 2 & 16 & 23 & 8 \ 8 & 21 & 16 & 5 & 1 & 9 \ 14 & 28 & 8 & 17& 12& 12 \ 6 & 24& 18& 19& 3& 1& \end{bmatrix} $
核心映射 F 和映射 T 的公鑰/組成是什麼？
秘密多項式是多元多項式，其油油項的係數為零。您可以將其表示為項的總和，或向量-矩陣-向量積。以你的例子的多項式為例， $ F_0(x_0, \ldots, x_5) = x^2_0 − 4x_0x_1 − 4x^2_1 + 8x_0x_2 + 11x_2^2 − 2x_0x_3 − x_1x_3 + 9x_2x_3 + 12x^2_3 + 7x_0x_4 − 11x_1x_4 − 9x_2x_4 − 2x_3x_4+3x_0x_5+5x_1x_5 + 14x_2x_5 − 11x_3x_5 $ . 使用矢量符號 $ \mathbf{x}^\mathsf{T} = (x_0, x_1, \ldots, x_5) $ 我們可以把這個多項式寫成下面的乘積：
$$ F_0(\mathbf{x}) = \mathbf{x}^\mathsf{T} \left( \begin{matrix} 1 & -4 & 8 & -2 & 7 & 3 \ 0 & -4 & 0 & -1 & -11 & 5 \ 0 & 0 & 0 & 9 & -9 & 14 \ 0 & 0 & 0 & 12 & -2 & -11 \ 0 & 0 & 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} \right) \mathbf{x} \enspace . $$ 矩陣中的係數與項和表示中的係數相同。請注意，在此矩陣表示中，右下角的塊由零組成；這反映了石油乘以石油項的係數為零的事實。另請注意，此矩陣不是唯一的：無論何時 $ F_i(\mathbf{x}) = \mathbf{x}^\mathsf{T} M_{F_i} \mathbf{x} $ 然後對於任何斜對稱矩陣 $ A $ （即這樣 $ A^\mathsf{T} = -A $ ) 你也可以寫 $ F_i(\mathbf{x}) = \mathbf{x}^\mathsf{T}(M_{F_i}+A)\mathbf{x} $ . 特別是，這意味著（假設奇特性）總是可以通過計算選擇中心矩陣是對稱的 $ \frac{1}{2}(M_{F_i}+M_{F_i}^\mathsf{T}) $ . 神秘的線性變換 $ \mathcal{T} $ 也可以用兩種方式表示。你給矩陣表示
$$ T = \left( \begin{matrix} 18 & 23 & 14 & 1 & 6 & 21 \ 24 & 3 & 3 & 0 & 2 & 0 \ 17 & 25 & 2 & 16 & 23 & 8 \ 8 & 21 & 16& 5 & 1 & 9 \ 14 & 28 & 8 & 17 & 12 & 12 \ 6 & 24 & 18 & 19 & 3 & 1 \end{matrix} \right) \enspace , $$ 在這種情況下 $ \mathcal{T}(\mathbf{x}) = T\mathbf{x} $ . 您也可以選擇多項式表示列表，在這種情況下有 6 個多項式， $ \mathcal{T}_0 $ 通過 $ \mathcal{T}_5 $ . 為了說明，第一個多項式由下式給出 $ \mathcal{T}_0(x_0, x_1, x_2, x_3, x_4, x_5) = 18 x_0 + 23 x_1 + 14 x_2 + 1 x_3 + 6 x_4 + 21 x_5 $ . 計算組成 $ F \circ \mathcal{T} $ 您必須首先選擇代表。在多項式表示中，我們有 $ F \circ \mathcal{T} (\mathbf{x}) = F(\mathcal{T}(\mathbf{x})) = F(\mathcal{T}_0(\mathbf{x}), \mathcal{T}_1(\mathbf{x}), \ldots, \mathcal{T}_5(\mathbf{x})) $ . 所以你可以計算 $ F \circ \mathcal{T} $ 從副本開始 $ F $ 然後替換每次出現的 $ x_i $ 和 $ \mathcal{T}(\mathbf{x}) = \mathcal{T}(x_0, x_1, x_2, x_3, x_4, x_5) $ . 但請務必跟踪哪些事件發生 $ x_i $ 作為替換的結果出現，因為它們顯然不應該被替換兩次。
In the matrix representation, we have $ F_i \circ \mathcal{T} (\mathbf{x}) = \mathcal{T}(\mathbf{x})^\mathsf{T} M_{F_i} \mathcal{T}(\mathbf{x}) = (T\mathbf{x})^\mathsf{T} M_{F_i} (T \mathbf{x}) = \mathbf{x}^\mathsf{T} (T^\mathsf{T} M_{F_i} T) \mathbf{x} $ . So a matrix representation $ M_{F_i \circ \mathcal{T}} $ of the composition can be computed just by sandwiching $ M_{F_i} $ between $ T^\mathsf{T} $ and $ T $ , i.e., $ M_{F_i \circ \mathcal{T}} = T^\mathsf{T} M_{F_i} T $ .
To complete the example you started, let’s assume we’re working modulo 31 (because otherwise the numbers get quite large). Then we have
$$ M_{F_0 \circ \mathcal{T}} \cong T^\mathsf{T} M_{F_i} T = \left( \begin{matrix} 6 & 25 & 19 & 19 & 3 & 26 \ 22 & 29 & 3 & 29 & 28 & 2 \ 8 & 15 & 12 & 18 & 6 & 7 \ 28 & 1 & 24 & 17 & 4 & 1 \ 6 & 21 & 18 & 5 & 30 & 23 \ 11 & 23 & 8 & 15 & 5 & 5 \end{matrix}\right) \cong \left( \begin{matrix} 6 & 8 & 29 & 8 & 20 & 3 \ 8 & 29 & 9 & 15 & 9 & 28 \ 29 & 19 & 12 & 21 & 12 & 23 \ 8 & 15 & 21 & 17 & 20 & 8 \ 20 & 9 & 12 & 20 & 30 & 14 \ 3 & 28 & 23 & 8 & 14 & 5 \end{matrix}\right) \cong \left( \begin{matrix} 6 & 16 & 27 & 16 & 9 & 6 \ 0 & 29 & 18 & 30 & 18 & 25 \ 0 & 0 & 12 & 11 & 24 & 15 \ 0 & 0 & 0 & 17 & 9 & 16 \ 0 & 0 & 0 & 0 & 30 & 28 \ 0 & 0 & 0 & 0 & 0 & 5 \end{matrix}\right) \enspace . $$ Here the congruence sign ( $ \cong $ ) indicates that the matrices represent the same quadratic form, i.e., up to addition of skew-symmetric matrices. In other words, after sandwiching them between $ \mathbf{x}^\mathsf{T} $ and $ \mathbf{x} $ they will result in the same polynomial. From the last upper triangular matrix we can read out the representation of the polynomial as a sum of terms, namely $$ F_0 \circ \mathcal{T}(x_0, x_1, x_2, x_3, x_4, x_5) = 6x_0^2 + 16x_0x_1 + 27x_0x_2 + 16x_0x_3 + 9x_0x_4 + 6x_0x_5 + 29x_1^2 + 18x_1x_2 + 30x_1x_3 + 18 x_1x_4 + 25x_1x_5 + 12x_2^2 + 11x_2x_3 + 24x_2x_4 + 15x_2x_5 + 17x_3^2 + 9x_3x_4 + 16x_3x_5 + 30x_4^2 + 28x_4x_5 + 5x_5^2 \enspace . $$ This should be the same result as obtained through the substitution method applied to the polynomial representations.
One more thing: it is a good idea to avoid mixing homogeneous quadratic polynomials (i.e., without linear or constant terms) with affine transforms (i.e., with constant terms) – or vice versa. In other words, whenever your secret polynomials are homogeneous, your secret transforms should be linear; whenever they are inhomogeneous, they should be affine. This guarantees that the public polynomials are (in)homogeneous whenever the secret ones are.