單向函式
![本頁使用了標題或全文手工轉換](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
![]() | 此條目可參照英語維基百科相應條目來擴充。 (2017年6月) |
未解決的電腦科學問題:單向函式存在嗎?
單向函式(One-way function)是一種具有下述特點的單射函式:對於每一個輸入,函式值都容易計算(多項式時間);但是對於一個隨機的函式值,算出其對應的輸入卻比較困難(無法在多項式時間內使用確定性圖靈機計算)。 單向函式是否存在仍然是電腦科學中的一個開放性問題。事實上,如果單向函式存在,將證明複雜性類別P/NP問題中,P不等於NP。[1]:ex. 2.2, page 70與之相對,P不等於NP的假設並不能直接推出單向函式的存在。[2]
實踐中,常將「容易計算」和「不容易計算」定義為「對於合法使用者容易計算,對於惡意使用者不容易計算」。從這個意義上,密碼雜湊函式可以被當作單向函式。這是因為,雖然單向函式可能根本不存在,也無人能證明一個雜湊函式真的是單向函式,但也無人發現可以在合理時間內破解它們的實用演算法。
理論定義
函式f: {0, 1}* → {0, 1}* 是一個單向函式若且唯若f可以用一個多項式時間的演算法計算,但是對於任意一個以x為輸入的隨機化多項式演算法A,任意一個多項式p(n),和足夠大n,使得
參見
參考資料
- ^ Oded Goldreich (2001). Foundations of Cryptography: Volume 1, Basic Tools, (draft available (頁面存檔備份,存於網際網路檔案館) from author's site). Cambridge University Press. ISBN 0-521-79172-3. (see also http://www.wisdom.weizmann.ac.il/~oded/foc-book.html (頁面存檔備份,存於網際網路檔案館))
- ^ Goldwasser, S. and Bellare, M. "Lecture Notes on Cryptography" (頁面存檔備份,存於網際網路檔案館). Summer course on cryptography, MIT, 1996–2001