Welcome to the resource topic for 2021/1084
Title:
Towards the Least Inequalities for Describing a Subset in Z_2^n
Authors: 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 APN-6. 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.
ePrint: https://eprint.iacr.org/2021/1084
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .