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 for every efficient algorithm $\mathcal{A}$ there is some negligible function $\nu$, where, for every $\lambda$: ${\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

• OWP ⇒ OWF — folklore
• No fully black-box construction of OWP from length-increasing injective OWF — MM11a

Participates in

Builds on One-way permutations

• OWP ⇒ OWF

Barriers

• No fully-black-box reduction from length-increasing injective OWF to OWP
• No relativizing reduction from OWP to CRHF
• No relativizing reduction from OWP to KE