Pseudorandom permutation

A Pseudorandom Permutation (PRP) allows someone to succinctly represent a permutation that is indistinguishable from a uniformly random permutation. A user generates a key and uses it to evaluate the permutation forward and backward at many points; any efficient adversary who sees only these input-output pairs cannot distinguish them from a truly random permutation. PRPs are the formal model behind block ciphers such as AES.

Syntax

A PRP is a triple of efficient algorithms $\mathsf{PRP}=(\mathsf{KeyGen},\mathsf{Eval},\mathsf{Invert})$ with respect to keyspace $\mathcal{K}$ and domain $\mathcal{D}$:

• $\mathsf{KeyGen}(1^{\lambda })\to k,$ is a randomized algorithm that samples a key $k\in \mathcal{K},$
• $\mathsf{Eval}(k,x)\to y,$ is a deterministic algorithm that takes a key $k\in \mathcal{K}$ and input $x\in \mathcal{D}$, outputting $y\in \mathcal{D},$
• $\mathsf{Invert}(k,y)\to x,$ is a deterministic algorithm that takes a key $k\in \mathcal{K}$ and input $y\in \mathcal{D}$, outputting $x\in \mathcal{D}.$

For every key $k$, $\mathsf{Eval}(k,\cdot )$ is a bijection on $\mathcal{D}$.

Properties

Correctness

A PRP $\mathsf{PRP}$ is correct if for all $k\in \mathcal{K}$ and $x\in \mathcal{D}$,

$$\mathsf{Invert}(k,\mathsf{Eval}(k,x))=x.$$

Security

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{prp}}_{\PRP,\calA}(\secpar)$}
\begin{algorithmic}
\State $k \gets \KeyGen(1^\secpar)$; $b \getsr \bits$
\State $\pi \getsr \Perms(\calD)$
\Comment{Can be sampled lazily}
\State $\calO_0(x) := \Eval(k,x)$
\State $\calO_1(x) := \pi(x)$
\State $b' \gets \calA^{\calO_b}(1^\secpar)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

A PRP $\mathsf{PRP}$ is pseudorandom if for all efficient $\mathcal{A}$,

$${\mathbf{Adv}}_{\mathsf{PRP},\mathcal{A}}^{\mathrm{prp}}(\lambda ):=\left|2\mathrm{Pr}\left[{\mathbf{G}}_{\mathsf{PRP},\mathcal{A}}^{\mathrm{prp}}(\lambda )=1\right]-1\right|$$

is negligible.

Strong Security

In the strong PRP (sPRP) security game, the adversary additionally receives an inverse oracle. This is a strictly stronger notion than standard PRP security.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{sprp}}_{\PRP,\calA}(\secpar)$}
\begin{algorithmic}
\State $k \gets \KeyGen(1^\secpar)$; $b \getsr \bits$
\State $\pi \getsr \Perms(\calD)$
\Comment{Can be sampled lazily}
\State $\calO_0(x) := \Eval(k,x)$ ; $\calO_0^{-1}(y) := \Invert(k,y)$
\State $\calO_1(x) := \pi(x)$ ; $\calO_1^{-1}(y) := \pi^{-1}(y)$
\State $b' \gets \calA^{\calO_b,\calO_b^{-1}}(1^\secpar)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

A PRP $\mathsf{PRP}$ is strongly pseudorandom if for all efficient $\mathcal{A}$,

$${\mathbf{Adv}}_{\mathsf{PRP},\mathcal{A}}^{\mathrm{sprp}}(\lambda ):=\left|2\mathrm{Pr}\left[{\mathbf{G}}_{\mathsf{PRP},\mathcal{A}}^{\mathrm{sprp}}(\lambda )=1\right]-1\right|$$

is negligible.

Variations

Small-domain PRPs

Typically, $|\mathcal{D}|$ is assumed to grow super-polynomially in $\lambda$, so that a brute-force enumeration of $\mathcal{D}$ is infeasible. When $|\mathcal{D}|$ is instead polynomial in $\lambda$, the primitive is called a small-domain PRP and requires additional care, as some standard constructions and security reductions no longer apply.

Other results

• PRFs imply the existence of large-domain PRPs — LR88
• PRPs imply the existence of large-domain PRFs (and infact these are invertible PRFs) — Switching Lemma