Cryptology ePrint Archive: Report 2016/1076

A Note on Quantum-Secure PRPs

Mark Zhandry

Abstract: 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.

Category / Keywords: foundations / quantum security, PRP

Date: received 16 Nov 2016, last revised 21 Nov 2016

Contact author: mzhandry at princeton edu

Available format(s): PDF | BibTeX Citation

Version: 20161121:181320 (All versions of this report)

Short URL: ia.cr/2016/1076

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]