View source for Pseudorandom Permutation (PRP)

<noinclude>
[[Category:Primitives]]
[[Category:Minicrypt]]

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 [[https://en.wikipedia.org/wiki/Advanced_Encryption_Standard AES]].

PRPs were originally defined by [[ccref#ggm84|[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 <math>(\mathsf{Gen}, P, P^{-1})</math>, with respect to a keyspace <math>\mathcal{K}</math> and domain <math>\mathcal{D}</math> such that:
* <math>\mathsf{Gen}(1^{\lambda}) \to k</math>, is a randomized algorithm that takes a security parameter, and outputs a key <math>k\in \mathcal{K}</math>,
* <math>P_k(x) \to y</math>, is a deterministic algorithm that takes a key <math>k\in \mathcal{K}</math> and input <math>x\in \mathcal{D}</math>, and outputs an element <math>y\in \mathcal{D}</math>,
* <math>P^{-1}_k(y) \to x</math>, is a deterministic algorithm that takes a key <math>k\in \mathcal{K}</math> and input <math>y\in \mathcal{D}</math>, and outputs a preimage set of element <math>x\in \mathcal{D}</math>.

Typically, we assume that <math>|\mathcal{D}|</math> is "large," in the sense that it grows exponentially with the security parameter. If instead <math>|\mathcal{D}|</math> 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 <math>k</math> and <math>x</math>, <math>P^{-1}_k(P_k(x)) = x</math>.

=== Security ===
A PRP is ''secure'' if for all efficient <math>D</math>, there exists a negligible function <math>\nu</math>, such that
<center><math>
\big| \Pr [D^{P_k,P^{-1}_k}(1^{\lambda}) = 1] -
\Pr [D^{\pi,\pi^{-1}}(1^{\lambda}) = 1 \big| \le \nu(\lambda),
</math></center>
where <math>k\gets \mathsf{Gen}(1^{\lambda})</math>, <math>\pi</math> is a random permutation over <math>\mathcal{D}</math> (and <math>\pi^{-1}</math> is its inverse).

== Relationship to other primitives ==
* [[PRF]]s imply the existence of large-domain [[PRP]]s, due to [[ccref#lr88|[LR88]]]
* [[PRP]]s imply the existence of large-domain [[PRF]]s, due to the switching lemma

== Variations ==
* [[Truncated PRP]]s
* [[Injective PRF]]s