Pseudorandom permutation
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. An unpredictable permutation (UP) Fk is a permutation whose values cannot be predicted by a fast randomized algorithm. Unpredictable permutations may be used as a cryptographic primitive, a building block for cryptographic systems with more complex properties.
Let F be a mapping {0,1}n × {0,1}s →{0,1}n. F is a PRP if
A pseudorandom permutation family is a collection of pseudorandom permutations, where a specific permutation may be chosen using a key.
An adversary for an unpredictable permutation is defined to be an algorithm that is given access to an oracle for both forward and inverse permutation operations. The adversary is given a challenge input k and is asked to predict the value of Fk. It is allowed to make a series of queries to the oracle to help it make this prediction, but is not allowed to query the value of k itself.
A randomized algorithm for generating permutations generates an unpredictable permutation if its outputs are permutations on a set of items (described by length-n binary strings) that cannot be predicted with accuracy significantly better than random by an adversary that makes a polynomial (in n) number of queries to the oracle prior to the challenge round, whose running time is polynomial in n, and whose error probability is less than 1/2 for all instances. That is, it cannot be predicted in the complexity class PP, relativized by the oracle for the permutation.
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.
...
Wikipedia