Schnorr 協議：惡意驗證者如何獲勝？
我的問題是關於 Schnorr 協議中的挑戰空間大小。確切地說，我覺得我已經閱讀了所有網際網路（兩次），但我仍然不明白為什麼讓挑戰空間很大是不好的（比如說，為什麼不應該讓 $ \text{Challenge} \in \mathbb{Z}_q $ )
我只對誠實證明者的情況感興趣 $ P $ 和惡意驗證者 $ \tilde{V} $ .
為了解決這個符號，回想一下（一輪）Schnorr 協議具有以下形式：
- 證明者隨機生成 $ r \in \mathbb{Z}_q $ , 計算 $ \text{Commit}=g^r \pmod p $ ，然後發送 $ \text{Commit} $ 給驗證者。
- 驗證者生成 $ m $ 隨機位並形成數字 $ \text{Challenge} $ 從他們那裡（因此 $ \text{Challenge} $ 是隨機數，範圍從 $ 0 $ 至 $ 2^{m} - 1 $ )，然後發送 $ \text{Challenge} $ 證明。
- 證明者計算 $ \text{Response} = r+s \cdot \text{Challenge} \pmod q $ ，然後發送 $ \text{Response} $ 給驗證者。
- 驗證者檢查 $ g^{\text{Response}} = \text{Commit} \cdot y^{\text{Challenge}} \pmod p $
在哪裡 $ y = g^s \pmod p $ 和 $ s $ 是證明者的秘密。
該協議的模擬器如下。
- 該算法生成隨機 $ \text{Response} \in \mathbb{Z}_p $ .
- 算法向驗證者詢問號碼 $ \text{Challenge} $ 並接收它。
- 算法集 $ \text{Commit} = g^{\text{Response}} \cdot y^{-\text{Challenge}} \pmod p $
- 算法附加 $ (\text{Commit}, \text{Challenge}, \text{Response}) $ 到成績單。
我的問題的標準答案是：如果 $ \text{Challenge} $ 是偽隨機的——即，取決於 $ \text{Commit} $ ，比如說，等於 $ \text{hash} (\text{Commit} || M) $ – 這個模擬器協議不能工作，因為在第 2 步它需要知道第 3 步生成的參數。沒有其他已知的適用於此協議的模擬器，所以在惡意驗證者的情況下，沒有模擬器。並且由於任何 ZK 協議都有模擬器，因此得出的結論是惡意驗證者案例不是 ZK。
**問題1。**但是，我仍然不明白惡意驗證者究竟是如何提取一些資訊的。好的，沒有已知的惡意驗證案例模擬器——嗯，它對他有什麼幫助？
**問題 2.*挑戰空間大小如何？毛文波在他們的“現代密碼學”中指出，因此，由於這個模擬器論證， $ \text{Challenge} $ 空間大小不應該很大（不要再次獲取邏輯）*（ $ \text{Challenge} \in \mathbb{Z}_q $ 被禁止）並聲明最佳選擇是 $ \text{Challenge} \in [0, \log_2 p) $ （或者，等效地， $ m = \log_2 \log_2 p $ ）。為什麼會有這麼奇怪的值？
我將首先回憶（誠實驗證者）零知識屬性的實際含義（非正式地）。
在誠實驗證者零知識的情況下，協議在與誠實驗證者互動時只是零知識。這是以模擬器對驗證器具有黑盒訪問但對驗證器的所有輸入磁帶（包括它的隨機磁帶）具有完全控制權的方式建模的，因此驗證器的行為具有確定性。實際上，這是通過向模擬器提出挑戰來建模的，然後模擬器需要計算整個對話的副本（即使挑戰來自整個 $ \mathbb{Z}_q $ - 您可以輕鬆檢查 Schnorr 協議，這正是您在問題中提供的模擬器）。
然而，零知識更棘手。在這種情況下，模擬器對潛在的惡意驗證者俱有黑盒訪問權限，因此您必須建構一個適用於任何惡意驗證者策略的模擬器。現在你能做些什麼來獲得 Schnorr 協議的零知識呢？好吧，模擬器可以做的是在計算承諾之前猜測驗證者的挑戰，然後發送承諾並獲得挑戰。如果猜測是正確的，那麼成績單將是一個接受成績單。但是，如果猜測不正確，那麼模擬器將不得不重試。現在，使用整個空間 $ \mathbb{Z}_q $ 使模擬器正確猜測的機率呈指數級小，因此您無法提出如此高效的模擬器。你能做的就是減少挑戰空間。如果你選擇挑戰空間 $ {0,1} $ 你的模擬器會以機率正確猜測 $ 1/2 $ . 現在您必須按順序多次重複 porotocol 並僅保留您猜測正確的成績單（請注意，單次互動會給您提供一個不可靠的協議）。現在你可以證明，如果你想要一個健全性錯誤 $ 1/2{^t} $ 你必須執行模擬器預期的數量 $ 2t $ times 為您提供預期的多項式時間模擬器。現在，很明顯，你可以讓挑戰空間“稍微”大一些（只要它不是指數級的）並且可以進行數學運算（這是毛文博所討論的）。但是，要調整穩健性以使惡意證明者獲勝的機會成倍減小，使用後一種方法，您必須順序執行許多協議（並行不安全，因為 Schnorr 不是同時安全的），這使得它在實際應用中效率很低應用程序（您可能想研究使用 Fiat Shamir 啟發式將誠實驗證者零知識證明轉變為非互動式零知識證明）。
現在回到你的問題：
**Q1：**想想誠實驗證者零知識但驗證者不誠實的模擬策略。例如，驗證者可以以某種方式根據協議的第一輪（承諾）提出挑戰。然後在它知道挑戰之後，驗證者倒回證明者並再次執行它，使得第一輪相同，但惡意驗證者很聰明，現在發送另一個不同的挑戰。現在，Schnorr 協議應該很容易弄清楚惡意驗證者是如何從證明者那裡提取秘密的（這正是 $ \Sigma $ 協議已定義）。對於 Schnorr，你可以觀察到你有 $ Response_1 = r + s\cdot Challenge_1 $ 和 $ Response_2 = r + s\cdot Challenge_2 $ 你現在可以解決這個秘密 $ s $ 在 $ \mathbb{Z}_q $ .
**Q2：**這正是上面討論的最後一段。為什麼會有這麼奇怪的值？因為它足夠小以使模擬策略起作用。
也許您應該查看涵蓋 Sigma 協議、誠實驗證者零知識等主題的替代講義或書籍。