arXiv:2609.40350
On The Simplest Quantum-Secure Block Cipher
Gorjan Alagic, Joseph Carolan, Christian Majenz, Saliha Tokat
Abstract
Pseudorandom permutations are ubiquitous in theoretical and applied cryptography. PRPs that offer security even against adversaries making quantum queries are of increasing interest, and used in applications ranging from constructing pseudorandom unitaries to separating SZK from BQP. A successful framework for constructing classically-secure PRPs is the key-alternating Even-Mansour approach, which interleaves applications of public permutations with additions of round keys. The single-round construction is already classically secure in the ideal permutation model (IPM), with added rounds offering improved concrete security. However, in the quantum-query setting, the status of this framework is presently unclear. A simple quantum-query attack based on Simon's algorithm breaks the one-round cipher. For two or more rounds, security is only known against non-adaptive adversaries who must prepare all queries in advance. In this work, we show that the two-round Even-Mansour cipher is information theoretically secure in the IPM against adversaries making polynomially-many adaptive forward and inverse quantum queries to all available oracles. Our proof uses compressed permutation oracles and a specially crafted isometry relating the ideal and real experiments. We also show that this construction is minimal, in the sense that essentially any cipher constructed via a single call to a public permutation is quantumly insecure.
AI Summary
The paper asks whether key-alternating block ciphers can be secure against adaptive quantum queries to both the cipher and its public permutations, including inverse queries (the Q2 model). One-round Even–Mansour is vulnerable to Simon’s algorithm; previously stated security results for two or more rounds covered only non-adaptive adversaries. It proves information-theoretic Q2 security for two-round Even–Mansour, $E_k(x)=P_2(P_1(x\oplus k_1)\oplus k_2)\oplus k_3$, with independent uniformly random public permutations and independent uniform keys. Writing $N=2^n$, any computationally unbounded adversary making $q\leq\sqrt{N/2}$ total queries has distinguishing advantage at most $O(\sqrt{q^3/N})+O(q/\sqrt N)$. Thus polynomial-query adversaries have negligible advantage, and the bound is nontrivial for $q=o(N^{1/3})$. The proof combines compressed permutation oracles with an ideal-to-real database isometry, query-by-query hybrids, and a symmetry argument handling inverse queries. A complementary impossibility result rules out information-theoretic security for deterministic one-public-permutation-query constructions that are permutations for every public permutation and key. For public and cipher block lengths $n,m$, and key length $\kappa$, a Choi-state distinguisher needs $O(\kappa+1+n/m)$ queries, assuming $\kappa+1+n/m=o(2^m)$; its offline computation need not be efficient. The security analysis is in the ideal permutation model, not for concrete permutations. Its query bound does not match the best-known $\tilde O(N^{1/2})$ attacks. The impossibility theorem requires exact bijectivity and a sufficiently large cipher domain; removing the bijectivity requirement is left open.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.