# What is the difference between PPE and SPPE?

Can somebody explain, in simple terms, the difference between Pseudo Random Permutation Ensemble and Super Pseudo Random Permutation Ensemble?

• “Super Pseudo-Random Permutations” are simply Strong Pseudo-Random Permutations. – e-sushi Dec 12 '13 at 0:41

Super-Pseudo-Random

A function family is super-pseudo-random if no polynomial time adversary can tell the difference between a function from the family and a real random function, given oracle access to the function and its inverse. (As a practical example: block ciphers are typically modeled as super-pseudo-random permutations.)

So, defining it a bit: a family of permutations $f_k(x)$ (where $|k|=n$ and $|x|=m$) is super-pseudo-random if for every polynomial time oracle algorithm A, the difference between the probability that A outputs one in the following two experiments is negligible:

• Choose $k$ at random, and run A with oracle access to $f_k$ and $(f_k)^{-1}$.
• Choose $f$ as a random permutation from $\{0,1\}^m$ to $\{0,1\}^m$, and run $A$ with oracle access to $f$ and $f^{-1}$. (Technically, $f$ is implemented as an algorithm that keeps track of all the queries asked by $A$, and answers new queries at random)

It is also assumed that $f_k$ and its inverse can be efficiently computed, given knowledge of the key $k$.

The above permutations are called super-pseudo-random because $A$ is given access to both $f$ and its inverse, so $A$ can make both encryption and decryption queries to the block cipher.

Pseudo-Random

A similar definition where $A$ has only access to $f$ results in the standard definition of pseudo-random permutation. (Note: super-pseudo-random permutations can be efficiently obtained from pseudo-random functions, using a construction of Luby-Rackoff… but that's another story.)

An efficiently computable Permutation Ensemble is (Weakly) Pseudo-Random
[$\hspace{.02 in}$[a function that was chosen either from then Ensemble or uniformly from