Pseudorandom Permutation (PRP)

A Pseudorandom Permutation (PRP) is a basic primitive which allows someone to succinctly sample and represent a permutation which appears to be uniformly randomly selected. The user, who generates the key, can evaluate the permutation over some domain both forward and backward efficiently. These pseudorandom permutations are also the primitive which represents block ciphers, such as [AES].

PRPs were originally defined by [GGM84] and are a basic building block for many more complex primitives such as Symmetric Encryption (SE).

Formal Definition

Syntax

A Pseudorandom Permutation (PRP) is a tuple of efficient functions $({\mathsf {Gen}},P,P^{-1})$, with respect to a keyspace ${\mathcal {K}}$ and domain ${\mathcal {D}}$ such that:

• ${\mathsf {Gen}}(1^{\lambda })\to k$, is a randomized algorithm that takes a security parameter, and outputs a key $k\in {\mathcal {K}}$,
• $P_{k}(x)\to y$, is a deterministic algorithm that takes a key $k\in {\mathcal {K}}$ and input $x\in {\mathcal {D}}$, and outputs an element $y\in {\mathcal {D}}$,
• $P_{k}^{-1}(y)\to x$, is a deterministic algorithm that takes a key $k\in {\mathcal {K}}$ and input $y\in {\mathcal {D}}$, and outputs a preimage set of element $x\in {\mathcal {D}}$.

Typically, we assume that $|{\mathcal {D}}|$ is "large," in the sense that it grows exponentially with the security parameter. If instead $|{\mathcal {D}}|$ is bounded by some polynomial in the security parameter, then the primitive is a "small-domain" PRP.

Correctness

A PRP is correct if for all $k$ and $x$, $P_{k}^{-1}(P_{k}(x))=x$.

Security

A PRP is secure if for all efficient $D$, there exists a negligible function $\nu$, such that

${\big |}\Pr[D^{P_{k},P_{k}^{-1}}(1^{\lambda })=1]-\Pr[D^{\pi ,\pi ^{-1}}(1^{\lambda })=1{\big |}\leq \nu (\lambda ),$

where $k\gets {\mathsf {Gen}}(1^{\lambda })$, $\pi$ is a random permutation over ${\mathcal {D}}$ (and $\pi ^{-1}$ is its inverse).

Relationship to other primitives

• PRFs imply the existence of large-domain PRPs, due to [LR88]
• PRPs imply the existence of large-domain PRFs, due to the switching lemma

Variations

• Truncated PRPs
• Injective PRFs