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

Lingchen Li, Wenling Wu, Yafei Zheng, and 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}$.

Available format(s)
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Contact author(s)
lilingchen601 @ 126 com
History
Short URL
https://ia.cr/2019/049

CC BY

BibTeX

@misc{cryptoeprint:2019/049,
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{https://eprint.iacr.org/2019/049}},
url = {https://eprint.iacr.org/2019/049}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.