[Resource Topic] 2025/945: Quantum Security Analysis of the Key-Alternating Ciphers

Resource Secret-key cryptography
1

Welcome to the resource topic for 2025/945

Title:
Quantum Security Analysis of the Key-Alternating Ciphers

Authors: Chen Bai, Mehdi Esmaili, Atul Mantri

Abstract:

In this work, we study the quantum security of key-alternating ciphers (KAC), a natural multi-round generalization of the Even–Mansour (EM) cipher underlying many block cipher constructions, including AES. While the classical security of KAC and the quantum security of the 1-round KAC (i.e. Even-Mansour) cipher are well understood, the quantum resistance of multi-round KAC remains largely unexplored. We focus on the 2-round KAC construction, defined using public n-bit permutations P_1, P_2 and keys k_0, k_1, and k_2 as E(x) = P_2(P_1(x \oplus k_0) \oplus k_1) \oplus k_2. Our main contributions are as follows:

  1. Quantum Lower Bounds. We provide the first formal analysis showing that a 2-round KAC is quantum-secure in both the Q1 and Q2 models. Specifically, in the Q1 model, a (non-adaptive) adversary must make at least 2^{2n/5} quantum queries to the public permutations and at least 2^{2n/5} classical queries to the cipher in order to distinguish it from a random permutation (in contrast to the classical lower bound of 2^{2n/3} queries). As a corollary, we show that in the Q2 model, a (non-adaptive) adversary requires 2^{n/4} quantum queries. To achieve such a result, we employ the quantum hybrid method along with recently proposed lifting theorems in the ideal cipher and random permutation oracle model.

  2. Quantum Key-Recovery Attack. We give the first nontrivial quantum key-recovery attack on multi-round KAC in the Q1 model where the adversary has quantum access to all of the public permutations. Our quantum attack applies to any t-round KAC and achieves quantum query complexity O(2^{\alpha n}), where \alpha = \frac{t(t+1)}{(t+1)^2 + 1}, improving over the best known classical bound of O(2^{\alpha' n}), where \alpha' = \frac{t}{t+1}, from Bogdanov et al. (EUROCRYPT 2012). The attack leverages a novel application of quantum walk algorithms specifically adapted to the KAC structure.

  3. The Q1^* Model. To bridge the classical and Q1 settings, we introduce the Q1^*, in which the adversary has quantum superposition access to at most one permutation. This model is crucial for our Q1 lower bound and supports similar key-recovery attacks to Q1, using fewer quantum resources. We believe Q1^* is of independent interest.

ePrint: https://eprint.iacr.org/2025/945

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .