August  2013, 7(3): 335-347. doi: 10.3934/amc.2013.7.335

On the distribution of auto-correlation value of balanced Boolean functions

1. 

Science and Technology on Communication Security Laboratory, Chengdu, Sichuan 610041, China

Received  November 2012 Revised  February 2013 Published  July 2013

In this paper, we study the lower bound on the sum-of-square indicator of balanced Boolean functions obtained by Son, et al. in 1998, and give a sufficient and necessary condition under which balanced Boolean functions achieve this lower bound. We introduce a new general class of balanced Boolean functions in $n$ variables $(n\geq 4)$ with optimal auto-correlation distribution, and we study two sub-classes more explicitely. Finally, we study the sets of Boolean functions having a same auto-correlation distribution, and derive a lower bound on the number of elements in such set.
Citation: 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
References:
[1]

C. M. Adams and S. E. Tavares, Generating and counting binary bent sequences,, IEEE Trans. Inform. Theory, 36 (1990), 1170.  doi: 10.1109/18.57222.  Google Scholar

[2]

A. Canteaut, C. Carlet, P. Charpin and C. Fontaine, Propagation characteristics and correlation immunity of hightly nonlinear Boolean functions,, in, (2000), 507.  doi: 10.1007/3-540-45539-6_36.  Google Scholar

[3]

A. Canteaut, C. Carlet, P. Charpin and C. Fontaine, On cryptographic properties of the coset of $R(1,m)$,, IEEE Trans. Inform. Theory, 47 (2001), 1494.  doi: 10.1109/18.923730.  Google Scholar

[4]

C. Carlet, Partially bent functions,, in, (1993), 280.  doi: 10.1007/3-540-48071-4_19.  Google Scholar

[5]

C. Carlet, Boolean functions for cryptography and error correcting codes,, in, (2010), 257.  doi: 10.1017/CBO9780511780448.011.  Google Scholar

[6]

P. Charpin and E. Pasalic, On propagation characteristics of resilient functions,, in, (2003), 175.  doi: 10.1007/3-540-36492-7_13.  Google Scholar

[7]

C. Ding and P. Sarkar, Personal communications,, 2000., ().   Google Scholar

[8]

G. Gong and K. Khoo, Additive autocorrelation of resilient Boolean functions,, in, (2004), 275.  doi: 10.1007/978-3-540-24654-1_20.  Google Scholar

[9]

S. Hirose and K. Ikeda, Nonlinearity criteria of Boolean functions,, Kyoto University, (1994), 94.   Google Scholar

[10]

S. Maitra, Highly nonlinear balanced Boolean functions with very good autocorrelation property,, in, (2001), 355.   Google Scholar

[11]

B. Preneel, "Analysis and Design of Cryptographic Hash Functions,'' Ph.D thesis,, Katholieke Universiteit te Leuven, (1993).   Google Scholar

[12]

B. Preneel, W. Leekwijck, L. V. Linden, et al., Propagation characteristics of Boolean functions,, in, (1991), 155.  doi: 10.1007/3-540-46877-3_14.  Google Scholar

[13]

J. J. Son, J. I. Lim, S. Chee and S. H. Sung, Global avalanche characteristics and nonlinearity of balanced Boolean functions,, Inform. Proc. Letters, 65 (1998), 139.  doi: 10.1016/S0020-0190(98)00009-X.  Google Scholar

[14]

S. H. Sung, S. Chee and C. Park, Global avalanche characteristics and propagation criterion of balanced Boolean functions,, Inform. Proc. Letters, 69 (1999), 21.  doi: 10.1016/S0020-0190(98)00184-7.  Google Scholar

[15]

A. F. Webster, "Plaintext/Ciphertext Bit Dependencies in Cryptographic System,'' Master's thesis,, Dep. Electrical Engineering, (1985).   Google Scholar

[16]

X. M. Zhang and Y. L. Zheng, GAC- the criterion for global avalanche characteristics of cryptographic functions,, J. Universal Comp. Sci., 1 (1995), 316.   Google Scholar

[17]

X. M. Zhang and Y. L. Zheng, Characterizing the structures of cryptographic functions satisfying the propagation criterion for almost all vectors,, Des. Codes Crypt., 7 (1996), 111.  doi: 10.1007/BF00125079.  Google Scholar

[18]

