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

Manjeet Kaur; Tarun Yadav; Manoj Kumar; Dhananjoy Dey

Paper 2024/2054

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

Manjeet Kaur

, Indian Institute of Information Technology, Lucknow, U.P., INDIA-226 002

Tarun Yadav

, Scientific Analysis Group, DRDO, Delhi, INDIA-110 054

Manoj Kumar

, Scientific Analysis Group, DRDO, Delhi, INDIA-110 054

Dhananjoy Dey

, Indian Institute of Information Technology, Lucknow, U.P., INDIA-226 002

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.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: GIFT-64 Impossible Differentials IVLBC MILP Representative Set
Contact author(s): rmm21101 @ iiitl ac in
tarunyadav sag @ gov in
manojkumar sag @ gov in
ddey @ iiitl ac in
History: 2024-12-22: approved; 2024-12-20: received; See all versions
Short URL: https://ia.cr/2024/2054
License: CC BY

BibTeX

@misc{cryptoeprint:2024/2054,
      author = {Manjeet Kaur and Tarun Yadav and Manoj Kumar and Dhananjoy Dey},
      title = {Greedy Algorithm for Representative Sets: Applications to {IVLBC} and {GIFT}-64 in Impossible Differential Attack},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/2054},
      year = {2024},
      url = {https://eprint.iacr.org/2024/2054}
}