|
A function  is a one-way function if for any probabilistic, polynomial time computable function  and any polynomial function  there is  such that
for all  :
where  has length  and all numbers of length  are equally likely.
That is, no probabilistic, polynomial time function can effectively compute  .
Note that, since  need not be injective, this is a stricter requirement than
since not only is  (almost always) not  , it is (almost always) no value such that
 .
| 
![$\displaystyle \operatorname{Pr}[f(g(f(x)))=f(x)]<\frac{1}{p(n)}$](http://images.planetmath.org:8080/cache/objects/3458/l2h/img6.png "$\displaystyle \operatorname{Pr}[f(g(f(x)))=f(x)]<\frac{1}{p(n)}$")
![$\displaystyle \operatorname{Pr}[g(f(x)))=x]<\frac{1}{p(n)}$](http://images.planetmath.org:8080/cache/objects/3458/l2h/img12.png "$\displaystyle \operatorname{Pr}[g(f(x)))=x]<\frac{1}{p(n)}$")