International Association
for Cryptologic Research

In 2022, Liu et al. summarized the Feistel-like structures which use a single round function, and proposed the unified form of these structures which is named the unified structure. This paper focuses on the unified structures which satisfy the following two conditions: (1) the round function is a permutation and (2) the size of the round function is the same as that of the branch. The main results are as follows: First of all, we give the definition of Affine Equivalence of different structures, present a condition for two structures being affine equivalent, and give two normalized forms of a unified structure. Surprisingly, we find that a target-heavy generalised Feistel structure is always affine equivalent to a source-heavy generalised Feistel structure, which shows these two structures always have almost the same cryptographic properties. Secondly, we give the definition of a self-equivalent structure, whose dual structure is affine equivalent to the structure itself. We prove that there is a large portion of the unified structures such as the SM4 structure and the Mars structure that are among the self-equivalent ones. For these structures, there is a one-to-one correspondence beween the impossible differentials and the zero correlation linear hulls, which shows that the longest integrals of a self-equivalent structure cover at least the rounds of the longest zero correlation linear hulls/impossible differentials. At last, we give the refined full-diffusion round of unified structures, and exploit the $\epsilon-\delta$ technique to compute this value, which can be further used to give a provable security evaluation of unified structures against the impossible differential and zero correlation linear cryptanalysis. For example, we prove that both the longest impossible differential and zero correlation linear hull of the $d$-branch SM4-like structures cover exactly $3d-1$ rounds.

In this paper, we study the quantum security of block ciphers based on Simon’s period-finding quantum algorithm. We explored the relations between periodic functions and truncated differentials. The basic observation is that truncated differentials with a probability of 1 can be used to construct periodic functions, and two such constructions are presented with the help of a new notion called difference-annihilation matrix. This technique releases us from the tedious manual work of verifying the period of functions. Based on these new constructions, we find an 8-round quantum distinguisher for LBlock and a 9/10/11/13/15-round quantum distinguisher for SIMON-32/48/64/96/128 which are the best results as far as we know. Besides, to explore the security bounds of block cipher structures against Simon’s algorithm based quantum attacks, the unified structure, which unifies the Feistel, Lai-Massey, and most generalized Feistel structures, is studied. We estimate the exact round number of probability 1 truncated differentials that one can construct. Based on these results, one can easily check the quantum security of specific block ciphers that are special cases of unified structures, when the details of the non-linear building blocks are not considered.

In this paper, we compare several non-tight degree evaluation methods i.e., Boura and Canteaut’s formula, Carlet’s formula as well as Liu’s numeric mapping and division property proposed by Todo, and hope to find the best one from these methodsfor practical applications. Specifically, for the substitution-permutation-network (SPN) ciphers, we first deeply explore the relationships between division property of an Sbox and its algebraic properties (e.g., the algebraic degree of its inverse). Based on these findings, we can prove theoretically that division property is never worse than Boura and Canteaut’s and Carlet’s formulas, and we also experimentally verified that the division property can indeed give a better bound than the latter two methods. In addition, for the nonlinear feedback shift registers (NFSR) based ciphers, according to the propagation of division property and the core idea of numeric mapping, we give a strict proof that the estimated degree using division property is never greater than that of numeric mapping. Moreover, our experimental results on Trivium and Kreyvium indicate the division property actually derives a much better bound than the numeric mapping. To the best of our knowledge, this is the first time to give a formal discussion on the relationships between division property and other degree evaluation methods, and we present the first theoretical proof and give the experimental verification to illustrate that division property is the optimal one among these methods in terms of the accuracy of the upper bounds on algebraic degree.

In recent years, Mixed Integer Linear Programming (MILP) has been widely used in cryptanalysis of symmetric-key primitives. For differential and linear cryptanalysis, MILP can be used to solve two kinds of problems: calculation of the minimum number of differentially/linearly active S-boxes, and search for the best differential/linear characteristics. There are already numerous papers published in this area. However, the efficiency is not satisfactory enough for many symmetric-key primitives. In this paper, we greatly improve the efficiency of the MILP-based search algorithm for both problems. Each of the two problems for an r-round cipher can be converted to an MILP model whose feasible region is the set of all possible r-round differential/linear characteristics. Generally, high-probability differential/linear characteristics are likely to have a low number of active S-boxes at a certain round. Inspired by the idea of a divide-and-conquer approach, we divide the set of all possible differential/linear characteristics into several smaller subsets, then separately search them. That is to say, the search of the whole set is split into easier searches of smaller subsets, and optimal solutions within the smaller subsets are combined to give the optimal solution within the whole set. In addition, we use several techniques to further improve the efficiency of the search algorithm. As applications, we apply our search algorithm to five lightweight block ciphers: PRESENT, GIFT-64, RECTANGLE, LBLOCK and TWINE. For each cipher, we obtain better results than the best-known ones obtained from the MILP method. For the minimum number of differentially/linearly active S-boxes, we reach 31/31, 16/15, 16/16, 20/20 and 20/20 rounds for the five ciphers respectively. For the best differential/linear characteristics, we reach 18/18, 15/13, 15/14, 16/15 and 15/16 rounds for the five ciphers respectively.

In this paper, we propose a new heuristic algorithm to search efficient implementations (in terms of Xor count) of linear layers used in symmetric-key cryptography. It is observed that the implementation cost of an invertible matrix is related to its matrix decomposition if sequential-Xor (s-Xor) metric is considered, thus reducing the implementation cost is equivalent to constructing an optimized matrix decomposition. The basic idea of this work is to find various matrix decompositions for a given matrix and optimize those decompositions to pick the best implementation. In order to optimize matrix decompositions, we present several matrix multiplication rules over F2, which are proved to be very powerful in reducing the implementation cost. We illustrate this heuristic by searching implementations of several matrices proposed recently and matrices already used in block ciphers and Hash functions, and the results show that our heuristic performs equally good or outperforms Paar’s and Boyar-Peralta’s heuristics in most cases.