“子組中的元素”協議的 ZK 證明
考慮以下協議 $ P $ 和 $ V $ :
注意：乘法組是 $ Z_p^* $ 和 $ p $ 是素數。
注意：該協議用於證明 $ x \in \langle \alpha \rangle $ .
輸入到 $ P $ 和 $ V $ : 一個素數 $ p $ 和 $ \alpha, x \in Z_p^∗, k = \log_2(p) $ .
輸入到 $ P $ : $ y $ ， 以便 $ \alpha^y = x \bmod p $ .
協議：
$ V $ 檢查 $ \gcd(x, p) = \gcd(\alpha, p) = 1 $ 如果不是這種情況，則拒絕。
$ P $ 選擇 $ r $ 隨機在 $ [0, p - 2] $ , 並發送 $ a = \alpha^r \bmod p $ 至 $ V $ .
$ V $ 選擇 $ b $ 隨機在 $ {0, 1} $ 並發送 $ b $ 至 $ P $ .
$ P $ 發送 $ z = (r + by) \bmod (p-1) $ 至 $ V $ .
$ V $ 檢查 $ \alpha^z = ax^b \bmod p $ . 如果OK，則接受，否則拒絕。
問題：
我已經證明了協議的完整性和可靠性。但是，我需要證明它是零知識。
為此，我考慮一個模擬器扮演的角色 $ P $ .
我知道，我可以使用Rewinding Lemma，所以我考慮了一個完美的誠實驗證模擬器。
我嘗試遵循圖同構協議的 ZK 證明，但是，我被卡住了。
如果我不知道如何回應 $ b=1 $ ，因為我不能假設模擬器知道 $ y $ . 這 $ b=0 $ 案子很簡單。
有人可以幫我嗎？
模擬器不知道 $ y $ ，但他確實知道 $ x $ ，並且提前知道哪個 $ b $ 驗證者將選擇。你已經知道模擬什麼時候 $ b=0 $ . 另一種情況，當模擬器知道驗證者會問 $ b=1 $ ，模擬器選擇 $ r $ 隨機發送 $ a = \alpha^r/x $ 代替 $ \alpha^r $ 給驗證者。然後，模擬器發送 $ z = r $ . 您可以輕鬆地看到檢查將通過： $ \alpha^z = \alpha^r = (\alpha^r/x)\cdot x = ax = ax^b $ .
編輯：稍微完善一下，您提供的協議是誠實驗證者零知識，這意味著只要驗證者不偏離規範，它就是零知識。在這種情況下，由於模擬器被給予驗證者的隨機磁帶作為輸入，他知道哪個 $ b $ 驗證者會提前選擇。
如果您想處理惡意驗證者，以獲得完全零知識的協議，則必須修改協議，例如通過要求驗證者在協議開始之前送出他的挑戰（如果您想了解更多關於這一點的詳細資訊，隨意問）。