Non-uniformity and Quantum Advice in the Quantum Random Oracle Model

In the quantum random oracle model (QROM) introduced by Boneh et al. (Asiacrypt 2011), a hash function is modeled as a uniformly random oracle, and a quantum algorithm can only interact with the hash function in a black-box manner. QRO methodology captures all generic algorithms. However, they fail to describe non-uniform quantum algorithms with preprocessing power, which receives a piece of bounded classical or quantum advice.

As non-uniform algorithms are largely believed to be the right model for attackers, starting from the work by Nayebi, Aaronson, Belovs, and Trevisan (QIC 2015), a line of works investigates non-uniform security in the random oracle model. Chung, Guo, Liu, and Qian (FOCS 2020) provide a framework and establish non-uniform security for many cryptographic applications. Although they achieve nearly optimal bounds for many applications with classical advice, their bounds for quantum advice are far from tight.

In this work, we continue the study on quantum advice in the QROM. We provide a new idea that generalizes the previous multi-instance framework, which we believe is more quantumfriendly and should be the quantum analog of multi-instance games. To this end, we match the bounds with quantum advice to those with classical advice by Chung et al., showing quantum advice is almost as good/bad as classical advice for many natural security games in the QROM. More formally, • OWFs: Even with 𝑆-qubits of quantum advice, a 𝑇 -query quantum algorithm has advantage 𝑂((𝑆𝑇 + 𝑇 2 )/𝑁 ) to invert a random function with domain and range size 𝑁 . As shown by Corrigan-Gibbs and Kogan (TCC 2019), any further improvement will lead to new classical circuit lower bounds. • PRGs: An 𝑆-qubit, 𝑇 -query quantum algorithm can distinguish between a random image and a random element in the range, with an winning probability at most 1/2 + 𝑂(𝑇 2 /𝑁 ) 1/2 + 𝑂(𝑆𝑇 /𝑁 ) 1/3 , in contrast to 1/2 + 𝑂((𝑆 5 𝑇 + 𝑆 4 𝑇 2 )/𝑁 ) 1/19 by Chung et al. • Salting: A commonly used mechanism in cryptography called salting defeats preprocessing, even with quantum advice, improved the bounds by Chung et al.

Finally, we show that for some contrived games in the QROM, quantum advice can be exponentially better than classical advice for some parameter regimes. To our best knowledge, it provides the first evidence of a general separation between quantum and classical advice relative to an unstructured oracle.