November  2016, 10(4): 895-919. doi: 10.3934/amc.2016048

Variation on correlation immune Boolean and vectorial functions

1. 

School of Computer Software, Tianjin University, Tianjin 300072, China

2. 

Department of Mathematics, University of Paris VIII, CNRS, UMR 7539 LAGA and Telecom ParisTech, Paris, France

3. 

School of Mathematical Sciences, Nankai University, Tianjin 300071, China

Received  March 2015 Revised  September 2015 Published  November 2016

Correlation immune functions were introduced to protect some shift register based stream ciphers against correlation attacks. For cryptographic applications, relaxing the concept of correlation immunity has been highlighted and proved to be more appropriate in several cryptographic situations. Various weakened notions of correlation immunity and resiliency have been widely introduced for cryptographic functions, but those notions are difficult to handle.
    As a variation, we focus on the notion of $\varphi$-correlation immunity which is closely related to (fast) correlation attacks on stream ciphers based on nonlinear combiner model. In particular, we exhibit new connections between $\varphi$-correlation immunity and $\epsilon$-almost resiliency, which are two distinct approaches for characterizing relaxed resiliency. We also extend the concept of $\varphi$-correlation immunity introduced by Carlet et al. in 2006 for Boolean functions to vectorial functions and study the main cryptographic parameters of $\varphi$-correlation immune functions. Moreover, we provide new primary constructions of $\varphi$-resilient functions with good designed immunity profile. Specially, we propose a new recursive method to construct $\varphi$-resilient functions with high nonlinearity, high algebraic degree, and monotone increasing immunity profile.
Citation: 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
References:
[1]

C. H. Bennett, G. Brassard and J. M. Robert, Privacy amplification by public discussion,, SIAM J. Comp., 17 (1988), 210. doi: 10.1137/0217014. Google Scholar

[2]

A. Braeken, V. Nikov, S. Nikova and B. Preneel, On Boolean functions with generalized cryptographic properties,, in Progr. Crypt. - INDOCRYPT 2004, (2004), 120. doi: 10.1007/978-3-540-30556-9_11. Google Scholar

[3]

A. Canteaut, On the correlations between a combining functions and functions of fewer variables,, in Proc. Inform. Theory Workshop 2002, (2002), 78. Google Scholar

[4]

A. Canteaut and M. Trabbia, Improved fast correlation attacks using parity-check equations of weight $4$ and $5$,, in Adv. Crypt. - EUROCRYPT 2000, (2000), 573. Google Scholar

[5]

C. Carlet, More correlation-immune and resilient functions over Galois fields and Galois rings,, in Adv. Crypt. - EUROCRYPT'97, (1997), 422. doi: 10.1007/3-540-69053-0_29. Google Scholar

[6]

C. Carlet, On the coset weight divisibility and nonlinearity of resilient and correlation-immune functions,, in Proc. SETA'01 Seq. Appl., (2002), 131. Google Scholar

[7]

C. Carlet, Boolean functions for cryptography and error correcting codes,, in Boolean Models and Methods in Mathematics, (2010), 257. Google Scholar

[8]

C. Carlet, Vectorial Boolean functions for cryptography,, in Boolean Models and Methods in Mathematics, (2010), 398. Google Scholar

[9]

C. Carlet, P. Guilot and S. Mesnager, On immunity profile of Boolean functions,, in Proc Seq. Appl. - SETA 2006, (2006), 364. doi: 10.1007/11863854_32. Google Scholar

[10]

C. Carlet and P. Sarkar, Spectral domain analysis of correlation immune and resilient Boolean functions,, Finite Fields Appl., 8 (2002), 120. doi: 10.1006/ffta.2001.0332. Google Scholar

[11]

V. V. Chepyzhov, T. Johansson and B. Smeets, A simple algorithm for fast correlation attacks on stream ciphers,, in Fast Software Encryption, (2000), 181. Google Scholar

[12]

