# American Institute of Mathematical Sciences

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-1173. 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 "EUROCRYPT 2000,'' (2000), 507-522. 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-1513. doi: 10.1109/18.923730.  Google Scholar [4] C. Carlet, Partially bent functions, in "Advances in Cryptology-Crypto'92,'' Springer-Verlag, (1993), 280-291. doi: 10.1007/3-540-48071-4_19.  Google Scholar [5] C. Carlet, Boolean functions for cryptography and error correcting codes, in "Boolean Models and Methods in Mathematics, Computer Science, and Engineering'' (eds. Y. Crama and P. Hammer), Cambridge University Press, Cambridge, (2010), 257-397. doi: 10.1017/CBO9780511780448.011.  Google Scholar [6] P. Charpin and E. Pasalic, On propagation characteristics of resilient functions, in "Selected Areas in Cryptography,'' Springer, Berlin, (2003), 175-195. 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 "Selected Areas in Cryptography,'' Springer, Berlin, (2004), 275-290. 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, available online at http://fuee.u-fukui.ac.jp/~hirose/publication/kuis-tech-rep-94-0002.pdf Google Scholar [10] S. Maitra, Highly nonlinear balanced Boolean functions with very good autocorrelation property, in "Proc. Workshop on Coding and Cryptography 2001,'' Elsevier, (2001), 355-364.  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 "Advances in Cryptology-Eurocrypt'90,'' Springer-Verlag, Berlin, (1991), 155-165. 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-144. 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-24. 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, Queen's University, Ontario, Cannada, 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-333.  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-134. 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-1223. 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-265. 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-278. 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-2179. 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-1173. 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 "EUROCRYPT 2000,'' (2000), 507-522. 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-1513. doi: 10.1109/18.923730.  Google Scholar [4] C. Carlet, Partially bent functions, in "Advances in Cryptology-Crypto'92,'' Springer-Verlag, (1993), 280-291. doi: 10.1007/3-540-48071-4_19.  Google Scholar [5] C. Carlet, Boolean functions for cryptography and error correcting codes, in "Boolean Models and Methods in Mathematics, Computer Science, and Engineering'' (eds. Y. Crama and P. Hammer), Cambridge University Press, Cambridge, (2010), 257-397. doi: 10.1017/CBO9780511780448.011.  Google Scholar [6] P. Charpin and E. Pasalic, On propagation characteristics of resilient functions, in "Selected Areas in Cryptography,'' Springer, Berlin, (2003), 175-195. 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 "Selected Areas in Cryptography,'' Springer, Berlin, (2004), 275-290. 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, available online at http://fuee.u-fukui.ac.jp/~hirose/publication/kuis-tech-rep-94-0002.pdf Google Scholar [10] S. Maitra, Highly nonlinear balanced Boolean functions with very good autocorrelation property, in "Proc. Workshop on Coding and Cryptography 2001,'' Elsevier, (2001), 355-364.  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 "Advances in Cryptology-Eurocrypt'90,'' Springer-Verlag, Berlin, (1991), 155-165. 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-144. 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-24. 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, Queen's University, Ontario, Cannada, 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-333.  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-134. 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-1223. 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-265. 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-278. 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-2179. doi: 10.1080/00207160.2012.712689.  Google Scholar

2020 Impact Factor: 0.935