**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 /

**Date: **received 8 Oct 2010

**Contact author: **fengxt at gmail com;fengxt@is iscas ac cn

**Available format(s): **PDF | BibTeX Citation

**Version: **20101012:131532 (All versions of this report)

**Short URL: **ia.cr/2010/521

[ Cryptology ePrint archive ]