單向函數（one-way function）

有些過程容易做、卻難以還原。砸碎一個盤子只需一秒；從碎片把它拼回去卻是惡夢。把兩種顏料攪在一起是瞬間的事；要把它們分回去基本上不可能。單向函數就是這種不對稱的數學版本：一個函數 f，正向計算容易（給定 x，算出 f(x) 很快），逆向卻很難（只給輸出 y = f(x)，要找出任何映射到它的 x 在計算上不可行）。

精確地說，f 是單向的，是指它能在多項式時間內計算，然而對任何試圖反轉它的高效（多項式時間）演算法而言，找到一個隨機輸出之有效原像的機率小到可忽略。正向便宜；反向擊敗每一個快速攻擊者。關鍵是：這講的是計算上的困難，而非不可能：原像永遠存在，對所有輸入做暴力搜尋也找得到，但那搜尋慢得天文，所以就實際用途而言該函數無法反轉。重點全在於「正向容易」與「反向不可行」之間的落差。

單向函數是現代密碼學的基石假設。從它你能建造偽隨機產生器、安全的密碼雜湊、數位簽章、承諾方案，以及（如前所述）NP 裡所有主張的零知識證明。這裡有一份深刻而謙卑的誠實：我們並不知道單向函數是否存在。它們的存在將蘊含 P 不等於 NP（反轉是一種 NP 式的搜尋，所以若 P = NP，就沒有任何東西真正單向），而且一般相信它比這更強。所以幾乎所有實用密碼學都建立在一個未證的假設上——像整數分解與離散對數這樣的候選者，是被相信很難、而非被證明很難，無論朝哪個方向給出證明都將是里程碑。