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

Research article

Export file:

Format

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

Content

  • 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$.
  Figure/Table
  Supplementary
  Article Metrics

References

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 (http://creativecommons.org/licenses/by/4.0)

Download full text in PDF

Export Citation

Article outline

Show full outline
Copyright © AIMS Press All Rights Reserved