# 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

## 2 Answers

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

-
I think "of pseudo-random function" should be replaced with "of pseudo-random permutations", $\hspace{.6 in}$ since those can be easily distinguished from each other when the domain is small. $\:$ I also think you should put back-slashes before each of the brackets around $0,1$ in your LaTeX. $\;\;\;$ –  Ricky Demer Dec 12 '13 at 5:23
@RickyDemer Valid point [+1], and thanks for the heads-up on those brackets too. –  e-sushi Dec 12 '13 at 5:26
@e-sushi can u give me pointer to luby-rackoff construction of SPRP you are talking about ? –  sashank Dec 12 '13 at 13:31
@sashank There are a few more related papers out there which might be interesting — depending on how deep you want to dive into the "super" version — but the two I mentioned (besides the Luby-Rackoff paper itself) should be able to provide a nice start. –  e-sushi Dec 12 '13 at 13:58

An efficiently computable Permutation Ensemble is (Weakly) Pseudo-Random
if and only if it is infeasible for an adversary with oracle access to
[a function that was chosen either from then Ensemble or uniformly from
the set of all permutations on bit-strings of the corresponding length]
to distinguish between those two cases.

An efficiently computable Permutation Ensemble is "Super" (= Strongly) Pseudo-Random
if and only if it is infeasible for an adversary with oracle access to
[$\hspace{.02 in}$[a function that was chosen either from then Ensemble or uniformly from
the set of all permutations on bit-strings of the corresponding length] and that function's inverse]
to distinguish between those two cases.

-