Subjects: Mathematics >> Applied Mathematics submitted time 2022-11-09
Abstract： In recent years, mixed integer linear programming (MILP, in short) is widely used to search differential characteristics and linear approximations with high probability and gradually becomes a powerful tool of automated cryptanalysis in symmetric ciphers. A key problem in the MILP method is how to fully characterize a set $S subseteq {0,1 }^n$ with as few linear integer inequalities $L$ as possible, which is called a full linear integer inequality characterization (FLIIC, in short) problem. In this work we establish a complete theory to solve the best solution of a FLIIC problem. We start from plain sets which can be characterized by exactly one linear integer inequality, and give their essential properties, including type, sparsity, degeneration, order, minimal and maximal element, norm and its bound, etc. Based on these essential properties, we further provide an efficient algorithm of solving a FLIIC problem with $S$, which can produce all minimal plain closures of $S$ and output a best FLIIC theoretically. As examples, we give their best solutions for differential properties of some common S-boxes used in block ciphers.
Peer Review Status:
Awaiting Review
Hits
Hits
Downloads
Comment