Time-space lower bounds for breaking quantum cryptography
Researchers prove near-optimal time-space lower bounds for breaking quantum cryptography in the random oracle model.
The paper proves near-optimal time-space lower bounds for key recovery from n-qubit binary phase states in the quantum random oracle model. A T-query adversary with S qubits of non-uniform advice succeeds with probability at most O((T^2+sqrt(ST))/N), for N=2^n, improving on the O((T^2+ST)/N) bound known for post-quantum one-way functions. The authors also obtain an O(T^2/N+sqrt(ST/N)) distinguishing bound for post-quantum PRGs, extend a one-query unitary-synthesis lower bound, and prove an O(sqrt(S)/N) pseudorandomness bound against space-S distinguishers.
- A T-query adversary with S qubits of advice succeeds with probability O((T^2+sqrt(ST))/N).
- n qubits of communication resist preprocessing attacks with space up to N^2, not N.
- The proof bounds a random-matrix operator norm using trace moments and compressed oracles.
- The paper also tightens post-quantum PRG bounds and a unitary-synthesis lower bound.
From the original article
1 min read at arxiv.orgWe prove near-optimal time-space lower bounds for breaking 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\rangle \propto \sum_{x} R(k,x) |x\rangle$ with probability at most $O(\frac{T^2 + \sqrt{ST}}{N})$ for $N=2^n$.
By Fangqi Dong · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.