Paper 2023/300
CNF Characterization of Sets over $\mathbb{Z}_2^n$ and Its Applications in Cryptography
Abstract
In recent years, the automatic search has been widely used to search differential characteristics and linear approximations with high probability/correlation. Among these methods, the automatic search with the Boolean Satisfiability Problem (SAT, in short) gradually becomes a powerful cryptanalysis tool in symmetric ciphers. A key problem in the automatic search method is how to fully characterize a set $S \subseteq \{0,1\}^n$ with as few Conjunctive Normal Form (CNF, in short) clauses as possible, which is called a full CNF characterization (FCC, in short) problem. In this work, we establish a complete theory to solve a best solution of a FCC problem. Specifically, we start from plain sets, which can be characterized by exactly one clause. By exploring mergeable sets, we find a sufficient and necessary condition for characterizing a plain set. Based on the properties of plain sets, we further provide an algorithm for solving a FCC problem with $S$, which can generate all the minimal plain closures of $S$ and produce a best FCC theoretically. We also apply our algorithm to S-boxes used in block ciphers to characterize their differential distribution tables and linear approximation tables. All of our FCCs are the best-known results at present.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Contact author(s)
-
huxiaobo @ sgchip sgcc com cn
xushengyuan18 @ amss ac cn
tuyinzi @ sgchip sgcc com cn
fengxt @ amss ac cn - History
- 2023-03-01: approved
- 2023-02-28: received
- See all versions
- Short URL
- https://ia.cr/2023/300
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/300,
author = {Hu Xiaobo and Xu Shengyuan and Tu Yinzi and Feng Xiutao},
title = {{CNF} Characterization of Sets over $\mathbb{Z}_2^n$ and Its Applications in Cryptography},
howpublished = {Cryptology {ePrint} Archive, Paper 2023/300},
year = {2023},
url = {https://eprint.iacr.org/2023/300}
}