American Institute of Mathematical Sciences

Advanced
May  2019, 13(2): 253-265. doi: 10.3934/amc.2019017

A new construction of rotation symmetric bent functions with maximal algebraic degree

Sihong Su ,

School of Mathematics and Statistics, Henan University, Kaifeng 475004, China

* Corresponding author: Sihong Su (E-mail: sush@henu.edu.cn)

Received  March 2018 Published  February 2019

Fund Project: The author is supported by the National Natural Science Foundation of China (Grant No. 61502147) and the Excellent Youth Program of Henan University (Grant No. yqpy20170063).

In this paper, for any even integer
$ n = 2m\ge4 $
, a new construction of
$ n $
-variable rotation symmetric bent function with maximal algebraic degree
$ m $
 is given as
$ f(x_0,x_1\cdots,x_{n-1}) = \bigoplus\limits_{i = 0}^{m-1}(x_ix_{m+i})\oplus \bigoplus\limits_{i = 0}^{n-1}(x_ix_{i+1}\cdots x_{i+m-2} \overline{x_{i+m}} ), $
whose dual function is
$ \widetilde{f}(x_0,x_1\cdots,x_{n-1}) = \bigoplus\limits_{i = 0}^{m-1}(x_ix_{m+i})\oplus \bigoplus\limits_{i = 0}^{n-1}(x_ix_{i+1}\cdots x_{i+m-2} \overline{x_{i+n-2}} ), $
where
$ \overline{x_{i}} = x_{i}\oplus 1 $
 and the subscript of
$ x $
 is modulo
$ n $
.
Keywords: Orbit, rotation symmetric Boolean function, Walsh-Hadamard transform, bent function, algebraic degree.
Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.
Citation: Sihong Su. A new construction of rotation symmetric bent functions with maximal algebraic degree. Advances in Mathematics of Communications, 2019, 13 (2) : 253-265. doi: 10.3934/amc.2019017
References:
[1]

A. Canteaut and P. Charpin, Decomposing Bent functions, IEEE Trans. Inf. Theory, 49 (2003), 2004-2019.  doi: 10.1109/TIT.2003.814476.  Google Scholar

[2]

C. Carlet, Boolean functions for cryptography and error correcting codes, in Boolean Models and Methods (eds. Y. Crama and P. L. Hammer), Cambridge, U.K.: Cambridge Univ. Press, (2010), 257–397. Google Scholar

[3]

C. Carlet, G. Gao and W. Liu, A secondary construction and a transformation on rotation symmetric functions, and their action on bent and semi-bent functions, J. Comb. Theory, Ser. A, 127 (2014), 161-175.  doi: 10.1016/j.jcta.2014.05.008.  Google Scholar

[4]

C. Carlet, G. Gao and W. Liu, Results on constructions of rotation symmetric bent and semi-bent functions, in Sequences and Their Applications–SETA 2014, Springer International Publishing, Switzerland, 8865 (2014), 21–33. doi: 10.1007/978-3-319-12325-7_2.  Google Scholar

[5]

P. Charpin, E. Pasalic and C. Tavernier, On bent and semi-bent quadratic Boolean functions, IEEE Trans. Inf. Theory, 51 (2005), 4286-4298.  doi: 10.1109/TIT.2005.858929.  Google Scholar

[6]

$\acute{E}$. Filiol and C. Fontaine, Highly nonlinear balanced Boolean functions with a good correlation-immunity, in EUROCRYPT 1998, (eds. K. Nyberg), Springer, Heidelberg, 1403 (1998), 475–488. doi: 10.1007/BFb0054147.  Google Scholar

[7]

C. Fontaine, On some cosets of the first-order Reed-Muller code with high minimum weight, IEEE Trans. Inf. Theory, 45 (1999), 1237-1243.  doi: 10.1109/18.761276.  Google Scholar

[8]

