Paper 2025/1925

Improved Modeling for Substitution Boxes with Negative Samples and Beyond (Extended Version)

Anubhab Baksi, Lund University

Surajit Mandal, Indian Institute of Technology Madras

Santanu Sarkar, Indian Institute of Technology Madras

Abstract

A common way to perform classical cryptanalysis on symmetric-key ciphers is to encode the problem as an instance of the Mixed Integer Linear Programming (MILP) problem and then run the instance with an efficient solver. For this purpose, it is essential to model the components in a way that is compatible with the MILP formulation while preserving the characteristics of the cipher. In this work, we aim at the problem of efficiently encoding a substitution box (SBox for short). More specifically, we take the evaluation tables, namely, the Difference Distribution Table (DDT) that models for the differential cryptanalysis, the Linear Approximation Table (LAT) that models for the linear cryptanalysis, the Division Property Table (DPT) that models for the integral cryptanalysis, and the Boomerang Connectivity Table (BCT) that models for the boomerang cryptanalysis. In the current stage, the only model proposed/used in the literature is to look for the non-zero entries in the evaluation table and encode for that (this ultimately leads to the minimum number of active SBoxes for the target cipher). In our first contribution, we experiment with the complementary concept of using the zero entries (i.e., treating the zero entries as nonzero entries and vice versa). In our second contribution, we observe that the top row and column of each table (which are always taken into consideration) are actually redundant, as those are inherently taken care of through additional constraints at another level (which we call the `secondary structure’). We show the efficacy of our proposals by furnishing results on the evaluation tables on multiple SBoxes. In fact, the first proposal reduces the number of constraints for certain SBox evaluation tables (depending on the properties of the table). The second proposal, on the other hand, always reduces the number of constraints from the state-of-the-art results.

BibTeX

@misc{cryptoeprint:2025/1925,
author = {Debranjan Pal and Anubhab Baksi and Surajit Mandal and Santanu Sarkar},
title = {Improved Modeling for Substitution Boxes with Negative Samples and Beyond (Extended Version)},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/1925},
year = {2025},
url = {https://eprint.iacr.org/2025/1925}
}