"Random permutation" in the random oracle model?
From the middle of p. 561:


  Algorithm $A$ accepts the public keys $P_1, P_2, \dots, P_r$ (but not any of the corresponding secret keys) and is given oracle access to $h$, $E$, $E^{-1}$, and to a ring signing oracle.  It can work adaptively, querying the oracles at arguments that may depend on previous answers.  Eventually, it must produce a valid ring signature on a new message that was not presented to the signing oracle, with a non-negligible probability (over the random answers of the oracles and its own random tape).


Specifically, $A$ is allowed to query $E$ and $E^{-1}$ at any key and any message, with the keys obtained from the oracle for $h$ as stated a little below.

(It doesn't matter that $A$ is allowed to know the bits of the key because presumably the choice of permutation is independent uniform random for each distinct key, so there's no meaningful structure to be had out of the bits of the key.)