Paper 2022/626

New method for combining Matsui’s bounding conditions with sequential encoding method

Senpeng Wang
Dengguo Feng
Bin Hu
Jie Guan
Kai Zhang
Tairong Shi

As the first generic method for finding the optimal differential and linear characteristics, Matsui's branch and bound search algorithm has played an important role in evaluating the security of symmetric ciphers. By combining Matsui's bounding conditions with automatic search models, search efficiency can be improved. In this paper, by studying the properties of Matsui's bounding conditions, we give the general form of bounding conditions that can eliminate all the impossible solutions determined by Matsui's bounding conditions. Then, a new method of combining bounding conditions with sequential encoding method is proposed. With the help of some small size Mixed Integer Linear Programming (MILP) models, we can use fewer variables and clauses to build Satisfiability Problem (SAT) models. As applications, we use our new method to search for the optimal differential and linear characteristics of some SPN, Feistel, and ARX block ciphers. The number of variables and clauses and the solving time of the SAT models are decreased significantly. In addition, we find some new differential and linear characteristics covering more rounds.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Minor revision. Des. Codes Cryptogr.
Automatic searchSAT modelMatsui's bounding conditionDifferential cryptanalysisLinear cryptanalysis
Contact author(s)
wsp2110 @ 126 com
2023-07-14: revised
2022-05-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Senpeng Wang and Dengguo Feng and Bin Hu and Jie Guan and Kai Zhang and Tairong Shi},
      title = {New method for combining Matsui’s bounding conditions with sequential encoding method},
      howpublished = {Cryptology ePrint Archive, Paper 2022/626},
      year = {2022},
      doi = {10.1007/s10623-023-01259-9},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.