AIMS Mathematics, 2020, 5(5): 4581-4595. doi: 10.3934/math.2020294

Research article

Export file:


  • RIS(for EndNote,Reference Manager,ProCite)
  • BibTex
  • Text


  • Citation Only
  • Citation and Abstract

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

Mathematical College, Sichuan University, Chengdu 610064, P. R. China

Let $e$, $l$ and $n$ be integers such that $1\le e<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_{i=0}^{n-1}x_{i} x_{\left\langle {i + e} \right\rangle}x_{\left\langle {i + 2e} \right\rangle }...x_{\left\langle {i + \left( {l - 1} \right)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$.
  Article Metrics


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.    

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.    

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.    

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.    

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.    

© 2020 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution Licese (

Download full text in PDF

Export Citation

Article outline

Show full outline
Copyright © AIMS Press All Rights Reserved