Paper 2019/049

The Relationship between the Construction and Solution of the MILP Models and Applications

Lingchen Li, Wenling Wu, Yafei Zheng, and Lei Zhang


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}$.

Available format(s)
Secret-key cryptography
Publication info
Preprint. MINOR revision.
MILPGurobiPRESENTGIFTDifferential Cryptanalysis
Contact author(s)
lilingchen601 @ 126 com
2019-01-25: received
Short URL
Creative Commons Attribution


      author = {Lingchen Li and Wenling Wu and Yafei Zheng and Lei Zhang},
      title = {The Relationship between the Construction and Solution of the MILP Models and Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2019/049},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.