Cryptology ePrint Archive: Report 2018/904
Quantum security proofs using semi-classical oracles
Andris Ambainis and 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.
Category / Keywords: foundations / post-quantum cryptography, quantum random oracle model, one-way to hiding, public-key encryption, provable security
Date: received 24 Sep 2018, last revised 18 Feb 2019
Contact author: unruh at ut ee, mike@shiftleft org, andris ambainis@lu lv
Available format(s): PDF | BibTeX Citation
Note: Changes:
- Extended introduction
- Discussion how bounds obtained in existing work change
- Proof of Targhi-Unruh transform with the new O2H Theorem
Version: 20190218:140908 (All versions of this report)
Short URL: ia.cr/2018/904
[ Cryptology ePrint archive ]