| Version current |
Version 3 |
| A function $f$ is a \emph{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$: |
A function $f$ is a \emph{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)}$$ |
$$\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. |
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}$. |
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 |
Note that, since $f$ need not be injective, this is a stricter requirement than |
| $$\operatorname{Pr}[g(f(x)))=x]<\frac{1}{p(n)}$$ |
$$\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)$. |
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)$. |
