Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
1  
“Super Pseudo-Random Permutations” are simply Strong Pseudo-Random Permutations. –  e-sushi Dec 12 '13 at 0:41

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
1  
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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