隨機預言機
在密碼學中，隨機預言機（英語：Random oracle）是一部預言機，對任何輸入都回傳一個均勻且隨機的輸出（請參考離散型均勻分佈），不過對相同的輸入，該預言機每次都會用同一方法輸出。換句話說，隨機預言機是一個將所有可能輸入與輸出作隨機反映的函數。
限制
只能產生有限個輸出的函數均不是一個隨機預言函數，因為隨機預言機的定義要求其是一個有無限個輸出的函數。
一些刻意設計的簽名和加密方式被證明如果使用隨機預言機的話是安全的，但是使用其他的函式替代隨機預言的話則明顯不安全。[1] 另外，對任何比較自然的安全協定，在隨機預言機模型之下證明為安全，是協定的「實用」可靠性的有力證據。
一個作法被證明是安全的的話，要攻擊此作法就必需要突破該證明的假設；例如，一個加密法的安全證明是基於質因數分解的困難度（像是RSA演算法），那麼打破此證明的方法就是找到快速質因數分解的演算法（像秀爾演算法就是一個可能的攻擊）。要打破隨機預言假設，我們就必須找到實際雜湊函式與隨機預言機未知且不好的不同之處。對於一般被認為不存在這種弱點，夠好的雜湊函式來說（這種雜湊函式現在被認爲是可靠的，像是SHA-3），相關的協定因此可證明是安全的。
雜湊函數與隨機預言機的關聯
在密碼學中，雜湊函式（Hash Function）是一種將輸入映射到固定長度輸出的函數，並廣泛應用於數據完整性驗證、數位簽章和密碼學協定中。然而，現實中的雜湊函數（如 SHA-256）並不完全符合理想的隨機預言機模型，因為它們是確定性的（Deterministic）且基於具體演算法設計，而非真正的隨機函數。 然而，在許多密碼學證明中，研究者會假設雜湊函數表現得類似於隨機預言機，並使用隨機預言機模型來分析加密協議的安全性。例如，數位簽章演算法（如 RSA-PSS）和密碼金鑰派生函數（如 HKDF）都在其安全性分析中使用了這一模型。
這種方法被稱為隨機預言機啟發（Random Oracle Heuristic），儘管在理論上某些 Hash 函數可能會與隨機預言機有所不同，但它仍然是一種實用且廣泛接受的安全性分析技術。
相關條目
參考資料
- ^ Ran Canetti, Oded Goldreich and Shai Halevi, The Random Oracle Methodology Revisited, STOC 1998, pp. 209–218 (PS and PDF).