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]

Huu-Quang Nguyen, Ya-Chi Chu, Ruey-Lin Sheu. On the convexity for the range set of two quadratic functions. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020169
[2]

Xinpeng Wang, Bingo Wing-Kuen Ling, Wei-Chao Kuang, Zhijing Yang. Orthogonal intrinsic mode functions via optimization approach. Journal of Industrial & Management Optimization, 2021, 17 (1) : 51-66. doi: 10.3934/jimo.2019098
[3]

Yu Zhou, Xinfeng Dong, Yongzhuang Wei, Fengrong Zhang. A note on the Signal-to-noise ratio of $ (n, m) $-functions. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020117
[4]

Djamel Aaid, Amel Noui, Özen Özer. Piecewise quadratic bounding functions for finding real roots of polynomials. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 63-73. doi: 10.3934/naco.2020015
[5]

Tahir Aliyev Azeroğlu, Bülent Nafi Örnek, Timur Düzenli. Some results on the behaviour of transfer functions at the right half plane. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020106
[6]

Ville Salo, Ilkka Törmä. Recoding Lie algebraic subshifts. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 1005-1021. doi: 10.3934/dcds.2020307
[7]

Laurent Di Menza, Virginie Joanne-Fabre. An age group model for the study of a population of trees. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020464
[8]

Qiao Liu. Local rigidity of certain solvable group actions on tori. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 553-567. doi: 10.3934/dcds.2020269
[9]

Kien Trung Nguyen, Vo Nguyen Minh Hieu, Van Huy Pham. Inverse group 1-median problem on trees. Journal of Industrial & Management Optimization, 2021, 17 (1) : 221-232. doi: 10.3934/jimo.2019108
[10]

Zonghong Cao, Jie Min. Selection and impact of decision mode of encroachment and retail service in a dual-channel supply chain. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020167
[11]

Teresa D'Aprile. Bubbling solutions for the Liouville equation around a quantized singularity in symmetric domains. Communications on Pure & Applied Analysis, 2021, 20 (1) : 159-191. doi: 10.3934/cpaa.2020262
[12]

Gang Luo, Qingzhi Yang. The point-wise convergence of shifted symmetric higher order power method. Journal of Industrial & Management Optimization, 2021, 17 (1) : 357-368. doi: 10.3934/jimo.2019115
[13]

Lei Liu, Li Wu. Multiplicity of closed characteristics on $ P $-symmetric compact convex hypersurfaces in $ \mathbb{R}^{2n} $. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020378

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (229)
  • HTML views (376)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences