Implications between quantum IND-CPA notions for symmetric encryption
Which of the panels survive superposition access, and which of the 41 open cells close by transitivity
Motivation
Classically there is nothing here to study: the one-ciphertext, two-ciphertext and real-or-random forms of chosen-plaintext indistinguishability for symmetric encryption are all equivalent up to polynomial loss. Give the adversary superposition access to the encryption oracle and the equivalences fail, for two independent reasons. The challenge phrasing stops being interchangeable — Boneh and Zhandry showed a superposition challenge returning ciphertexts in the standard model is simply unachievable — and, separately, how the oracle hands its answer back becomes part of the definition.
Three query models are in use. In the standard model \(ST\) the adversary supplies the output register and the oracle XORs into it. In the embedding model \(EM\) the challenger supplies it in state \(|0\rangle\). In the erasing model \(ER\) the isometry consumes the input register and returns only the image. On a classical query the three coincide; on a superposition query they do not, and the differences are exactly where the separations live.
Crossing those choices — classical or superposition, which oracle, which challenge phrasing, at the learning stage and at the challenge stage — gives a grid of panels \(P_1, \ldots, P_{13}\). The research question is the implication order on that grid.
Provenance and history
The classification, and the open cells, are from Carstens, Ebrahimi, Tabia and Unruh, Relationships between quantum IND-CPA notions, ePrint 2020/596, read at the revision of 13 October 2021 — the later of two postings, and byte-identical to the copy this site harvested.
Two facts about the paper shape everything on this page. First, it leaves 41 cells of its implication table open — so this is a partially-mapped order, not a settled one. Second, it marks six non-implications with dashed arrows and observes that “if they hold, all the open questions will be resolved by the transitivity”. The six are not equally valuable: closing some settles more cells than closing others.
Three of those six are tracked here as their own statements. Every one is stated under the paper’s own uniform assumption — “All of non-implications hold on the assumption of the existence of a quantum secure one-way function” — so none of them is unconditional, and each is a construction task: exhibit a scheme secure under one notion and broken under the other.
The three tracked cells
| cell | notions | why it is interesting |
|---|---|---|
| c/0031 | \(P_4 \not\Rightarrow P_6\) | erasing real-or-random against Boneh–Zhandry. The reverse is known only in the quantum random oracle model, so this is the standard-model half of an asymmetric pair. |
| c/0032 | \(P_3 \not\Rightarrow P_{11}\) | one strong challenge against many strong learning queries. On the paper’s own bookkeeping, the highest-leverage of the six — resolving it closes the most remaining cells. |
| c/0033 | \(P_{12} \not\Rightarrow P_7\) | both panels are singleton equivalence classes, both fix a classical learning phase and one challenge query. The narrowest cell, and the one with no query-budget slack to exploit. |
The other three of the paper’s six conjectured non-implications are not tracked on this site. That is a gap in coverage rather than a judgment about them: nobody has transcribed them here yet.
What would close the table
The paper’s transitivity observation is the reason to care about these cells individually rather than the 41 collectively. A separation is a construction — a single scheme, secure one side and broken the other — and each such construction propagates through the implications already proved. So the practical question for anyone attacking this is not “which cell is open” but “which construction buys the most”, and the paper answers that: c/0032 first.
Two caveats worth carrying. The quantum-secure one-way function assumption is the paper’s uniform framing, and whether each individual separation actually needs it is unexamined. And the one known non-implication in this neighbourhood that is proved — \(P_6 \not\Rightarrow P_4\) — holds in the quantum random oracle model only, so moving it to the standard model is an open problem the paper does not list among its six.