B. Chor, O. Goldreich, J. Hastad, J. Friedman, S. Rudich and R. Smolensky, The bit extraction problem or $t$-resilient functions,, in 26th IEEE Symp. Found. Comp. Sci., (1985), 396. Google Scholar

[13]

G. Cohen, I. Honkala , S. Litsyn and A. Lobstein, Covering Codes,, North-Holland, (1997). Google Scholar

[14]

J. F. Dillon, Elementary Hadamard Difference Sets,, Ph.D. thesis, (1974). Google Scholar

[15]

T. Johansson and E. Pasalic, A construction of resilient functions with high nonlinearity,, IEEE Trans. Inform. Theory, 49 (2003), 494. doi: 10.1109/TIT.2002.807297. Google Scholar

[16]

K. Kurosawa, T. Johansson and D. Stinson, Almost $k$-wise independent sample spaces and their cryptologic applications,, J. Crypt., 14 (2001), 301. doi: 10.1007/3-540-69053-0_28. Google Scholar

[17]

K. Kurosawa and R. Matsumoto, Almost security of cryptographic Boolean functions,, IEEE Trans. Inform. Theory, 50 (2004), 2572. doi: 10.1109/TIT.2004.836684. Google Scholar

[18]

P. Lacharme, Analysis and construction of correctors,, IEEE Trans. Inform. Theory, 55 (2009), 4742. doi: 10.1109/TIT.2009.2027483. Google Scholar

[19]

J. Liu, L. Chen and X. Guang, Highly nonlinear resilient functions without linear structures,, IEICE Trans. Fundam., E97-A (2014), 1405. Google Scholar

[20]

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes,, North-Holland, (1977). Google Scholar

[21]

W. Meier and O. Staffelbach, Fast correlation attacks on stream ciphers,, in Adv. Crypt. - EUROCRYPT'88, (1988), 301. Google Scholar

[22]

P. Sarkar and S. Maitra, Nonlinearity bounds and constructions of resilient Boolean functions,, in Adv. Crypt. - CRYPTO 2000, (2000), 515. doi: 10.1007/3-540-44598-6_32. Google Scholar

[23]

T. Siegenthaler, Correlation immunity of nonlinear combining functions for cryptographic applications,, IEEE Trans. Inform. Theory, 30 (1984), 776. doi: 10.1109/TIT.1984.1056949. Google Scholar

[24]

T. Siegenthaler, Decrypting a class of stream ciphers using ciphertext only,, IEEE Trans. Comp., C-34 (1985), 81. Google Scholar

[25]

Y. V. Tarannikov, New constructions of resilient Boolean functions with maximum nonlinearity,, in Proc. 8th Int. Workshop FSE 2001, (2001), 66. Google Scholar

[26]

G. Z. Xiao and J. L. Massey, A spectral characterization of correlation-immune combining functions,, IEEE Trans. Inform. Theory, 34 (1988), 569. doi: 10.1109/18.6037. Google Scholar

[27]

W. Zhang and E. Pasalic, Constructions of resilient S-boxes with strictly almost optimal nonlinearity through disjoint linear codes,, IEEE Trans. Inform. Theory, 60 (2014), 1638. doi: 10.1109/TIT.2014.2300067. Google Scholar

[28]

X.-M. Zhang and Y. Zheng, Cryptographically resilient functions,, IEEE Trans. Inform. Theory, 43 (1997), 1740. doi: 10.1109/18.623184. Google Scholar

show all references

References:
[1]

C. H. Bennett, G. Brassard and J. M. Robert, Privacy amplification by public discussion,, SIAM J. Comp., 17 (1988), 210. doi: 10.1137/0217014. Google Scholar

[2]

A. Braeken, V. Nikov, S. Nikova and B. Preneel, On Boolean functions with generalized cryptographic properties,, in Progr. Crypt. - INDOCRYPT 2004, (2004), 120. doi: 10.1007/978-3-540-30556-9_11. Google Scholar

[3]

A. Canteaut, On the correlations between a combining functions and functions of fewer variables,, in Proc. Inform. Theory Workshop 2002, (2002), 78. Google Scholar

