每一個單向函數（本身屬於 P 但反函數不屬於）都可以構造一種公鑰密碼嗎？

補充 @玄星 大牛的回答

事實上，所有的密碼學源語的構建，都是基於某個假設的——不僅僅公鑰源語如此，對稱密碼源語等等也都如此。比如，公鑰密碼中假設的「大整數分解的困難性「，以及對稱密碼中假設的「偽隨機性存在」（偽隨機發生器的存在）等。通常來講，有些假設是「高層假設」，這些假設可以通過更「低」層的假設推倒出來（可以規約到更底層的假設）。

事實上，「單項函數存在」實際上是最基本的密碼學假設。有了單項函數，我們可以構造hash函數，可以用來構造其他多種對稱密碼源語，可以保證認證性。所以說，如過說構造「公鑰密碼源語」，可以！

但是，並不能保證所有的單項函數都是lossless的，只有one-way function will trapdoor(陷門單項函數)可以用來構造公鑰加密演算法。

Lamport, Leslie. Constructing digital signatures from a one-way function. Vol. 238. Palo Alto: Technical Report CSL-98, SRI International, 1979

得具備交換性吧，不然只能拿來做散列。

比如MD5。

是否存在逆運算？反向計算能否證明安全性或複雜度？前者是構造的關鍵，後者是安全的基石

就是 Minicrypt 和 Cryptomania 是否同一的問題。結論是（暫時）不知道。

可以參考 http://ieeexplore.ieee.org/document/514853/ 和 Status of Impagliazzo"s Worlds? 。