什麼是“隨機預言機模型”，為什麼會引起爭議？
什麼是“隨機預言機模型”？它是類似於因式分解和離散對數的硬度的“假設”嗎？或者是其他東西？
為什麼一些研究人員對這個模型有強烈的不信任？
隨機預言機由以下模型描述：
- 有一個黑匣子。盒子裡住著一個侏儒，帶著一本大書和一些骰子。
- 我們可以在框中輸入一些數據（任意位序列）。
- 給定一些他事先沒有看到的輸入，侏儒使用他的骰子在一些正常空間（預言機輸出的空間）中均勻且隨機地生成新的輸出。侏儒還在他的書中記下輸入和新生成的輸出。
- 如果給定一個已經看過的輸入，侏儒使用他的書來恢復他上次返回的輸出，然後再次返回。
因此，隨機預言機就像一種雜湊函式，因此我們對給定輸入消息可以獲得的輸出一無所知 $ m $ , 直到我們真正嘗試 $ m $ . 這是一個有用的安全證明工具，因為它們允許根據對預言機的呼叫次數來表達攻擊努力。
隨機預言機的問題在於，建構一個真正“隨機”的預言機**非常困難。**首先，沒有證據表明不使用 gnome 就可以真正存在隨機預言機。然後，我們可以看看我們有哪些候選：雜湊函式。安全散列函式意味著對沖突、原像和第二原像具有彈性。這些屬性並不意味著該函式是隨機預言機。
確實，請參閱SHA-256（或 SHA-512，如果您願意）。它遭受稱為“長度擴展攻擊”的東西。這是來自Merkle-Damgård 構造的人工製品：散列消息 $ m $ ，消息首先被分成固定大小的塊（SHA-256 為 64 字節），最後一個塊用一些位填充，其中包括 $ m $ , 和一些 1 和 0 使得我們最終得到一個完整的塊。然後在執行狀態下處理每個塊，雜湊輸出是最後一個塊值。
所以假設有一條消息 $ m $ ，我不知道，但我知道 $ m $ 及其雜湊 $ h(m) $ . 有了這些資訊，我可以重建添加的填充位（我們稱它們為 $ \pi $ ）。然後，我可以想像消息 $ m’ $ :
$$ m’ = m || \pi || x $$ 為了一些價值 $ x $ 我隨意選擇。然後我知道計算 $ h(m’) $ 將從分裂開始 $ m || \pi $ 成塊並處理它們，並在處理完最後一位之後 $ \pi $ ，目前的“執行狀態”將是 $ h(m) $ . 所以，如果我知道 $ h(m) $ ，我可以完成計算 $ h(m’) $ 從那裡拿走，我可以在不知不覺中做到這一點 $ m $ . 特別是，我最終得到 $ h(m’) $ 雖然沒有提出 $ m’ $ 給侏儒。 該屬性證明 SHA-256不是隨機預言機。然而，它不會以任何方式危害 SHA-256 對碰撞或原像的抵抗力。因此，作為一個隨機預言機似乎比作為一個安全的雜湊函式更難。
實際上已經證明（Canetti、Goldreich 和 Halevi）隨機預言機不能在以下意義上“普遍存在”：可以建構病態簽名和非對稱加密方案，當它們在內部使用隨機預言機時是安全的，但是每當使用實際的可計算函式而不是神話般的 gnome-in-the-box 時，它們都是不安全的。
**總結：**隨機預言模型中的證明很好，但還不夠完整，無法涵蓋實際的實現：我們知道我們將用來代替隨機預言的任何函式都不是隨機預言；因此安全性依賴於熱切希望實際功能不是隨機預言機的部分不會影響安全性。這證明了一點不信任。儘管如此，隨機預言模型中的證明總比沒有證明要好得多。