Fiat-Shamir 範式和分叉引理
我正在閱讀 Pointcheval 和 Stern 以及 Bellare 和 Neven 關於分叉引理的證明。論文通過應用引理討論了數字簽名的安全證明。似乎還提到了同樣的證明想法，用於展示 Fiat-Shamir 轉換的互動式證明系統在隨機預言模型中是合理的。
我不確定我是否理解為什麼分叉引理暗示 Fiat-Shamir 轉換的非互動式協議使用隨機預言是可靠的，或者僅將其應用於可靠是必不可少的。有很多關於在普通模型中實例化的論文，但這超出了我現在想要理解的範圍。
如果有人能解釋這種聯繫，或者指出一些很好的參考資料，我們將不勝感激。
讓我們回顧一下重要的定義。證明系統 $ (\mathsf{P}, \mathsf{V}) $ 對於NP語言 $ \mathcal{L} $ 是一對互動式圖靈機，其中證明者 ( $ \mathsf{P} $ ) 和驗證者 ( $ \mathsf{V} $ ) 接收一個公共輸入 $ \ell \in {0,1}^* $ 並且證明者收到額外的輸入 $ w \in {0,1}^* $ 那是見證 $ \ell $ ,即, 關係 $ \mathcal{R}\mathcal{L} $ 由NP語言定義 $ \mathcal{L} $ 滿足 $ \mathcal{R}\mathcal{L}(\ell,w) = 1 $ . 證明者和驗證者交換一些消息，最後驗證者輸出一個比特，表示為 $ \mathsf{out}_\mathsf{V}(\langle\mathsf{P}(\ell,w)\leftrightarrow\mathsf{V}(\ell)\rangle) $ ，表示驗證者是接受證明（1）還是拒絕證明（0）。如果驗證者的消息由純的、未處理的隨機性組成，則證明系統是公共幣。在這種情況下，Fiat-Shamir 啟發式表示，通過將這些隨機選擇的消息替換為直到該點之前所有消息的雜湊值，不會失去任何安全性。（並且由於有證據證明這一事實，儘管在隨機預言模型中，將其稱為啟發式在技術上是錯誤的——因此更常見的片語“Fiat-Shamir 變換”。）
一種語言的證明系統是完整的 $ \mathcal{L} \in $ 如果誠實的證明者有可能成功，則為NP，即 $ \forall \ell \in \mathcal{L} , . , \forall w \in {0,1}^* , . , \mathrm{Pr}[\mathcal{R}\mathcal{L}(\ell,w) = 1 , \Rightarrow , \mathsf{out}\mathsf{V}(\langle\mathsf{P}(\ell,w) \leftrightarrow \mathsf{V}(\ell)\rangle) = 1] \geq 1 - \mathsf{negl}(\lambda) $ , 對於某些函式 $ \mathsf{negl}(\lambda) $ 這在安全參數中可以忽略不計。
如果成績單，即所有交換消息的列表，則證明系統是零知識的，表示為 $ \langle\mathsf{P}(\ell,v) \leftrightarrow \mathsf{V}(\ell)\rangle $ , 與某些模擬器的輸出無法區分 $ \mathsf{S} $ 接收字元串 $ \ell $ 但不是證人 $ w $ . 正式地， $ \forall \ell \in \mathcal{L} , . , \forall w \in {0,1}^* , . , \mathcal{R}_\mathcal{L}(\ell, w) = 1 , \Rightarrow , \langle\mathsf{P}(\ell,w) \leftrightarrow \mathsf{V}(\ell)\rangle \sim \mathsf{S}(\ell) $ . 這裡 $ \sim $ 表示您最喜歡的機率分佈不可區分性的概念，即完美、統計或計算。
關於健全性，重要的是要明確區分兩個相關概念。首先，如果沒有（適當有界的）對手，證明系統具有明顯的可靠性 $ \mathsf{A} $ 可以使驗證者接受非語言成員： $ \forall n \not \in \mathcal{L} , . , \mathrm{Pr}[\mathsf{out}\mathsf{V}(\langle \mathsf{A}(n) \leftrightarrow \mathsf{V}(n)\rangle) = 1] \leq \mathsf{negl}(\lambda) $ . 為了說明起見，我將這個概念稱為簡單的健全性，但文獻將其簡稱為健全性。其次，如果存在（適當有效的）提取機，則證明系統具有知識健全性 $ E $ 可以從任何成功的證明偽造者中提取並輸出有效的證人 $ \mathsf{B} $ , 是否接收見證 $ w $ 或不。正式地， $ \forall \ell \in \mathcal{L} , . , \mathrm{Pr}[\mathsf{out}\mathsf{V}(\langle\mathsf{B}(\ell) \leftrightarrow \mathsf{V}(\ell)\rangle) = 1 , \Rightarrow , \mathcal{R}_\mathcal{L}(\ell, \mathsf{E}^\mathsf{B}()) = 1] \geq \mathsf{noti}(\lambda) $ ， 在哪裡 $ \mathsf{noti}(\lambda) $ 是安全參數的一些值得注意的功能。這裡 $ \mathsf{E}^\mathsf{B} $ 意味著算法 $ \mathsf{E} $ 具有黑盒訪問權限 $ \mathsf{B} $ ， 意思是 $ \mathsf{E} $ 被允許與 $ \mathsf{B} $ 通過具有證明系統格式的消息，但 $ \mathsf{E} $ 不允許查看或更改 $ \mathsf{B} $ 的狀態。文獻還將這個概念稱為證人可提取性，並且令人困惑的是，它是健全的。具有此屬性的證明系統是知識證明。
對於許多語言來說，知識的健全性是相關的屬性，而簡單的健全性則不是。例如，考慮離散對數知識的標準 Schnorr 證明，其中指數知識 $ x \in \mathbb{Z}_{|\mathbb{G}|} $ 被證明是這樣的 $ x $ 發送 $ g \in \mathbb{G} $ 至 $ X = g^x \in \mathbb{G} $ . 什麼時候 $ g $ 是一個生成器，因為它通常是，簡單的健全性是微不足道的：因為 $ X $ 是一個群元素，它必須有一個離散對數關於 $ g $ . 然而，對於電路可滿足性類型的語言，簡單的健全性通常比知識的健全性更重要。
為了證明簡單的合理性，只需計算驗證者可能會暴露作弊證明者的挑戰的數量即可；以及使他能夠逃脫欺詐的可能挑戰的數量。未暴露作弊證明者的挑戰次數與總數的比值稱為健全性誤差— 驗證者隨機選擇他的挑戰這一事實使得該比率等於作弊證明者的成功機率，如果它在安全參數中可以忽略不計，則滿足簡單的穩健性。使用 Fiat-Shamir 變換，從尋找特定原像的困難到隨機預言就足夠了。形式上，您可以將（經典）隨機預言建模為僅在需要時才對隨機輸出進行採樣的過程。然後，找到導致可回答挑戰的輸入的唯一方法是測試足夠多的輸入。
為了證明知識的合理性，必須為證人提取者提供描述 $ \mathsf{E} $ 並表明它的成功機率是顯著的，如果 $ \mathsf{B} $ 具有說服驗證者的顯著成功機率。分叉引理提供了這樣的描述：
- $ \mathsf{E} $ 扮演 $ \mathsf{V} $ 誠實地執行協議 $ \mathsf{B} $ 從而獲得一份成績單 $ T_1 $ .
- $ \mathsf{E} $ 倒帶 $ \mathsf{B} $ 就在它的一條消息之後，通常是它承諾做某事的地方。
- 再次， $ \mathsf{E} $ 扮演 $ \mathsf{V} $ 誠實但具有不同的隨機性，從而獲得第二份成績單 $ T_2 $ .
該語言的結構使得很容易從兩個具有相同承諾但不同挑戰的有效成績單中提取證人。此描述僅涉及倒帶的一個實例；可能需要多次倒帶才能獲得一組滿足非常特殊約束的轉錄本。
直覺地，提取器的成功機率 $ \mathsf{E} $ 應該與證明偽造者的成功機率有某種關係 $ \mathsf{B} $ . 然而，Bellare 和 Neven 表明必然存在平方根安全性降級。特別是，如果提取器 $ \mathsf{E} $ 分成2個分支，然後 $ \mathrm{Pr}[\mathsf{B} , \mathit{success}] \leq \sqrt{\mathrm{Pr}[\mathsf{E} , \mathit{success}]} $ ，因為證明偽造者 $ \mathsf{B} $ 必須在兩個分支都取得成功。這意味著即使離散對數問題需要 $ 2^{128} $ 要計算的工作單元，證明僅表明對手至少要執行 $ 2^{64} $ . 一般來說，如果提取需要 $ b $ 分支，那麼證明技術將導致 $ b $ 根退化。
使用 Fiat-Shamir 變換，驗證者的隨機消息在被查詢到該點之前的協議消息列表時被隨機預言機的響應替換。這個隨機預言機是由提取器模擬的 $ \mathsf{E} $ ，這意味著它可以選擇隨機預言機將提供哪些響應。訣竅是通過倒帶證明偽造者 $ \mathsf{B} $ , 提取器 $ \mathsf{E} $ 可以為隨機預言機重新程式不同的輸出。特別是提取器 $ \mathsf{E} $ 進行如下。
- $ \mathsf{E} $ 執行 $ \mathsf{B} $ 並通過隨機預言機為其提供訪問權限 $ \mathsf{RO} $ 其響應在需要時隨機均勻採樣，並且明顯符合先前查詢的響應。這提供了提取器 $ \mathsf{E} $ 與第一份成績單 $ T $ .
- $ \mathsf{E} $ 倒帶 $ \mathsf{B} $ 就在它的一條消息之後，通常是它承諾做某事的地方。請注意，到目前為止，所有消息的列表都是固定的；將此列表表示為 $ L $ .
- $ \mathsf{E} $ 重播 $ \mathsf{B} $ 再次從這一點開始，但為其提供了對隨機預言機的訪問權限 $ \mathsf{RO}’ $ 唯一的區別是它對 $ L $ . 特別是，該響應是隨機抽樣的。這第二次執行 $ \mathsf{B} $ 提供 $ \mathsf{E} $ 與第二個成績單 $ T_2 $ .
和 $ T_1 $ 和 $ T_2 $ , 提取器 $ \mathsf{E} $ 應該能夠提取證人。如果需要更多的成績單，那麼提取器會根據需要經常倒帶並重放校對器。
好吧，首先，分叉引理有助於證明如果互動式協議 IP 是可靠的，那麼它的 Fiat-Shamir 轉換 FS(IT) 是一個可靠的非互動式協議。
所以它只是表明在應用 Fiat-Shamir 變換後保持穩健性。健全不是憑空出現的。
它到底有什麼幫助？它適用於這種特別健全的IP ，這意味著：具有相同承諾但不同挑戰的2個成績單導致洩露秘密（證人）。顯然，對於互動式協議，特殊健全性意味著健全性（這是協議的另一個屬性，根據定義意味著對證明者俱有黑盒訪問權限，包括所有輸入/輸出，您可以提取秘密見證）。確實：您只需執行 2 個具有不同挑戰的證明者副本（您可以通過黑盒訪問來執行此操作）；由於IP是特別健全的，這兩個獲得的成績單揭示了一個秘密，所以你可以從黑盒訪問證明者中獲得一個秘密！
好吧，轉向非互動式FS(ID)。 現在，你不能只執行 2 次不同挑戰的證明，因為你就是不允許選擇挑戰！證明者現在使用隨機預言機選擇挑戰。 分叉引理幫助我們證明，作為對證明者俱有黑盒訪問權限的攻擊者，您可以通過操縱隨機預言機響應獲得 2 個具有相同承諾但不同挑戰的成績單。請注意，您可以操縱證明者使用的隨機預言機，因為您可以黑盒訪問證明者並模擬其工作環境。