单向函数
维基百科,自由的 encyclopedia
单向函数(One-way function)是一种具有下述特点的单射函数:对于每一个输入,函数值都容易计算(多项式时间);但是对于一个随机的函数值,算出其对应的输入却比较困难(无法在多项式时间内使用确定性图灵机计算)。 单向函数是否存在仍然是计算机科学中的一个开放性问题。事实上,如果单向函数存在,将证明复杂性类P/NP问题中,P不等于NP。[1]:ex. 2.2, page 70与之相对,P不等于NP的假设并不能直接推出单向函数的存在。[2]
![]() | 此条目可参照英语维基百科相应条目来扩充。 (2017年6月) |
未解决的计算机科学问题:单向函数存在吗?
实践中,常将“容易计算”和“不容易计算”定义为“对于合法用户容易计算,对于恶意用户不容易计算”。从这个意义上,密码散列函数可以被当作单向函数。这是因为,虽然单向函数可能根本不存在,也无人能证明一个散列函数真的是单向函数,但也无人发现可以在合理时间内破解它们的实用算法。