關聯多元置換

流行的多元方案是通過將幾個易於反轉的函式/映射作為派生密鑰並將它們的組合作為公鑰來建構的。

簽名時，散列或其填充形式被轉換為一系列多變數變數，並且其在映射下的原像被計算為簽名。然而，目前在多元密碼學中，公鑰加密並不像簽名方案那樣容易建構。

我想知道是否可以執行以下操作：

簽名：

1. 生成一個隨機公共多元系統 $ g() $ ,
2. 生成隨機私有多元系統 $ f() $ 作為私鑰，並發布 $ p = g \circ f $ 作為公鑰。
3. 發布 $ \sigma = f(h) $ 在哪裡 $ h $ 是簽名消息的雜湊值，並驗證 $ g(\sigma) = p(h) $ .

對於密鑰交換：

1. 生成一個隨機公共多元系統 $ g() $ ,
2. 生成隨機私有多元系統 $ f() $ 作為私鑰，並發布 $ p = f \circ g $ 作為公鑰。
3. 客戶端隨機生成 $ x $ 並發送 $ y = g(x) $ 作為公共組件，併計算 $ p(x) $ 作為交換的密鑰。
4. 伺服器計算 $ f(y) $ 作為交換的密鑰。

我的問題是：

1. 不涉及反轉多元方程系統的已知攻擊有哪些？
2. 有沒有類似的提議？如果不是，可能是為什麼？

Faugère 和 Perret（在一種情況下，von zur Gathen）的幾篇論文提供了有效的（即多項式時間）算法來解決功能分解問題：

• 給定：列表 $ u $ 多元多項式 $ H = (h_1, \ldots, h_u) \in (\mathbb{K}[x_1, \ldots, x_n])^u $ 在 $ n $ 某些領域的變數 $ \mathbb{K} $ .
• 任務：找到一個非平凡的分解 $ (F,G) $ 在哪裡 $ F = (f_1, \ldots, f_u) \in (\mathbb{K}[x_1, \ldots, x_n])^u $ 和 $ G = (g_1, \ldots, g_n) \in (\mathbb{K}[x_1, \ldots, x_n])^n $ 這樣 $ H = F \circ G $ .

“非平凡”有多種定義，旨在明確排除病理情況，例如 $ F $ 或者 $ G $ 是恆等或線性變換。可以說，任何聲稱基於多元多項式分解硬度的安全性的密碼系統，例如您的提議，都應該令人信服地爭論為什麼 Faugère*等人的算法。*請勿應用。

具體來說，這些算法使攻擊者能夠獲得 $ f $ 從 $ p $ 在您的提案中，即使沒有使用 $ g $ . 這打破了計劃而不反轉任何東西，因為 $ f $ 表示密鑰。

有一個類似的提議，稱為2R $ ^- $ . 正是 Faugère 和 Perret 研究 FDP 的最初動機導致了該計劃的失敗。

引用自：https://crypto.stackexchange.com/questions/66425