Efficient Algorithm for Generating Optimal Inequality Candidates for MILP Modeling of Boolean Functions

Alexander Bille; Elmar Tischhauser

doi:10.62056/ahvr-zoja5

Efficient Algorithm for Generating Optimal Inequality Candidates for MILP Modeling of Boolean Functions

Authors

Alexander Bille, Elmar Tischhauser

Alexander Bille

University of Marburg, Marburg, Germany
bille at informatik dot uni-marburg dot de

Elmar Tischhauser

University of Marburg, Marburg, Germany
tischhauser at informatik dot uni-marburg dot de

Keywords: MILP modeling Boolean functions S-boxes Differential cryptanalysis Linear cryptanalysis Symmetric cryptography

Abstract

Mixed-Integer Linear Programming (MILP) modeling has become an important tool for both the analysis and the design of symmetric cryptographic primitives. The bit-wise modeling of their nonlinear components, especially the S-boxes, is of particular interest since it allows more informative analysis compared to word-oriented models focusing on counting active S-boxes. At the same time, the size of these models, especially in terms of the number of required inequalities, tends to significantly influence and ultimately limit the applicability of this method to real-world ciphers, especially for larger number of rounds.

It is therefore of great cryptographic significance to study optimal linear inequality descriptions for Boolean functions. The pioneering works of Abdelkhalek et al. (FSE 2017), Boura and Coggia (FSE 2020) and Li and Sun (FSE 2023) provided various heuristic techniques for this computationally hard problem, decomposing it into two algorithmic steps, coined Problem 1 and Problem 2, with the latter being identical to the well-known NP-hard set cover problem, for which there are many heuristic and exact algorithms in the literature.

In this paper, we introduce a novel and efficient branch-and-bound algorithm for generating all minimal, non-redundant candidate inequalities that satisfy a given Boolean function, therefore solving Problem 1 in an optimal manner without relying on heuristics. We furthermore prove that our algorithm correctly computes optimal solutions. Using a number of dedicated optimizations, it provides significantly improved runtimes compared to previous approaches and allows the optimal modeling of the difference distribution tables (DDT) and linear approximation tables (LAT) of many practically used S-boxes. The source code for our algorithm is publicly available as a tool for researchers and practitioners in symmetric cryptography.

References

[AHS23a]

Gennadiy Averkov, Christopher Hojny, and Matthias Schymura. Computational aspects of relaxation complexity: possibilities and limitations. Math. Program., 197(2):1173–1200, 2023. DOI: 10.1007/S10107-021-01754-8

Google Scholar ePrint

[AHS23b]

Gennadiy Averkov, Christopher Hojny, and Matthias Schymura. Efficient MIP techniques for computing the relaxation complexity. Math. Program. Comput., 15(3):549–580, 2023. DOI: 10.1007/S12532-023-00241-9

Google Scholar ePrint

[AST⁺17]

Ahmed Abdelkhalek, Yu Sasaki, Yosuke Todo, Mohamed Tolba, and Amr M. Youssef. MILP Modeling for (Large) S-boxes to Optimize Probability of Differential Characteristics. IACR Trans. Symmetric Cryptol., 2017(4):99–129, 2017. DOI: 10.13154/TOSC.V2017.I4.99-129

Google Scholar ePrint

[BC20]

Christina Boura and Daniel Coggia. Efficient MILP Modelings for Sboxes and Linear Layers of SPN ciphers. IACR Trans. Symmetric Cryptol., 2020(3):327–361, 2020. DOI: 10.13154/TOSC.V2020.I3.327-361

Google Scholar ePrint

[BFSW22]

Thomas Bläsius, Tobias Friedrich, David Stangl, and Christopher Weyand. An Efficient Branch-and-Bound Solver for Hitting Set. In Cynthia A. Phillips and Bettina Speckmann, editors, Proceedings of the Symposium on Algorithm Engineering and Experiments, ALENEX 2022, Alexandria, VA, USA, January 9-10, 2022, pages 209–220. 2022. SIAM. DOI: 10.1137/1.9781611977042.17

