单向函数

未解决的计算机科学问题：单向函数存在吗？

单向函数（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]