1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ “Super Pseudo-Random Permutations” are simply Strong Pseudo-Random Permutations. $\endgroup$ – e-sushi Dec 12 '13 at 0:41
3
$\begingroup$

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

| improve this answer | |
$\endgroup$
3
$\begingroup$

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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.