arXiv:2610.04674
Indistinguishability Lifting for Keyed Oracles, Compressed Ideal Cipher, and More Applications
Ritam Bhaumik, Yu-Hsuan Huang
Abstract
Cryptographic security proofs often involve an adversary interacting with a larger, keyed oracle that consists of (potentially exponentially) many independent instances of a smaller, base oracle. However, showing quantum indistinguishability between two such keyed oracles can be tricky, since a single query made by an adversary may involve a superposition that covers all instances of the base oracles simultaneously. In this paper, we establish a generic indistinguishability lifting theorem of the following form: 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. Our lifting theorem applies to both statistical and computational settings, and to oracles that are stateful as well. It is also optimal in that it matches the obvious Grover search attack for a certain (contrived) choice of oracles. As an immediate application, we extend Carolan's compressed permutation oracle to an efficiently implementable compressed ideal cipher, and use it to prove preimage resistance of the Davies-Meyer compression function in the quantum ideal cipher model. Thanks to our lifting theorem, the soundness of our compressed ideal cipher reduces to that of Carolan's oracle, and any further improvement on the latter would automatically carry over to the former. As our second application, we give a modular construction that doubles the message length of any quantum-secure strong pseudorandom permutation. Along the way, we show that an existing two-round tweakable Feistel construction is indistinguishable from a random permutation under quantum bidirectional queries. This is done via a dedicated polynomial-method argument, which may be of independent interest.
AI Summary
The paper asks whether quantum indistinguishability of two base oracles survives replacing each by a keyed family of independent instances, when queries may superpose exponentially many keys. It proves a generic lifting theorem: a $q$-query distinguisher for the keyed families with advantage $\epsilon$ yields a base-oracle distinguisher with advantage at least $\epsilon/(8q^2)$. The result accommodates stateful oracles and statistical or computational security. Formally, the reduction also accesses both reference keyed families; these accesses can be internalized in the statistical setting or when the reference oracles are efficiently implementable. The proof uses random biased routing between oracle instances, relates derivatives of distinguishing-probability polynomials, and applies a constructive Markov inequality to obtain the reduction. A Grover-search example shows that the quadratic loss is unavoidable for arbitrary black-box oracles. Applications include an efficiently implementable compressed ideal cipher, with distinguishing bound $8q^2\Delta_{\mathrm{cpO}}(n,q)=O(q^3/2^{n/2})$, and a Davies–Meyer preimage-resistance bound. A second application doubles the domain of a quantum-secure strong PRP through PRF-based tweak-key derivation and a two-round tweakable construction. Its security loss is quadratic in $q$ on the underlying PRP advantage, with an additional $O(\lceil\lambda/n\rceil q^3/2^n+q^4/2^n)$ term. The two-round analysis uses polynomial symmetrization and counting input–output constraints. The paper notes that concurrent direct analysis gives a tighter $O(q/2^{n/2})$ compressed-ideal-cipher bound and $O(q^2/2^n)$ Davies–Meyer preimage bound; generic lifting need not be tight for particular oracle pairs.
GPT-6~Astra helped us with several counting arguments concerning randomized matrices and contributed to the idea of rerandomizing the permutation oracle
Central claim may not hold: The abstract's unqualified computational lifting claim is established only with auxiliary keyed-oracle access, or under an additional efficient-simulation condition that allows the reduction to internalize that access.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.