Can somebody explain, in simple terms, the difference between Pseudo Random Permutation Ensemble and Super Pseudo Random Permutation Ensemble?
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ “Super Pseudo-Random Permutations” are simply Strong Pseudo-Random Permutations. $\endgroup$– e-sushiDec 12, 2013 at 0:41
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
7
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.)
-
1$\begingroup$ 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. $\;\;\;$ $\endgroup$– user991Dec 12, 2013 at 5:23
-
$\begingroup$ @RickyDemer Valid point [+1], and thanks for the heads-up on those brackets too. $\endgroup$– e-sushiDec 12, 2013 at 5:26
-
$\begingroup$ @e-sushi can u give me pointer to luby-rackoff construction of SPRP you are talking about ? $\endgroup$– sashankDec 12, 2013 at 13:31
-
$\begingroup$ M. Luby, C. Rackoff, "How to construct pseudorandom permutations from pseudorandom functions", SIAM Journal on Computing, 17 (2) (1988), pp. 373–386. Thinking about it, you might also want to check on "A construction of the simplest super pseudorandom permutation generator" by Lee, Kim, and Choi and "Building PRFs from PRPs" by Hall, Wagner, Kelsey, and Schneier (which build upon and mention that Luby-Rackoff paper). $\endgroup$– e-sushiDec 12, 2013 at 13:56
-
$\begingroup$ @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. $\endgroup$– e-sushiDec 12, 2013 at 13:58
$\begingroup$
$\endgroup$
0
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.