## You are here

Homeone-way function

## Primary tabs

# 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)}$ |

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)$.

Synonym:

one way function, one-way, one way

Type of Math Object:

Definition

Major Section:

Reference

## Mathematics Subject Classification

68Q30*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections