Paper 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.
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- MILPModelingBoolean functionsS-boxesDDT
- Contact author(s)
- aleksei @ affine group
- History
- 2021-08-26: received
- Short URL
- https://ia.cr/2021/1099
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2021/1099,
author = {Aleksei Udovenko},
title = {{MILP} modeling of Boolean functions by minimum number of inequalities},
howpublished = {Cryptology {ePrint} Archive, Paper 2021/1099},
year = {2021},
url = {https://eprint.iacr.org/2021/1099}
}
