Non-uniform security allows an adversary to receive bounded advice about an oracle before attempting a fresh challenge. This captures the most realistic attacks and has already been studied extensively in prior work. In this work, we introduce an operator-norm approach for non-uniform security in the quantum random oracle and random permutation models. This new approach yields a unified reduction for both search success probability and distinguishing advantage. Previously, the reduction only worked with success probability even in the decision games, yielding a worse bound.
Our framework enables tight bounds for Yao's box, both with and without salting, and improved bounds for pseudorandom generators. We also prove an optimal generic salting theorem for decision games. By defining a property of a game, which separates the contributions of the existing queries in the offline stage and subsequent online queries, we obtain stronger bounds for specific salted constructions. These include salted permutation inversion, tight up to logarithmic factors, and salted random-function inversion, tight up to logarithmic factors and the gap already present in classical function inversion.
We prove near-optimal lower bounds for preprocessing attacks on quantum cryptography in the random oracle model. Specifically, we show that a T-query adversary with S qubits of non-uniform advice can recover a random key k from the n-qubit binary phase state ∣ψk⟩∝∑xR(k,x)∣x⟩ with probability at most O(NT2+ST) for N=2n. In contrast, the best known bound for post-quantum one-way functions is O(NT2+ST), with a trivial attack at S=N. This demonstrates a new advantage of quantum cryptography over classical cryptography: n qubits of communication suffice for security against preprocessing attacks with space up to N2 rather than N. Our methodology is simple: express the optimal preprocessing attack as the operator norm of a random matrix, and bound this value in expectation over the random oracle via the trace-moment method. These trace moments have a natural interpretation using compressed oracles [Zhandry, Crypto 2019], which we then analyze. This can be viewed as a simplification and generalization of the approach of Liu [Eurocrypt 2023] for proving the security of post-quantum cryptography against preprocessing attacks. We also prove the following results: (1) We tighten Liu's analysis of post-quantum PRGs in QROM, achieving a distinguishing advantage bound of O(NT2+NST). (2) For unitary synthesis, we extend the one-query lower bound of Lombardi-Ma-Wright [STOC 2024] to hold against adversaries that can make one arbitrary function query along with polynomially many (adaptive) queries to the random oracle, either before or after the function query. This also interprets the original LMW24 result in terms of compressed oracles. (3) Finally, we prove a tight O(NS) bound for the pseudorandomness of random binary phase states against space S distinguishers.
In function inversion, we are given a function f:[N]→[N], and want to prepare some advice of size S, such that we can efficiently invert any image in time T. This is a well studied problem with profound connections to cryptography, data structures, communication complexity, and circuit lower bounds. Investigation of this problem in the quantum setting was initiated by Nayebi, Aaronson, Belovs, and Trevisan (2015), who proved a lower bound of ST2=Ω̃(N) for random permutations against classical advice, leaving open an intriguing possibility that Grover's search can be sped up to time Õ(√{N/S}). Recent works by Hhan, Xagawa, and Yamakawa (2019), and Chung, Liao, and Qian (2019) extended the argument for random functions and quantum advice, but the lower bound remains ST2=Ω̃(N). In this work, we prove that even with quantum advice, ST+ T2=Ω̃(N), is required for an algorithm to invert random functions. This demonstrates that Grover's search is optimal for S=Õ(√N), ruling out any substantial speed-up for Grover's search even with quantum advice. Further improvements to our bounds would imply new classical circuit lower bounds, as shown by Corrigan-Gibbs and Kogan (2019). To prove this result, we develop a general framework for establishing quantum time-space lower bounds. We further demonstrate the power of our framework by proving the following results. (a) Yao's box problem: We prove a tight quantum time-space lower bound for classical advice. For quantum advice, we prove a first time-space lower bound using shadow tomography. These results resolve two open problems posted by Nayebi et al (2015). (b) Salted cryptography: We show that “salting generically provably defeats preprocessing,” a result shown by Coretti, Dodis, Guo, and Steinberger (2018), also holds in the quantum setting. In particular, we prove quantum time-space lower bounds for a wide class of salted cryptographic primitives in the quantum random oracle model. This yields the first quantum time-space lower bound for salted collision-finding, which in turn implies that PWPPO⊈ FBQPO/qpoly relative to a random oracle O.