-
Previous Article
Some generalizations of good integers and their applications in the study of self-dual negacyclic codes
- AMC Home
- This Issue
-
Next Article
New self-dual and formally self-dual codes from group ring constructions
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 |
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.
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
Other articles
by authors
[Back to Top]