CryptoDB
Xiangyong Zeng
NOTE: imports for ToSC and TCHES are no longer functioning.
Publications
Year
Venue
Title
2024
TOSC
Links between Quantum Distinguishers Based on Simon’s Algorithm and Truncated Differentials
Abstract
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.
2021
TOSC
On the Relationships between Different Methods for Degree Evaluation
📺
Abstract
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.
Coauthors
- Siwei Chen (1)
- Nian Li (1)
- Xuan Shen (1)
- Bing Sun (1)
- Xiaoyu Wang (1)
- Zejun Xiang (2)
- Bo Yu (1)
- Xiangyong Zeng (2)
- Shasha Zhang (2)