# one-way function

A function $f$ is a one-way function if for any probabilistic, polynomial time computable function $g$ and any polynomial function $p$ there is $m$ such that for all $n>m$:

 $\operatorname{Pr}[f(g(f(x)))=f(x)]<\frac{1}{p(n)}$

where $x$ has length $n$ and all numbers of length $n$ are equally likely.

That is, no probabilistic, polynomial time function can effectively compute $f^{-1}$.

Note that, since $f$ need not be injective, this is a stricter requirement than

 $\operatorname{Pr}[g(f(x)))=x]<\frac{1}{p(n)}$

since not only is $g(f(x))$ (almost always) not $x$, it is (almost always) no value such that $f(g(f(x)))=f(x)$.

Title one-way function OnewayFunction 2013-03-22 13:03:14 2013-03-22 13:03:14 Henry (455) Henry (455) 7 Henry (455) Definition msc 68Q30 one way function one-way one way