Paper 2021/1084
Towards the Least Inequalities for Describing a Subset in $Z_2^n$
Yao Sun
Abstract
Mixed Integer Linear Programming (MILP) solvers have become one of the most powerful tools for searching cryptographic characteristics, including differentials, impossible differentials, and division trails. Generally, one MILP problem can be formulated by several different MILP models, and the models with fewer constraints and variables are usually easier to solve. How to model a subset of $Z_2^n$ with the least number of constraints is also an interesting mathematical problem. In this paper, we discuss this problem in a general form. Specifically, given a set $C \subset Z_2^n$, let $L$ be a set of inequalities, and we say $L$ describes $C$ if the inequalities in $L$ only involve $n$ variables and the solution set to $L$ is exactly $C$. Our goal is to find such a set $L$ with the least number of inequalities. We present a brand new approach, named as SuperBall approach, for resolving this problem completely. Our approach is able to generate all available inequalities. Once these inequalities are obtained, Sasaki and Todo's method is used to find out the smallest subset of inequalities that describes $C$. If Sasaki and Todo's method succeeds, the found subset will be proved as the smallest. As a result, we found the smallest subsets of inequalities that describe the Sboxes of Keccak and APN6. The previous best results were 34 and 167, presented in FSE 2020, and we decreased these numbers to 26 and 145. Moreover, we can prove these numbers are the smallest if no dummy variables are used for generating inequalities.
Metadata
 Available format(s)
 Category
 Secretkey cryptography
 Publication info
 Preprint.
 Keywords
 MILPinequalitiesSbox
 Contact author(s)
 sunyao @ iie ac cn
 History
 20210825: revised
 20210825: received
 See all versions
 Short URL
 https://ia.cr/2021/1084
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/1084, author = {Yao Sun}, title = {Towards the Least Inequalities for Describing a Subset in $Z_2^n$}, howpublished = {Cryptology ePrint Archive, Paper 2021/1084}, year = {2021}, note = {\url{https://eprint.iacr.org/2021/1084}}, url = {https://eprint.iacr.org/2021/1084} }