Paper 2022/626
New method for combining Matsui’s bounding conditions with sequential encoding method
Abstract
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.
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- Published elsewhere. Minor revision. Des. Codes Cryptogr.
- DOI
- 10.1007/s10623-023-01259-9
- Keywords
- Automatic searchSAT modelMatsui's bounding conditionDifferential cryptanalysisLinear cryptanalysis
- Contact author(s)
- wsp2110 @ 126 com
- History
- 2023-07-14: revised
- 2022-05-23: received
- See all versions
- Short URL
- https://ia.cr/2022/626
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/626,
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},
url = {https://eprint.iacr.org/2022/626}
}