Y. L. Zheng and X. M. Zhang, On the plateaued functoins,, IEEE Trans. Inform. Theory, 47 (2001), 1215.  doi: 10.1109/18.915690.  Google Scholar

[19]

Y. Zhou, M. Xie and G. Z. Xiao, On the global avalanche characteristics of two Boolean functions and the higher order nonlinearity,, Inform. Sci., 180 (2010), 256.  doi: 10.1016/j.ins.2009.09.012.  Google Scholar

[20]

Y. Zhou, W. G. Zhang, J. Li, X. F. Dong and G. Z. Xiao, The autocorrelation distribution of balanced Boolean function,, Frontier Comp. Sci., 7 (2013), 272.  doi: 10.1007/s11704-013-2013-x.  Google Scholar

[21]

Y. Zhou, W. Z. Zhang, S. X. Zhu and G. Z. Xiao, The global avalanche characteristics of two Boolean functions and algebraic immunity,, Int. J. Comp. Math., 89 (2012), 2165.  doi: 10.1080/00207160.2012.712689.  Google Scholar

show all references

References:
[1]

C. M. Adams and S. E. Tavares, Generating and counting binary bent sequences,, IEEE Trans. Inform. Theory, 36 (1990), 1170.  doi: 10.1109/18.57222.  Google Scholar

[2]

A. Canteaut, C. Carlet, P. Charpin and C. Fontaine, Propagation characteristics and correlation immunity of hightly nonlinear Boolean functions,, in, (2000), 507.  doi: 10.1007/3-540-45539-6_36.  Google Scholar

[3]

A. Canteaut, C. Carlet, P. Charpin and C. Fontaine, On cryptographic properties of the coset of $R(1,m)$,, IEEE Trans. Inform. Theory, 47 (2001), 1494.  doi: 10.1109/18.923730.  Google Scholar

[4]

C. Carlet, Partially bent functions,, in, (1993), 280.  doi: 10.1007/3-540-48071-4_19.  Google Scholar

[5]

C. Carlet, Boolean functions for cryptography and error correcting codes,, in, (2010), 257.  doi: 10.1017/CBO9780511780448.011.  Google Scholar

[6]

P. Charpin and E. Pasalic, On propagation characteristics of resilient functions,, in, (2003), 175.  doi: 10.1007/3-540-36492-7_13.  Google Scholar

[7]

C. Ding and P. Sarkar, Personal communications,, 2000., ().   Google Scholar

[8]

G. Gong and K. Khoo, Additive autocorrelation of resilient Boolean functions,, in, (2004), 275.  doi: 10.1007/978-3-540-24654-1_20.  Google Scholar

[9]

S. Hirose and K. Ikeda, Nonlinearity criteria of Boolean functions,, Kyoto University, (1994), 94.   Google Scholar

[10]

S. Maitra, Highly nonlinear balanced Boolean functions with very good autocorrelation property,, in, (2001), 355.   Google Scholar

[11]

B. Preneel, "Analysis and Design of Cryptographic Hash Functions,'' Ph.D thesis,, Katholieke Universiteit te Leuven, (1993).   Google Scholar

[12]

B. Preneel, W. Leekwijck, L. V. Linden, et al., Propagation characteristics of Boolean functions,, in, (1991), 155.  doi: 10.1007/3-540-46877-3_14.  Google Scholar

[13]

J. J. Son, J. I. Lim, S. Chee and S. H. Sung, Global avalanche characteristics and nonlinearity of balanced Boolean functions,, Inform. Proc. Letters, 65 (1998), 139.  doi: 10.1016/S0020-0190(98)00009-X.  Google Scholar

[14]

S. H. Sung, S. Chee and C. Park, Global avalanche characteristics and propagation criterion of balanced Boolean functions,, Inform. Proc. Letters, 69 (1999), 21.  doi: 10.1016/S0020-0190(98)00184-7.  Google Scholar

[15]

A. F. Webster, "Plaintext/Ciphertext Bit Dependencies in Cryptographic System,'' Master's thesis,, Dep. Electrical Engineering, (1985).   Google Scholar

[16]

X. M. Zhang and Y. L. Zheng, GAC- the criterion for global avalanche characteristics of cryptographic functions,, J. Universal Comp. Sci., 1 (1995), 316.   Google Scholar

[17]

