Schnorr 協議的完美零知識？
有人可以解釋（或指向參考）為什麼不能證明Schnorr 協議是零知識嗎？
Schnorr 可以在挑戰時證明零知識 $ e $ 僅限於一個小集合（通常 $ 0 $ 和 $ 1 $ ).
回想一下，在 Schnorr 協議中，證明者知道對數 $ u $ 的 $ y $ 基地 $ g $ . 他選擇一個隨機值 $ r $ , 計算 $ a = g^r $ 並發送 $ a $ 給驗證者。驗證者選擇一個隨機挑戰 $ e $ 從某個集合併將其發送給證明者。證明者計算 $ z = r + ue $ 並將其發送給驗證者。驗證者檢查 $ g^z = a y^e $ .
請記住，（非正式地）協議對於任何驗證者來說都是零知識 $ V^* $ 存在一個模擬器，它可以創建與誠實證明者和誠實證明者之間的對話具有相同分佈的對話 $ V^* $ .
證明草圖：我們的模擬器選擇 $ z $ 均勻地隨機猜測什麼挑戰 $ V^* $ 會發出。根據猜測 $ e $ ，它計算它的初始消息 $ a $ 作為 $ g^z y^{-e} $ . 如果 $ V^* $ 選擇 $ e $ 作為其挑戰，模擬器具有正確的響應，並以正確的分佈創造了挑戰。證明它以機率成功是一個相當容易的練習 $ 1/2 $ ， 什麼時候 $ V^* $ 僅限於回應 $ 0 $ 或者 $ 1 $ .
所以 Schnorr 在挑戰空間很小的時候是零知識（這樣我們可以以很大的機率猜測挑戰），但是在挑戰空間很小的時候 Schnorr 也不是很有用，因為你需要多次執行協議才能確定證明者真的知道這個秘密。
當挑戰空間很大時，上面的模擬器就失敗了。我不記得有證據證明不可能有其他模擬器成功，但不知道這樣的模擬器。這意味著雖然我們不能說 Schnorr 是零知識。另一方面，據我所知，我們不能說它不是零知識。
有零知識的替代概念，例如誠實驗證者零知識。即使挑戰集很大，我們也可以證明 Schnorr 滿足這些概念，並且對於許多應用程序來說這已經足夠了。例如在隨機預言機模型中，我們可以通過 Fiat-Shamir 啟發式獲得非互動式零知識。還有將誠實驗證者零知識轉換為零知識的結構。