CryptoDB
Improved Quantum Lifting by Coherent Measure-and-Reprogram
| Authors: |
|
|---|---|
| Download: | |
| Conference: | ASIACRYPT 2024 |
| Abstract: | We give a tighter lifting theorem for security games in the quantum random oracle model. At the core of our main result lies a novel measure-and-reprogram framework that we call coherent reprogramming. This framework gives a tighter lifting theorem for query complexity problems, that only requires purely classical reasoning. As direct applications of our lifting theorem, we first provide a quantum direct product theorem in the average case --- i.e., an enabling tool to determine the hardness of solving multi-instance security games. This allows us to derive in a straightforward manner the hardness of various security games, for example (i) the non-uniform hardness of salted games, (ii) the hardness of specific cryptographic tasks such as the multiple instance version of one-wayness and collision-resistance, and (iii) uniform or non-uniform hardness of many other games. |
BibTeX
@inproceedings{asiacrypt-2024-34670,
title={Improved Quantum Lifting by Coherent Measure-and-Reprogram},
publisher={Springer-Verlag},
author={Alexandru Cojocaru and Juan Garay and Qipeng Liu and Fang Song},
year=2024
}