### Fast MILP Models for Division Property

##### Abstract

Nowadays, MILP is a very popular tool to help cryptographers search for various distinguishers, in particular for integral distinguishers based on the division property. However, cryptographers tend to use MILP in a rather naive way, modeling problems in an exact manner and feeding them to a MILP solver. In this paper, we show that a proper use of some features of MILP solvers such as lazy constraints, along with using simpler but less accurate base models, can achieve much better solving times, while maintaining the precision of exact models. In particular, we describe several new modelization techniques for division property related models as well as a new variant of the Quine-McCluskey algorithm for this specific setting. Moreover, we positively answer a problem raised in [DF20] about handling the large sets of constraints describing valid transitions through Super S-boxes into a MILP model. As a result, we greatly improve the solving times to recover the distinguishers from several previous works ([DF20], [HWW20], [SWW17], [Udo21], [EY21]) and we were able to search for integral distinguishers on 5-round ARIA which was out of reach of previous modeling techniques.

Available format(s)
Category
Secret-key cryptography
Publication info
Keywords
Block Cipher Integral Distinguisher MILP
Contact author(s)
patrick derbez @ irisa fr
baptiste lambin @ uni lu
History
2022-06-15: approved
See all versions
Short URL
https://ia.cr/2022/753

CC BY

BibTeX

@misc{cryptoeprint:2022/753,
author = {Patrick Derbez and Baptiste Lambin},
title = {Fast MILP Models for Division Property},
howpublished = {Cryptology ePrint Archive, Paper 2022/753},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/753}},
url = {https://eprint.iacr.org/2022/753}
}

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