訂單未知時的 Sigma 協議
在下面的論文（第 5 頁）中，他們證明了三元組 $ \left(g,b_{i-1},b_{i}\right) $ 形式為： $ \left(g,g^{x},g^{x^{2}}\right) $ 對於一些 x。
論文中的相關文字如下：
他們說該協議基於元組是 DH 元組的經典證明，但我不同意，因為我認為他們遺漏了一個基本問題：
在 DH 元組的 ZKP 中，g 的順序是已知的，但是，在這裡 - g 的順序是未知的，因為它可能會洩露關於 $ \phi(N) $ .
我的目標是將論文中的協議轉換為 Sigma 協議，使其成為非互動式的。
我試圖為論文中的協議建構一個見證提取（以證明特殊的穩健性），但我經常碰壁，我必須知道 g 的順序：
所以假設我們有 2 個不同的成績單具有相同的 $ z_{i},w_{i} $ 但不同的挑戰 $ c_{i},c’_{i} $ 驗證者接受。
因此，以下等式成立：
$ (1)~,g^{y_{i}}\cdot b_{i-1}^{-c_{i}}=z_{i} $
$ (2)~b_{i-1}^{y_{i}}\cdot b_{i}^{-c_{i}}=w_{i} $
$ (3)~ g^{y_{i}’}\cdot b_{i-1}^{-c’{i}}=z’{i} $
$ (4)~ b_{i-1}^{y’{i}}\cdot b{i}^{-c’{i}}=w’{i} $
從第一個方程和第三個方程我們得到：
$ g^{y_{i}}\cdot b_{i-1}^{-c_{i}}=g^{y_{i}’}\cdot b_{i-1}^{-c’{i}} $ ， 因此 $ g^{y{i}-y’{i}}=b{i-1}^{c_{i}-c’_{i}}. $
但是，現在我被卡住了，因為我找不到 $ \left(c_{i}-c’_{i}\right)^{-1}mod,\phi(N) $ 因為我不知道 $ \phi(N) $ 首先（作為一個有效的證人提取者），我也不能做某種 $ gcd(a,b)=1 $ 詭計 。
同時，本文暗示在未知順序的組中工作時可能無法建構 Sigma 協議。
然而，定時送出論文中的協議認為，每個 ZKP 的 $ (g, g^x, g^{x^2}) $ 三元組的健全性可以忽略不計，因此它似乎具備成為 Sigma 協議候選者的所有先決條件。
我錯過了什麼？
你如何在沒有見證人提取的情況下從論文中證明 ZKP 的健全性（這似乎是不可能的）？
（順便說一句 - 我知道一篇論文以不同的方式證明了這一點，我只想了解我在這裡遺漏了什麼）。
提前謝謝了。
你如何在沒有見證人提取的情況下從論文中證明 ZKP 的健全性（這似乎是不可能的）？
這是完全可能的，你幾乎已經做到了！你是對的，當你想建立知識證明時，未知的順序組會讓你的生活變得非常複雜——我們知道這個方向的結果（你引用的那個）——儘管應該提到的是，一旦你使用CRS（例如我們在本文中所做的）。
但是如果你只想要健全性而不是更強的知識提取，你就不需要計算這個繁瑣的 $ (c_i-c’_i)^{-1}\bmod \varphi(n) $ .
讓 $ z_i \gets y_i - y’_i $ 和 $ d_i \gets c_i - c’_i $ .
從等式（1）和（3），你得到 $ g^{z_i} = b_{i-1}^{d_i} $ .
從等式（2）和（4），你得到 $ b_{i-1}^{z_i} = b_{i}^{d_i} $ .
因此，在數學上必然存在一個指數 $ x $ 這樣 $ g^x = b_{i-1} $ 和 $ b_{i-1}^x = b_i $ . 的確，這 $ x $ 等於 $ z_i\cdot d_i^{-1}\bmod \varphi(n) $ . 可以肯定的是，您無法計算它 - 但它存在的事實足以證明協議的合理性！換句話說， $ (z_i, d_i) $ 仍然構成該詞在該語言中的證明，只要證明者產生可接受的證明，您就可以提取該證明。該證書不是目標關係的見證人，但它的存在仍然足以保證該語言的成員資格。
回答評論中的問題
你能指出我們可以用他們的協議提取的證人嗎？（如何？ ：-） ）
考慮以下關係 $ R $ : $ (a,b,c) $ 如果存在值，則在語言中 $ (x,y) $ 這樣 $ a^x = b^y $ 和 $ b^x = g^y $ . 那是， $ R((a,b,c), (x,y)) $ 返回 1 iff $ a^x = b^y $ 和 $ b^x = g^y $ （和 $ 0 $ 否則）。這種關係的見證人是一對 $ (x,y) $ .
首先，觀察這個關係擷取的語言與元組的語言完全一樣 $ (a,b,c) = (g,g^z,g^{z^2}) $ . 不同之處在於，在第一種情況下，您作為見證人看到的是一對 $ (x,y) $ 這樣 $ a^x = b^y $ 和 $ b^x = g^y $ ，而在第二種情況下，它是單個指數 $ z $ 這樣 $ a^z = b $ 和 $ b^z = c $ . 這對應於不同的關係 $ R’ $ 對於相同的語言： $ R’((a,b,c), z) = 1 $ 當且當 $ a^z = b $ 和 $ b^z = c $ .
在上面的協議中，您確實提取了一對 $ (x,y) $ , 它是根據關係的見證人 $ R $ （因此足以證明該語言成員資格證人的知識 - 但與您想到的第二個關係相比，證人關於不同關係的證人， $ R’ $ ）。確實，剛剛設置 $ y_i - y’_i $ 成為 $ x $ 和 $ c_i - c’_i $ 成為 $ y $ ，並且您擁有您提取的證人（因為提取器當然知道 $ y_i, y’_i, c_i, c’_i $ ).
但是，這種健全性的證據是什麼？為了證明這一點，您需要證明，如果作弊證明者可以使驗證者相信一對不在該語言中，在該語言中 - 那麼它也可以做一些棘手的事情。你能說出你將如何證明這樣的事情嗎？
您對我們使用一些難題來證明計算合理性的情況感到困惑。如果協議僅在計算上是可靠的，那麼證明將如下所示：假設該詞不在該語言中，並且證明者設法提供令人信服的成員資格證明。然後我可以使用這個證明器來解決一個難題。
在這裡，我們處於一個證明更加直接的場景：可靠性是無條件的。這意味著我不必證明可以使用證明語言以外的詞的成員資格的證明者來解決難題：我可以直接證明，如果任何證明者提供了成功的成員資格證明，則必然，該詞具有在語言中。不涉及任何難題。
正式拼寫（多一點）：
**健全性：**如果不存在惡意證明者，上述協議是無條件健全的 $ P $ （即使有無限的力量）和一句話 $ (a,b,c) $ 語言之外 $ L = {(a,b,c) = (g,g^z,g^{z^2})} $ 這樣 $ P $ 提供令人信服的會員證明 $ (a,b,c)\in L $ .
**健全性證明：**修正任何詞 $ (g,b_{i-1},b_i) $ , 和任何證明者 $ P $ . 使用倒帶；以不可忽略的機率，我們得到值 $ (y_i, y’i, c_i, c’i) $ 滿足你的問題的方程（1）到（4）。但這意味著存在價值 $ (z_i,d_i) $ 這樣 $ g^{z_i} = b{i-1}^{d_i} $ （由 1 和 3）和 $ b{i-1}^{z_i} = b_{i}^{d_i} $ （由 2 和 4）。但是現在，這兩個等式意味著存在一些價值 $ z $ 這樣 $ (g,b_{i-1},b_i) = (g, g^z, g^{z^2}) $ . 這個 $ z $ 實際上等於 $ z_i/d_i \bmod \varphi(n) $ : 它存在，但你無法計算它。但既然它存在，我們可以得出結論，這個詞 $ (g,b_{i-1},b_i) $ 實際上屬於該語言 $ L $ ！換句話說：每次證明者產生一個令人信服的證明 $ (g,b_{i-1},b_i) \in L $ ，那麼確實是這樣 $ (g,b_{i-1},b_i) \in L $ ——因此，證明者不可能產生一個可接受的證明 $ (g,b_{i-1},b_i) \notin L $ ，這證明了穩健性。
如果證明者猜到 $ c_i $ 驗證者會發送，它可以發送 $ z_i = g^{y_i}\cdot b_{i-1}^{-c_i} $ 和 $ w_i = b_{i-1}^{y_i}\cdot b_{i}^{-c_i} $ 並且驗證者會接受任何 $ b_i,b_{i-1} $ 不？現在如果它可以做一次，它可以做兩次，有機率 $ 1/R^2 $ 這可以忽略不計但仍然不完全是𝑝𝑟𝑜𝑣𝑒𝑟𝑐𝑜𝑛𝑣𝑖𝑛𝑐𝑒𝑠𝑣𝑒𝑟𝑖𝑓𝑖𝑒𝑟⇒ $ (g,b_{i-1},b_i) \in L $ ……我錯過了什麼？
您建議的上述攻擊不起作用，原因如下：要執行攻擊，您必須猜測 $ c_i $ 並且寄出 $ z_i = g^{y_i}\cdot b_{i-1}^{-c_i} $ 和 $ w_i = b_{i-1}^{y_i}\cdot b_{i}^{-c_i} $ . 然後，你說“如果它可以做一次，它可以做兩次，有機率 $ 1/R^2 $ ”。但這不是真的！記住，當回滾協議時，相同的第一個流被重複用於兩次回滾。因此，證明者沒有機會創建“另一個”對 $ (z_i, w_i) $ 通過猜測 $ c’_i $ .
現在，上述可靠性證明可能會失敗仍然是真的，因為有一些機率，當你隨機抽樣 $ c’_i $ ，它等於 $ c_i $ ; 當這件事發生時， $ c_i-c’_i = 0 $ ，因此不再保證該詞在該語言中。
但事實上，這種微不足道的攻擊適用的唯一原因是因為為了可讀性，我決定保持簡單。如果您想確切了解為什麼這個問題不是一個真正的問題，這裡有一個關於如何進行完全正式的安全分析的高級草圖：
完全正式證明的草圖
假設有一個證明者 $ P $ 那會破壞健全性。（統計）健全性正式表示的是，對於任何（可能是無限的）候選證明者 $ P $ 選擇一個詞 $ X $ 並與驗證者互動 $ V $ , 的機率 ( $ X \notin L $ ） 和 （ $ V $ 確信）必須可以忽略不計。所以假設一個可以破壞可靠性的證明者意味著假設存在一個 $ P $ 輸出一個詞 $ X $ 並與誠實的驗證者互動 $ V $ , 這樣
$ \mathsf{Pr}[X \notin L \wedge V \text{ is convinced}] \geq \varepsilon, $
對於一些不可忽略的數量 $ \varepsilon $ （警告：在定義“可忽略”和“不可忽略”時，我再次在這裡隱藏了一些關於確切量詞的技術細節）。
因此，我們所擁有的是一個輸出單詞的證明者 $ X $ 並與之互動 $ V $ 這樣它同時發生 $ X $ 不在 $ L $ 和 $ V $ 以不可忽略的機率接受互動 $ \varepsilon $ .
第一個問題是： 我們如何從這個證明器中提取滿足問題中方程（1）到（4）的值？
我之前給出的答案只是“我們使用倒帶”，但這並不能解釋它為什麼起作用。證明者的單次執行輸出一個單詞 $ X $ 和成績單 $ T $ 他與他的互動 $ V $ , 這樣 $ X \notin L $ 和 $ V $ 接受，有機率 $ \varepsilon $ . 但是我們想要的是得到兩個接受的成績單，關於同一個詞 $ X \notin L $ ，也相對於第一流。
事實證明，有一個簡單的引理，即分裂引理，可以完全做到這一點——例如參見我論文的第 10 頁（我已經在這個答案中提到過）。這個引理表明我們可以修復單詞和第一個流程，並重複協議的其餘部分兩次；仍然，這個詞 $ X $ 不會在 $ L $ 然而兩個成績單（具有相同的第一個流程，但不同的第二個流程）將被接受，至少總體機率 $ \varepsilon^2/4 $ . 這不是太難，但也不是完全微不足道的——這是一個很好的機率練習。
現在，如果我們找到了上面的兩個轉錄本，那麼我們可以完全按照我之前所說的那樣做，並使用等式（1）到（4）來驗證 $ X $ 必須在語言中，因此達到矛盾（因此這樣的作弊證明者 $ P $ 不存在）。請注意，我們不需要以機率 1 找到這些轉錄本：我們可以以一些不可忽略的機率找到它們的簡單事實已經足以解決矛盾。
另一種查看方式是提取見證（對於關係 $ R $ ) 通常不能通過單次執行協議來完成：您需要平均重複上述過程 $ 4/\varepsilon^2 $ 次（多項式）通過上述過程成功提取見證。這個問題正是知識證明的標准定義沒有說證人可以在嚴格多項式時間內提取，而是在預期多項式時間內提取的原因。在這裡，我們可以成功提取見證人，但提取過程的執行時間只會是 $ O(4/\varepsilon^2) $ 在期待中。