Skip to content
Preprint

Compressed Oracle Duality: A simple framework for knowing what quantum adversaries know

Oct 2026 · 0 citations · 43 references
Physics Computer Science

TL;DR

This work presents a simple and interpretable framework called "Compressed Oracle Duality," which extends the Compressed Oracle method for space-bounded algorithms and gives a simplified proof of the recent quantum time-space tradeoff for label-symmetric algorithms due to Magniez-Zur.

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 = \Omega(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=\Omega(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.

View source

Similar papers

Preprint Oct 2026

Indistinguishability Lifting for Keyed Oracles, Compressed Ideal Cipher, and More Applications

A generic indistinguishability lifting theorem is established: if the two base oracles are indistinguishable under quantum queries, then their corresponding keyed oracles are too, up to an O(q^2) multiplicative loss in distinguishing advantage, where q is the number of queries made by the adversary.

Ritam Bhaumik, Yu-Hsuan Huang · 0 citations
Preprint Sep 2026

Oracle Distillation

Learning and sensing are among the most promising applications of quantum technology, often with provable quantum advantages. In any realistic experiment, however, noise threatens to erase these advantages as the problem size grows. We introduce oracle distillation, a procedure that distills many queries to a noisy ora...

Ruo-Han Shen, Soonwon Choi · 1 citation
Preprint Sep 2026

Compressed Permutation Oracles Revisited

The compressed permutation oracle has been used to analyze the quantum security of a number of cryptographic constructions which resisted prior techniques. However, these analyses were fundamentally limited by the poor soundness of the method: the technique was proven sound only up to $O(N^{1/12})$ queries to permutati...

J. Carolan, Christian Majenz · 3 citations

UvA-DARE (Digital

The first complete post-quantum security proof of the textbook Fujisaki-Okamoto transformation is presented, i.e, without adjustments to facilitate the proof, including concrete security bounds, including concrete security bounds.

Jelle Don, S. Fehr, Christian Majenz et al. · 0 citations
Sep 2026

Need for Coherent Access in Constructing Quantum Cryptography

It is shown that fully black-box PRS length extension from logarithmic to superlogarithmic output length must use coherent access to the underlying short PRS, giving an oracle separation between classically accessible logarithmic length PRFSs and superlogarithmic length PRSs.

Minki Hhan, Changhun Oh, Vaughn Sohn · 0 citations
Preprint Oct 2026

How to Build Pseudorandom Unitaries in Microcrypt

We provide the first evidence relative to a classical oracle that pseudorandom unitaries (PRUs) can exist without quantum-computable one-way functions. To obtain this result, we first prove that five independent random diagonal phase layers interleaved with Hadamard transforms \[ U=F_5HF_4HF_3HF_2HF_1 \] form a strong...

Aditya Gulati, Dakshita Khurana, Kabir Tomer · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.