S. Fu, L. Qu, C. Li and B. Sun, Balanced rotation symmetric Boolean functions with maximum algebraic immunity, IET Inf. Secur., 5 (2011), 93-99.  doi: 10.1049/iet-ifs.2010.0048.  Google Scholar

[9]

G. Gao, X. Zhang, W. Liu and C. Carlet, Constructions of quadratic and cubic rotation symmetric bent functions, IEEE Trans. Inf. Theory, 58 (2012), 4908-4913.  doi: 10.1109/TIT.2012.2193377.  Google Scholar

[10]

S. Kavut, S. Maitra and M. Yücel, Search for Boolean functions with excellent profiles in the rotation symmetric class, IEEE Trans. Inf. Theory, 53 (2007), 1743-1751.  doi: 10.1109/TIT.2007.894696.  Google Scholar

[11]

A. Lempel and M. Cohn, Maximal families of bent sequences, IEEE Trans. Inf. Theory, 28 (1982), 865-868.  doi: 10.1109/TIT.1982.1056590.  Google Scholar

[12]

F. MacWilliams and N. Sloane, The Theory of Error-Correcting Codes, Amsterdam, The Netherlands, North-Holland, 1977.  Google Scholar

[13]

S. Mesnager, Several new infinite families of bent functions and their duals, IEEE Trans. Inf. Theory, 60 (2014), 4397-4407.  doi: 10.1109/TIT.2014.2320974.  Google Scholar

[14]

S. Mesnager, Bent Functions, Springer International Publishing Switzeland, 2016. doi: 10.1007/978-3-319-32595-8.  Google Scholar

[15]

J. Olsen, R. Scholtz and L. Welch, Bent-function sequences, IEEE Trans. Inf. Theory, 28 (1982), 858-864.  doi: 10.1109/TIT.1982.1056589.  Google Scholar

[16]

J. Pieprzyk and C. Qu, Fast hashing and rotation-symmetric functions, J. Univ. Comput. Sci., 5 (1999), 20-31.   Google Scholar

[17]

O. Rothaus, On 'bent' functions, J. Comb. Theory, Series A, 20 (1976), 300-305.  doi: 10.1016/0097-3165(76)90024-8.  Google Scholar

[18]

S. Su and X. Tang, Systematic constructions of rotation symmetric bent functions, 2-rotation symmetric bent functions, and bent idempotent functions, IEEE Trans. Inf. Theory., 63 (2017), 4658-4667.  doi: 10.1109/TIT.2016.2621751.  Google Scholar

[19]

W. Zhang, Z. Xing and K. Feng, A construction of bent functions with optimal algebraic degree and large symmetric group, preprint, Cryptology ePrint Archive, : Submission 2017/229. Google Scholar

show all references

References:
[1]

A. Canteaut and P. Charpin, Decomposing Bent functions, IEEE Trans. Inf. Theory, 49 (2003), 2004-2019.  doi: 10.1109/TIT.2003.814476.  Google Scholar

[2]

C. Carlet, Boolean functions for cryptography and error correcting codes, in Boolean Models and Methods (eds. Y. Crama and P. L. Hammer), Cambridge, U.K.: Cambridge Univ. Press, (2010), 257–397. Google Scholar

[3]

C. Carlet, G. Gao and W. Liu, A secondary construction and a transformation on rotation symmetric functions, and their action on bent and semi-bent functions, J. Comb. Theory, Ser. A, 127 (2014), 161-175.  doi: 10.1016/j.jcta.2014.05.008.  Google Scholar

[4]

C. Carlet, G. Gao and W. Liu, Results on constructions of rotation symmetric bent and semi-bent functions, in Sequences and Their Applications–SETA 2014, Springer International Publishing, Switzerland, 8865 (2014), 21–33. doi: 10.1007/978-3-319-12325-7_2.  Google Scholar

[5]

P. Charpin, E. Pasalic and C. Tavernier, On bent and semi-bent quadratic Boolean functions, IEEE Trans. Inf. Theory, 51 (2005), 4286-4298.  doi: 10.1109/TIT.2005.858929.  Google Scholar

