American Institute of Mathematical Sciences

Advanced
May  2008, 2(2): 201-221. doi: 10.3934/amc.2008.2.201

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

Claude Carlet 1, , Khoongming Khoo 2, , Chu-Wee Lim 2, and  Chuan-Wen Loe 2,

1. 

Université Paris 8, Département de mathématiques, 2, rue de la Liberté, 93526 - SAINT-DENIS cedex 02, France
2. 

DSO National Laboratories, 20 Science Park Drive S118230, Singapore, Singapore, Singapore

Received  December 2007 Revised  April 2008 Published  April 2008

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: generalized nonlinearity., unrestricted nonlinearity, Vectorial Boolean functions.
Mathematics Subject Classification: Primary: 94A60; Secondary: 11T71, 14G5.
Citation: Claude Carlet, Khoongming Khoo, Chu-Wee Lim, Chuan-Wen Loe. On an improved correlation analysis of stream ciphers using multi-output Boolean functions and the related generalized notion of nonlinearity. Advances in Mathematics of Communications, 2008, 2 (2) : 201-221. doi: 10.3934/amc.2008.2.201
[1]

Jian Liu, Sihem Mesnager, Lusheng Chen. Variation on correlation immune Boolean and vectorial functions. Advances in Mathematics of Communications, 2016, 10 (4) : 895-919. doi: 10.3934/amc.2016048
[2]

Sugata Gangopadhyay, Constanza Riera, Pantelimon Stăniă. Gowers $ U_2 $ norm as a measure of nonlinearity for Boolean functions and their generalizations. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020056
[3]

SelÇuk Kavut, Seher Tutdere. Highly nonlinear (vectorial) Boolean functions that are symmetric under some permutations. Advances in Mathematics of Communications, 2020, 14 (1) : 127-136. doi: 10.3934/amc.2020010
[4]

Constanza Riera, Pantelimon Stănică. Landscape Boolean functions. Advances in Mathematics of Communications, 2019, 13 (4) : 613-627. doi: 10.3934/amc.2019038
[5]

Sugata Gangopadhyay, Goutam Paul, Nishant Sinha, Pantelimon Stǎnicǎ. Generalized nonlinearity of $ S$-boxes. Advances in Mathematics of Communications, 2018, 12 (1) : 115-122. doi: 10.3934/amc.2018007
[6]

Yang Yang, Xiaohu Tang, Guang Gong. Even periodic and odd periodic complementary sequence pairs from generalized Boolean functions. Advances in Mathematics of Communications, 2013, 7 (2) : 113-125. doi: 10.3934/amc.2013.7.113
[7]

Claude Carlet, Serge Feukoua. Three basic questions on Boolean functions. Advances in Mathematics of Communications, 2017, 11 (4) : 837-855. doi: 10.3934/amc.2017061
[8]

Sihem Mesnager, Gérard Cohen. Fast algebraic immunity of Boolean functions. Advances in Mathematics of Communications, 2017, 11 (2) : 373-377. doi: 10.3934/amc.2017031
[9]

Kyril Tintarev. Is the Trudinger-Moser nonlinearity a true critical nonlinearity?. Conference Publications, 2011, 2011 (Special) : 1378-1384. doi: 10.3934/proc.2011.2011.1378
[10]

Xingxing Liu, Zhijun Qiao, Zhaoyang Yin. On the Cauchy problem for a generalized Camassa-Holm equation with both quadratic and cubic nonlinearity. Communications on Pure & Applied Analysis, 2014, 13 (3) : 1283-1304. doi: 10.3934/cpaa.2014.13.1283
[11]

Q-Heung Choi, Tacksun Jung. A nonlinear wave equation with jumping nonlinearity. Discrete & Continuous Dynamical Systems - A, 2000, 6 (4) : 797-802. doi: 10.3934/dcds.2000.6.797
[12]

Eugenia N. Petropoulou. On some difference equations with exponential nonlinearity. Discrete & Continuous Dynamical Systems - B, 2017, 22 (7) : 2587-2594. doi: 10.3934/dcdsb.2017098
[13]

Yingshu Lü, Chunqin Zhou. Symmetry for an integral system with general nonlinearity. Discrete & Continuous Dynamical Systems - A, 2019, 39 (3) : 1533-1543. doi: 10.3934/dcds.2018121
[14]

Ayça Çeşmelioğlu, Wilfried Meidl. Bent and vectorial bent functions, partial difference sets, and strongly regular graphs. Advances in Mathematics of Communications, 2018, 12 (4) : 691-705. doi: 10.3934/amc.2018041
[15]

Yu Zhou. On the distribution of auto-correlation value of balanced Boolean functions. Advances in Mathematics of Communications, 2013, 7 (3) : 335-347. doi: 10.3934/amc.2013.7.335
[16]

Claude Carlet, Serge Feukoua. Three parameters of Boolean functions related to their constancy on affine spaces. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020036
[17]

Ian Schindler, Kyril Tintarev. Mountain pass solutions to semilinear problems with critical nonlinearity. Conference Publications, 2007, 2007 (Special) : 912-919. doi: 10.3934/proc.2007.2007.912
[18]

Manuel del Pino, Jean Dolbeault, Monica Musso. Multiple bubbling for the exponential nonlinearity in the slightly supercritical case. Communications on Pure & Applied Analysis, 2006, 5 (3) : 463-482. doi: 10.3934/cpaa.2006.5.463
[19]

Jong Uhn Kim. On the stochastic Burgers equation with a polynomial nonlinearity in the real line. Discrete & Continuous Dynamical Systems - B, 2006, 6 (4) : 835-866. doi: 10.3934/dcdsb.2006.6.835
[20]

Nakao Hayashi, Tohru Ozawa. Schrödinger equations with nonlinearity of integral type. Discrete & Continuous Dynamical Systems - A, 1995, 1 (4) : 475-484. doi: 10.3934/dcds.1995.1.475

2018 Impact Factor: 0.879

Tools

Metrics

  • PDF downloads (13)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences