Quantum Meet-in-the-Middle Attacks on Key-Length Extension Constructions

• URL: http://arxiv.org/abs/2511.09351v1
• Date: Thu, 13 Nov 2025 01:48:11 GMT
• Title: Quantum Meet-in-the-Middle Attacks on Key-Length Extension Constructions
• Authors: Min Liang, Ruihao Gao, Jiali Wu,
• Abstract summary: 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.
• Score: 3.767827267403057
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Key-length extension (KLE) techniques provide a general approach to enhancing the security of block ciphers by using longer keys. There are mainly two classes of KLE techniques, cascade encryption and XOR-cascade encryption. This paper presents several quantum meet-in-the-middle (MITM) attacks against two specific KLE constructions. For the two-key triple encryption (2kTE), we propose two quantum MITM attacks under the Q2 model. The first attack, leveraging the quantum claw-finding (QCF) algorithm, achieves a time complexity of $O(2^{2κ/3})$ with $O(2^{2κ/3})$ quantum random access memory (QRAM). The second attack, based on Grover's algorithm, achieves a time complexity of $O(2^{κ/2})$ with $O(2^κ)$ QRAM. The latter complexity is nearly identical to Grover-based brute-force attack on the underlying block cipher, indicating that 2kTE does not enhance security under the Q2 model when sufficient QRAM resources are available. For the 3XOR-cascade encryption (3XCE), we propose a quantum MITM attack applicable to the Q1 model. This attack requires no QRAM and has a time complexity of $O(2^{(κ+n)/2})$ ($κ$ and $n$ are the key length and block length of the underlying block cipher, respectively.), achieving a quadratic speedup over classical MITM attack. Furthermore, we extend the quantum MITM attack to quantum sieve-in-the-middle (SITM) attack, which is applicable for more constructions. We present a general quantum SITM framework for the construction $ELE=E^2\circ L\circ E^1$ and provide specific attack schemes for three different forms of the middle layer $L$. The quantum SITM attack technique can be further applied to a broader range of quantum cryptanalysis scenarios.

Related papers

• 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)
• 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)
• A distillation-teleportation protocol for fault-tolerant QRAM [95.99192129224721]
  We present a protocol for fault-tolerantly implementing the logical quantum random access memory (QRAM) operation.<n>For coherently accessing classical memories of size $2n$, our protocol consumes only $mathrmpoly(n)$ fault-tolerant quantum resources.
  arXiv  Detail & Related papers  (2025-05-26T17:42:56Z)
• Post-Quantum Cryptography: An Analysis of Code-Based and Lattice-Based Cryptosystems [55.49917140500002]
  Quantum computers will be able to break modern cryptographic systems using Shor's Algorithm.<n>We first examine the McEliece cryptosystem, a code-based scheme believed to be secure against quantum attacks.<n>We then explore NTRU, a lattice-based system grounded in the difficulty of solving the Shortest Vector Problem.
  arXiv  Detail & Related papers  (2025-05-06T03:42:38Z)
• Security of Key-Alternating Ciphers: Quantum Lower Bounds and Quantum Walk Attacks [5.221158079775365]
  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.
  arXiv  Detail & Related papers  (2024-12-06T13:23:29Z)
• 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 All-Subkeys-Recovery Attacks on 6-round Feistel-2* Structure Based on Multi-Equations Quantum Claw Finding [3.845166861382186]
  We propose a quantum all-subkeys-recovery (ASR) attack based on multi-equations quantum claw-finding. It only requires 3 plain-ciphertext pairs to quickly crack the 6-round Feistel-2* structure.
  arXiv  Detail & Related papers  (2023-09-24T04:40:48Z)
• 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)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• 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)

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.