Security of Key-Alternating Ciphers: Quantum Lower Bounds and Quantum Walk Attacks

• URL: http://arxiv.org/abs/2412.05026v3
• Date: Thu, 09 Oct 2025 18:14:51 GMT
• Title: Security of Key-Alternating Ciphers: Quantum Lower Bounds and Quantum Walk Attacks
• Authors: Chen Bai, Mehdi Esmaili, Atul Mantri,
• Abstract summary: We study the quantum security of key-alternating ciphers (KAC)<n>We prove security of the $t$-round KAC against a non-adaptive adversary in both the Q1 and Q2 models.<n>We give the first non-trivial quantum key-recovery algorithm for $t$-round KAC in the Q1 model.
• Score: 5.221158079775365
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the quantum security of key-alternating ciphers (KAC), a natural multi-round generalization of the Even--Mansour construction. KAC abstracts the round structure of practical block ciphers as public permutations interleaved with key XORs. The $1$-round KAC or EM setting already highlights the power of quantum superposition access: EM is secure against classical and Q1 adversaries (quantum access to the public permutation), but insecure in the Q2 model. The security of multi-round KACs remain largely unexplored; in particular, whether the quantum-classical separation extends beyond a single round had remained open. 1) Quantum Lower Bounds. We prove security of the $t$-round KAC against a non-adaptive adversary in both the Q1 and Q2 models. In the Q1 model, any distinguiser requires $\Omega(2^{\frac{tn}{2t+1}})$ oracle queries to distinguish the cipher from a random permutation, whereas classically any distinguisher needs $\Omega(2^{\frac{tn}{t+1}})$ queries. As a corollary, we obtain a Q2 lower bound of $\Omega (2^{\frac{(t-1)n}{2t}})$ quantum queries. Thus, for $t \geq 2$, the exponential Q1-Q2 gap collapses in the non-adaptive setting, partially resolving an open problem posed by Kuwakado and Morii (2012). Our proofs develop a controlled-reprogramming framework within a quantum hybrid argument, sidestepping the lack of quantum recording techniques for permutation-based ciphers; we expect this framework to be useful for analyzing other post-quantum symmetric primitives. 2) Quantum Key-Recovery Attack. We give the first non-trivial quantum key-recovery algorithm for $t$-round KAC in the Q1 model. It makes $O(2^{\alpha n})$ queries with $\alpha = \frac{t(t+1)}{(t+1)^2 + 1}$, improving on the best known classical bound of $O(2^{\alpha' n})$ with $\alpha' = \frac{t}{t+1}$. The algorithm adapts quantum walk techniques to the KAC structure.

Related papers

• Quantum Meet-in-the-Middle Attacks on Key-Length Extension Constructions [3.767827267403057]
  Key-length extension (KLE) techniques provide a general approach to enhancing the security of block ciphers by using longer keys.<n>This paper presents several quantum meet-in-the-middle (MITM) attacks against two specific KLE constructions.
  arXiv  Detail & Related papers  (2025-11-12T14:03:20Z)
• Offline Dedicated Quantum Attacks on Block Ciphers Based on Two Parallel Permutation-Based Pseudorandom Functions [3.9213113404194666]
  Shi it et al. introduced the dedicated quantum attack on XOR-type function.<n>We propose an offline quantum attack on block ciphers based on TPP-PRFs.<n>Compared to previous results, our offline attack exhibits significantly reduced query complexity.
  arXiv  Detail & Related papers  (2025-10-16T09:19:32Z)
• On the Cryptographic Futility of Non-Collapsing Measurements [13.234610219099102]
  We investigate quantum analogues of collision resistance and obtain separations between quantum one-way'' and collision-resistant'' primitives.
  arXiv  Detail & Related papers  (2025-10-06T17:36:22Z)
• Quantum Key-Recovery Attacks on FBC Algorithm [2.2002244657481826]
  We present a comprehensive security analysis of the FBC quantum adversaries with different query capabilities.<n>Considering an adversary with classical queries and quantum computing capabilities, we demonstrate low-data quantum key-recovery attacks on FBC-KF/FK structures.
  arXiv  Detail & Related papers  (2025-08-01T09:08:53Z)
• Towards Unconditional Uncloneable Encryption [1.18749525824656]
  Uncloneable encryption is a cryptographic primitive which encrypts a classical message into a quantum ciphertext. We show that the adversary's success probability in the related security game converges quadratically as $1/2+1/ (2sqrtK)$, where $K$ represents the number of keys and $1/2$ is trivially achievable.
  arXiv  Detail & Related papers  (2024-10-30T14:40:06Z)
• Entanglement-assisted Quantum Error Correcting Code Saturating The Classical Singleton Bound [44.154181086513574]
  We introduce a construction for entanglement-assisted quantum error-correcting codes (EAQECCs) that saturates the classical Singleton bound with less shared entanglement than any known method for code rates below $ frackn = frac13 $. We demonstrate that any classical $[n,k,d]_q$ code can be transformed into an EAQECC with parameters $[n,k,d;2k]]_q$ using $2k$ pre-shared maximally entangled pairs.
  arXiv  Detail & Related papers  (2024-10-05T11:56:15Z)
• Efficient unitary designs and pseudorandom unitaries from permutations [35.66857288673615]
  We show that products exponentiated sums of $S(N)$ permutations with random phases match the first $2Omega(n)$ moments of the Haar measure. The heart of our proof is a conceptual connection between the large dimension (large-$N$) expansion in random matrix theory and the method.
  arXiv  Detail & Related papers  (2024-04-25T17:08:34Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• Generalized Hybrid Search and Applications to Blockchain and Hash Function Security [50.16790546184646]
  We first examine the hardness of solving various search problems by hybrid quantum-classical strategies. We then construct a hybrid quantum-classical search algorithm and analyze its success probability.
  arXiv  Detail & Related papers  (2023-11-07T04:59:02Z)
• Quantum Symmetric Private Information Retrieval with Secure Storage and Eavesdroppers [32.97918488607827]
  We consider both the classical and quantum variations of $X$-secure, $E$-eavesdropped and $T$-colluding symmetric private information retrieval (SPIR) We first develop a scheme for classical $X$-secure, $E$-eavesdropped and $T$-colluding SPIR (XSETSPIR) based on a modified version of cross subspace alignment (CSA)
  arXiv  Detail & Related papers  (2023-08-21T17:30:38Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
  arXiv  Detail & Related papers  (2022-10-12T17:54:02Z)
• A Variational Quantum Attack for AES-like Symmetric Cryptography [69.80357450216633]
  We propose a variational quantum attack algorithm (VQAA) for classical AES-like symmetric cryptography. In the VQAA, the known ciphertext is encoded as the ground state of a Hamiltonian that is constructed through a regular graph.
  arXiv  Detail & Related papers  (2022-05-07T03:15:15Z)
• Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
  Two models of quantum computation: CQ_d and QC_d. CQ_d captures the scenario of a d-depth quantum computer many times; QC_d is more analogous to measurement-based quantum computation. We show that, despite the similarities between CQ_d and QC_d, the two models are intrinsically, i.e. CQ_d $nsubseteq$ QC_d and QC_d $nsubseteq$ CQ_d relative to an oracle.
  arXiv  Detail & Related papers  (2022-01-06T03:10:53Z)
• Speeding up Learning Quantum States through Group Equivariant Convolutional Quantum Ans\"atze [13.651587339535961]
  We develop a framework for convolutional quantum circuits with SU$(d)$symmetry. We prove Harrow's statement on equivalence between $nameSU(d)$ and $S_n$ irrep bases.
  arXiv  Detail & Related papers  (2021-12-14T18:03:43Z)
• Post-Quantum Security of the Even-Mansour Cipher [14.141778162933013]
  Even-Mansour cipher is secure against classical attacks. Even-Mansour can still be proven secure in natural, "post-quantum" setting.
  arXiv  Detail & Related papers  (2021-12-14T16:43:34Z)
• Beyond quadratic speedups in quantum attacks on symmetric schemes [30.01567358439495]
  We report the first quantum key-recovery attack on a symmetric block cipher design, using classical queries only. Our attack shows that the structure of some symmetric constructions can be exploited to overcome this limit.
  arXiv  Detail & Related papers  (2021-10-06T15:10:31Z)
• Efficient Quantum Public-Key Encryption From Learning With Errors [1.8021287677546958]
  Our main result is a quantum public-key encryption scheme based on the Extrapolated Dihedral Coset problem (EDCP) For limited number of public keys, the proposed scheme is information-theoretically secure.
  arXiv  Detail & Related papers  (2021-05-26T18:48:26Z)
• Quantum Multi-Solution Bernoulli Search with Applications to Bitcoin's Post-Quantum Security [67.06003361150228]
  A proof of work (PoW) is an important cryptographic construct enabling a party to convince others that they invested some effort in solving a computational task. In this work, we examine the hardness of finding such chain of PoWs against quantum strategies. We prove that the chain of PoWs problem reduces to a problem we call multi-solution Bernoulli search, for which we establish its quantum query complexity.
  arXiv  Detail & Related papers  (2020-12-30T18:03:56Z)
• Quantum copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
  We introduce a quantum copy-protection scheme for a class of evasive functions known as " compute-and-compare programs" We prove that our scheme achieves non-trivial security against fully malicious adversaries in the quantum random oracle model (QROM) As a complementary result, we show that the same scheme fulfils a weaker notion of software protection, called "secure software leasing"
  arXiv  Detail & Related papers  (2020-09-29T08:41:53Z)
• Succinct Blind Quantum Computation Using a Random Oracle [0.8702432681310399]
  We give a new universal blind quantum computation protocol. The protocol's first phase is succinct, that is, its complexity is independent of circuit size.
  arXiv  Detail & Related papers  (2020-04-27T07:47:11Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)
• Backflash Light as a Security Vulnerability in Quantum Key Distribution Systems [77.34726150561087]
  We review the security vulnerabilities of quantum key distribution (QKD) systems. We mainly focus on a particular effect known as backflash light, which can be a source of eavesdropping attacks.
  arXiv  Detail & Related papers  (2020-03-23T18:23:12Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.