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.

Lattice reduction algorithms have been proved to be one of the most powerful and versatile tools in public key cryptanalysis. In this work, we primarily concentrate on lattice attacks against (EC)DSA with nonce leakage via some sidechannel analysis. Previous works relying on lattice reduction algorithms such as LLL and BKZ will finally lead to the “lattice barrier”: lattice algorithms become infeasible when only fewer nonce is known. Recently, Albrecht and Heninger introduced lattice algorithms augmented with a predicate and broke the lattice barrier (Eurocrypt 2021). We improve their work in several aspects.We first propose a more efficient predicate algorithm which aims to search for the target lattice vector in a large database. Then, we combine sieving with predicate algorithm with the “dimensions for free” and “progressive sieving” techniques to further improve the performance of our attacks. Furthermore, we give a theoretic analysis on how to choose the optimal Kannan embedding factor.As a result, our algorithm outperforms the state-of-the-art lattice attacks for existing records such as 3-bit nonce leakage for a 256-bit curve and 2-bit nonce leakage for a 160-bit curve in terms of running time, sample numbers and success probability. We also break the lattice records on the 384-bit curve with 3-bit nonce leakage and the 256-bit curve with 2-bit nonce leakage which are thought infeasible previously. Finally, we give the first lattice attack against ECDSA with a single-bit nonce leakage, which enables us to break a 112-bit curve with 1-bit nonce leakage in practical time.