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
  • Reader Comments
  • © 2020 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

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

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(3983) PDF downloads(332) Cited by(1)

Article outline

Figures and Tables

Tables(1)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog