Cryptology ePrint Archive: Report 2021/1099

MILP modeling of Boolean functions by minimum number of inequalities

Aleksei Udovenko

Abstract: This work presents techniques for modeling Boolean functions by mixed-integer linear inequalities (MILP) on binary variables in-place (without auxiliary variables), reaching minimum possible number of inequalities for small functions and providing meaningful lower bounds on the number of inequalities when reaching the minimum is infeasible. While the minimum number of inequalities does not directly translate to best performance in MILP applications, it nonetheless provides a useful benchmark. We remark that our framework is heuristic and relies on SAT solvers and MILP optimization and so its feasibility is limited.

Category / Keywords: secret-key cryptography / MILP, Modeling, Boolean functions, S-boxes, DDT

Date: received 25 Aug 2021

Contact author: aleksei at affine group

Available format(s): PDF | BibTeX Citation

Version: 20210826:115311 (All versions of this report)

Short URL: ia.cr/2021/1099


[ Cryptology ePrint archive ]