CNF Characterization of Sets over $\mathbb{Z}_2^n$ and Its Applications in Cryptography

Hu Xiaobo; Xu Shengyuan; Tu Yinzi; Feng Xiutao

Paper 2023/300

CNF Characterization of Sets over $\mathbb{Z}_2^n$ and Its Applications in Cryptography

Hu Xiaobo

Xu Shengyuan, Key Laboratory of Mathematics Mechanization, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, University of Chinese Academy of Sciences

Tu Yinzi, Beijing Smartchip Microelectronics Technology Company Limited

Feng Xiutao, Key Laboratory of Mathematics Mechanization, Academy of Mathematics and Systems Science, Chinese Academy of Sciences

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},
      note = {\url{https://eprint.iacr.org/2023/300}},
      url = {https://eprint.iacr.org/2023/300}
}