[6]

$\acute{E}$. Filiol and C. Fontaine, Highly nonlinear balanced Boolean functions with a good correlation-immunity, in EUROCRYPT 1998, (eds. K. Nyberg), Springer, Heidelberg, 1403 (1998), 475–488. doi: 10.1007/BFb0054147.  Google Scholar

[7]

C. Fontaine, On some cosets of the first-order Reed-Muller code with high minimum weight, IEEE Trans. Inf. Theory, 45 (1999), 1237-1243.  doi: 10.1109/18.761276.  Google Scholar

[8]

S. Fu, L. Qu, C. Li and B. Sun, Balanced rotation symmetric Boolean functions with maximum algebraic immunity, IET Inf. Secur., 5 (2011), 93-99.  doi: 10.1049/iet-ifs.2010.0048.  Google Scholar

[9]

G. Gao, X. Zhang, W. Liu and C. Carlet, Constructions of quadratic and cubic rotation symmetric bent functions, IEEE Trans. Inf. Theory, 58 (2012), 4908-4913.  doi: 10.1109/TIT.2012.2193377.  Google Scholar

[10]

S. Kavut, S. Maitra and M. Yücel, Search for Boolean functions with excellent profiles in the rotation symmetric class, IEEE Trans. Inf. Theory, 53 (2007), 1743-1751.  doi: 10.1109/TIT.2007.894696.  Google Scholar

[11]

A. Lempel and M. Cohn, Maximal families of bent sequences, IEEE Trans. Inf. Theory, 28 (1982), 865-868.  doi: 10.1109/TIT.1982.1056590.  Google Scholar

[12]

F. MacWilliams and N. Sloane, The Theory of Error-Correcting Codes, Amsterdam, The Netherlands, North-Holland, 1977.  Google Scholar

[13]

S. Mesnager, Several new infinite families of bent functions and their duals, IEEE Trans. Inf. Theory, 60 (2014), 4397-4407.  doi: 10.1109/TIT.2014.2320974.  Google Scholar

[14]

S. Mesnager, Bent Functions, Springer International Publishing Switzeland, 2016. doi: 10.1007/978-3-319-32595-8.  Google Scholar

[15]

J. Olsen, R. Scholtz and L. Welch, Bent-function sequences, IEEE Trans. Inf. Theory, 28 (1982), 858-864.  doi: 10.1109/TIT.1982.1056589.  Google Scholar

[16]

J. Pieprzyk and C. Qu, Fast hashing and rotation-symmetric functions, J. Univ. Comput. Sci., 5 (1999), 20-31.   Google Scholar

[17]

O. Rothaus, On 'bent' functions, J. Comb. Theory, Series A, 20 (1976), 300-305.  doi: 10.1016/0097-3165(76)90024-8.  Google Scholar

[18]

S. Su and X. Tang, Systematic constructions of rotation symmetric bent functions, 2-rotation symmetric bent functions, and bent idempotent functions, IEEE Trans. Inf. Theory., 63 (2017), 4658-4667.  doi: 10.1109/TIT.2016.2621751.  Google Scholar

[19]

W. Zhang, Z. Xing and K. Feng, A construction of bent functions with optimal algebraic degree and large symmetric group, preprint, Cryptology ePrint Archive, : Submission 2017/229. Google Scholar

[1]

Wenying Zhang, Zhaohui Xing, Keqin Feng. A construction of bent functions with optimal algebraic degree and large symmetric group. Advances in Mathematics of Communications, 2020, 14 (1) : 23-33. doi: 10.3934/amc.2020003
[2]

Tingting Pang, Nian Li, Li Zhang, Xiangyong Zeng. Several new classes of (balanced) Boolean functions with few Walsh transform values. Advances in Mathematics of Communications, 2021, 15 (4) : 757-775. doi: 10.3934/amc.2020095
[3]

