One-way permutations

A one-way permutation is a permutation which is easy to compute in one direction but hard to invert.

Properties

A one-way permutation is a family of efficiently computable permutations $\{{\pi }_{\lambda }:\mathcal{D}\to \mathcal{D}{\}}_{\lambda \in \mathbb{N}}$ and a distribution $X$ over $\mathcal{D}$, such that there is some negligible function $\nu$, where, for every $\lambda$ and efficient algorithm $\mathcal{A}$: ${\mathrm{Pr}}_{x\sim X}[{\pi }_{\lambda }(x^{\prime })={\pi }_{\lambda }(x):x^{\prime }\leftarrow \mathcal{A}(1^{\lambda },{\pi }_{\lambda }(x))]\le \nu (\lambda ).$

Other results

• A OWP is trivially a OWF.
• A OWP cannot be constructed from an injective one-way function in a black-box way. — MM11