為什麼採樣單個隨機位的能力不意味著建構隨機預言？
我試圖準確了解隨機預言模型與標準模型的不同之處。在許多證明和應用中，有一些假設是採樣了一些隨機性（即有點 $ b \leftarrow{0,1} $ ).
我的問題是：鑑於能夠隨機採樣單個位，我們不能用它來建構隨機預言嗎？假設我們要模擬一個隨機函式 $ H:{0,1}^m \rightarrow {0,1}^n $ . 只是樣品 $ n $ 位作為輸出，並保留一個日誌，以便所有未來的查詢都是一致的。
我的問題是：鑑於能夠隨機採樣單個位，我們不能用它來建構隨機預言嗎？假設我們要模擬一個隨機函式 $ H:{0,1}^m \rightarrow {0,1}^n $ . 只是樣品 $ n $ 位作為輸出，並保留一個日誌，以便所有未來的查詢都是一致的。
當然。你可以設計一個簽名方案，其中有一個中央方——一個侏儒坐在標準盒子裡擲硬幣——地球上的每個人都有一條直接連接到侏儒的電話線，不會被攔截，這樣每個人都可以從侏儒那裡得到相同的值. 這不是設計密碼系統的一種特別實用的方法——例如，我們可能希望能夠離線簽署和驗證消息——但更重要的是，這並不是隨機預言模型的真正意義所在。
隨機預言機模型不僅僅是散列函式的模型，而是對手的模型。 舉個例子：在簽名遊戲 EUF-CMA——在選擇消息攻擊下存在不可偽造性——一個對手 $ A $ 根據定義，它是一種可以訪問簽名預言機和公鑰的隨機算法： $ A(S, \mathit{pk}) $ . 如果他們能找到任何對手，他們就會獲勝 $ (m, \sigma) $ 通過任何消息的簽名驗證的對 $ m $ 他們沒有傳遞給簽署的預言機 $ S $ . 這有時被稱為“標準模型”。
在隨機預言機模型中，我們考慮由函式的統一隨機選擇索引的一系列簽名方案 $ H $ . 為了清楚地表明它依賴於雜湊函式，我們可能會標記簽名預言機 $ S_H $ . 例如，在 RSA-FDH 簽名中，公鑰是一個大整數 $ n $ 和消息上的簽名 $ m $ 是一個整數 $ \sigma $ 這樣$$ \sigma^3 \equiv H(m) \pmod n. $$ 合法使用者的簽名預言通常定義為$$ S_H(m) := H(m)^d \pmod n, $$秘密指數在哪裡 $ d $ 解決 $ 3d \equiv 1 \pmod{\lambda(n)} $ . 然後，在隨機預言機模型中，攻擊者獲得的不僅僅是一個簽名預言機和公鑰，如 $ A(S, n) $ 在“標準模型”中，還有雜湊預言，如 $ A(H, S_H, n) $ .
ROM定理是以下形式的陳述：
- 如果有隨機算法 $ A(H, S_H, n) $ 其中，當 $ H $ 是均勻分佈的，返回一個偽造的機率很高，那麼有一個算法 $ A’(y, n) $ 其中，當 $ y $ 是均勻分佈的，返回一個立方根 $ y $ 模組 $ n $ 機率很高。
定理的證明是算法的定義 $ A’ $ ，它構造了一個雜湊預言和簽名預言，它們具有正確的分佈來欺騙偽造者，但另外做足夠的簿記以從偽造者所做的任何計算中提取立方根——而不使用 $ d $ 合法使用者將擁有的。
顯然，內部隨機算法 $ A’ $ 將涉及像您描述的那樣翻轉硬幣，以實現雜湊預言和簽名預言。有關證明的詳細資訊，以及更多背景、歷史和文獻參考，請參閱我早期的 ROM 答案；另請參閱標準的Bellare & Rogaway 論文，以獲取 RSA-FDH 定理的原始證明。
換句話說，隨機預言模型是關於對手結構的假設。 一些作者沒有使用有點令人困惑的術語“隨機預言模型”，而是更願意說上面引用的定理只是一個關於 $ H $ -generic adversaries，意思是根據任意散列函式一般定義的對手，而不是利用特定散列函式細節（如 MD5 中的衝突）的對手。
當然，MD5 特定的偽造者已經被展出——例如，它們在美國和以色列針對伊朗的國際工業破壞事件中表現突出——但它們並不與這個定理相矛盾，因為這樣的偽造者只在極低的機率下工作什麼時候 $ H $ 是均勻分佈的。換句話說，如果用 MD5 實例化的 RSA-FDH 簽名方案變壞了，這並不是因為 RSA-FDH 的花哨數學變壞了——而是因為 MD5 變壞了，很有可能使用 SHAKE128 代替會很好.