NISQ Security and Complexity via Simple Classical Reasoning

Alexandru Cojocaru, Juan Garay, Qipeng Liu, Fang Song · 2025

Read NISQ Security and Complexity via Simple Classical Reasoning by Alexandru Cojocaru, Juan Garay, Qipeng Liu, Fang Song (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-09900.txt.

Introduction

Alexandru Cojocaru and 3 co-authors extend their lifting machinery to noisy quantum machines in a 2025 cryptography paper. Security games are analysed in the quantum random oracle model, but real near-term devices query in hybrid ways, face noisy oracles, or run only shallow circuits. No lifting theorem had covered hybrid algorithms that mix classical and quantum queries, leaving those settings without a shortcut.

Their hybrid coherent measure-and-reprogram framework fills the gap for all three noisy settings. Analysts can now settle security and complexity questions by computing one combinatorial quantity with purely classical reasoning. First fruits include average-case direct product results for hybrid attackers and direct hardness proofs for salted games and multi-instance versions of core cryptographic tasks.

Catalog record

CREATORAlexandru Cojocaru, Juan Garay, Qipeng Liu, Fang Song
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE102 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-09900

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

NISQ Security and Complexity via Simple Classical Reasoning Alexandru Cojocaru, Juan Garay, Qipeng Liu, Fang Song 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. 1 Introduction Hash functions are a fundamental workhorse in modern cryptography. Efficient constructions such as SHA-2 and SHA-3 are widely used in real-world cryptographic applications. This is in no small part facilitated by the random oracle model (ROM) abstraction [ BR93 ] , which often enables efficient cryptographic constructions and simple analysis. The development of quantum computing poses significant threats to cryptography. Quantum random oracle model (QROM) has since been proposed to take into account quantum attackers [ BDF+11 ] . The various techniques that have been developed for analyzing security in the QROM, however, are often either ad-hoc (for specific scenarios) or too involved to apply. They include approaches such as polynomial methods [ BBC+01 ] , adversarial methods [ Amb02 ] , small-range distributions [ Zha12 ] , and compressed oracles [ Zha18 ] . Achieving post-quantum security often comes with the need for larger security parameters, hence causing an efficiency blow-up. For hash functions in particular, this leads to substantially longer output length and increased running time. On the other hand, the study of Noisy Intermediate-Scale Quantum (NISQ) devices [ Pre18 ] constitutes a crucial intermediate goal. In the NISQ model, one focuses on: (i) hybrid algorithms, where parties are granted a quota of both classical and quantum resources, resulting in a model which subsumes the purely classical or purely quantum computing models as special cases; (ii) quantum algorithms with access to noisy oracles , where each quantum query is affected by a dephasing noise; or (iii) bounded-depth quantum algorithms. These models of computation are also practically motivated as a fully quantum algorithm typically requires running a large-scale quantum computer coherently for an extended amount of time, while in the near-to-intermediate term, the available quantum devices are likely to be computationally restricted as well as expensive [ Pre18 ] . Understanding the complexity of various cryptographic tasks against adversaries with both classical and quantum capabilities is not only crucial in near-term cryptography, but also a key step towards advancing our knowledge of quantum computational complexity, and efforts have been made to analyze, in this model, pre-image resistance [ Ros24 , CGS23 , HLS24 ] and collision resistance [ HLS24 ] . However, while these methods establish tight security for these two cryptographic uses of hash functions, they appear too complex and specific to be ported to other applications. 1.1 Summary of Our Results In this work we establish novel lifting theorems for search games in the presence of NISQ adversaries, specifically, (i) hybrid algorithms that are equipped with both classical and quantum queries, (ii) quantum algorithms with access to noisy oracles, as well as (iii) quantum algorithms with bounded quantum depth. At the heart of this result is a novel measure-and-reprogram technique, which we refer to as hybrid coherent reprogramming . This technique can be viewed as a generalization of the coherent reprogramming method [ CGLS25 ] . The lifting theorems allow us to prove quantum and NISQ security for various cryptographic applications by calculating a single combinatorial quantity, relying solely on classical reasoning. Using this new framework, we derive the first direct product theorems in the average case, in the NISQ setting. Hybrid Lifting Theorem for Search Games. Our central result proposes a novel hybrid lifting theorem for search games relating the success probability of an arbitrary hybrid algorithm to the success probability of a hybrid algorithm performing a small number of queries to the RO. Theorem 1.1 (Hybrid Lifting Theorem – Informal) . Let \mathcal{G} be a search game with a classical challenger \mathcal{C} that performs at most k queries to the RO, and let \mathcal{A} be a hybrid adversary equipped with q quantum and c classical queries in the game \mathcal{G} (against the k -classical query challenger \mathcal{C} ). Then there exists a k (quantum + classical) hybrid query adversary 1 1 1 Algorithm \mathcal{B} has oracle access to the random oracle as well as to the algorithm \mathcal{A} . \mathcal{B} such that: \Pr[\mathcal{B}\textrm{ wins }\mathcal{G}]\geq\frac{1}{\left(O\left(\frac{q^{2}}{k^{2}}+\frac{c}{k}\right)\right)^{k}}\Pr[\mathcal{A}\text{ wins }\mathcal{G}], where the probabilities are taken over the RO and the randomness of algorithms \mathcal{A} and \mathcal{B} , respectively. Lifting Theorem for Search Games in the Noisy Oracle Model. Next, we give the lifting theorem in the noisy oracle setting. In this model, we assume a quantum algorithm that performs quantum queries to an oracle O_{p} where, with probability p , the input/output registers will be measured, and the query becomes a classical query, and with probability 1-p , it will be a regular quantum query. Theorem 1.2 (Lifting Theorem for Noisy Oracles – Informal) . Let \mathcal{G} be a search game with a classical challenger \mathcal{C} that performs at most k queries to the noisy oracle O_{p} , and let \mathcal{A} be a quantum adversary equipped with T queries in the game \mathcal{G} (against the k -classical query challenger \mathcal{C} ). Then there exists a k -query adversary \mathcal{B} such that: \Pr[\mathcal{B}\textrm{ wins }\mathcal{G}]\geq E(p,T,k)\cdot\Pr[\mathcal{A}\text{ wins }\mathcal{G}]. Where: \displaystyle E(p,T,k)=\frac{1}{O\left({T\choose k}\left(((1-p)Tk)^{k}+k\right)\right)}. Remark 1.3 . The bound is tight in the regime where p is close to 0 or 1 . For instance, let’s consider the function inversion problem where the goal is to find x such that f(x)=0 ; in this case k=1 . When p approaches 0 , it recovers the tight bound for a T -query quantum algorithm; conversely, as p nears 1 , the bound degrades to that of a T -query classical algorithm. However, this bound is not generally tight when p is away from 0 and 1 . Specifically, for function inversion, as shown in [ HLS24 ] , when p is a constant, the best achievable performance of a T -quantum algorithm using a noisy oracle O_{p} is no better than that of a classical algorithm (i.e., having advantage O(T/N) ), whereas our result gives O(T^{2}/N) . We note that establishing a general lifting lemma that tightly applies to noisy

Read the complete text