Lower Bounds for Preprocessing Attacks on Quantum Cryptography
Abstract
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⟩ ∝ ∑x R(k,x) |x⟩ with probability at most O((T2 + √(ST))/N) for N=2n. In contrast, the best known bound for post-quantum one-way functions is O((T2 + ST)/N), 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(T2/N + √(ST/N)). (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(√S/N) bound for the pseudorandomness of random binary phase states against space S distinguishers.
Related
- Exponential lower bounds for low-degree strategies in position-based quantum cryptography
- Elementary proofs of quantum lower bounds for element distinctness and k-sum
- Natural proofs for quantum state preparation lower bounds
- Quantum lower bounds for convex optimization and real matrix-vector query problems
- Improved Upper and Lower Bounds for Quantum Convex-Body Volume Estimation
BibTeX
@misc{dong2026lower,
title = {{Lower Bounds for Preprocessing Attacks on Quantum Cryptography}},
author = {Fangqi Dong and Alex Lombardi},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.02101},
eprint = {2610.02101},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.02101},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - Lower Bounds for Preprocessing Attacks on Quantum Cryptography
AU - Fangqi Dong
AU - Alex Lombardi
PY - 2026
DA - 2026/10/03
PB - arXiv
DO - 10.48550/arxiv.2610.02101
UR - https://arxiv.org/abs/2610.02101
AB - 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⟩ ∝ ∑_x R(k,x) |x⟩ with probability at most O((T^2 + √(ST))/N) for N=2^n. In contrast, the best known bound for post-quantum one-way functions is O((T^2 + ST)/N), 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 N^2 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(T^2/N + √(ST/N)). (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(√S/N) bound for the pseudorandomness of random binary phase states against space S distinguishers.
ER -