American Institute of Mathematical Sciences

Advanced
February  2020, 14(1): 23-33. doi: 10.3934/amc.2020003

A construction of bent functions with optimal algebraic degree and large symmetric group

Wenying Zhang 1, , Zhaohui Xing 1, and  Keqin Feng 2,3,

1. 

School of Information Science and Engineering, Shandong Normal University, Jinan 250014, China
2. 

Department of Mathematical Sciences, Tsinghua University, Beijing, 100084 China
3. 

State Key Lab. of Cryptology, P.O.Box 5159, Beijing 100878 China

Received  April 2018 Revised  November 2018 Published  August 2019

Fund Project: This work was supported by National Science Foundation of China (Grant No. 61672330 and 61602287) and the State Scholarship Fund no.201808370069 from China Scholarship Council.

As maximal, nonlinear Boolean functions, bent functions have many theoretical and practical applications in combinatorics, coding theory, and cryptography. In this paper, we present a construction of bent function $ f_{a,S} $ with $ n = 2m $ variables for any nonzero vector $ a\in \mathbb{F}_{2}^{m} $ and subset $ S $ of $ \mathbb{F}_{2}^{m} $ satisfying $ a+S = S $. We give a simple expression of the dual bent function of $ f_{a,S} $ and prove that $ f_{a,S} $ has optimal algebraic degree $ m $ if and only if $ |S|\equiv 2 (\bmod 4) $. This construction provides a series of bent functions with optimal algebraic degree and large symmetric group if $ a $ and $ S $ are chosen properly. We also give some examples of those bent functions $ f_{a,S} $ and their dual bent functions.

Keywords: Boolean functions, bent functions, dual functions, algebraic degree, symmetric group.
Mathematics Subject Classification: 03G05, 06E25.
Citation: 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
References:
[1]

C. Carlet, On bent and highly nonlinear balanced resilient functions and their algebraic immunities, in Proc. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes 2006, Springer Berlin, 3857 (2006), 1–28. doi: 10.1007/11617983_1.

[2]

C. Carlet, Two new classes of bent functions, in Proc. Advances in Cryptology EUROCRYPT 1993, Springer, Berlin, 765 (1994), 77–101. doi: 10.1007/3-540-48285-7_8.

[3]

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

[4]

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

[5]

N. T. Courtois and W. Meier, Algebraic attacks on stream ciphers with linear feedback, in Proc. Advances in Cryptology - EUROCRYPT 2003, Springer, Berlin, 2656 (2003), 345–359. doi: 10.1007/3-540-39200-9_21.

[6]

D. K. Dalai, S. Maitra and S. Sarkar, Results on rotation symmetric bent functions, Discrete Math., 309 (2009), 2398-2409.  doi: 10.1016/j.disc.2008.05.017.

[7]

J. F. Dillon, Elementary Hadamard Difference Sets, Ph.D thesis, Univ. Maryland, College Park, 1974.

[8]

I. Dinur and A. Shamir, Cube attacks on tweakable black box polynomials, in Proc. Advances in Cryptology-EUROCRYPT 2009, Springer, Berlin, $$ (2009), 278–299. doi: 10.1007/978-3-642-01001-9_16.

[9]

E. Filiol and C. Fontaine, Highly nonlinear balanced Boolean functions with a good correlation immunity, Advances in Cryptology EUROCRYPT 1998, Springer, Berlin, 1403 (1998), 475–488. doi: 10.1007/BFb0054147.

[10]

G. P. Gao, X. Y. Zhang, W. F. 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.

[11]

X. J. Lai, Higher order derivatives and differential cryptanalysis, in Proc. Symp. Commun., Coding Cryptography 2004, Kluwer, 276 (2004), 227–233. doi: 10.1007/978-1-4615-2694-0_23.

[12]

Q. Meng, L. S. Chen and F.-W. Fu, On homogeneous rotation symmetric bent functions, Discrete Applied Mathematics, 158 (2010), 1111-1117.  doi: 10.1016/j.dam.2010.02.009.

[13]

S. Mesnager, Bent Functions: Fundamentals and Results, Springer-Verlag, 2016. doi: 10.1007/978-3-319-32595-8.

