Key-length extension (KLE) techniques provide a general approach to enhance the security of block ciphers. There are two primary categories of KLE techniques: cascade encryption and XOR-cascade encryption. We present several quantum meet-in-the-middle (MITM) attacks on them. 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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$O(2^{2\kappa /3})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mn>2</mn> <mrow> <mn>2</mn> <mi>κ</mi> <mo stretchy="false">/</mo> <mn>3</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> with <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$O(2^{2\kappa /3})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mn>2</mn> <mrow> <mn>2</mn> <mi>κ</mi> <mo stretchy="false">/</mo> <mn>3</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> quantum random access memory (QRAM). The second attack, based on Grover’s algorithm, achieves a time complexity of <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$O(2^{\kappa /2})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mn>2</mn> <mrow> <mi>κ</mi> <mo stretchy="false">/</mo> <mn>2</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> with <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$O(2^\kappa )$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mn>2</mn> <mi>κ</mi> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> QRAM. The latter complexity is nearly identical to that of Grover-based brute-force attack against the underlying block cipher, indicating that 2kTE provides no asymptotic security enhancement under the Q2 model. 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 <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$O(2^{(\kappa +n)/2})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mn>2</mn> <mrow> <mo stretchy="false">(</mo> <mi>κ</mi> <mo>+</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo stretchy="false">/</mo> <mn>2</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> (<InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\kappa $</EquationSource> <EquationSource Format="MATHML"><math> <mi>κ</mi> </math></EquationSource> </InlineEquation> 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 to more constructions. We present a general quantum SITM framework for the construction <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$ELE=E^2\circ L\circ E^1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>E</mi> <mi>L</mi> <mi>E</mi> <mo>=</mo> <msup> <mi>E</mi> <mn>2</mn> </msup> <mo>∘</mo> <mi>L</mi> <mo>∘</mo> <msup> <mi>E</mi> <mn>1</mn> </msup> </mrow> </math></EquationSource> </InlineEquation> 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.

Quantum meet-in-the-middle attacks on key-length extension constructions

期刊论文
发表日期：

2026年6月15日

查看全文

Min Liang,
Ruihao Gao,
Jiali Wu

摘要

Key-length extension (KLE) techniques provide a general approach to enhance the security of block ciphers. There are two primary categories of KLE techniques: cascade encryption and XOR-cascade encryption. We present several quantum meet-in-the-middle (MITM) attacks on them. 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\kappa /3})$ $O (2^{2 κ / 3})$ with $O(2^{2\kappa /3})$ $O (2^{2 κ / 3})$ quantum random access memory (QRAM). The second attack, based on Grover’s algorithm, achieves a time complexity of $O(2^{\kappa /2})$ $O (2^{κ / 2})$ with $O(2^\kappa )$ $O (2^{κ})$ QRAM. The latter complexity is nearly identical to that of Grover-based brute-force attack against the underlying block cipher, indicating that 2kTE provides no asymptotic security enhancement under the Q2 model. 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^{(\kappa +n)/2})$ $O (2^{(κ + n) / 2})$ ( $\kappa $ $κ$ 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 to more constructions. We present a general quantum SITM framework for the construction $ELE=E^2\circ L\circ E^1$ $E L E = 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.