隨機預言機

维基百科,自由的百科全书
(重定向自隨機預言
跳转至: 导航搜索

密碼學裡面,隨機預言機是一部預言機(簡單說像是理論的黑箱),對任何輸入都回傳一個真正均勻隨機的輸出(請參考離散型均勻分佈),不過對相同的輸入,該預言機每次都會用同一方法輸出。換句話說,隨機預言機是一個將所有可能輸入與輸出作隨機映射的函數

限制[编辑]

任何有限的函數均不是一個隨機預言函數, 因為隨機預言機的定義要求其是一個無限大的函數。

事實上,一些刻意設計的英语Pathological (mathematics)簽名和加密方式被證明如果使用隨機預言機的話是安全的,但是使用其他的函式替代隨機預言的話則明顯不安全。[1] 另外,對任何比較自然的安全協定,在隨機預言機模型之下證明為安全,是協定的「實用」可靠性的有力證據。

大體上說,一個作法被證明是安全的的話,要攻擊此作法就必需要突破該證明的假設;例如,一個加密法的安全證明是基於質因數分解的困難度(像是RSA演算法),那麼打破此證明的方法就是找到快速質因數分解的演算法(像是秀爾演算法就被視為是一個可能的攻擊)。在這裡,要打破隨機預言假設,我們就必須找到實際雜湊函式與隨機預言機未知且不好的不同之處。對於一般被認為不存在這種弱點,夠好的雜湊函式來說(這種雜湊函式現在蠻可靠的,像是SHA-3),相關的協定因此可證明是安全的。

相關條目[编辑]

參考資料[编辑]

  1. ^ Ran Canetti, Oded Goldreich and Shai Halevi, The Random Oracle Methodology Revisited, STOC 1998, pp. 209–218 (PS and PDF).

外部連接[编辑]