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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[7]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[13]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[17]

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

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[7]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[13]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[17]

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

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Jian Liu, Sihem Mesnager, Lusheng Chen. Variation on correlation immune Boolean and vectorial functions. Advances in Mathematics of Communications, 2016, 10 (4) : 895-919. doi: 10.3934/amc.2016048
[16]

Samir Hodžić, Enes Pasalic. Generalized bent functions -sufficient conditions and related constructions. Advances in Mathematics of Communications, 2017, 11 (3) : 549-566. doi: 10.3934/amc.2017043
[17]

Claude Carlet, Juan Carlos Ku-Cauich, Horacio Tapia-Recillas. Bent functions on a Galois ring and systematic authentication codes. Advances in Mathematics of Communications, 2012, 6 (2) : 249-258. doi: 10.3934/amc.2012.6.249
[18]

Ayça Çeşmelioğlu, Wilfried Meidl. Bent and vectorial bent functions, partial difference sets, and strongly regular graphs. Advances in Mathematics of Communications, 2018, 12 (4) : 691-705. doi: 10.3934/amc.2018041
[19]

Joan-Josep Climent, Francisco J. García, Verónica Requena. On the construction of bent functions of $n+2$ variables from bent functions of $n$ variables. Advances in Mathematics of Communications, 2008, 2 (4) : 421-431. doi: 10.3934/amc.2008.2.421
[20]

Domingo Gómez-Pérez, László Mérai. Algebraic dependence in generating functions and expansion complexity. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020022

2018 Impact Factor: 0.879

Tools

Metrics

  • PDF downloads (99)
  • HTML views (201)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences