CryptoDB
NISQ Security and Complexity via Simple Classical Reasoning
| Authors: |
|
|---|---|
| Download: | |
| Conference: | TCC 2025 |
| Abstract: | We give novel lifting theorems for security games in the quantum random oracle model (QROM) in Noisy Intermediate-Scale Quantum (NISQ) settings such as the hybrid query model, the noisy oracle and the bounded-depth models. We provide, for the first time, a hybrid lifting theorem for hybrid algorithms that can perform both quantum and classical queries, as well as a lifting theorem for quantum algorithms with access to noisy oracles or bounded quantum depth. At the core of our results lies a novel measure-and-reprogram framework, called hybrid coherent measure-and-reprogramming, tailored specifically for hybrid algorithms. Equipped with the lifting theorem, we are able to prove directly NISQ security and complexity results by calculating a single combinatorial quantity, relying solely on classical reasoning. As applications, we derive the first direct product theorems in the average case, in the hybrid setting---i.e., an enabling tool to determine the hybrid hardness of solving multi-instance security games. This allows us to derive in a straightforward manner the NISQ hardness of various security games, such as (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{tcc-2025-36247,
title={NISQ Security and Complexity via Simple Classical Reasoning},
publisher={Springer-Verlag},
author={Alexandru Cojocaru and Juan Garay and Qipeng Liu and Fang Song},
year=2025
}