One Standard-Oracle Real-or-Random Challenge Query Does Not Imply One Embedding Two-Ciphertext Challenge Query

–

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_{12} \;=\; \mathrm{learn}(*,CL)\text{-}\mathrm{chall}(1,ST,\mathrm{ror}), \qquad P_7 \;=\; \mathrm{learn}(*,CL)\text{-}\mathrm{chall}(1,EM,2\mathrm{ct}).\]

Both give the adversary classical learning queries and exactly one superposition challenge query. They differ only in how that one query is answered — standard oracle versus embedding oracle — and in how the challenge is phrased — real-or-random versus two-ciphertext.

Conjecture (\(P_{12} \not\Rightarrow P_7\)). 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_{12}\)-IND-CPA-secure and yet insecure in the sense of \(P_7\).

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, the equivalence classes and the quantum-one-way-function assumption are on pp. 5–6; the six conjectured non-implications on p. 44.

View PDF — no proof written yet · LaTeX source — no proof written yet · Formal proof — not yet formalized

Open, and the narrowest of the three cells this site records from the source.

What the source settles around it. \(P_{12}\)’s relation to five other panels is settled. On the other side, \(P_7\) is known not to be implied by the Boneh–Zhandry family or by the erasing-learning-query family. What is left open is whether \(P_{12}\) implies it.

Both are singletons. In the source’s classification each of these two panels is its own equivalence class — neither collapses into a larger group of notions proved equivalent. So the cell is a comparison between two isolated points, not between two families, and closing it does not come with a cluster of consequences the way c/0032 does.

Why the narrowness cuts both ways. With the learning phase classical and the challenge budget fixed at one on both sides, there is no query-budget slack for a separating scheme to exploit: the whole separation has to come from the difference between the standard and embedding oracles on a single query, together with the challenge phrasing. That makes a contrived separation harder to construct, and it also means a proof of the implication would have to be a genuine simulation argument rather than a counting one.

The standard and embedding models differ in who supplies the output register: in \(ST\) the adversary provides it and the oracle XORs into it, in \(EM\) the challenger provides it in state \(|0\rangle\). On a classical query the distinction vanishes. On a superposition query it does not, because an adversary that supplies its own register may prepare it entangled with something else — which is precisely the freedom the embedding model removes.

Boneh and Zhandry’s impossibility is what makes this pair worth stating at all: a superposition challenge returning ciphertexts in the standard model is unachievable, which is why \(P_{12}\) phrases its standard-model challenge as real-or-random rather than two-ciphertext. So the two panels are not “the same challenge through two oracles” — the phrasing had to change to keep the standard-model side achievable, and the conjecture is that the resulting notions are incomparable.