Improved Modeling for Substitution Boxes with Negative Samples and Beyond
Pal, Debranjan ; Baksi, Anubhab LU
; Mandal, Surajit
and Sarkar, Santanu
(2026)
26th International Conference on Cryptology in India, INDOCRYPT 2025
In Lecture Notes in Computer Science
16372 LNCS.
p.45-69
- Abstract
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... (More)
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.
(Less)
- author
- Pal, Debranjan
; Baksi, Anubhab
LU
; Mandal, Surajit
and Sarkar, Santanu
- organization
- publishing date
- 2026
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- keywords
- Block Cipher, Mixed Integer Linear Programming, Substitution Box, Substitution Box Evaluation Table
- host publication
- Progress in Cryptology - INDOCRYPT 2025 - 26th International Conference on Cryptology in India, Proceedings
- series title
- Lecture Notes in Computer Science
- editor
- Dutta, Ratna ; De Feo, Luca and Gangopadhyay, Sugata
- volume
- 16372 LNCS
- pages
- 25 pages
- publisher
- Springer Science and Business Media B.V.
- conference name
- 26th International Conference on Cryptology in India, INDOCRYPT 2025
- conference location
- Bhubaneshwar, India
- conference dates
- 2025-12-14 - 2025-12-17
- external identifiers
-
- scopus:105025977553
- ISSN
- 1611-3349
- 0302-9743
- ISBN
- 9783032133007
- DOI
- 10.1007/978-3-032-13301-4_3
- language
- English
- LU publication?
- yes
- additional info
- Publisher Copyright: © The Author(s), under exclusive license to Springer Nature Switzerland AG 2026.
- id
- ba643296-3c48-48a2-b9a7-9478ea5b253d
- date added to LUP
- 2026-03-24 14:01:45
- date last changed
- 2026-05-05 18:57:34
@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}},
}