One Erasing Challenge Query Does Not Buy Security Against Many Embedding Learning Queries
Statement: AI-written, not yet formalized. Proof: open – no attempt yet.
View PDF · LaTeX source · Formal statement — not yet formalized
In the source’s classification (see c/0031 for the three query models and the panel notation), the two panels at issue are
\[P_3 \;=\; \mathrm{learn}(*,CL)\text{-}\mathrm{chall}(1,ER,2\mathrm{ct}), \qquad P_{11} \;=\; \mathrm{learn}(*,EM)\text{-}\mathrm{chall}(*,CL,1\mathrm{ct}).\]
\(P_3\) gives the adversary classical learning queries and exactly one superposition challenge query, answered by an erasing oracle, in two-ciphertext form. \(P_{11}\) gives it polynomially many superposition learning queries in the embedding model and a classical one-ciphertext challenge.
Conjecture (\(P_3 \not\Rightarrow P_{11}\)). Assume quantum-secure one-way functions exist. Then there are polynomially bounded parameters and a symmetric encryption scheme \(\Pi = (\mathsf{KGen}, \mathsf{Enc}, \mathsf{Dec})\) that is \(P_3\)-IND-CPA-secure and yet insecure in the sense of \(P_{11}\).
The two notions trade a strong challenge against many strong learning queries, which is why neither obviously dominates: one superposition challenge is the most the erasing model can be asked for, and polynomially many embedding learning queries are the most the learning phase can be asked for.
Sources
- Carstens, Ebrahimi, Tabia, and Unruh. Relationships between quantum IND-CPA notions. Cryptology ePrint Archive, Report 2020/596. Read at the revision of 13 October 2021, byte-identical to the harvested copy (SHA-256 prefix
6bf24750709898e7, 47 pages). The panel classification and the quantum-one-way-function assumption are on p. 6; the list of six conjectured non-implications and the transitivity remark on p. 44.
View PDF — no proof written yet · LaTeX source — no proof written yet · Formal proof — not yet formalized
Open.
What the source settles around it. \(P_3\) implies four other panels and is separated from two more; its relation to six panels — \(P_{11}\) among them — is left open.
Why this one is worth attacking first. The source marks six non-implications whose joint resolution closes all 41 of its open cells by transitivity, and on its own bookkeeping this is the one whose resolution would settle the largest number of them. A single scheme would therefore do a disproportionate amount of work on the table.
Where the difficulty sits. A separating scheme must survive a single erasing two-ciphertext challenge — the erasing oracle consumes its input, so the adversary cannot retain the message register it queried — while being broken by an adversary that may make polynomially many embedding-model learning queries. The two requirements pull in opposite directions: whatever structure the scheme exposes to the many-learning-query attack must be invisible to the one-challenge game.
The panel classification exists because the classical picture collapses: with classical queries, one-ciphertext, two-ciphertext and real-or-random IND-CPA are all equivalent up to polynomial loss, and there is nothing to compare. Superposition access separates the notions along two independent axes at once — how many superposition queries, and which oracle answers them — and the source’s contribution is to work out which of the resulting combinations imply which.
What makes this cell different from c/0031 is that the comparison is not oracle-against-oracle at a fixed query budget; it is a budget trade. That is also why it closes so many other cells: a scheme separating one strong challenge from many strong learning queries says something about every panel sitting between them.