Google Scholar ePrint

[BHMS84]

Robert K. Brayton, Gary D. Hachtel, Curtis T. McMullen, and Alberto L. Sangiovanni-Vincentelli. Logic Minimization Algorithms for VLSI Synthesis, volume 2 of The Kluwer International Series in Engineering and Computer Science. The Kluwer International Series in Engineering and Computer Science. Springer 1984. DOI: 10.1007/978-1-4613-2821-6

Google Scholar ePrint

[BHW74]

Gordon H. Bradley, Peter L. Hammer, and Laurence A. Wolsey. Coefficient reduction for inequalities in 0-1 variables. Math. Program., 7(1):263–282, 1974. DOI: 10.1007/BF01585527

Google Scholar ePrint

[BR14]

Andrey Bogdanov and Vincent Rijmen. Linear hulls with correlation zero and linear cryptanalysis of block ciphers. Des. Codes Cryptogr., 70(3):369–383, 2014. DOI: 10.1007/S10623-012-9697-Z

Google Scholar ePrint

[DL22]

Patrick Derbez and Baptiste Lambin. Fast MILP Models for Division Property. IACR Trans. Symmetric Cryptol., 2022(2):289–321, 2022. DOI: 10.46586/TOSC.V2022.I2.289-321

Google Scholar ePrint

[DR07]

Joan Daemen and Vincent Rijmen. Probability distributions of correlation and differentials in block ciphers. J. Math. Cryptol., 1(3):221–242, 2007. DOI: 10.1515/JMC.2007.011

Google Scholar ePrint

[FTW⁺22]

Xiutao Feng, Yu Tian, Yongxing Wang, Shengyuan Xu, and Anpeng Zhang. Full Linear Integer Inequality Characterization of Sets over $\mathbb{Z}_{2^n}$. chinaXiv Preprint Archive, 202210.00055v2, 2022.

Google Scholar ePrint

[FWG⁺16]

Kai Fu, Meiqin Wang, Yinghua Guo, Siwei Sun, and Lei Hu. MILP-Based Automatic Search Algorithms for Differential and Linear Trails for Speck. In Thomas Peyrin, editor, Fast Software Encryption - 23rd International Conference, FSE 2016, Bochum, Germany, March 20-23, 2016, Revised Selected Papers, volume 9783 of Lecture Notes in Computer Science, pages 268–288. 2016. Springer. DOI: 10.1007/978-3-662-52993-5_14

Google Scholar ePrint

[HLM⁺20]

Yonglin Hao, Gregor Leander, Willi Meier, Yosuke Todo, and Qingju Wang. Modeling for Three-Subset Division Property Without Unknown Subset - Improved Cube Attacks Against Trivium and Grain-128AEAD. In Anne Canteaut and Yuval Ishai, editors, Advances in Cryptology - EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10-14, 2020, Proceedings, Part I, volume 12105 of Lecture Notes in Computer Science, pages 466–495. 2020. Springer. DOI: 10.1007/978-3-030-45721-1_17

Google Scholar ePrint

[KV18]

B. Korte and Jens Vygen. Combinatorial Optimization: Theory and Algorithms. Springer-Verlag, New York, NY 2018. DOI: https://doi.org/10.1007/978-3-662-56039-6

Google Scholar ePrint

[LDW07]

Guanghui Lan, Gail W. DePuy, and Gary E. Whitehouse. An effective and simple heuristic for the set covering problem. Eur. J. Oper. Res., 176(3):1387–1403, 2007. DOI: 10.1016/J.EJOR.2005.09.028

Google Scholar ePrint

[LS22]

Ting Li and Yao Sun. SuperBall: A New Approach for MILP Modelings of Boolean Functions. IACR Trans. Symmetric Cryptol., 2022(3):341–367, 2022. DOI: 10.46586/TOSC.V2022.I3.341-367

Google Scholar ePrint

[McC56]

Edward J McCluskey. Minimization of Boolean functions. The Bell System Technical Journal, 35(6):1417–1444, 1956. DOI: 10.1002/j.1538-7305.1956.tb03835.x

