單向函式
 |
單向函數 (One-way function)是一種具有下述特點的單射函數：對於每一個輸入，函數值都容易計算（多項式時間）；但是對於一個隨機的函數值，算出其對應的輸入卻比較困難（無法在多項式時間內使用確定性圖靈機計算）。 單向函數是否存在仍然是計算機科學中的一個開放性問題。事實上，如果單向函數存在，將證明複雜性類P/NP問題中，P不等於NP。與之相對，P不等於NP的假設並不能直接推出單向函數的存在。
實踐中，常將「容易計算」和「不容易計算」定義為「對於合法用戶容易計算，對於惡意用戶不容易計算」。從這個意義上，密碼散列函數[1] 可以被當作單向函數。這是因為，雖然單向函數可能根本不存在，也無人能證明一個散列函數真的是單向函數，但也無人發現可以在合理時間內破解它們的實用算法。
目錄
理論定義
函數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)}