International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Fast MILP Models for Division Property

Authors:
Patrick Derbez , Univ Rennes, Centre National de la Recherche Scientifique (CNRS), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Rennes, France
Baptiste Lambin , Ruhr University Bochum, Bochum, Germany
Download:
DOI: 10.46586/tosc.v2022.i2.289-321
URL: https://tosc.iacr.org/index.php/ToSC/article/view/9722
Search ePrint
Search Google
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.
BibTeX
@article{tosc-2022-32087,
  title={Fast MILP Models for Division Property},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universität Bochum},
  volume={2022, Issue 2},
  pages={289-321},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/9722},
  doi={10.46586/tosc.v2022.i2.289-321},
  author={Patrick Derbez and Baptiste Lambin},
  year=2022
}