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.
A pseudorandom permutation family is a collection of pseudorandom permutations, where a specific permutation may be chosen using a key.
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.
Michael Luby and Charles Rackoff showed that a "strong" pseudorandom permutation can be built from a pseudorandom function using a Luby-Rackoff construction.
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
- Mihir Bellare, Phillip Rogaway (2005-09-20). "Chapter 3: Pseudorandom functions". Introduction to Modern Cryptography. Retrieved 2007-09-30.