Pseudorandom Permutation (PRP)

From Cryptology City
(Redirected from Prp)
Jump to navigation Jump to search


A Pseudorandom Permutation (PRP) is a basic primitive which allows someone to succinctly sample and represent a permutation which appears to be uniformly randomly selected. The user, who generates the key, can evaluate the permutation over some domain both forward and backward efficiently. These pseudorandom permutations are also the primitive which represents block ciphers, such as [AES].

PRPs were originally defined by [GGM84] and are a basic building block for many more complex primitives such as Symmetric Encryption (SE).

Formal Definition

Syntax

A Pseudorandom Permutation (PRP) is a tuple of efficient functions , with respect to a keyspace and domain such that:

  • , is a randomized algorithm that takes a security parameter, and outputs a key ,
  • , is a deterministic algorithm that takes a key and input , and outputs an element ,
  • , is a deterministic algorithm that takes a key and input , and outputs a preimage set of element .

Typically, we assume that is "large," in the sense that it grows exponentially with the security parameter. If instead is bounded by some polynomial in the security parameter, then the primitive is a "small-domain" PRP.

Correctness

A PRP is correct if for all and , .

Security

A PRP is secure if for all efficient , there exists a negligible function , such that

where , is a random permutation over (and is its inverse).

Relationship to other primitives

  • PRFs imply the existence of large-domain PRPs, due to [LR88]
  • PRPs imply the existence of large-domain PRFs, due to the switching lemma

Variations