×

Hamming weights of symmetric Boolean functions. (English) Zbl 1346.05296

Summary: It has been known since 1996 [J.-Y. Cai et al., Math. Syst. Theory 29, No. 3, 245–258 (1996; Zbl 0858.94033)] that the sequence of Hamming weights \(\{\mathrm{wt}(f_n(x_1, \ldots, x_n)) \}\), where \(f_n\) is a symmetric Boolean function of degree \(d\) in \(n\) variables, satisfies a linear recurrence with integer coefficients. F. N. Castro and L. A. Medina [Electron. J. Comb. 18, No. 2, Research Paper P8, 21 p. (2011; Zbl 1250.11102)] used this result to show that a conjecture of T. W. Cusick et al. [IEEE Trans. Inf. Theory 54, No. 3, 1304–1307 (2008; Zbl 1306.94041)] about when an elementary symmetric Boolean function can be balanced is true for all sufficiently large \(n\). Quite a few papers have been written about this conjecture, but it is still not completely settled. Recently, Y. Guo et al. [“Recent results on balanced symmetric Boolean functions” (2015; doi:10.1109/TIT.2015.2455052)] proved that the conjecture is equivalent to the statement that all balanced elementary symmetric Boolean functions are trivially balanced. This motivates the further study of the weights of symmetric Boolean functions \(f_n\). In this paper we prove various new results on the trivially balanced functions. We also determine a period (sometimes the minimal one) for the sequence of weights \(\mathrm{wt}(f_n)\) modulo any odd prime \(p\), where \(f_n\) is any symmetric function, and we prove some related results about the balanced symmetric functions.

MSC:

05E05 Symmetric functions and generalizations
06E30 Boolean functions
94A60 Cryptography
Full Text: DOI

References:

[1] Braeken, A.; Preneel, B., On the algebraic immunity of symmetric Boolean functions, (Indocrypt 2005. Indocrypt 2005, LNCS, vol. 3797 (2005), Springer: Springer Berlin), 35-48, Extended version in http://eprint.iacr.org/2005/245 · Zbl 1153.94353
[2] Cai, J.; Green, F.; Thierauf, T., On the correlation of symmetric functions, Math. Syst. Theory, 29, 245-258 (1996) · Zbl 0858.94033
[3] Canteaut, A.; Videau, M., Symmetric Boolean functions, IEEE Trans. Inform. Theory, 51, 2791-2811 (2005) · Zbl 1264.94094
[4] Carlet, C.; Dalai, D. K.; Gupta, K. C.; Maitra, S., Algebraic immunity for cryptographically significant Boolean functions: analysis and construction, IEEE Trans. Inform. Theory, 52, 3105-3121 (2006) · Zbl 1192.94091
[5] Castro, F. N.; González, O. E.; Medina, L. A., A divisibility approach to the open boundary cases of Cusick-Li-Stănică’s conjecture, Cryptogr. Commun., 7, 379-402 (2015) · Zbl 1326.05164
[6] Castro, F. N.; Medina, L. A., Linear recurrences and asymptotic behavior of exponential sums of symmetric Boolean functions, Electron. J. Combin., 18, 2 (2011), paper 8, 21 pages · Zbl 1250.11102
[7] Cusick, T. W.; Li, Y.; Stănică, P., Balanced symmetric functions over \(G F(p)\), IEEE Trans. Inform. Theory, 54, 1304-1307 (2008) · Zbl 1306.94041
[8] Cusick, T. W.; Li, Y.; Stănică, P., On a conjecture for balanced symmetric Boolean functions, J. Math. Cryptol., 3, 273-290 (2009) · Zbl 1187.94022
[9] Cusick, T. W.; Stănică, P., Cryptographic Boolean Functions and Applications (2009), Academic Press: Academic Press San Diego · Zbl 1173.94002
[10] Dalai, D. K.; Maitra, S.; Sarkar, P., Basic theory in construction of Boolean functions with maximum possible annihilator immunity, Des. Codes Cryptogr., 40, 41-58 (2006) · Zbl 1202.94179
[11] Gopalakrishnan, K.; Hoffman, D. G.; Stinson, D. R., A note on a conjecture concerning symmetric resilient functions, Inform. Process. Lett., 47, 3, 139-143 (1993) · Zbl 0782.05002
[12] Guo, Y.; Gao, G.; Zhao, Y., Recent results on balanced symmetric Boolean functions, IEEE Trans. Inform. Theory (2016), in press. Earlier version http://eprint.iacr.org/2012/093. http://dx.doi.org/10.1109/TIT.2015.2455052 · Zbl 1359.94933
[13] Jefferies, N., Sporadic partitions of binomial coefficients, Electron. Lett., 27, 1334-1336 (1991) · Zbl 0739.94021
[14] Kolountzakis, M. N.; Lipton, R. J.; Markakis, E.; Mehta, A.; Vishnoi, N. K., On the Fourier spectrum of symmetric Boolean functions, Combinatorica, 29, 363-387 (2009) · Zbl 1212.42017
[15] Liu, M.; Lin, D.; Pei, D., Fast algebraic attacks and decomposition of symmetric Boolean functions, IEEE Trans. Inform. Theory, 57, 4817-4821 (2011) · Zbl 1365.94445
[16] Mitchell, C., Enumerating Boolean functions of cryptographic significance, J. Cryptology, 2, 3, 155-170 (1990) · Zbl 0705.94010
[17] Qu, L.; Feng, K.; Liu, F.; Wang, L., Constructing symmetric Boolean functions with maximum algebraic immunity, IEEE Trans. Inform. Theory, 55, 2406-2412 (2009) · Zbl 1367.94477
[18] Shpilka, A.; Tal, A., On the minimal Fourier degree of symmetric Boolean functions, Combinatorica, 34, 359-377 (2014) · Zbl 1340.68042
[19] Su, W.; Tang, X.; Pott, A., A note on a conjecture for balanced elementary symmetric Boolean functions, IEEE Trans. Inform. Theory, 59, 665-671 (2013) · Zbl 1364.94807
[20] Sun, Z.-W.; Tauraso, R., Congruences for sums of binomial coefficients, J. Number Theory, 126, 287-296 (2007) · Zbl 1215.11013
[21] von zur Gathen, J.; Roche, J. R., Polynomials with two values, Combinatorica, 17, 345-362 (1997) · Zbl 0907.68134
[22] Wang, H.; Peng, J.; Li, Y.; Kan, H., On \(2 k\)-variable symmetric Boolean functions with maximum algebraic immunity \(k\), IEEE Trans. Inform. Theory, 58, 5612-5624 (2012) · Zbl 1364.94811
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.