[14]

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.

[15]

S. Mesnager and F. R. Zhang, On constructions of bent, semi-bent and five valued spectrum functions from old bent functions, Adv. Math. Commun., 11 (2017), 339-345.  doi: 10.3934/amc.2017026.

[16]

S. Mesnager, F. R. Zhang and Y. Zhou, On construction of bent functions involving symmetric functions and their duals, Adv. Math. Commun., 11 (2017), 347-352.  doi: 10.3934/amc.2017027.

[17]

O. S. Rothaus, On "bent" functions, J. Combin. Theory Ser. A, 20 (1976), 300-305.  doi: 10.1016/0097-3165(76)90024-8.

[18]

P. Stǎnicǎ and S. Maitra, Rotation symmetric Boolean functions - count and cryptographic properties, Discrete Applied Mathematics, 156 (2008), 1567-1580.  doi: 10.1016/j.dam.2007.04.029.

[19]

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

[20]

C. Tang, Y. F. Qi, Z. C. Zhou and C. L. Fan, Two infinite classes of rotation symmetric bent functions with simple representation, arXiv preprint, arXiv: 1508.05674, 2015.

show all references

References:
[1]

C. Carlet, On bent and highly nonlinear balanced resilient functions and their algebraic immunities, in Proc. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes 2006, Springer Berlin, 3857 (2006), 1–28. doi: 10.1007/11617983_1.

[2]

C. Carlet, Two new classes of bent functions, in Proc. Advances in Cryptology EUROCRYPT 1993, Springer, Berlin, 765 (1994), 77–101. doi: 10.1007/3-540-48285-7_8.

[3]

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

[4]

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

[5]

N. T. Courtois and W. Meier, Algebraic attacks on stream ciphers with linear feedback, in Proc. Advances in Cryptology - EUROCRYPT 2003, Springer, Berlin, 2656 (2003), 345–359. doi: 10.1007/3-540-39200-9_21.

[6]

D. K. Dalai, S. Maitra and S. Sarkar, Results on rotation symmetric bent functions, Discrete Math., 309 (2009), 2398-2409.  doi: 10.1016/j.disc.2008.05.017.

[7]

J. F. Dillon, Elementary Hadamard Difference Sets, Ph.D thesis, Univ. Maryland, College Park, 1974.

[8]

I. Dinur and A. Shamir, Cube attacks on tweakable black box polynomials, in Proc. Advances in Cryptology-EUROCRYPT 2009, Springer, Berlin, $$ (2009), 278–299. doi: 10.1007/978-3-642-01001-9_16.

[9]

E. Filiol and C. Fontaine, Highly nonlinear balanced Boolean functions with a good correlation immunity, Advances in Cryptology EUROCRYPT 1998, Springer, Berlin, 1403 (1998), 475–488. doi: 10.1007/BFb0054147.

[10]

G. P. Gao, X. Y. Zhang, W. F. 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.

[11]

X. J. Lai, Higher order derivatives and differential cryptanalysis, in Proc. Symp. Commun., Coding Cryptography 2004, Kluwer, 276 (2004), 227–233. doi: 10.1007/978-1-4615-2694-0_23.

[12]

Q. Meng, L. S. Chen and F.-W. Fu, On homogeneous rotation symmetric bent functions, Discrete Applied Mathematics, 158 (2010), 1111-1117.  doi: 10.1016/j.dam.2010.02.009.

[13]

S. Mesnager, Bent Functions: Fundamentals and Results, Springer-Verlag, 2016. doi: 10.1007/978-3-319-32595-8.

[14]

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.

[15]

S. Mesnager and F. R. Zhang, On constructions of bent, semi-bent and five valued spectrum functions from old bent functions, Adv. Math. Commun., 11 (2017), 339-345.  doi: 10.3934/amc.2017026.

[16]

S. Mesnager, F. R. Zhang and Y. Zhou, On construction of bent functions involving symmetric functions and their duals, Adv. Math. Commun., 11 (2017), 347-352.  doi: 10.3934/amc.2017027.

[17]

