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.
