單向函數

维基百科,自由的百科全书
跳转至: 导航搜索

单向函数 (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)}
  1. ^ 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