單向函式

未解決的電腦科學問題：單向函式存在嗎？

單向函式（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,使得

Pr_{x\in \{0,1\}^{n}}[f(A(f(x)))=f(x)]<{\frac {1}{p(n)}}

參見

陷門函式（英語：Trapdoor function）

參考資料

^ Oded Goldreich（英語：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

[Goldreich-1] Oded Goldreich（英語：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 （頁面存檔備份，存於網際網路檔案館）)

[2] Goldwasser, S. and Bellare, M. "Lecture Notes on Cryptography" （頁面存檔備份，存於網際網路檔案館）. Summer course on cryptography, MIT, 1996–2001

[1]

[2]