@inproceedings{ba643296-3c48-48a2-b9a7-9478ea5b253d,
  abstract     = {{<p>It is a common practice for symmetric-key ciphers is to encode a cryptanalysis problem as an instance of the Mixed Integer Linear Programming (MILP) 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 look 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), the Linear Approximation Table (LAT), the Division Property Table (DPT) and the Boomerang Connectivity Table (BCT). In the current stage, the only model proposed/used in the literature is to look for the positive samples (i.e., 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 negative samples (i.e., treating the zero entries as non-zero entries and vice versa), finally a proper recovery procedure is performed to get back to the original problem. In our second contribution, we observe that the top row and column of each table (which are always taken into consideration by the past researchers) are actually redundant, as those are inherently taken care of through additional constraints at another level. We thus propose a simplified model that removes those row and column. We show the efficacy of our proposals by furnishing results on the evaluation tables on multiple SBoxes. Our proposals often reduce the number of constraints for certain SBox evaluation tables (depending on the properties of the table) from the state-of-the-art results.</p>}},
  author       = {{Pal, Debranjan and Baksi, Anubhab and Mandal, Surajit and Sarkar, Santanu}},
  booktitle    = {{Progress in Cryptology - INDOCRYPT 2025 - 26th International Conference on Cryptology in India, Proceedings}},
  editor       = {{Dutta, Ratna and De Feo, Luca and Gangopadhyay, Sugata}},
  isbn         = {{9783032133007}},
  issn         = {{1611-3349}},
  keywords     = {{Block Cipher; Mixed Integer Linear Programming; Substitution Box; Substitution Box Evaluation Table}},
  language     = {{eng}},
  pages        = {{45--69}},
  publisher    = {{Springer Science and Business Media B.V.}},
  series       = {{Lecture Notes in Computer Science}},
  title        = {{Improved Modeling for Substitution Boxes with Negative Samples and Beyond}},
  url          = {{http://dx.doi.org/10.1007/978-3-032-13301-4_3}},
  doi          = {{10.1007/978-3-032-13301-4_3}},
  volume       = {{16372 LNCS}},
  year         = {{2026}},
}