X. M. Zhang and Y. L. Zheng, Characterizing the structures of cryptographic functions satisfying the propagation criterion for almost all vectors,, Des. Codes Crypt., 7 (1996), 111.  doi: 10.1007/BF00125079.  Google Scholar

[18]

Y. L. Zheng and X. M. Zhang, On the plateaued functoins,, IEEE Trans. Inform. Theory, 47 (2001), 1215.  doi: 10.1109/18.915690.  Google Scholar

[19]

Y. Zhou, M. Xie and G. Z. Xiao, On the global avalanche characteristics of two Boolean functions and the higher order nonlinearity,, Inform. Sci., 180 (2010), 256.  doi: 10.1016/j.ins.2009.09.012.  Google Scholar

[20]

Y. Zhou, W. G. Zhang, J. Li, X. F. Dong and G. Z. Xiao, The autocorrelation distribution of balanced Boolean function,, Frontier Comp. Sci., 7 (2013), 272.  doi: 10.1007/s11704-013-2013-x.  Google Scholar

[21]

Y. Zhou, W. Z. Zhang, S. X. Zhu and G. Z. Xiao, The global avalanche characteristics of two Boolean functions and algebraic immunity,, Int. J. Comp. Math., 89 (2012), 2165.  doi: 10.1080/00207160.2012.712689.  Google Scholar

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

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

[3]

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

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

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

[6]

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

[7]

Qi Wang, Yue Zhou. Sets of zero-difference balanced functions and their applications. Advances in Mathematics of Communications, 2014, 8 (1) : 83-101. doi: 10.3934/amc.2014.8.83

[8]

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

[9]

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

[10]

Claudio Qureshi, Daniel Panario, Rodrigo Martins. Cycle structure of iterating Redei functions. Advances in Mathematics of Communications, 2017, 11 (2) : 397-407. doi: 10.3934/amc.2017034

[11]

Simone Fiori. Auto-regressive moving-average discrete-time dynamical systems and autocorrelation functions on real-valued Riemannian matrix manifolds. Discrete & Continuous Dynamical Systems - B, 2014, 19 (9) : 2785-2808. doi: 10.3934/dcdsb.2014.19.2785

[12]

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

[13]

Yang Yang, Xiaohu Tang, Guang Gong. New almost perfect, odd perfect, and perfect sequences from difference balanced functions with d-form property. Advances in Mathematics of Communications, 2017, 11 (1) : 67-76. doi: 10.3934/amc.2017002

[14]

René Henrion. Gradient estimates for Gaussian distribution functions: application to probabilistically constrained optimization problems. Numerical Algebra, Control & Optimization, 2012, 2 (4) : 655-668. doi: 10.3934/naco.2012.2.655

[15]

Yuyuan Ouyang, Yunmei Chen, Ying Wu. Total variation and wavelet regularization of orientation distribution functions in diffusion MRI. Inverse Problems & Imaging, 2013, 7 (2) : 565-583. doi: 10.3934/ipi.2013.7.565

[16]

Laurent Gosse. Well-balanced schemes using elementary solutions for linear models of the Boltzmann equation in one space dimension. Kinetic & Related Models, 2012, 5 (2) : 283-323. doi: 10.3934/krm.2012.5.283

[17]

Martin Redmann, Melina A. Freitag. Balanced model order reduction for linear random dynamical systems driven by Lévy noise. Journal of Computational Dynamics, 2018, 5 (1&2) : 33-59. doi: 10.3934/jcd.2018002

[18]

Robert Glassey, Stephen Pankavich, Jack Schaeffer. Separated characteristics and global solvability for the one and one-half dimensional Vlasov Maxwell system. Kinetic & Related Models, 2016, 9 (3) : 455-467. doi: 10.3934/krm.2016003

[19]

Qiang Du, M. D. Gunzburger, L. S. Hou, J. Lee. Analysis of a linear fluid-structure interaction problem. Discrete & Continuous Dynamical Systems - A, 2003, 9 (3) : 633-650. doi: 10.3934/dcds.2003.9.633

[20]

Amin Sakzad, Mohammad-Reza Sadeghi, Daniel Panario. Cycle structure of permutation functions over finite fields and their applications. Advances in Mathematics of Communications, 2012, 6 (3) : 347-361. doi: 10.3934/amc.2012.6.347

2018 Impact Factor: 0.879

Metrics

  • PDF downloads (6)
  • HTML views (0)
  • Cited by (4)

Other articles
by authors

[Back to Top]