A pseudorandom permutation can be defined formally as a function $\phi$ from $\{0,1\}^k\times\{0,1\}^n$ to $\{0,1\}^n$ such that for every $x\in\{0,1\}^k$ the function $\phi_x:y\mapsto\phi(x,y)$ is a bijection. The difficulty of distinguishing between a random permutation of the form $\phi_x$ and a purely random permutation of $\{0,1\}^n$ is defined roughly as follows. The function $\phi$ has hardness at least m if for every algorithm $A$ that takes at most $m$ steps in the worst case and has access to an oracle that tells it values $\pi(y)$ of a given permutation $\pi$ whenever it wants to know them (taking, say, one step to do so), the probability that $A$ outputs 1 when $\pi$ is a random $\phi_x$ differs from the probability that $A$ outputs 1 when $\pi$ is a fully random permutation by at most $m^{-1}$.

A celebrated result of Luby and Rackoff shows that pseudorandom permutations of superpolynomial hardness exist if pseudorandom functions of superpolynomial hardness exist. I won't bother here to explain what a pseudorandom function is, since this question is aimed at people who already know. What I would like to know is whether under suitable assumptions there are pseudorandom permutations of hardness $2^{Cn}$ for arbitrarily large $C$. I don't mind if $k$ is bigger than $n$. It might at first seem a silly question, since one can look at every single value that $\pi$ takes. But that's fine by me. For this question, the oracle is no longer needed, since one can just think of the function as a gigantic table of values. Even given those values, it doesn't seem easy to distinguish between a pseudorandom permutation and a random one.

This question is motivated by thoughts connected with Razborov and Rudich's famous Natural Proofs paper, where they consider a pseudorandom function of very large hardness. It may be that if you take such a function and apply the Luby-Rackoff construction to it, then you get a very hard pseudorandom permutation, but from the accounts I've found online I've been unable to see easily whether that is the case.

  • $\begingroup$ I have now found a source that seems to suggest that the Luby-Rackoff construction won't give hardness greater than $2^n$. So it looks as though a different idea would be needed. But maybe there are some different ideas out there. $\endgroup$ – gowers Jun 18 '13 at 17:00
  • 3
    $\begingroup$ If you don't get a good answer here on MO, you might try asking your question at cstheory.stackexchange.com $\endgroup$ – Timothy Chow Jun 18 '13 at 17:13
  • $\begingroup$ You must want some upper bound on $k$, right? Otherwise you could take $k = \log(2^n!)$ and then define $\phi(x,y) = \pi_x(y)$ where $\pi_x$ is the $x$th permutation on $\{0,1\}^n$ in lexicographic order. Then $\phi$ is completely indistinguishible from truly random. (I'm ignoring here the issue that $\log(2^n!)$ is not an integer, but one could hack around this.) $\endgroup$ – Ryan O'Donnell Jun 19 '13 at 1:08
  • 1
    $\begingroup$ Yes. I was vague about it, but the precise requirement I would like is that $k$ should be at most a polynomial function of $n$ (or perhaps a very slightly superpolynomial function). $\endgroup$ – gowers Jun 19 '13 at 6:55
  • $\begingroup$ I now think it may be possible to do something by composing polynomially many Feistel permutations. $\endgroup$ – gowers Jun 19 '13 at 8:45

I am not sure what exactly are the parameters you are interested in, but you may for example check the following papers by Patarin: Luby-Rackoff: 7 Rounds Are Enough for 2 n(1 − ε) Security Security of random Feistel schemes with 5 or more rounds

| cite | improve this answer | |

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.