## Cryptology ePrint Archive: Report 2010/521

Linear Approximations of Addition Modulo \$2^n\$-1

Xiutao Feng and Chunfang Zhou and Chuankun Wu

Abstract: Addition modulo \$2^{31}-1\$ is a basic arithmetic operation in the stream cipher ZUC. For evaluating ZUC in resistance to linear cryptanalysis, it is necessary to study properties of linear approximations of the addition modulo \$2^{31}-1\$. In this paper we discuss linear approximations of the addition modulo \$2^n-1\$ for integer \$n\ge2\$. As results, an exact formula on the correlations of linear approximations of the addition modulo \$2^n-1\$ is given for the case when two inputs are involved, and an iterative formula for the case when more than two inputs are involved. For a class of special linear approximations with all masks being equal to 1, we further discuss the limit of their correlations when \$n\$ goes to infinity. Let \$k\$ be the number of inputs of the addition modulo \$2^n-1\$. It's shows that when \$k\$ is even, the limit is equal to zero, and when \$k\$ is odd, the limit is bounded by a constant depending on \$k\$.

Category / Keywords: secret-key cryptography /