Questions regarding easy-to-compute, but hard-to-invert functions.

Informally, a function is called one-way if it is easy to compute, but hard to invert. These definitions are formally captured as follows: function $f \colon \{0,1\}^* \to \{0,1\}^*$ is called one-way if it has the following properties:

  1. Easy to compute: There exist a (deterministic) polynomial-time machine $M$ such that, $\forall x \in \{0,1\}^* \quad M(x)=f(x)$.
  2. Hard to invert: For all probabilistic polynomial-time machines $A$, for all positive polynomials $p(\cdot)$, and for all sufficiently large $n\in \mathbb{N}$, the inequality $\Pr_{x\leftarrow _R \{0,1\}^n}[f(A(1^n,f(x)))=f(x)] < \tfrac{1}{p(n)}$ holds.

There are several definitions which more or less resemble this one. For instance, one might let the machine $M$ to be probabilistic, and let it fail with negligible probability.

One-way permutations are a special class of one-way functions. It is proven that, secure secret-key encryptions exist iff one-way functions exits, and secure public-key encryptions exist iff one-way permutations exits.

history | excerpt history