[4]

A. Canteaut and M. Trabbia, Improved fast correlation attacks using parity-check equations of weight $4$ and $5$,, in Adv. Crypt. - EUROCRYPT 2000, (2000), 573. Google Scholar

[5]

C. Carlet, More correlation-immune and resilient functions over Galois fields and Galois rings,, in Adv. Crypt. - EUROCRYPT'97, (1997), 422. doi: 10.1007/3-540-69053-0_29. Google Scholar

[6]

C. Carlet, On the coset weight divisibility and nonlinearity of resilient and correlation-immune functions,, in Proc. SETA'01 Seq. Appl., (2002), 131. Google Scholar

[7]

C. Carlet, Boolean functions for cryptography and error correcting codes,, in Boolean Models and Methods in Mathematics, (2010), 257. Google Scholar

[8]

C. Carlet, Vectorial Boolean functions for cryptography,, in Boolean Models and Methods in Mathematics, (2010), 398. Google Scholar

[9]

C. Carlet, P. Guilot and S. Mesnager, On immunity profile of Boolean functions,, in Proc Seq. Appl. - SETA 2006, (2006), 364. doi: 10.1007/11863854_32. Google Scholar

[10]

C. Carlet and P. Sarkar, Spectral domain analysis of correlation immune and resilient Boolean functions,, Finite Fields Appl., 8 (2002), 120. doi: 10.1006/ffta.2001.0332. Google Scholar

[11]

V. V. Chepyzhov, T. Johansson and B. Smeets, A simple algorithm for fast correlation attacks on stream ciphers,, in Fast Software Encryption, (2000), 181. Google Scholar

[12]

B. Chor, O. Goldreich, J. Hastad, J. Friedman, S. Rudich and R. Smolensky, The bit extraction problem or $t$-resilient functions,, in 26th IEEE Symp. Found. Comp. Sci., (1985), 396. Google Scholar

[13]

G. Cohen, I. Honkala , S. Litsyn and A. Lobstein, Covering Codes,, North-Holland, (1997). Google Scholar

[14]

J. F. Dillon, Elementary Hadamard Difference Sets,, Ph.D. thesis, (1974). Google Scholar

[15]

T. Johansson and E. Pasalic, A construction of resilient functions with high nonlinearity,, IEEE Trans. Inform. Theory, 49 (2003), 494. doi: 10.1109/TIT.2002.807297. Google Scholar

[16]

K. Kurosawa, T. Johansson and D. Stinson, Almost $k$-wise independent sample spaces and their cryptologic applications,, J. Crypt., 14 (2001), 301. doi: 10.1007/3-540-69053-0_28. Google Scholar

[17]

K. Kurosawa and R. Matsumoto, Almost security of cryptographic Boolean functions,, IEEE Trans. Inform. Theory, 50 (2004), 2572. doi: 10.1109/TIT.2004.836684. Google Scholar

[18]

P. Lacharme, Analysis and construction of correctors,, IEEE Trans. Inform. Theory, 55 (2009), 4742. doi: 10.1109/TIT.2009.2027483. Google Scholar

[19]

J. Liu, L. Chen and X. Guang, Highly nonlinear resilient functions without linear structures,, IEICE Trans. Fundam., E97-A (2014), 1405. Google Scholar

[20]

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes,, North-Holland, (1977). Google Scholar

[21]

W. Meier and O. Staffelbach, Fast correlation attacks on stream ciphers,, in Adv. Crypt. - EUROCRYPT'88, (1988), 301. Google Scholar

[22]

P. Sarkar and S. Maitra, Nonlinearity bounds and constructions of resilient Boolean functions,, in Adv. Crypt. - CRYPTO 2000, (2000), 515. doi: 10.1007/3-540-44598-6_32. Google Scholar

[23]

T. Siegenthaler, Correlation immunity of nonlinear combining functions for cryptographic applications,, IEEE Trans. Inform. Theory, 30 (1984), 776. doi: 10.1109/TIT.1984.1056949. Google Scholar

[24]

