多元密碼學：仿射變換 T 的安全性
在這個問題中，我想討論最後一次轉換的安全性 $ T $ 用於建構 MV 方案。MVCrypto 基於求解多項式方程組，但最終，這些多項式是由以下的線性組合構成的 $ T $ 和表示單變數多項式的向量 $ F_{q^n} $ 係數在 $ F_q[x_1,\cdots, x_n] $ . 下面的結構說明了一個典型的描述，其中 $ \alpha : F_{q^n} \mapsto F_{q^n} $ 是改變係數的變換函式（即松本今井） $ x’ $ 從多元線性多項式到多元非線性多項式。注意這裡 $ v_s,v_t=[0]_n\in F_q^n $ . $$ \begin{equation} S,T \in F_q^{n \times n}, \quad x=(x_1,\dots,x_n)\in F_q^n \ x’=S\cdot x \y’=\alpha(x’)\y=T\cdot y' \end{equation} $$
矩陣非常有用，因為我們可以表示 $ F_{q^n} $ 作為 $ F_q^n $ : n 維向量空間 $ F_q $ . 所以 $ x’ $ 可以看作是一個多項式，其係數是線性組合 $ x $ .
$$ x’= \sum_{i=1}^{n}(\sum_{j=1}^{n} S_{i,j}\cdot x_j)y^{i-1} $$
攻擊者有 $ n $ 多元多項式及其對 $ x=(x_1,\cdots,x_n) $ . 如果他發現了轉變 $ T $ ，他可以嘗試反轉 $ \alpha $ 獲得 $ x’ $ 最後， $ x $ . 我的直覺告訴我，攻擊者可以找到一對 $ z\in F_q^n, T’\in F_q^{n\times n} $ st 滿足 $ T’\cdot z = y $ . 例如，考慮以下情況 $ V=F_5^2 $ :
$ T=\left( \begin{array}{cc} 1 & 2 \ 3 & 1 \ \end{array} \right) $ $ y’=(x_1x_2-1,x_1^2x_2+3) $
$ T\cdot y’ = y = (x_1x_2+2x_1^2x_2, 3x_1x_2+x_1^2x_2) $
恢復很簡單 $ T’=T $ 和 $ z=(x_1x_2,x_1^2x_2) $ 自從 $ y $ 包含的係數是 $ n $ 相同的總和 $ n $ 因素，這裡 $ n=2 $ . 注意 $ z\neq y’ $ 但在這種情況下，直到找到正確的“蠻力”並不難。
編輯：重要的是你注意到 $ S $ 和 $ T $ 在我的範例中互換， $ S $ 是第一個仿射變換和 $ T $ 是最後一個，然而，在文學中你發現這是相反的。所以要注意的是，這個問題是關於構造中應用的最後一個變換。
**問題：**是否有任何資訊描述了這種結構的反轉，而不是通過求解多項式方程。但是反轉地圖？
自從我發布這個問題將近一年後，那時我才開始研究該領域。現在我可以回答自己了：
兩種仿射變換的安全性 $ (T,S) $ 依賴於多項式同構中定義的IP2假設。另外，如果私有多項式 $ \mathcal{F} $ 已知還有其他含義，例如發現 $ T $ 或者 $ S $ 將揭示另一個仿射變換。
這是，任何多元方案，其中 $ F,S $ 或者 $ F,T $ 已知使我們有能力打破它。什麼時候 $ F $ 是未知的，通常我們可以得到 $ T\cdot S $ 如果兩者都是線性變換而不是仿射，則作為矩陣，並且 $ F $ 是單位矩陣。從那一刻起，在我的書房裡，沒有其他東西可以從這裡提取出來。
關於IP1，它可以在 $ F $ 是已知的，或者當 $ F $ 通過查詢神諭是未知的 $ n $ 使用規範向量的時間 $ \overrightarrow{e_i} $ .
除了其他剝離技術 $ T,S $ 存在，即：當特徵不存在時 $ 2 $ 並且兩個變換都是線性的。
我發現還有更多未發表在文獻中的工作，即：矩陣的特殊結構 $ S $ 以我們可以恢復的方式使私有多項式不變 $ T $ ，以及更多觀眾必須等待的技巧。