Paper 2018/904

Quantum security proofs using semi-classical oracles

Andris Ambainis, Mike Hamburg, and Dominique Unruh

Abstract

We present an improved version of the one-way to hiding (O2H) Theorem by Unruh, J ACM 2015. Our new O2H Theorem gives higher flexibility (arbitrary joint distributions of oracles and inputs, multiple reprogrammed points) as well as tighter bounds (removing square-root factors, taking parallelism into account). The improved O2H Theorem makes use of a new variant of quantum oracles, semi-classical oracles, where queries are partially measured. The new O2H Theorem allows us to get better security bounds in several public-key encryption schemes.

Note: Change history:<p> Version 2: Extended introduction. Discussion how bounds obtained in existing work change. Proof of Targhi-Unruh transform with the new O2H Theorem.<p> Version 3: Added disclaimer about flaw on front page. Minor editorial changes.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in CRYPTO 2019
Keywords
post-quantum cryptographyquantum random oracle modelone-way to hidingpublic-key encryptionprovable security
Contact author(s)
unruh @ ut ee
mike @ shiftleft org
andris ambainis @ lu lv
History
2021-12-09: last of 2 revisions
2018-09-25: received
See all versions
Short URL
https://ia.cr/2018/904
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/904,
      author = {Andris Ambainis and Mike Hamburg and Dominique Unruh},
      title = {Quantum security proofs using semi-classical oracles},
      howpublished = {Cryptology ePrint Archive, Paper 2018/904},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/904}},
      url = {https://eprint.iacr.org/2018/904}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.