Pseudorandom permutation

In cryptography, the term pseudorandom permutation, abbreviated PRP, refers to 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}ⁿ × {0,1}^s →{0,1}ⁿ. F is a PRP if

• For any K∈{0,1}^s, F is a bijection from {0,1}ⁿ to {0,1}ⁿ.
• For any K∈{0,1}^s, there is an "efficient" algorithm to evaluate F_K(x).
• For all probabilistic polynomial-time distinguishers D: ∣Pr(D^F_K(1ⁿ) = 1) - Pr(D^f_n(1ⁿ) = 1)∣<ε(s), where K←{0,1}ⁿ is chosen uniformly at random and f_n is chosen uniformly at random from the set of permutations on n-bit strings.^[1]

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. 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.^[2]

Connections with PRF

Michael Luby and Charles Rackoff^[3] 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.

See also

• Block cipher (pseudorandom permutation families operating on fixed-size blocks of bits)
• Format-preserving encryption (pseudorandom permutation families operating on arbitrary finite sets)

References

1. Katz, Jonathan; Lindell, Yehuda (2007). Introduction to Modern Cryptography: Principles and Protocols. Chapman and Hall/CRC.
2. Mihir Bellare, Phillip Rogaway (2005-09-20). "Chapter 3: Pseudorandom functions". Introduction to Modern Cryptography. Retrieved 2007-09-30.
3. Luby, Michael; Rackoff, Charles (1988). "How to Construct Pseudorandom Permutations from Pseudorandom Functions". SIAM J. Comput. 17 (2). pp. 373–386.