實例化隨機預言機
我正在研究 RO 模型，剛剛得到了這個問題，即哪些因素導致無法使用 Hash 函式實例化 RO。為了參考我對它們和其他規範的了解程度，到目前為止，我已經關注了這一系列部落格文章。因此，例如，我知道一個因素是 RO 大小在輸入時呈指數增長，但這是在現實世界中無法實例化它的唯一因素嗎？
（散列函式是確定性函式，而 RO 是隨機函式，這是最重要的因素嗎？）
正如您已經提到的，您無法有效地實例化隨機預言，因為它需要一個指數級的大描述。這是簡單的原因。
通常，隨機預言機只是從具有給定域和範圍的所有函式集合中採樣的隨機函式。如果您考慮低效的構造，您實際上可以實例化一個隨機預言：只需對包含域中每個值的範圍中的隨機值的表進行抽樣。該表成為函式描述，評估函式是查表。
因此，只有當我們需要有效的（= 多尺寸描述）函式（我們在實踐中確實這樣做）時，不可實例化才成立。
現在，顯然任何有效函式都不能是隨機函式。更準確地說，我們將不得不談論函式族。對於隨機預言模型 (ROM)，我們假設函式族是具有給定域和範圍的所有函式的集合，RO 是從該集合中採樣的隨機函式。對於（加密）散列函式，我們考慮一組較小的函式，這些函式具有一個共同的描述，將一個密鑰或索引（想想 IV）作為第二個輸入，並且通過對隨機密鑰進行採樣，您可以從該家族中獲得一個隨機元素。但是，由於這些函式的集合比較小，所以也存在家族中不存在的函式。因此，一定存在某種偏見。例如，大多數密碼散列函式族將不包含任何常量函式。
那麼加密安全散列函式（通常在其中發揮作用）的想法是盡可能地模仿隨機 Oracle 模型。現在，沒有一點小精靈（也許？）、一些完全無偏的骰子、一個神奇的球體和一種儲存每個輸入的所有可能結果的神奇方法，我們需要這些函式。我假設你知道這一點，你要問的是我們為什麼需要“魔法”？
隨機預言機值得關注的幾點：
- Oracle 需要無限的記憶體來記住它收到的每個查詢（以及真正隨機的回复）。
- Oracle 是真正隨機的，這已經足夠挑戰了。
- 神諭不僅需要無限的記憶體，以前提到過但最終是無限的力量，這兩種想法都違反了一些物理常數。
- 甲骨文……已經被揭穿了。（這是一個有用的模型，但它很神奇）
所以接下來最好看的是Crypto-Secure-DRBGs。- 它們和基於的散列函式是 RO 試圖重新創建的所有內容的核心……除了我們應該注意的是，使用電腦算法，任何有權訪問該算法的人都可以查詢“預言機”（這不是確實是一個問題，但以不同的方式期待是可笑的）。
（散列函式是確定性函式，而 RO 是隨機函式，這是最重要的因素嗎？）
基本上，不：最重要的是你提到的第一個，你無法記住每個輸入的結果，這是一個物理問題或數學問題，無論哪種方式，我認為它不需要拖延。