  We show how to construct pseudorandom permutations (PRPs) that remain secure
even if the adversary can query the permutation on a quantum superposition of
inputs. Such PRPs are called \emph{quantum-secure}. Our construction combines a
quantum-secure pseudorandom \emph{function} together with constructions of
\emph{classical} format preserving encryption. By combining known results, we
obtain the first quantum-secure PRP in this model whose security relies only on
the existence of one-way functions. Previously, to the best of the author's
knowledge, quantum security of PRPs had to be assumed, and there were no prior
security reductions to simpler primitives, let alone one-way functions.
