與黑盒零知識的順序自組合性矛盾？
簡而言之：眾所周知，黑盒零知識協議是順序自組合的。然而，Goldreich 和 Krawczyk$$ GK90 $$提出一個被證明是零知識的協議（對我來說是黑盒方式），但不是順序自組合的。這對我來說似乎是一個悖論。我在下面詳細說明這個問題。
零知識證明的概念最初定義在$$ GMR85 $$. 但是這個定義在順序自組合下不是封閉的。為了解決這個問題（並尋求更合適的定義）$$ GO94 $$提出了黑盒 ZK 和輔助輸入 ZK 並顯示了這些定義之間的關係。在這個問題中，我將使用以下縮寫來簡化展示。
- GMR：滿足ZK原始定義的協議類$$ GMR85 $$
- BBZK：屬於黑盒零知識的協議類，如$$ GO94 $$
- AuxZK：作為輔助輸入 ZK 的協議類，如$$ GO94 $$
$$ GO94 $$證明以下關係：BBZK $ \subsetneq $ 輔助ZK $ \subsetneq $ GMR。 $$ GO94 $$也證明了 AuxZK 在順序自組合下是封閉的。 在$$ GK90 $$, 一個滿足 GMR 但不是順序自組合的協議被構造為將 AuxZK 與 GMR 分開。但是，該協議對我來說似乎是 BBZK。我的理解不應該是正確的，因為 BBZK $ \subsetneq $ AuxZK（因此 BBZK 協議也必須是順序自組合的）。所以，我覺得我一定錯過了證明的一些重要方面。
我知道這可能不是一個有價值的問題，因為 ZK 的定義已經很成熟了，但它有點困擾我……所以如果有人能糾正我的誤解，我將不勝感激。
在下文中，我將簡要描述該協議並解釋為什麼我認為它是 BBZK。
該協議基於 P 規避偽隨機集。粗略地說，P-evasive 偽隨機集合是一系列集合 $ {S_n}_n $ 這樣 $ S_n $ 和 $ {0,1}^{4n} $ 在計算上無法區分，任何 PPT 對手都可以在 $ S_n $ 只有可忽略的機率（可忽略的函式是 $ n $ ，可以視為安全參數）。
他們還需要一個硬布爾函式 $ K(\cdot) $ 這樣語言 $ L_K = {x: K(x) = 1} $ 不在 BPP 中。
使用上述兩個工具（它們的存在在
$$ GK90 $$)，該協議的工作原理如下，以用簡單的語言證明一個陳述 $ x \in L = {0,1}^* $ （即，每個二進製字元串 $ x $ 是真實的陳述）：
- 第一輪： $ V $ 發送 $ s $
- 第二輪：如果 $ s \in S_n $ , $ P $ 發送 $ K(x) $ ; 否則， $ P $ 發送一個 $ s_0\in S_n $ .
- 驗證者的決定： $ V $ 總是接受。
完整性和可靠性是顯而易見的。這個協議不是順序自組合的：考慮它的兩個順序執行。 $ V^* $ 可以只使用 $ s_0 $ （他從第一次執行中獲得）作為第二次執行中的 Round-2 消息來學習 $ K(s_0) $ ，難到沒有PPT模擬器能模擬出來。
**零知識：*為了證明它是 GMR 零知識（在獨立設置中），他們建構了一個模擬器，該模擬器總是從 $ {0,1}^{4n} $ 作為模擬的第 2 輪消息。通過偽隨機性 $ S_n $ ，該模擬在計算上與（單次）實際執行無法區分。唯一有問題的情況是 $ V^ $ 選擇一個 $ s\in S_n $ 作為他的第一輪消息，模擬器需要計算 $ K(s) $ ，這是不可行的。但這只會以微不足道的機率發生，因為 $ S_n $ 是 P 規避的。
我的問題是：在上面的Zero-Knowledge證明中，模擬器似乎只使用 $ V^* $ 以黑盒方式，即該協議看起來像 BBZK。如果是這樣，這與 BBZK 是順序自組合的事實相矛盾。希望有人能糾正我的誤解。謝謝！
參考：
- **$$ GMR85 $$**S Goldwasser、S Micali 和 C Rackoff。1985. 互動式證明系統的知識複雜性。在第十七屆年度 ACM 計算理論研討會論文集 (STOC ‘85)。ACM，紐約，紐約，美國，291-304。
- **$$ GK90 $$**Goldreich、Oded 和 Hugo Krawczyk。“關於零知識證明系統的組成。” 自動機、語言和程式國際學術討論會。施普林格，柏林，海德堡，1990。
- **$$ GO94 $$**Goldreich、Oded 和 Yair Oren。“零知識證明系統的定義和屬性。” 密碼學雜誌 7.1 (1994): 1-32。
這個答案來自@Maeher 的評論。所有的功勞都應該歸功於 Maeher。另外，感謝@Occams_Trimmer 引起了對這個問題的更多關注。
Maeher 展示了一個不誠實的驗證者 $ V^_s $ 問題中的模擬技術失敗。 $ V^_s $ 有價值 $ s \in S_n $ 裡面硬編碼。然後它忽略它的隨機磁帶並簡單地發送硬編碼值 $ s $ 作為第一輪消息。所以模擬器 $ M^{V^_s} $ 被迫回應 $ K(s) $ , 任何 PPT 機器都無法計算。因此， $ M^{V^_s} $ 無法成功完成模擬。
請注意，上述論點中有一個隱含但重要的方面： $ V^_s $ 必須是不均勻的。否則不能有 $ s $ 當安全參數增長時在內部進行硬編碼。換句話說，上述攻擊只有在我們考慮 ZK 屬性對抗非統一對手時才會發生。但是 GMR 定義只保證 ZK 對抗統一的對手（PPT 圖靈機）。因此，ZK 屬性 wrt GMR 定義的證明（在上述問題中）仍然通過。但是，AuxZK 的定義本質上保證了針對非均勻性的安全性 $ V^ $ （因為 $ V^* $ 現在有一個輔助磁帶，任何不統一的建議都可以放在這個輔助磁帶上）。BBZK 也是如此，因為它是 AuxZK 的子集。因此，如果要證明黑盒零知識屬性，問題中的證明將失敗。
綜上所述，雖然問題中的證明是以黑盒方式完成的，但僅針對統一的對手，不足以給我們BBZK（甚至是AuxZK）。感謝 Maeher 明確了這一點。