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

As the first generic method for finding the optimal differentialand 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 efficien...

Full description

Saved in:
Bibliographic Details
Published in:Designs, codes, and cryptography codes, and cryptography, 2023-11, Vol.91 (11), p.3603-3642
Main Authors: Wang, Senpeng, Feng, Dengguo, Hu, Bin, Guan, Jie, Zhang, Kai, Shi, Tairong
Format: Article
Language:English
Subjects:
Coding
Coding and Information Theory
Computer Science
Cryptology
Discrete Mathematics in Computer Science
Encryption
Integer programming
Linear programming
Mixed integer
Search algorithms
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:As the first generic method for finding the optimal differentialand 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.
ISSN:0925-1022
1573-7586
DOI:10.1007/s10623-023-01259-9