Junchao Zhou, Nian Li, Xiangyong Zeng, Yunge Xu. A generic construction of rotation symmetric bent functions. Advances in Mathematics of Communications, 2021, 15 (4) : 721-736. doi: 10.3934/amc.2020092
[4]

Michel C. Delfour. Hadamard Semidifferential, Oriented Distance Function, and some Applications. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021076
[5]

Li Zhang, Xiaofeng Zhou, Min Chen. The research on the properties of Fourier matrix and bent function. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 571-578. doi: 10.3934/naco.2020052
[6]

Thomas W. Cusick, Younhwan Cheon. The weight recursions for the 2-rotation symmetric quartic Boolean functions. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021011
[7]

Bingxin Wang, Sihong Su. A New Construction of odd-variable Rotation symmetric Boolean functions with good cryptographic properties. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020115
[8]

Hans Rullgård, Eric Todd Quinto. Local Sobolev estimates of a function by means of its Radon transform. Inverse Problems & Imaging, 2010, 4 (4) : 721-734. doi: 10.3934/ipi.2010.4.721
[9]

Bimal Mandal, Aditi Kar Gangopadhyay. A note on generalization of bent boolean functions. Advances in Mathematics of Communications, 2021, 15 (2) : 329-346. doi: 10.3934/amc.2020069
[10]

Sihem Mesnager, Gérard Cohen. Fast algebraic immunity of Boolean functions. Advances in Mathematics of Communications, 2017, 11 (2) : 373-377. doi: 10.3934/amc.2017031
[11]

Behrouz Kheirfam. A full Nesterov-Todd step infeasible interior-point algorithm for symmetric optimization based on a specific kernel function. Numerical Algebra, Control & Optimization, 2013, 3 (4) : 601-614. doi: 10.3934/naco.2013.3.601
[12]

Ingrid Beltiţă, Anders Melin. The quadratic contribution to the backscattering transform in the rotation invariant case. Inverse Problems & Imaging, 2010, 4 (4) : 599-618. doi: 10.3934/ipi.2010.4.599
[13]

Sihem Mesnager, Fengrong Zhang, Yong Zhou. On construction of bent functions involving symmetric functions and their duals. Advances in Mathematics of Communications, 2017, 11 (2) : 347-352. doi: 10.3934/amc.2017027
[14]

Yuri Latushkin, Alim Sukhtayev. The Evans function and the Weyl-Titchmarsh function. Discrete & Continuous Dynamical Systems - S, 2012, 5 (5) : 939-970. doi: 10.3934/dcdss.2012.5.939
[15]

J. William Hoffman. Remarks on the zeta function of a graph. Conference Publications, 2003, 2003 (Special) : 413-422. doi: 10.3934/proc.2003.2003.413
[16]

H. N. Mhaskar, T. Poggio. Function approximation by deep networks. Communications on Pure & Applied Analysis, 2020, 19 (8) : 4085-4095. doi: 10.3934/cpaa.2020181
[17]

Hassan Emamirad, Philippe Rogeon. Semiclassical limit of Husimi function. Discrete & Continuous Dynamical Systems - S, 2013, 6 (3) : 669-676. doi: 10.3934/dcdss.2013.6.669
[18]

Ken Ono. Parity of the partition function. Electronic Research Announcements, 1995, 1: 35-42.

[19]

Tomasz Downarowicz, Yonatan Gutman, Dawid Huczek. Rank as a function of measure. Discrete & Continuous Dynamical Systems, 2014, 34 (7) : 2741-2750. doi: 10.3934/dcds.2014.34.2741
[20]

Jaume Llibre, Y. Paulina Martínez, Claudio Vidal. Phase portraits of linear type centers of polynomial Hamiltonian systems with Hamiltonian function of degree 5 of the form $ H = H_1(x)+H_2(y)$. Discrete & Continuous Dynamical Systems, 2019, 39 (1) : 75-113. doi: 10.3934/dcds.2019004

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (198)
  • HTML views (362)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences