Advances in Mathematics of Communications (AMC)

On an improved correlation analysis of stream ciphers using multi-output Boolean functions and the related generalized notion of nonlinearity

Pages: 201 - 221, Volume 2, Issue 2, May 2008      doi:10.3934/amc.2008.2.201

       Abstract        Full Text (259.5K)       Related Articles

Claude Carlet - Université Paris 8, Département de mathématiques, 2, rue de la Liberté, 93526 - SAINT-DENIS cedex 02, France (email)
Khoongming Khoo - DSO National Laboratories, 20 Science Park Drive S118230, Singapore (email)
Chu-Wee Lim - DSO National Laboratories, 20 Science Park Drive S118230, Singapore (email)
Chuan-Wen Loe - DSO National Laboratories, 20 Science Park Drive S118230, Singapore (email)

Abstract: We investigate the security of $n$-bit to $m$-bit vectorial Boolean functions in stream ciphers. Such stream ciphers have higher throughput than those using single-bit output Boolean functions. However, as shown by Zhang and Chan at Crypto 2000, linear approximations based on composing the vector output with any Boolean functions have higher bias than those based on the usual correlation attack. In this paper, we introduce a new approach for analyzing vector Boolean functions called generalized correlation analysis. It is based on approximate equations which are linear in the input $x$ but of free degree in the output $z = F(x)$. The complexity for computing the generalized nonlinearity for this new attack is reduced from $2$2m×n+n to $2$2n. Based on experimental results, we show that the new generalized correlation attack gives linear approximation with much higher bias than the Zhang-Chan and usual correlation attack. We confirm this with a theoretical upper bound for generalized nonlinearity, which is much lower than for the unrestricted non-linearity (for Zhang-Chan's attack) and a fortiori for usual nonlinearity. We also prove a lower bound for generalized nonlinearity which allows us to construct vector Boolean functions with high generalized nonlinearity from bent and almost bent functions. We derive the generalized nonlinearity of some known secondary constructions for secure vector Boolean functions. Finally, we prove that if a vector Boolean function has high nonlinearity or even a high unrestricted nonlinearity, it cannot ensure that it will have high generalized nonlinearity.

Keywords:  Vectorial Boolean functions, unrestricted nonlinearity, generalized nonlinearity.
Mathematics Subject Classification:  Primary: 94A60; Secondary: 11T71, 14G50.

Received: December 2007;      Revised: April 2008;      Available Online: April 2008.