One-way function

From CRYPTUTOR

A one-way function (OWF) is a function that is easy to compute, but hard to invert on average.

Definition

A function $f$ is a one-way function if it has the following properties:

Efficiently computable: $f(x)\,$ can be computed in polynomial time in $|x|\,$ .
Hard to invert: For all non-uniform PPT (polynomial in the security parameter $k$ ) adversaries $A$ , the probability that $A$ succeeds in the following experiment is negligible in $k$ :

One-way Inversion Experiment:

We choose a random $x \gets \{0,1\}^k$ .
We compute $z=f(x)\,$ and give it to the adversary $A$ .
$A$ outputs a string $y$ .
We say that $A$ "succeeds" in this experiment if $f(y) = z\,$ .

Although we talk about "inverting" $f$ , it is not necessary that $f$ be 1-to-1 and have a mathematical inverse. In the experiment, the adversary succeeds by giving any inverse/pre-image of $f(x)\,$ , not just $x$ .

[edit]

Existence

A one-way function must have "average-case" hardness, which is a stronger requirement than NP-completeness, a "worst-case" hardness. So if one-way functions exist, then P ≠ NP (though the converse may not be true). Thus, proving (unconditionally) that a function is one-way is a very hard problem.

It is known that if one-way functions exist, then so do many other cryptographic primitives, such as pseudorandom generators, pseudorandom functions, and CPA-secure private-key encryption schemes.

[edit]