Welcome to the resource topic for 2019/049
Title:
The Relationship between the Construction and Solution of the MILP Models and Applications
Authors: Lingchen Li, Wenling Wu, Yafei Zheng, Lei Zhang
Abstract:The automatic search method based on Mix-integer Linear Programming (MILP) is one of the most common tools to search the distinguishers of block ciphers. For differential analysis, the byte-oriented MILP model is usually used to count the number of differential active s-boxes and the bit-oriented MILP model is used to search the optimal differential characteristic. In this paper, we present the influences between the construction and solution of MILP models solved by Gurobi : 1). the number of variables; 2). the number of constraints; 3). the order of the constraints; 4). the order of variables in constraints. We carefully construct the MILP models according to these influences in order to find the desired results in a reasonable time. As applications, we search the differential characteristic of PRESENT,GIFT-64 and GIFT-128 in the single-key setting. We do a dual processing for the constraints of the s-box. It only takes 298 seconds to finish the search of the 8-round optimal differential characteristic based on the new MILP model. We also obtain the optimal differential characteristic of the 9/10/11-round PRESENT. With a special initial constraint, it only takes 4 seconds to obtain a 9-round differential characteristic with probability 2^{-42}. We also get a 12/13-round differential characteristic with probability 2^{-58}/2^{-62}. For GIFT-128, we improve the probability of differential characteristic of 9 \sim 21 rounds and give the first attack on 26-round GIFT-128 based on a 20-round differential characteristic with probability 2^{-121.415}.
ePrint: https://eprint.iacr.org/2019/049
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 .