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

Wenying Zhang; Zhaohui Xing; Keqin Feng

doi:10.3934/amc.2020003

Article Contents

2020, Volume 14, Issue 1: 23-33. Doi: 10.3934/amc.2020003

This issue Previous Article New self-dual and formally self-dual codes from group ring constructions Next Article Some generalizations of good integers and their applications in the study of self-dual negacyclic codes

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

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

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.

Abstract / Introduction Full Text(HTML) Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: 03G05, 06E25.

Citation:

Full Text(HTML)

Related Papers

Cited by

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.