查看“︁單向函數”︁的源代码

{{Expand_English|date=2017年6月}}
{{NoteTA
|G1 = IT
}}
{{unsolved|計算機科學|單向函數存在嗎？}}
'''单向函数'''（{{lang|en|'''One-way function'''}}）是一种具有下述特点的单射函数：对于每一个输入，函数值都容易计算（多项式时间）；但是对于一个随机的函数值，算出其对应的输入却比较困难（无法在多项式时间内使用确定性图灵机计算）。
单向函数是否存在仍然是计算机科学中的一个开放性问题。事实上，如果单向函数存在，将证明[[复杂性类]][[P/NP问题]]中，P不等于NP。<ref name="Goldreich">{{tsl|en|Oded Goldreich|}} (2001). Foundations of Cryptography: Volume 1, Basic Tools, ([http://www.wisdom.weizmann.ac.il/~oded/PSBookFrag/part2N.ps draft available] {{Wayback|url=http://www.wisdom.weizmann.ac.il/~oded/PSBookFrag/part2N.ps |date=20191023044544 }} from author's site). Cambridge University Press. ISBN 0-521-79172-3. (see also http://www.wisdom.weizmann.ac.il/~oded/foc-book.html {{Wayback|url=http://www.wisdom.weizmann.ac.il/~oded/foc-book.html |date=20160809044453 }})</ref>{{rp|ex. 2.2, page 70}}与之相对，P不等于NP的假设并不能直接推出单向函数的存在。<ref>[[莎菲·戈德瓦塞尔|Goldwasser, S.]] and Bellare, M. [http://cseweb.ucsd.edu/~mihir/papers/gb.html "Lecture Notes on Cryptography"] {{Wayback|url=http://cseweb.ucsd.edu/~mihir/papers/gb.html |date=20120421084751 }}. Summer course on cryptography, MIT, 1996–2001</ref>

实践中，常将“容易计算”和“不容易计算”定义为“对于合法用户容易计算，对于恶意用户不容易计算”。从这个意义上，[[密码散列函数]]可以被当作单向函数。这是因为，虽然单向函数可能根本不存在，也无人能证明一个散列函数真的是单向函数，但也无人发现可以在合理时间内破解它们的实用算法。

==理论定义==
函数''f'': {0, 1}<sup>*</sup> → {0, 1}<sup>*</sup> 是一个单向函数当且仅当''f''可以用一个多项式时间的算法计算，但是对于任意一个以''x''为输入的随机化多项式算法''A''，任意一个多项式''p''(''n'')，和足够大''n'',使得

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

== 参见 ==
* [[陷門函數]]

==參考資料==
<references />

[[Category:密码学|D]]
[[Category:密碼原語]]