T. Siegenthaler, Decrypting a class of stream ciphers using ciphertext only,, IEEE Trans. Comp., C-34 (1985), 81. Google Scholar

[25]

Y. V. Tarannikov, New constructions of resilient Boolean functions with maximum nonlinearity,, in Proc. 8th Int. Workshop FSE 2001, (2001), 66. Google Scholar

[26]

G. Z. Xiao and J. L. Massey, A spectral characterization of correlation-immune combining functions,, IEEE Trans. Inform. Theory, 34 (1988), 569. doi: 10.1109/18.6037. Google Scholar

[27]

W. Zhang and E. Pasalic, Constructions of resilient S-boxes with strictly almost optimal nonlinearity through disjoint linear codes,, IEEE Trans. Inform. Theory, 60 (2014), 1638. doi: 10.1109/TIT.2014.2300067. Google Scholar

[28]

X.-M. Zhang and Y. Zheng, Cryptographically resilient functions,, IEEE Trans. Inform. Theory, 43 (1997), 1740. doi: 10.1109/18.623184. Google Scholar

[1]

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

[2]

Deng Tang. A note on the fast algebraic immunity and its consequences on modified majority functions. Advances in Mathematics of Communications, 2020, 14 (1) : 111-125. doi: 10.3934/amc.2020009

[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]

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

[5]

Claude Carlet, Brahim Merabet. Asymptotic lower bound on the algebraic immunity of random balanced multi-output Boolean functions. Advances in Mathematics of Communications, 2013, 7 (2) : 197-217. doi: 10.3934/amc.2013.7.197

[6]

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

[7]

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

[8]

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

[9]

Lassi Roininen, Markku S. Lehtinen, Sari Lasanen, Mikko Orispää, Markku Markkanen. Correlation priors. Inverse Problems & Imaging, 2011, 5 (1) : 167-184. doi: 10.3934/ipi.2011.5.167

[10]

Sihem Mesnager, Fengrong Zhang, Yong Zhou. On construction of bent functions involving symmetric functions and their duals. Advances in Mathematics of Communications, 2017, 11 (2) : 347-352. doi: 10.3934/amc.2017027

[11]

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

[12]

Jia Li. A malaria model with partial immunity in humans. Mathematical Biosciences & Engineering, 2008, 5 (4) : 789-801. doi: 10.3934/mbe.2008.5.789

[13]

C. Connell Mccluskey. Lyapunov functions for tuberculosis models with fast and slow progression. Mathematical Biosciences & Engineering, 2006, 3 (4) : 603-614. doi: 10.3934/mbe.2006.3.603

[14]

Ming Su, Arne Winterhof. Hamming correlation of higher order. Advances in Mathematics of Communications, 2018, 12 (3) : 505-513. doi: 10.3934/amc.2018029

[15]

Vladimír Špitalský. Local correlation entropy. Discrete & Continuous Dynamical Systems - A, 2018, 38 (11) : 5711-5733. doi: 10.3934/dcds.2018249

[16]

Xiao-Hong Liu, Wei Wu. Coerciveness of some merit functions over symmetric cones. Journal of Industrial & Management Optimization, 2009, 5 (3) : 603-613. doi: 10.3934/jimo.2009.5.603

[17]

Nian Li, Xiaohu Tang, Tor Helleseth. A class of quaternary sequences with low correlation. Advances in Mathematics of Communications, 2015, 9 (2) : 199-210. doi: 10.3934/amc.2015.9.199

[18]

Xin-Guo Liu, Kun Wang. A multigrid method for the maximal correlation problem. Numerical Algebra, Control & Optimization, 2012, 2 (4) : 785-796. doi: 10.3934/naco.2012.2.785

[19]

Kaitlyn (Voccola) Muller. SAR correlation imaging and anisotropic scattering. Inverse Problems & Imaging, 2018, 12 (3) : 697-731. doi: 10.3934/ipi.2018030

[20]

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

2018 Impact Factor: 0.879

Metrics

  • PDF downloads (11)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]