# Are there very strongly pseudorandom permutations?

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.

-
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. –  gowers Jun 18 '13 at 17:00
If you don't get a good answer here on MO, you might try asking your question at cstheory.stackexchange.com –  Timothy Chow Jun 18 '13 at 17:13
Good point -- thanks for the tip. –  gowers Jun 18 '13 at 17:57
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.) –  Ryan O'Donnell Jun 19 '13 at 1:08
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). –  gowers Jun 19 '13 at 6:55