O. S. Rothaus, On "bent" functions, J. Combin. Theory Ser. A, 20 (1976), 300-305.  doi: 10.1016/0097-3165(76)90024-8.

[18]

P. Stǎnicǎ and S. Maitra, Rotation symmetric Boolean functions - count and cryptographic properties, Discrete Applied Mathematics, 156 (2008), 1567-1580.  doi: 10.1016/j.dam.2007.04.029.

[19]

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

[20]

C. Tang, Y. F. Qi, Z. C. Zhou and C. L. Fan, Two infinite classes of rotation symmetric bent functions with simple representation, arXiv preprint, arXiv: 1508.05674, 2015.

[1]

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
[2]

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
[3]

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
[4]

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
[5]

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
[6]

Ayça Çeşmelioǧlu, Wilfried Meidl, Alexander Pott. On the dual of (non)-weakly regular bent functions and self-dual bent functions. Advances in Mathematics of Communications, 2013, 7 (4) : 425-440. doi: 10.3934/amc.2013.7.425
[7]

Constanza Riera, Pantelimon Stănică. Landscape Boolean functions. Advances in Mathematics of Communications, 2019, 13 (4) : 613-627. doi: 10.3934/amc.2019038
[8]

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
[9]

SelÇuk Kavut, Seher Tutdere. Highly nonlinear (vectorial) Boolean functions that are symmetric under some permutations. Advances in Mathematics of Communications, 2020, 14 (1) : 127-136. doi: 10.3934/amc.2020010
[10]

Claude Carlet. Parameterization of Boolean functions by vectorial functions and associated constructions. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022013
[11]

Jacques Wolfmann. Special bent and near-bent functions. Advances in Mathematics of Communications, 2014, 8 (1) : 21-33. doi: 10.3934/amc.2014.8.21
[12]

Junchao Zhou, Yunge Xu, Lisha Wang, Nian Li. Nearly optimal codebooks from generalized Boolean bent functions over $ \mathbb{Z}_{4} $. Advances in Mathematics of Communications, 2022, 16 (3) : 485-501. doi: 10.3934/amc.2020121
[13]

Claude Carlet, Fengrong Zhang, Yupu Hu. Secondary constructions of bent functions and their enforcement. Advances in Mathematics of Communications, 2012, 6 (3) : 305-314. doi: 10.3934/amc.2012.6.305
[14]

Claude Carlet, Serge Feukoua. Three basic questions on Boolean functions. Advances in Mathematics of Communications, 2017, 11 (4) : 837-855. doi: 10.3934/amc.2017061
[15]

Claude Carlet, Brahim Merabet. Asymptotic lower bound on the algebraic immunity of random balanced multi-output Boolean functions. Advances in Mathematics of Communications, 2013, 7 (2) : 197-217. doi: 10.3934/amc.2013.7.197
[16]

Heping Liu, Yu Liu. Refinable functions on the Heisenberg group. Communications on Pure and Applied Analysis, 2007, 6 (3) : 775-787. doi: 10.3934/cpaa.2007.6.775
[17]

Sihem Mesnager, Fengrong Zhang. On constructions of bent, semi-bent and five valued spectrum functions from old bent functions. Advances in Mathematics of Communications, 2017, 11 (2) : 339-345. doi: 10.3934/amc.2017026
[18]

Jyrki Lahtonen, Gary McGuire, Harold N. Ward. Gold and Kasami-Welch functions, quadratic forms, and bent functions. Advances in Mathematics of Communications, 2007, 1 (2) : 243-250. doi: 10.3934/amc.2007.1.243
[19]

Kanat Abdukhalikov, Sihem Mesnager. Explicit constructions of bent functions from pseudo-planar functions. Advances in Mathematics of Communications, 2017, 11 (2) : 293-299. doi: 10.3934/amc.2017021
[20]

Bingxin Wang, Sihong Su. A new construction of odd-variable rotation symmetric boolean functions with good cryptographic properties. Advances in Mathematics of Communications, 2022, 16 (2) : 365-382. doi: 10.3934/amc.2020115

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (576)
  • HTML views (388)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy