Quantum method shows what adversaries really know from oracle queries
Compressed Oracle Duality: A simple framework for knowing what quantum adversaries know
Computational ComplexityCryptography and SecurityData Structures and Algorithms
Summary
When a quantum computer tries to learn about a secret by asking questions to a random system (called a random oracle), it can forget or erase information it once had. The researchers present a new way to capture exactly what information the quantum computer still remembers, even when it tries to clean up. They do this by creating a pair of special records that perfectly match what the computer actually keeps in memory. This helps better understand the limits of quantum attacks and improves proofs about how fast and how much memory quantum computers need to break certain problems.
What this means in practice
- •For quantum cryptography engineers: Develop stronger security proofs by precisely characterizing what quantum attackers can remember after querying cryptographic oracles.
- •For quantum algorithm designers: Use the framework to better understand time-memory tradeoffs in quantum search algorithms under specific symmetry conditions.
A theory result. No direct application yet.
Authors
Matthew Ding, Mark Zhandry
Abstract
Given a quantum adversary that queries a random oracle, how do we characterize the information that they "know"? The Compressed Oracle method of Zhandry (CRYPTO 2019) is one method that records the queries that the adversary makes; this recording serves as a representation of the information that is learned. However, a significant limitation of the Compressed Oracle method is that it may continue to store information that the adversary has "forgotten." This issue is especially pertinent in the space-bounded setting, where the adversary may uncompute information to free up space, while the information may still reside in the compressed oracle. In this work, we present a simple and interpretable framework called "Compressed Oracle Duality," which extends the Compressed Oracle method for space-bounded algorithms. By applying an isometry to the memory of a quantum adversary, we obtain a pair of compressed oracles with identical marginal distributions and classical correlations which correspond to the knowledge the adversary retains. In fact, we show that the outcome of measuring the new compressed oracle database corresponds exactly to applying the pretty-good measurement on the adversary's memory. As an application of our framework for collision search, we give a simplified proof of the recent $T^2S = Ω(N\log N)$ quantum time-space tradeoff for label-symmetric algorithms due to Magniez-Zur (arXiv:2609.10808); we also prove a stronger classical tradeoff of $TS=Ω(N\log N)$ assuming label symmetry. The proofs under our framework do not require representation theory and instead bound the mutual information between the compressed oracle pairs. This highlights both how the label symmetry assumption bypasses known proof barriers as well as the challenges that remain in achieving unconditional quantum time-space tradeoffs.