隨機預言機模型

隨機預言機模型（ROM）是一個證明框架，其中我們假裝某個雜湊函數是真正的隨機函數——一個神奇黑盒，對每個全新的輸入回傳一個嶄新、均勻隨機的輸出，若再次查詢則一致作答。它是用來證明密碼方案安全的一種理想化。

為何要假裝？許多高效的簽章與證明（Schnorr、全域雜湊 RSA，以及每一種 Fiat–Shamir 轉換）唯有在雜湊表現理想時才有乾淨的安全歸約。在 ROM 中，證明可以「編排」預言機的回答，並觀察對手提出的每一次查詢，從而做出對任何具體、固定的雜湊函數都行不通的歸約。接著你以 SHA-256 或 Keccak 之類真實雜湊來實例化這個預言機，並期望證明的直覺能延續過去。

問題真實存在但範圍很窄：Canetti、Goldreich 與 Halevi 於 1998 年證明，存在（刻意建構的）方案在 ROM 中可證安全，卻在每一種可能的真實雜湊下都不安全。因此 ROM 證明是個強力的啟發法，而非絕對保證。儘管如此，從未有任何自然、已部署的方案因為這個模型而被攻破，所以從業者接受它。與區塊鏈最相關的 ROM 應用是 Fiat–Shamir 啟發法，它藉由雜湊抄本來產生挑戰，把互動式證明轉為非互動式——這是鏈上零知識驗證的骨幹。