Google Scholar ePrint

[MWGP11]

Nicky Mouha, Qingju Wang, Dawu Gu, and Bart Preneel. Differential and Linear Cryptanalysis Using Mixed-Integer Linear Programming. In Chuankun Wu, Moti Yung, and Dongdai Lin, editors, Information Security and Cryptology - 7th International Conference, Inscrypt 2011, Beijing, China, November 30 - December 3, 2011. Revised Selected Papers, volume 7537 of Lecture Notes in Computer Science, pages 57–76. 2011. Springer. DOI: 10.1007/978-3-642-34704-7_5

Google Scholar ePrint

[Qui52]

Willard V Quine. The problem of simplifying truth functions. The American mathematical monthly, 59(8):521–531, 1952. DOI: 10.2307/2308219

Google Scholar ePrint

[Qui55]

Willard V Quine. A way to simplify truth functions. The American mathematical monthly, 62(9):627–631, 1955. DOI: 10.2307/2307285

Google Scholar ePrint

[SC10]

Lei Shi and Xuan Cai. An exact fast algorithm for minimum hitting set. In 2010 Third International Joint Conference on Computational Science and Optimization, volume 1, pages 64–67. 2010. IEEE. DOI: 10.1109/cso.2010.240

Google Scholar ePrint

[SHW⁺14a]

Siwei Sun, Lei Hu, Meiqin Wang, Peng Wang, Kexin Qiao, Xiaoshuang Ma, Danping Shi, Ling Song, and Kai Fu. Towards Finding the Best Characteristics of Some Bit-oriented Block Ciphers and Automatic Enumeration of (Related-key) Differential and Linear Characteristics with Predefined Properties. Cryptology ePrint Archive, Paper 2014/747. 2014.

Google Scholar ePrint

[SHW⁺14b]

Siwei Sun, Lei Hu, Peng Wang, Kexin Qiao, Xiaoshuang Ma, and Ling Song. Automatic Security Evaluation and (Related-key) Differential Characteristic Search: Application to SIMON, PRESENT, LBlock, DES(L) and Other Bit-Oriented Block Ciphers. In Palash Sarkar and Tetsu Iwata, editors, Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 7-11, 2014. Proceedings, Part I, volume 8873 of Lecture Notes in Computer Science, pages 158–178. 2014. Springer. DOI: 10.1007/978-3-662-45611-8_9

Google Scholar ePrint

[ST17]

Yu Sasaki and Yosuke Todo. New Algorithm for Modeling S-box in MILP Based Differential and Division Trail Search. In Pooya Farshim and Emil Simion, editors, Innovative Security Solutions for Information Technology and Communications - 10th International Conference, SecITC 2017, Bucharest, Romania, June 8-9, 2017, Revised Selected Papers, volume 10543 of Lecture Notes in Computer Science, pages 150–165. 2017. Springer. DOI: 10.1007/978-3-319-69284-5_11

Google Scholar ePrint

[Udo21]

Aleksei Udovenko. MILP modeling of Boolean functions by minimum number of inequalities. IACR Cryptol. ePrint Arch., 2021.

Google Scholar ePrint

[WHG⁺19]

Senpeng Wang, Bin Hu, Jie Guan, Kai Zhang, and Tairong Shi. MILP-aided Method of Searching Division Property Using Three Subsets and Applications. In Steven D. Galbraith and Shiho Moriai, editors, Advances in Cryptology - ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Kobe, Japan, December 8-12, 2019, Proceedings, Part III, volume 11923 of Lecture Notes in Computer Science, pages 398–427. 2019. Springer. DOI: 10.1007/978-3-030-34618-8_14

Google Scholar ePrint

[Wil77]

JM Wilson. A method for reducing coefficients in zero-one linear inequalities. International Journal of Mathematical Educational in Science and Technology, 8(1):31–35, 1977. DOI: 10.1080/0020739770080104

Google Scholar ePrint

[XFW23]

Shengyuan Xu, Xiutao Feng, and Yongxing Wang. On Two Factors Affecting the Efficiency of MILP Models in Automated Cryptanalyses. IACR Cryptol. ePrint Arch., 2023.

