Paper 2024/2054 Original: eprint.iacr.org/2024/2054 ↗

Greedy Algorithm for Representative Sets: Applications to IVLBC and GIFT-64 in Impossible Differential Attack

Abstract

The impossible differential (ID) attack is crucial for analyzing the strength of block ciphers. The critical aspect of this technique is to identify IDs, and the researchers introduced several methods to detect them. Recently, the researchers extended the mixed-integer linear programming (MILP) approach by partitioning the input and output differences to identify IDs. The researchers proposed techniques to determine the representative set and partition table of a set over any nonlinear function. In this paper, we introduce a deterministic algorithm using the greedy approach~\cite{cormen2022introduction} for finding the representative set and partition table of a set over any nonlinear function. This algorithm iteratively selects the set that covers the maximum uncovered elements of the target set. This performs better than the existing algorithms in terms of time complexity. We use this algorithm to compute the representative sets and partition tables of the two block ciphers, IVLBC and GIFT-64, and identify 6-round IDs for them. Our research contributes a deterministic algorithm to compute the representative set and partition table of a set over any nonlinear function with at most 16-bit input size.