<p>Differential-linear (DL) cryptanalysis, introduced by Langford and Hellman in 1994, has been widely studied since then. At EUROCRYPT 2019, Bar-On et al. proposed the Differential-Linear Connectivity Table (DLCT), which divides a target cipher <i>E</i> into three sub-ciphers: the differential part <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$E_{U}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>E</mi> <mi>U</mi> </msub> </math></EquationSource> </InlineEquation>, the middle part <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$E_{M}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>E</mi> <mi>M</mi> </msub> </math></EquationSource> </InlineEquation>, and the linear part <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$E_{L}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>E</mi> <mi>L</mi> </msub> </math></EquationSource> </InlineEquation>, i.e., <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$E=E_{L}\circ E_{M}\circ E_{U}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>E</mi> <mo>=</mo> <msub> <mi>E</mi> <mi>L</mi> </msub> <mo>∘</mo> <msub> <mi>E</mi> <mi>M</mi> </msub> <mo>∘</mo> <msub> <mi>E</mi> <mi>U</mi> </msub> </mrow> </math></EquationSource> </InlineEquation>. The primary task of DL cryptanalysis is to find high-correlation DL distinguishers. In recent years, automatic methods of searching for differential-linear (DL) distinguishers have received widespread attention. However, previous works failed to precisely characterize the integer weights of the three types of active S-boxes (differential active S-boxes in <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$E_{U}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>E</mi> <mi>U</mi> </msub> </math></EquationSource> </InlineEquation>, common active S-boxes in <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$E_{M}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>E</mi> <mi>M</mi> </msub> </math></EquationSource> </InlineEquation>, and linear active S-boxes in <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$E_{L}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>E</mi> <mi>L</mi> </msub> </math></EquationSource> </InlineEquation>) in the three parts <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$E_{L}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>E</mi> <mi>L</mi> </msub> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$E_{M}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>E</mi> <mi>M</mi> </msub> </math></EquationSource> </InlineEquation>, and <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$E_{U}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>E</mi> <mi>U</mi> </msub> </math></EquationSource> </InlineEquation>. Meanwhile, their main focus was on finding DL distinguishers with the minimum weighted sum of the three types of active S-boxes, which may not be optimal. In this paper, we aim to tackle these problems and present an improved automatic framework based on Mixed Integer Linear Programming (MILP) to identify better DL distinguishers. Firstly, we provide a more precise method to determine the integer weights of the three types of active S-boxes in DL distinguishers. Secondly, a heuristic search algorithm is proposed to find good truncated DL (TDL) trails, which are not limited to the minimum weighted sum of the three types of active S-boxes. Finally, we propose a “divide and conquer” strategy to instantiate the TDL trails. This strategy can find better DL distinguishers under the truncated patterns. As applications, we employ our automatic framework to search for DL distinguishers for SPN and Feistel block ciphers. For SPN block ciphers, the numbers of longest rounds of valid DL distinguishers for <Emphasis FontCategory="NonProportional">Midori64</Emphasis> and <Emphasis FontCategory="NonProportional">CRAFT</Emphasis> are extended by 2 rounds, respectively. The previous best 8-round and 10-round DL distinguishers for <Emphasis FontCategory="NonProportional">SKINNY64</Emphasis> are improved in terms of correlations. For Feistel block ciphers, the longest-round DL distinguisher for <Emphasis FontCategory="NonProportional">WARP</Emphasis> is extended from 22 to 23 rounds. For <Emphasis FontCategory="NonProportional">TWINE</Emphasis> and <Emphasis FontCategory="NonProportional">LBlock</Emphasis>, the previous best DL distinguishers are also improved in terms of correlations.</p>

An improved automatic framework for searching for differential-linear distinguishers with applications to SPN and Feistel block ciphers

期刊论文
发表日期：

2026年7月4日

查看全文

Yanyan Zhou,
Lin Jiao,
Senpeng Wang,
Yunong Wu,
Bin Hu,
Tairong Shi,
Kai Zhang

摘要

Differential-linear (DL) cryptanalysis, introduced by Langford and Hellman in 1994, has been widely studied since then. At EUROCRYPT 2019, Bar-On et al. proposed the Differential-Linear Connectivity Table (DLCT), which divides a target cipher E into three sub-ciphers: the differential part $E_{U}$ $E_{U}$ , the middle part $E_{M}$ $E_{M}$ , and the linear part $E_{L}$ $E_{L}$ , i.e., $E=E_{L}\circ E_{M}\circ E_{U}$ $E = E_{L} \circ E_{M} \circ E_{U}$ . The primary task of DL cryptanalysis is to find high-correlation DL distinguishers. In recent years, automatic methods of searching for differential-linear (DL) distinguishers have received widespread attention. However, previous works failed to precisely characterize the integer weights of the three types of active S-boxes (differential active S-boxes in $E_{U}$ $E_{U}$ , common active S-boxes in $E_{M}$ $E_{M}$ , and linear active S-boxes in $E_{L}$ $E_{L}$ ) in the three parts $E_{L}$ $E_{L}$ , $E_{M}$ $E_{M}$ , and $E_{U}$ $E_{U}$ . Meanwhile, their main focus was on finding DL distinguishers with the minimum weighted sum of the three types of active S-boxes, which may not be optimal. In this paper, we aim to tackle these problems and present an improved automatic framework based on Mixed Integer Linear Programming (MILP) to identify better DL distinguishers. Firstly, we provide a more precise method to determine the integer weights of the three types of active S-boxes in DL distinguishers. Secondly, a heuristic search algorithm is proposed to find good truncated DL (TDL) trails, which are not limited to the minimum weighted sum of the three types of active S-boxes. Finally, we propose a “divide and conquer” strategy to instantiate the TDL trails. This strategy can find better DL distinguishers under the truncated patterns. As applications, we employ our automatic framework to search for DL distinguishers for SPN and Feistel block ciphers. For SPN block ciphers, the numbers of longest rounds of valid DL distinguishers for Midori64 and CRAFT are extended by 2 rounds, respectively. The previous best 8-round and 10-round DL distinguishers for SKINNY64 are improved in terms of correlations. For Feistel block ciphers, the longest-round DL distinguisher for WARP is extended from 22 to 23 rounds. For TWINE and LBlock, the previous best DL distinguishers are also improved in terms of correlations.