Paper 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. Minor revision.
Keywords
quantum securityPRP
Contact author(s)
mzhandry @ princeton edu
History
2016-11-21: revised
2016-11-21: received
See all versions
Short URL
https://ia.cr/2016/1076
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/1076,
      author = {Mark Zhandry},
      title = {A Note on Quantum-Secure PRPs},
      howpublished = {Cryptology ePrint Archive, Paper 2016/1076},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/1076}},
      url = {https://eprint.iacr.org/2016/1076}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.