### AIMS Mathematics

2020, Issue 5: 4581-4595. doi: 10.3934/math.2020294
Research article

# The nonlinearity and Hamming weights of rotation symmetric Boolean functions of small degree

• Received: 14 January 2020 Accepted: 14 May 2020 Published: 22 May 2020
• MSC : Primary 06E30, 94C10

• Let $e$, $l$ and $n$ be integers such that $1\le e \lt n$ and $3\le l\le n$. Let $\left\langle{i}\right\rangle$ denote the least nonnegative residue of $i \mod n$. In this paper, we investigate the following Boolean function $F_{l, e}^n(x^n) = \sum\limits_{i = 0}^{n-1}x_{i} x_{\left\langle{i+e}\right\rangle}x_{\left\langle{i+2e}\right\rangle}...x_{\left\langle{i+(l-1)e}\right\rangle},$ which plays an important role in cryptography and coding theory. We introduce some new sub-functions and provide some recursive formulas for the Fourier transform. Using these recursive formulas, we show that the nonlinearity of $F_{l, e}^n(x^n)$ is the same as its weight for $5\leq l\leq 7$. Our result confirms partially a conjecture of Yang, Wu and Hong raised in 2013. It also gives a partial answer to a conjecture of Castro, Medina and Stănică proposed in 2018. Our result extends the result of Zhang, Guo, Feng and Li for the case $l = 3$ and that of Yang, Wu and Hong for the case $l = 4$.

Citation: Liping Yang, Shaofang Hong, Yongchao Xu. The nonlinearity and Hamming weights of rotation symmetric Boolean functions of small degree[J]. AIMS Mathematics, 2020, 5(5): 4581-4595. doi: 10.3934/math.2020294

### Related Papers:

• Let $e$, $l$ and $n$ be integers such that $1\le e \lt n$ and $3\le l\le n$. Let $\left\langle{i}\right\rangle$ denote the least nonnegative residue of $i \mod n$. In this paper, we investigate the following Boolean function $F_{l, e}^n(x^n) = \sum\limits_{i = 0}^{n-1}x_{i} x_{\left\langle{i+e}\right\rangle}x_{\left\langle{i+2e}\right\rangle}...x_{\left\langle{i+(l-1)e}\right\rangle},$ which plays an important role in cryptography and coding theory. We introduce some new sub-functions and provide some recursive formulas for the Fourier transform. Using these recursive formulas, we show that the nonlinearity of $F_{l, e}^n(x^n)$ is the same as its weight for $5\leq l\leq 7$. Our result confirms partially a conjecture of Yang, Wu and Hong raised in 2013. It also gives a partial answer to a conjecture of Castro, Medina and Stănică proposed in 2018. Our result extends the result of Zhang, Guo, Feng and Li for the case $l = 3$ and that of Yang, Wu and Hong for the case $l = 4$.

 [1] F. N. Castro, R. Chapman, L. A. Medina, et al. Recursions associated to trapezoid, symmetric and rotation symmetric functions over Galois fields, Discrete Math. 341 (2018), 1915-1931. doi: 10.1016/j.disc.2018.03.019 [2] F. N. Castro, L. A. Medina and P. Stănică, Generalized Walsh transforms of symmetric and rotation symmetric Boolean functions are linear recurrent, Appl. Algebra Eng. Comm., 29 (2018), 433-453. doi: 10.1007/s00200-018-0351-5 [3] L. C. Ciungu, Cryptographic Boolean functions: Thus-Morse sequences, weight and nonlinearity, Ph.D. Thesis, The State University of New York Buffalo, 2010. [4] E. Filiol and C. Fontaine, Highly nonlinear balanced Boolean functions with a good correlation immunity. In: International Conference on the Theory and Applications of Cryptographic Techniques, 1403 (1998), 475-488, Springer, Berlin. [5] S. Kavut, S. Maitra and M. D. Yucel, Search for Boolean functions with excellent profiles in the rotation symmetric class, IEEE T. Inform. Theory, 53 (2007), 1743-1751. [6] H. Kim, S. Park and S. G. Hahn, On the weight and nonlinearity of homogeneous rotation symmetric Boolean functions of degree 2, Discrete Appl. Math., 157 (2009), 428-432. doi: 10.1016/j.dam.2008.06.022 [7] S. Mariai, T. Shimoyama and T. Kaneko, Higher order differential attack using chosen higher order differences, International Workshop on Selected Areas in Cryptography, 1556 (1998), 106-117, Springer-Verlag, Berlin. [8] J. Pieprzyk and C. X. Qu, Fast hashing and rotation-symmetric functions, J. Univers. Comput. Sci., 5 (1999), 20-31. [9] P. Stănică and S. Maitra, Rotation symmetric Boolean functions count and cryptographic properties, Discrete Appl. Math., 156 (2008), 1567-1580. doi: 10.1016/j.dam.2007.04.029 [10] L. P. Yang, R. J. Wu and S. F. Hong, Nonlinearity of quartic rotation symmetric Boolean functions, Southeast Asian Bull. Math., 37 (2013), 951-961. [11] X. Zhang, H. Guo, R. Feng, et al. Proof of a conjecture about rotation symmetric functions, Discrete Math., 311 (2011), 1281-1289. doi: 10.1016/j.disc.2011.03.012
###### 通讯作者: 陈斌, bchen63@163.com
• 1.

沈阳化工大学材料科学与工程学院 沈阳 110142

0.882 0.9

Article outline

Tables(1)

• On This Site