In cryptography, a pseudorandom permutation (PRP) is a function that cannot be distinguished from a random permutation (that is, a permutation selected at random with uniform probability, from the family of all permutations on the function's domain) with practical effort.
Definition Let F be a mapping { 0 , 1 } n × { 0 , 1 } s → { 0 , 1 } n {\displaystyle \left\{0,1\right\}^{n}\times \left\{0,1\right\}^{s}\rightarrow \left\{0,1\right\}^{n}} . F is a PRP if and only if
For any K ∈ { 0 , 1 } s {\displaystyle K\in \left\{0,1\right\}^{s}} , F K {\displaystyle F_{K}} is a bijection from { 0 , 1 } n {\displaystyle \left\{0,1\right\}^{n}} to { 0 , 1 } n {\displaystyle \left\{0,1\right\}^{n}} , where F K ( x ) = F ( x , K ) {\displaystyle F_{K}(x)=F(x,K)} . For any K ∈ { 0 , 1 } s {\displaystyle K\in \left\{0,1\right\}^{s}} , there is an "efficient" algorithm to evaluate F K ( x ) {\displaystyle F_{K}(x)} for any x ∈ { 0 , 1 } n {\displaystyle x\in \left\{0,1\right\}^{n}} ,. For all probabilistic polynomial-time distinguishers D {\displaystyle D} : | P r ( D F K ( 1 n ) = 1 ) − P r ( D f n ( 1 n ) = 1 ) | < ε ( s ) {\displaystyle \left|Pr\left(D^{F_{K}}(1^{n})=1\right)-Pr\left(D^{f_{n}}(1^{n})=1\right)\right|<\varepsilon (s)} , where K ∈ { 0 , 1 } s {\displaystyle K\in \left\{0,1\right\}^{s}} is chosen uniformly at random and f n {\displaystyle f_{n}} is chosen uniformly at random from the set of permutations on n-bit strings. A pseudorandom permutation family is a collection of pseudorandom permutations, where a specific permutation may be chosen using a key.
The model of block ciphers The idealized abstraction of a (keyed) block cipher is a truly random permutation on the mappings between plaintext and ciphertext. If a distinguishing algorithm exists that achieves significant advantage with less effort than specified by the block cipher's security parameter (this usually means the effort required should be about the same as a brute force search through the cipher's key space), then the cipher is considered broken at least in a certificational sense, even if such a break doesn't immediately lead to a practical security failure. Modern ciphers are expected to have super pseudorandomness. That is, the cipher should be indistinguishable from a randomly chosen permutation on the same message space, even if the adversary has black-box access to the forward and inverse directions of the cipher.
Connections with pseudorandom function Michael Luby and Charles Rackoff showed that a "strong" pseudorandom permutation can be built from a pseudorandom function using a Luby–Rackoff construction which is built using a Feistel cipher.
Related concepts
… excerpt ends here. Continue reading the full article.