Google Scholar ePrint

[XZBL16]

Zejun Xiang, Wentao Zhang, Zhenzhen Bao, and Dongdai Lin. Applying MILP Method to Searching Integral Distinguishers Based on Division Property for 6 Lightweight Block Ciphers. In Jung Hee Cheon and Tsuyoshi Takagi, editors, Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4-8, 2016, Proceedings, Part I, volume 10031 of Lecture Notes in Computer Science, pages 648–678. 2016. DOI: 10.1007/978-3-662-53887-6_24

Google Scholar ePrint

[ZZDX19]

Chunning Zhou, Wentao Zhang, Tianyou Ding, and Zejun Xiang. Improving the MILP-based Security Evaluation Algorithm against Differential/Linear Cryptanalysis Using A Divide-and-Conquer Approach. IACR Trans. Symmetric Cryptol., 2019(4):438–469, 2019. DOI: 10.13154/TOSC.V2019.I4.438-469

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/ahvr-zoja5

History

Submitted: 2024-07-08
Accepted: 2024-09-02
Published: 2024-10-07

How to cite

Alexander Bille and Elmar Tischhauser, Efficient Algorithm for Generating Optimal Inequality Candidates for MILP Modeling of Boolean Functions. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/ahvr-zoja5.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@article{CiC-1-3-38,
    author = "Bille, Alexander and Tischhauser, Elmar",
    journal = "{IACR} {C}ommunications in {C}ryptology",
    publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
    title = "Efficient Algorithm for Generating Optimal Inequality Candidates for {MILP} Modeling of Boolean Functions",
    volume = "1",
    number = "3",
    date = "2024-10-07",
    year = "2024",
    issn = "3006-5496",
    doi = "10.62056/ahvr-zoja5"
}

TY - JOUR
AU - Bille, Alexander
AU - Tischhauser, Elmar
PY  - 2024
TI  - Efficient Algorithm for Generating Optimal Inequality Candidates for MILP Modeling of Boolean Functions
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 1
IS  - 3
DO  - 10.62056/ahvr-zoja5
UR  - https://doi.org/10.62056/ahvr-zoja5
AB  - <p>  Mixed-Integer Linear Programming (MILP) modeling has become an important   tool for both the analysis and the design of symmetric cryptographic   primitives. The bit-wise modeling of their nonlinear components,   especially the S-boxes, is of particular interest since it allows more   informative analysis compared to word-oriented models focusing on   counting active S-boxes. At the same time, the size of these models,   especially in terms of the number of required inequalities, tends to   significantly influence and ultimately limit the applicability of this   method to real-world ciphers, especially for larger number of rounds.</p><p>  It is therefore of great cryptographic significance to study optimal   linear inequality descriptions for Boolean functions. The pioneering   works of Abdelkhalek et al. (FSE 2017), Boura and Coggia (FSE 2020) and   Li and Sun (FSE 2023) provided various heuristic techniques for this   computationally hard problem, decomposing it into two algorithmic steps,   coined Problem 1 and Problem 2, with the latter being identical to the   well-known NP-hard set cover problem, for which there are many heuristic   and exact algorithms in the literature.</p><p>  In this paper, we introduce a novel and efficient branch-and-bound   algorithm for generating all minimal, non-redundant candidate   inequalities that satisfy a given Boolean function, therefore solving   Problem 1 in an optimal manner without relying on heuristics.  We   furthermore prove that our algorithm correctly computes optimal   solutions.  Using a number of dedicated optimizations, it provides   significantly improved runtimes compared to previous approaches and   allows the optimal modeling of the difference distribution tables (DDT)   and linear approximation tables (LAT) of many practically used   S-boxes. The source code for our algorithm is publicly available as a   tool for researchers and practitioners in symmetric cryptography. </p>
ER  -

Alexander Bille and Elmar Tischhauser, Efficient Algorithm for Generating Optimal Inequality Candidates for MILP Modeling of Boolean Functions. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/ahvr-zoja5.