隨機預言機
在密碼學裡面，隨機預言機（英語：）是一部預言機（簡單說像是理論的黑箱），對任何輸入都回傳一個真正均勻隨機的輸出（請參考離散型均勻分佈），不過對相同的輸入，該預言機每次都會用同一方法輸出。換句話說，隨機預言機是一個將所有可能輸入與輸出作隨機映射的函數。
限制
任何只能產生有限個輸出的函數均不是一個隨機預言函數, 因為隨機預言機的定義要求其是一個有無限個輸出的函數。
事實上，一些刻意設計的簽名和加密方式被證明如果使用隨機預言機的話是安全的，但是使用其他的函式替代隨機預言的話則明顯不安全。[1] 另外，對任何比較自然的安全協定，在隨機預言機模型之下證明為安全，是協定的「實用」可靠性的有力證據。
大體上說，一個作法被證明是安全的的話，要攻擊此作法就必需要突破該證明的假設；例如，一個加密法的安全證明是基於質因數分解的困難度（像是RSA演算法），那麼打破此證明的方法就是找到快速質因數分解的演算法（像是秀爾演算法就被視為是一個可能的攻擊）。在這裡，要打破隨機預言假設，我們就必須找到實際雜湊函式與隨機預言機未知且不好的不同之處。對於一般被認為不存在這種弱點，夠好的雜湊函式來說（這種雜湊函式現在蠻可靠的，像是SHA-3），相關的協定因此可證明是安全的。
相關條目
- 預言機
- 標準模型 (密碼學)
- 密碼學主題列表
- 图灵机
- 图灵归约
- 交互式证明系统
參考資料
- Ran Canetti, Oded Goldreich and Shai Halevi, The Random Oracle Methodology Revisited, STOC 1998, pp. 209–218 (PS and PDF).
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.