Incryptography, apseudorandom permutation (PRP) is a function that cannot be distinguished from arandom 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.

LetF be a mapping${\displaystyle {\left\{0,1\right\}}^n\times {\left\{0,1\right\}}^s\to {\left\{0,1\right\}}^n}$.F is a PRP if and only if

• For any${\displaystyle K\in {\left\{0,1\right\}}^s}$,${\displaystyle F_K}$ is abijection from${\displaystyle {\left\{0,1\right\}}^n}$ to${\displaystyle {\left\{0,1\right\}}^n}$, where${\displaystyle F_K(x)=F(x,K)}$.
• For any${\displaystyle K\in {\left\{0,1\right\}}^s}$, there is an "efficient" algorithm to evaluate${\displaystyle F_K(x)}$ for any${\displaystyle x\in {\left\{0,1\right\}}^n}$,.
• For all probabilistic polynomial-timedistinguishers${\displaystyle D}$:, where${\displaystyle K\in {\left\{0,1\right\}}^s}$ is chosen uniformly at random and${\displaystyle f_n}$ is chosen uniformly at random from the set of permutations onn-bit strings.^[1]

Apseudorandom 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 trulyrandom permutation on the mappings betweenplaintext andciphertext. If a distinguishing algorithm exists that achieves significantadvantage with less effort than specified by the block cipher'ssecurity 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 practicalsecurity failure.^[2]

Modern ciphers are expected to have super pseudorandomness.That is, the cipher should beindistinguishable 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.^[3]

Michael Luby and Charles Rackoff^[4] showed that a "strong" pseudorandom permutation can be built from apseudorandom function using aLuby–Rackoff construction which is built using aFeistel cipher.

Anunpredictable permutation (UP)F_k is apermutation whose values cannot be predicted by a fastrandomized algorithm. Unpredictable permutations may be used as acryptographic primitive, a building block for cryptographic systems with more complex properties.

Anadversary 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 inputk and is asked to predict the value ofF_k. 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 ofk itself.^[5]

A randomized algorithm for generating permutations generates anunpredictable 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 (inn) number of queries to the oracle prior to the challenge round, whose running time ispolynomial inn, and whose error probability is less than 1/2 for all instances. That is, it cannot be predicted in thecomplexity classPP,relativized by the oracle for the permutation.^[5]

It can be shown that a functionF_k is not a securemessage authentication code (MAC) if it satisfies only the unpredictability requirement. It can also be shown that one cannot build an efficient variable input length MAC from a block cipher which is modelled as a UP ofn bits. It has been shown that the output of ak = n/ω(log λ) round Feistel construction with unpredictable round functions may leak all the intermediate round values.^[5] Even for realistic Unpredictable Functions (UF), some partial information about the intermediate round values may be leaked through the output. It was later shown that if a super-logarithmic number of rounds in the Feistel construction is used, then the resulting UP construction is secure even if the adversary gets all the intermediate round values along with the permutation output.^[6]

There is also a theorem that has been proven in this regard which states that if there exists an efficient UP adversaryA_π that has non-negligible advantageε_π in the unpredictability game against UP construction ψ_U,k and which makes a polynomial number of queries to the challenger, then there also exists a UF adversaryA_f that has non-negligible advantage in the unpredictability game against a UF sampled from the UF family F . From this, it can be shown that the maximum advantage of the UP adversaryA_π isε_π = O (ε_f. (qk)⁶). Hereε_f denotes the maximum advantage of a UF adversary running in time O(t + (qk)⁵) against a UF sampled fromF, wheret is the running time of the PRP adversaryA_ψ andq is the number of queries made by it.^[6][7]

In addition, a signature scheme that satisfies the property of unpredictability and not necessarily pseudo-randomness is essentially a Verifiable Unpredictable Function (VUF). A verifiable unpredictable function is defined analogously to a Verifiable Pseudorandom Function (VRF) but for pseudo-randomness being substituted with weaker unpredictability. Verifiable unpredictable permutations are the permutation analogs of VUFs or unpredictable analogs of VRPs. A VRP is also a VUP and a VUP can actually be built by building a VRP via the Feistel construction applied to a VRF. But this is not viewed useful since VUFs appear to be much easier to construct than VRFs.^[8]

• DES

K x X → X ∀ X={0,1}⁶⁴, K={0,1}⁵⁶

• AES-128

K x X → X ∀ k=X={0,1}¹²⁸

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

• Theory of cryptography
• Cryptographic primitives
• Permutations

• Articles with short description
• Short description matches Wikidata