One-way permutations

A one-way permutation is an efficiently computable, length-preserving permutation of each $\{0,1{\}}^n$ that no efficient adversary inverts on a uniform input, except with negligible probability.

Syntax

A one-way permutation is a deterministic polynomial-time algorithm computing $\pi :\{0,1{\}}^{\ast }\to \{0,1{\}}^{\ast }$ such that for every $n$, the restriction ${\pi }_n:\{0,1{\}}^n\to \{0,1{\}}^n$ is a permutation.

Properties

One-wayness

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{owp}}_{\pi,\calA}(\secpar)$}
\begin{algorithmic}
\State $x \getsr \bits^\secpar$
\State $\hat{x} \gets \calA(1^\secpar, \pi_\secpar(x))$
\Return $[\hat{x} = x]$
\end{algorithmic}
\end{algorithm}

A permutation $\pi$ is one-way if for all efficient $\mathcal{A}$,

$${\mathbf{Adv}}_{\pi ,\mathcal{A}}^{\mathrm{owp}}(\lambda ):=\mathrm{Pr}\left[{\mathbf{G}}_{\pi ,\mathcal{A}}^{\mathrm{owp}}(\lambda )=1\right]$$

is negligible — Gol01. Hardness is on a uniform input over all of $\{0,1{\}}^{\lambda }$: for a one-way $\pi$, the permutation of $\{0,1{\}}^{2n}$ mapping $0^n\Vert u$ to $0^n\Vert {\pi }_n(u)$ and fixing every other input is hard to invert on $0^n\Vert U_n$, yet it is the identity on a $1-2^{-n}$ fraction of its domain, so it is not one-way — standard.

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

• iO + OWP ⇒ CLS hardness
• iO + OWP ⇒ PPAD hardness
• OWP inversion ∈ NP ∩ coNP
• OWP ⇒ OWF
• OWP ⇒ PRG (Blum–Micali–Yao)
• OWP ⇒ Size-verifiable OWF
• OWP ⇒ Statistically hiding COM (NOVY)
• OWP ⇒ UOWHF (Naor–Yung)

Barriers

• No fully-black-box reduction from length-increasing injective OWF to OWP
• No fully-black-box reduction from iO + OWF to domain-invariant OWP
• No fully-black-box reduction from iO + OWP to CRHF
• No fully-black-box reduction from iO + OWP to average-case-hard SZK
• No deterministic reduction from NP to OWP
• No fully-black-box reduction from OWF to OWP
• No relativizing reduction from OWP to CRHF
• No relativizing reduction from OWP to KE