Paper 2022/753
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.
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- Published by the IACR in TOSC 2022
- Keywords
- Block Cipher Integral Distinguisher MILP
- Contact author(s)
-
patrick derbez @ irisa fr
baptiste lambin @ uni lu - History
- 2022-06-15: approved
- 2022-06-12: received
- See all versions
- Short URL
- https://ia.cr/2022/753
- License
-
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},
url = {https://eprint.iacr.org/2022/753}
}
