隨機預言機模型證明和可程式性
- 使用隨機預言機模型(ROM) 證明方案的安全性包括兩個步驟：首先證明該方案在存在隨機預言機的理想世界中是安全的，然後通過替換隨機預言機在現實世界中實施該方案帶有雜湊函式的預言機。為什麼不使用最終實現世界的散列函式證明該方案的安全性？是因為沒有找到證據還是有其他原因？你能給我一些例子嗎？
- 您能向我解釋一下隨機預言機模型的“可程式性”特性嗎？在我的書 (Katz-Lindell) 中它說：減少可以根據需要選擇 H 的輸出值（只要這些值正確分佈，即均勻隨機）。
- 如果我理解正確，函式 $ H $ 將充當隨機預言機的功能可以預先固定，也可以“即時”生成，方法是生成輸入和輸出表，當有新輸入時，函式會生成新輸出並將其輸入表中。兩者的理論區別是什麼？
您的第二個問題是關於可程式性的。托馬斯的回答或評論尚未直接解決此問題，因此我將僅關注該問題。不幸的是，我不知道在需要可程式性的隨機預言模型中安全的簡單原語，但是一旦我解釋了背景，我將使用一個希望清楚的原語。它被稱為Fiat-Shamir 啟發式；製作非互動式零知識證明是一個不錯的技巧。
在了解 Fiat-Shamir 之前，請考慮一下您最喜歡的基本零知識證明是如何工作的。由於這是 Crypto SE，而不是 CSTheory SE，希望您正在考慮證明離散對數和二次殘差的知識，而不是圖同構或 3 色圖。;)
[旁白：從技術上講，這些不是真正的零知識證明，它們是誠實驗證者的零知識證明（有時稱為 $ \Sigma $ -protocols），但我們不關心這裡的區別]
Schnorr 的離散對數知識證明
$ P $ （證明者）有兩個值 $ g $ 和 $ y $ 在某組 $ \mathbb{G}_q $ 其中離散對數很難。她聲稱：我知道價值 $ x $ 這樣 $ y=g^x $ . 作為 $ x $ 是的離散對數 $ y $ 根據 $ g $ , 計算 $ x $ 直接是不可行的所以 $ V $ （驗證者）最初無法確定她是否真的知道 $ x $ 或不。
Schnorr 協議允許 $ P $ 證明知識 $ x $ 到 $ V $ 以一種不透露任何關於 $ x $ . 它是這樣的：
- $ P $ 生成一個隨機值 $ a $ , 計算 $ b=g^a $ , 並發送 $ b $ 到 $ V $
- $ V $ 生成一個隨機值 $ c $ 並發送 $ c $ 回到 $ P $
- $ P $ 計算 $ d=a+cx $ 並發送 $ d $ 到 $ V $
- $ V $ 接受 $ \langle b,c,d\rangle $ 作為證明 $ \langle g,y \rangle $ 當且當 $ g^d=by^c $
安全分析
我們可以問自己，在這種協議的安全性方面，我們想要什麼？ $ V $ 擔心來回發送一堆數字實際上可能無法證明 $ P $ 知道這樣一個 $ x $ . 如果他真的能得出這樣的結論 $ P $ 必須知道 $ x $ 如果 $ P $ 可以產生許多接受 $ \langle b,c,d\rangle $ 成績單，據說證明是健全的。
$ P $ 可能會擔心 $ V $ 可能會了解一些關於 $ x $ 從看到一個或多個接受成績單。這應該是一個洩露零資訊的證據 $ x $ （掩飾誠實驗證者的技術性）。如果它洩露了零資訊，就說它是零知識。
健全性（通過提取）
為了證明 Schnorr 協議是合理的，我們實際上是間接地這樣做。我們首先要證明它是一種叫做“可提取”的東西，然後證明可提取性意味著健全性。我不會給出實際的定義或證明，只是一個正在發生的事情的草圖。
Schnorr 協議有一個特殊的健全性屬性（你猜對了，稱為特殊的健全性）：如果有兩個接受的轉錄本 $ t_1=\langle b,c,d \rangle $ 和 $ t_2=\langle b,c’,d’ \rangle $ 在哪裡 $ t_1 $ 共享相同的價值 $ b $ 和 $ t_2 $ 但 $ c $ （因此 $ d $ ) 不同，則可以計算出 $ x $ : $ x=(d-d’)/(c-c’) $ . 如果 $ P $ 可以可靠地生成接受的成績單，那麼沒有理由假設她不能生成 $ t_1 $ . 同樣地 $ t_2 $ . 如果她能同時生產，那麼她“知道” $ x $ 從某種意義上說，生產所需的知識 $ t_1 $ 和 $ t_2 $ 足以生產 $ x $ 本身。
當我們最終到達 Fiat-Shamir 時，將這個“可提取性”概念正式化一點很重要。考慮以下情況 $ P $ 是一個編譯的二進製程序而不是一個人。你可以跑 $ P $ 這將執行協議，你可以倒帶 $ P $ 到以前的內部狀態，但您不能反編譯它或查看內部狀態（這稱為可重繞黑盒訪問；為什麼在證明可提取性時允許使用這些特殊能力是另一個話題）。
我們說如果你能得到一個協議是可提取的 $ x $ 從與這樣的黑匣子進行互動。如果一個協議可以以這種方式提取（一個可以倒帶的黑盒），我們就說它是可靠的。這兩個命題在文獻中都有證據，我省略了很多精美的印刷品。請注意，除了可提取性之外，您還可以通過其他方式證明穩健性，或者通過黑盒可重繞可提取性以外的其他方式證明可靠性（可提取性就足夠了，但不是必需的）。
對於 Schnorr，它應該是顯而易見的，但是您可以執行以下操作：
- 讓 $ P $ 輸出 $ b $
- 給 $ P $ 一個隨機的 $ c $ 作為輸入
- 讓 $ P $ 輸出 $ d $
- 倒帶 $ P $ 在步驟 1 之後和步驟 2 之前
- 給 $ P $ 不一樣的隨機 $ c’ $ 作為輸入
- 讓 $ P $ 輸出 $ d’ $
- 計算 $ x $ 從 $ \langle b,c,d \rangle $ 和 $ \langle b,c’,d’ \rangle $
零知識（通過模擬）
類似地，我們可以通過顯示協議具有不同的屬性：可模擬性來間接證明該協議是零知識的。在這種情況下，我們得到一個編譯後的二進製文件 $ V $ 並且必須可靠地為其提供可接受的 $ b $ 和 $ d $ 的值 $ c $ 它給了我們。然而，該協議是為了了解 $ x $ 我們其實不知道！如果我們可以在不知道的情況下模擬可接受的協議執行 $ x $ , 那麼協議中的值一定不會洩露任何關於 $ x $ . 所以如果協議在這方面是可模擬的，那麼它就是零知識。
我之前提到過，Schnorr 實際上並不是一個零知識協議。這會在模擬 Schnorr 成績單時產生一些問題，當我們使用帶有 Fiat-Shamir 的隨機預言機時，這些問題將得到解決。為了模擬 Schnorr 協議，我們執行以下操作：
- 生成隨機值 $ d $
- 猜測值 $ c $
- 供應 $ b=g^dy^{-c } $ 作為輸入 $ V $
- 讓 $ V $ 輸出 $ c’ $
- 如果 $ c’\neq c $ （你猜錯了），倒回第 2 步。否則繼續
- 供應 $ d $ 到 $ V $ 這將接受
如果值 $ c $ 真的很短（說一點），那麼模擬器很有效。對於較長的值，您無法用這種方法證明 Schnorr 的零知識。有一些技巧可以將 Schnorr 轉換為真正的零知識。
菲亞特-沙米爾啟發式
閱讀以上內容，您可能會做出雙重考慮：一方面，您可以證明 $ x $ 必須知道成績單是否接受，另一方面，您可以生成不接受的成績單 $ x $ ： 是什麼賦予了？如果您仔細觀察，您會發現模擬的成績單是亂序生成的，而可提取的成績單是按順序生成的。實際上，通過亂序生成，我們無法生成 $ \langle b,c,d \rangle $ 和 $ \langle b,c’,d’\rangle $ 成績單以來的價值 $ b $ 不再被選擇：它由 $ d $ 和 $ c $ .
Fiat-Shamir 的想法是使 Schnorr（和相關）協議非互動。這表示 $ P $ 可以產生所有三個值 $ \langle b,c,d \rangle $ 而不是依靠 $ V $ 提供 $ c $ . 此外，由於我們知道成績單是可模擬的， $ P $ 可以產生一個價值 $ c $ 必須在值之後生成 $ b $ 因此排除了任何模擬。如何？其實很簡單：設置 $ c=\mathcal{H}(b) $ . 驗證者還檢查 $ c=\mathcal{H}(b) $ . [旁白：這裡實際上有一個巧妙的優化，您不必發送值 $ b $ 除了把它放在一邊]。
最後我們可以引入隨機預言機。事實證明，如果您使用正常散列函式，則無法將可提取性或模擬排除在協議之外。我們會嘗試，但最終我們將需要一個可以程式的隨機預言機。
使用 Fiat-Shamir 啟發式提取
回想一下，提取依賴於成對的轉錄本，例如 $ \langle b,c,d \rangle $ 和 $ \langle b,c’,d’ \rangle $ . 與菲亞特沙米爾， $ c=\mathcal{H}(b) $ 所以如果 $ b $ 兩個轉錄本之間是相同的，那麼 $ c $ 因此 $ d $ 也會如此。因此，我們無法獲得兩個具有正常確定性雜湊函式的這樣的成績單。但如果 $ \mathcal{H} $ 是一個可程式的隨機預言機，我們可以讓它為相同的輸入產生不同的值。再一次，我們玩了讓可倒帶黑盒訪問的遊戲 $ P $ 但這次我們也得到了隨機預言：
- 讓 $ P $ 產生 $ b $
- 看 $ P $ 詢問 $ O $ 和 $ b $ 為了 $ \mathcal{H}(b) $
- 生成隨機 $ c $ 和程序 $ c=\mathcal{H}(b) $ 在 $ O $
- 讓 $ O $ 回答查詢
- 讓 $ P $ 計算 $ d $
- 讓 $ P $ 輸出 $ \langle b,c,d \rangle $
- 倒退到步驟 2 的結尾
- 生成隨機 $ c’ $ 和程序 $ c’=\mathcal{H}(b) $ 在 $ O $
- 像以前一樣進行，最終讓 $ P $ 輸出 $ \langle b,c’,d’ \rangle $
一些注意事項：（1）因為這是非互動式的， $ P $ 不輸出 $ b $ 在第 1 步之後，我們依靠查看對隨機預言機的查詢的能力；(2) 如果預言機“即時”生成答案（而不是使用包含所有查詢/響應的碼本進入協議），我們實際上不必使用不同的值對其進行程式 $ c $ . 我們只是回到它即將生成響應的點之前，讓它生成一個隨機值（這將與第一次執行時完全不同）。這為原始海報的第三個問題提供了一些啟示。
使用 Fiat-Shamir 進行模擬
與提取類似，隨機預言機的使用使模擬變得輕而易舉。假設你已經讀到這裡，你可能會明白怎麼做，所以我會用一句話說：為 $ c $ , 計算 $ \langle b,c,d \rangle $ 通過選擇 $ d $ 首先，當驗證者與預言機核對時 $ c=\mathcal{H}(b) $ ， 程序 $ c $ 作為回應。
隨機預言機是一個理想的對象；有關詳細資訊，請參閱上一個問題。使隨機預言機便於證明的原因在於，如果您不嘗試它，對於給定輸入的輸出一無所知。例如，考慮以下加密方案：
- $ H $ 是一個隨機預言機，它輸出 $ n $ 位值。
- 關鍵是一個 $ K $ ，一串 $ k $ 位。
- 一條消息 $ m $ 通過計算加密 $ c = m \oplus H(K || 1) || H(K || 2) || … $ （你用隨機預言反复“散列”通過連接獲得的連續字元串 $ K $ 使用計數器，然後將 oracle 輸出連接到一個大流中，該流與要加密的消息進行異或運算）。
如果 $ H $ 是一個隨機預言機，那麼很容易證明加密是安全的，工作因數為 $ 2^{k-1} $ 的呼叫 $ H $ : 對於任何索引 $ i $ , 你什麼也學不到 $ i $ 除非您呼叫 $ H $ 關於產生它的確切輸入；因為有 $ 2^k $ 可能的值 $ K $ , 最好的攻擊就是嘗試（以任何順序），平均而言，它會在之後按下正確的鍵 $ 2^{k-1} $ 猜測。每個猜測都涉及呼叫 $ H $ .
現在，有了加密雜湊函式，事情就沒有那麼容易了。加密散列函式被定義為抵抗原像、第二原像和衝突。這些是弱得多的屬性。一個函式可能是一個很好的散列函式，但仍然不能成為一個隨機預言機。對於常用的Merkle-Damgård函式（如SHA-256 和 SHA-512 ）尤其如此：這些函式遭受所謂的“長度擴展攻擊”。給定 $ H(x) $ ，有可能，在某些條件下，但不知道 $ x $ ， 計算 $ H(x||x’) $ 對於一些值 $ x’ $ . 一個隨機的預言機不會允許這樣做。而這個特定的屬性完全破壞了我們證明上述加密方案安全性的嘗試。然而，當您嘗試計算原像或碰撞時，“長度擴展”似乎沒有任何幫助。事實上，目前尚無針對 SHA-256 或 SHA-512 的有效原像或碰撞攻擊。
總而言之，隨機預言機是一個理想的對象，它允許簡單地證明使用它們的結構，證明依賴於實際散列函式不一定表現出的屬性（即使它們是“安全”散列函式）。
當我們“實現”隨機預言機時，我們使用散列函式和其他原語來模仿隨機預言機的理想屬性。如上所示，現有的散列函式本身還不夠好。一個常見的工具是HMAC，它使用一個密鑰並建立在現有的雜湊函式之上，但以特定的方式呼叫它兩次，以避免具體函式（如 SHA-256）的已知缺點。這就是為什麼，例如，在建構NIST所描述的加密安全偽隨機數生成器時，您可能更喜歡“HMAC_DRBG”結構而不是更快但“不太成熟”的 Hash_DRBG。
在應該使用隨機預言機的協議中使用具有散列函式的給定結構仍然存在一些技術性、直覺和徹底的信念。但我們沒有更好的辦法：我們不知道隨機預言是否真的存在（或者甚至是安全的散列函式，就此而言）。
給定的實現是否使用表來儲存預先計算的結果對理論安全性沒有任何影響：隨機預言模型中的證明依賴於預言必須被呼叫的次數（在不同的輸入上），而不是呼叫的時間地方。您可以根據需要使用內部表。
該函式的誕生日期有一個微妙之處：如果預言機是帶有密鑰的 HMAC，那麼預言機在生成密鑰後就“存在”，並且所有預言機呼叫都必須使用該密鑰；另一方面，像 SHA-256 這樣的無密鑰雜湊函式可以被認為是一種隨機預言機，從 SHA-256 首次定義開始，十多年前就已經存在，全世界可能都有在過去的十年中一直忙於呼叫它。因此，使用原始 SHA-256 作為隨機預言機（如果我們忽略有關長度擴展的部分）相當於考慮到攻擊者可能與整個世界一樣強大，並且具有十年的計算領先優勢。為避免這種情況，定義使用鍵控函式作為隨機預言機的協議是司空見慣的。