Fiat-Shamir 變換：通過互動式證明對雜湊輸入的依賴
Peggy 想向 Victor 證明她知道 $ y $ 基於 $ g $ ; 也就是說，她知道 $ x $ 這樣 $ y = g^x \bmod p $ . 一輪互動證明協議包括以下步驟。
- 佩吉隨機選擇 $ k \in \mathbb Z/(p−1)\mathbb Z $ , 計算 $ t = g^k \bmod p $ , 並發送 $ t $ 給維克多。
- 維克多隨機選擇 $ h \in \mathbb Z/(p−1)\mathbb Z $ 並發送 $ h $ 對佩吉。
- 佩吉計算 $ r = (k − hx) \bmod (p − 1) $ 並發送 $ r $ 給維克多。
- 維克多證實 $ t = g^r y^h \bmod p $ .
互動協議可以通過選擇和公開一個抗衝突的雜湊函式轉換為非互動的零知識證明 $ H $ ，並將互動協議的第二步更改為以下內容：Peggy 計算 $ h = H(y, t) $ . 那麼非互動式證明包括 $ (t, h, r) $ , 可以驗證如下：$$ h = H(y, t), \qquad t \stackrel?= g^r y^h \bmod p. $$
- 如果在非互動式證明中雜湊是什麼問題 $ h $ 只取決於 $ y $ ? 那是， $ h = H(y) $ , 證明包括 $ (t, h, r) $ , 可以驗證如下：$$ h = H(y), \qquad t \stackrel?= g^r y^h \bmod p. $$
- 如果在非互動式證明中雜湊是什麼問題 $ h $ 只取決於 $ t $ ? 那是， $ h = H(t) $ , 證明包括 $ (t, h, r) $ , 可以驗證如下：$$ h = H(t), \qquad t \stackrel?= g^r y^h \bmod p. $$
我認為您對菲亞特 Shamir 的驗證是錯誤的。證明包括 $ (h,r) $ 和 $ y $ 無論如何都是公開的，只有關係 $ h = H(y,g^r y^h) $ 被檢查。因此，在您的第一個案例中，證明是微不足道的。您的第二種情況很有趣，因為它對自適應對手並不安全。David Bernhard、Olivier Pereira 和 Bogdan Warinschi 就這個問題發表了一篇論文，該論文也考慮了它在電子投票中的應用。請查看https://eprint.iacr.org/2016/771第 6 頁。
Schnorr 簽名方案是 Schnorr 辨識協議的弱 Fiat-Shamir 變換。在由 G 生成的 q 階組 G 中，它證明了一個指數 x 的知識，該指數 x 滿足已知 X 的方程 X = G^x。將 (x, X) 視為簽名/驗證密鑰對並在雜湊輸入產生知識的簽名。為了創建一個證明，證明者選擇一個隨機的 a ← Zq 併計算 A = G^a。然後他對 A 進行雜湊運算以創建挑戰 c = H(A)。最後他計算 f = a+cx; 證明是對 (c, f)，驗證過程包括檢查等式 c= H(G^f/X^c) 在這裡可以安全地使用弱 Fiat-Shamir 變換，正如之前的分析中所討論的，因為首先選擇公鑰 X，並將其作為輸入提供給試圖進行偽造的對手。然而，如果對手的目標是為他選擇的任何 X 建構一個有效的三元組 (X, c, f)，那麼這個協議不再是知識證明，除非 G 中的離散對數問題很容易。假設確實有是一個提取器 K，它通過與任何提供有效三元組 (X, c, f) 的證明者 P 互動，提取 x = log(baseG)(X)。該提取器可用於求解關於 (G, G) 的離散對數問題的實例 Y，如下所示：使用 Y 作為證明承諾，計算 c = H(Y )，選擇 f ← Zq 並設置 X = ( G^f/y)^(1/c)。由於證明 (Y, c, f) 通過了語句 X 的驗證過程，提取器 K 應該能夠通過與我們的證明者互動來計算 x = log(base G)(X)。我們現在觀察到，通過在 X 的定義兩側取以 G 為底的離散對數，