In cryptography

Cryptography

Cryptography is the practice and study of techniques for secure communication in the presence of third parties...

, the term pseudorandom permutation, abbreviated PRP, refers to a function that cannot be distinguished from a random permutation

Random permutation

A random permutation is a random ordering of a set of objects, that is, a permutation-valued random variable. The use of random permutations is often fundamental to fields that use randomized algorithms such as coding theory, cryptography, and simulation...

 (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 block cipher

Block cipher

In cryptography, a block cipher is a symmetric key cipher operating on fixed-length groups of bits, called blocks, with an unvarying transformation. A block cipher encryption algorithm might take a 128-bit block of plaintext as input, and output a corresponding 128-bit block of ciphertext...

 is a truly random permutation. If a distinguishing algorithm exists that achieves significant advantage

Advantage (cryptography)

In cryptography, an adversary's advantage is a measure of how successfully it can attack a cryptographic algorithm, by distinguishing it from an idealized version of that type of algorithm. Note that in this context, the "adversary" is itself an algorithm and not a person...

 with less effort than specified by the block cipher's security parameter

Security parameter

In cryptography, the security parameter is a variable that measures the input size of the problem. Both the resource requirements of the cryptographic algorithm or protocol as well as the adversary's probability of breaking security are expressed in terms of the security parameter.The security...

 (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.

See also

• Block cipher
  Block cipher
  In cryptography, a block cipher is a symmetric key cipher operating on fixed-length groups of bits, called blocks, with an unvarying transformation. A block cipher encryption algorithm might take a 128-bit block of plaintext as input, and output a corresponding 128-bit block of ciphertext...
  
   (pseudorandom permutation families operating on fixed-size blocks of bits)
• Format-Preserving Encryption
  Format-Preserving Encryption
  In cryptography, format-preserving encryption refers to encrypting in such a way that the output is in the same format as the input . The meaning of "format" varies...
  
   (pseudorandom permutation families operating on arbitrary finite sets)
• Pseudorandom function
  Pseudorandom function
  In cryptography, a pseudorandom function family, abbreviated PRF, is a collection of efficiently-computable functions which emulate a random oracle in the following way: no efficient algorithm can distinguish between a function chosen randomly from the PRF family and a random oracle...
  
  
• Permutation box
  Permutation box
  In cryptography, a permutation box is a method of bit-shuffling used to permute or transpose bits across S-boxes inputs, retaining diffusion while transposing....