MILP-based automatic search algorithms for differential-linear distinguishers

Abstract Differential-linear (DL) cryptanalysis divides the target cipher $E$ into three part, i.e. $E = E_{2} \circ E_{m} \circ E_{1}$. Existing DL distinguishers search frameworks typically begin by estimating the theoretical correlation of $E_{m}$, followed by an experimental evaluation to determine its precise value. However, the deviation between the actual correlation and the theoretical correlation often renders the distinguishers identified by the models invalid. In this paper, we propose a pre-pruning technique to reduce the frequency of invalid distinguishers and improve the existing Mixed-Integer Linear Programming (MILP)-based DL distinguishers search frameworks. Specifically, we first filter the output differences of $E_{d}$ according to the probability of one-round differential characteristics. Subsequently, we identify the high-correlation bits of the output mask of the middle part and designate the low-correlation bits as inactive mask bits in our MILP models for each selected difference. Our pre-pruning technique significantly reduces the number of low-correlation distinguishers in the model’s solution pool, allowing our tool to identify more valid DL distinguishers from a larger pool of higher quality candidates under limited computing resources. As an application, we find $12$-round and nine-round DL distinguishers for GIFT-64 and LELBC, respectively, and improve the best-known $13$-round DL distinguisher of PRESENT by one round. To the best of our knowledge, our nine-round DL distinguisher is the best distinguisher for LELBC in the single-key scenario.