Gowers <inline-formula><tex-math id="M1">\begin{document}$ U_2 $\end{document}</tex-math></inline-formula> norm as a measure of nonlinearity for Boolean functions and their generalizations

Sugata Gangopadhyay; Constanza Riera; Pantelimon Stănică

doi:10.3934/amc.2020056

Previous Article
Verifying solutions to LWE with implications for concrete security
AMC Home
This Issue
Next Article
Construction of minimal linear codes from multi-variable functions

May 2021, 15(2): 241-256. doi: 10.3934/amc.2020056

Gowers $ U_2 $ norm as a measure of nonlinearity for Boolean functions and their generalizations

Sugata Gangopadhyay ^1, , Constanza Riera ^2, and Pantelimon Stănică ^3,,

1.	Department of Computer Science and Engineering, Indian Institute of Technology Roorkee, Roorkee 247667, India
2.	Department of Computer Science, Electrical Engineering and Mathematical Sciences, Western Norway University of Applied Sciences, 5020 Bergen, Norway
3.	Department of Applied Mathematics, Naval Postgraduate School, Monterey, CA 93943, USA

^* Corresponding author: Pantelimon Stăniă

Received July 2019 Revised October 2019 Published May 2021 Early access January 2020

In this paper, we investigate the Gowers $ U_2 $ norm for generalized Boolean functions, and $ \mathbb{Z} $-bent functions. The Gowers $ U_2 $ norm of a function is a measure of its resistance to affine approximation. Although nonlinearity serves the same purpose for the classical Boolean functions, it does not extend easily to generalized Boolean functions. We first provide a framework for employing the Gowers $ U_2 $ norm in the context of generalized Boolean functions with cryptographic significance, in particular, we give a recurrence rule for the Gowers $ U_2 $ norms, and an evaluation of the Gowers $ U_2 $ norm of functions that are affine over spreads. We also give an introduction to $ \mathbb{Z} $-bent functions, as proposed by Dobbertin and Leander [8], to provide a recursive framework to study bent functions. In the second part of the paper, we concentrate on $ \mathbb{Z} $-bent functions and their $ U_2 $ norms. As a consequence of one of our results, we give an alternate proof to a known theorem of Dobbertin and Leander, and also find necessary and sufficient conditions for a function obtained by gluing $ \mathbb{Z} $-bent functions to be bent, in terms of the Gowers $ U_2 $ norms of its components.

Keywords: Gowers norms, Boolean functions, generalized Boolean functions, bent functions, $ \mathbb{Z} $-bent functions.

Mathematics Subject Classification: Primary: 94C10; Secondary: 06E30.

Citation: Sugata Gangopadhyay, Constanza Riera, Pantelimon Stănică. Gowers $ U_2 $ norm as a measure of nonlinearity for Boolean functions and their generalizations. Advances in Mathematics of Communications, 2021, 15 (2) : 241-256. doi: 10.3934/amc.2020056

References:

[1]	L. Budaghyan, Construction and Analysis of Cryptographic Functions, Springer, Cham, 2014. doi: 10.1007/978-3-319-12991-4.
[2]	C. Carlet, Boolean functions for cryptography and error correcting codes, Boolean Methods and Models, Cambridge Univ. Press, Cambridge, (2010), 257–397.
[3]	C. Carlet and S. Mesnager, Four decades of research on bent functions, Des. Codes Cryptogr., 78 (2016), 5-50. doi: 10.1007/s10623-015-0145-8.
[4]	F. Caullery and F. Rodier, Distribution of the absolute indicator of random Boolean functions, hal-01679358f, (2018), available at: https://hal.archives-ouvertes.fr/hal-01679358/document.
[5]	V. Y.-W. Chen, The Gowers Norm in the Testing of Boolean Functions, Ph.D. Thesis, Massachusetts Institute of Technology, June 2009.
[6]	T. W. Cusick and P. Stănică, Cryptographic Boolean Functions and Applications, Elsevier/Academic Press, Amsterdam, 2009.
[7]	J. F. Dillon, Elementary Hadamard difference sets, Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory, and Computing, Congressus Numerantium, Utilitas Math., Winnipeg, Man., 14 (1975), 237-249.
[8]	H. Dobbertin and G. Leander, Bent functions embedded into the recursive framework of $\mathbb{Z}$-bent functions, Des. Codes Cryptogr., 49 (2008), 3-22. doi: 10.1007/s10623-008-9189-3.
[9]	S. Gangopadhyay, B. Mandal and P. Stănică, Gowers $U_3$ norm of some classes of bent Boolean functions, Des. Codes Cryptogr., 86 (2018), 1131-1148. doi: 10.1007/s10623-017-0383-z.
[10]	S. Gangopadhyay, E. Pasalic, P. Stănică and S. Datta, A note on non-splitting $\mathbb{Z}$-functions, Inf. Proc. Letters, 121 (2017), 1-5. doi: 10.1016/j.ipl.2017.01.001.
[11]	S. Hodžić, W. Meidl and E. Pasalic, Full characterization of generalized bent functions as (semi)-bent spaces, their dual and the Gray image, IEEE Trans. Inf. Theory, 64 (2018), 5432-5440. doi: 10.1109/TIT.2018.2837883.
[12]	S. Hodžić and E. Pasalic, Generalized bent functions—Some general construction methods and related necessary and sufficient conditions, Cryptogr. Commun., 7 (2015), 469-483. doi: 10.1007/s12095-015-0126-9.
[13]	N. Kolomeec and A. Pavlov, Bent Functions on the Minimal Distance, IEEE Region 8 SIBIRCON-2010, Irkutsk Listvyanka, Russia, 2010.
[14]	P. V. Kumar, R. A. Scholtz and L. R. Welch, Generalized bent functions and their properties, J. Combin Theory Ser. A, 40 (1985), 90-107. doi: 10.1016/0097-3165(85)90049-4.
[15]	T. Martinsen, W. Meidl, S. Mesnager and P. Stănică, Decomposing generalized bent and hyperbent functions, IEEE Trans. Inf. Theory, 63 (2017), 7804-7812. doi: 10.1109/TIT.2017.2754498.
[16]	T. Martinsen, W. Meidl, A. Pott and P. Stănică, On symmetry and differential properties of generalized Boolean functions, Arithmetic of Finite Fields, Lecture Notes in Comput. Sci., Springer, Cham, 11321 (2018), 207-223.
[17]	T. Martinsen, W. Meidl and P. Stănică, Generalized bent functions and their Gray images, Arithmetic of Finite Fields, Lecture Notes in Comput. Sci., Springer, Cham, 10064 (2017), 160-173.
[18]	T. Martinsen, W. Meidl and P. Stănică, Partial spread and vectorial generalized bent functions, Des. Codes Cryptogr., 85 (2017), 1-13. doi: 10.1007/s10623-016-0283-7.
[19]	S. Mesnager, Bent Functions. Fundamentals and Results, Springer-Verlag, 2016. doi: 10.1007/978-3-319-32595-8.
[20]	S. Mesnager, C. M. Tang, Y. F. Qi, L. B. Wang, B. F. Wu and K. Q. Feng, Further results on generalized bent functions and their complete characterization, IEEE Trans. Inform. Theory, 64 (2018), 5441-5452. doi: 10.1109/TIT.2018.2835518.
[21]	B. Preneel, R. Govaerts and J. Vandewalle, Cryptographic properties of quadratic Boolean functions, Int. Symp. Finite Fields and Appl., (1991), 9pp.
[22]	O. S. Rothaus, On "bent" functions, J. Combin. Theory Ser. A, 20 (1976), 300-305. doi: 10.1016/0097-3165(76)90024-8.
[23]	K. U. Schmidt, Quaternary constant-amplitude codes for multicode CDMA, IEEE Trans. Inf. Theory, 55 (2009), 1824-1832. doi: 10.1109/TIT.2009.2013041.
[24]	P. Solé and N. Tokareva, Connections between quaternary and binary bent functions, Prikl. Diskr. Mat., 1 (2009), 16–18, http://eprint.iacr.org/2009/544.pdf.
[25]	P. Stănică, Weak and strong $2^k$-bent functions, IEEE Trans. Inf. Theory, 62 (2016), 2827-2835.
[26]	P. Stănică, T. Martinsen, S. Gangopadhyay and B. K. Singh, Bent and generalized bent Boolean functions, Des. Codes Cryptogr., 69 (2013), 77-94. doi: 10.1007/s10623-012-9622-5.
[27]	C. M. Tang, C. Xiang, Y. F. Qi and K. Q. Feng, Complete characterization of generalized bent and $2^k$-bent Boolean functions, IEEE Trans. Inf. Theory, 63 (2017), 4668-4674. doi: 10.1109/TIT.2017.2686987.
[28]	N. Tokareva, Bent Functions. Results and Applications to Cryptography, Elsevier/Academic Press, Amsterdam, 2015.
[29]	F. Zhang, S. Xia, P. Stănică and Y. Zhou, Further results on constructions of generalized bent Boolean functions, Inf. Sciences-China, 59 (2016), 1-3.
[30]	X.-M. Zhang and Y. L. Zheng, GAC—the criterion for global avalanche characteristics of cryptographic functions, J. UCS, 1 (1995), 320-337.

show all references

References:

[1]	L. Budaghyan, Construction and Analysis of Cryptographic Functions, Springer, Cham, 2014. doi: 10.1007/978-3-319-12991-4.
[2]	C. Carlet, Boolean functions for cryptography and error correcting codes, Boolean Methods and Models, Cambridge Univ. Press, Cambridge, (2010), 257–397.
[3]	C. Carlet and S. Mesnager, Four decades of research on bent functions, Des. Codes Cryptogr., 78 (2016), 5-50. doi: 10.1007/s10623-015-0145-8.
[4]	F. Caullery and F. Rodier, Distribution of the absolute indicator of random Boolean functions, hal-01679358f, (2018), available at: https://hal.archives-ouvertes.fr/hal-01679358/document.
[5]	V. Y.-W. Chen, The Gowers Norm in the Testing of Boolean Functions, Ph.D. Thesis, Massachusetts Institute of Technology, June 2009.
[6]	T. W. Cusick and P. Stănică, Cryptographic Boolean Functions and Applications, Elsevier/Academic Press, Amsterdam, 2009.
[7]	J. F. Dillon, Elementary Hadamard difference sets, Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory, and Computing, Congressus Numerantium, Utilitas Math., Winnipeg, Man., 14 (1975), 237-249.
[8]	H. Dobbertin and G. Leander, Bent functions embedded into the recursive framework of $\mathbb{Z}$-bent functions, Des. Codes Cryptogr., 49 (2008), 3-22. doi: 10.1007/s10623-008-9189-3.
[9]	S. Gangopadhyay, B. Mandal and P. Stănică, Gowers $U_3$ norm of some classes of bent Boolean functions, Des. Codes Cryptogr., 86 (2018), 1131-1148. doi: 10.1007/s10623-017-0383-z.
[10]	S. Gangopadhyay, E. Pasalic, P. Stănică and S. Datta, A note on non-splitting $\mathbb{Z}$-functions, Inf. Proc. Letters, 121 (2017), 1-5. doi: 10.1016/j.ipl.2017.01.001.
[11]	S. Hodžić, W. Meidl and E. Pasalic, Full characterization of generalized bent functions as (semi)-bent spaces, their dual and the Gray image, IEEE Trans. Inf. Theory, 64 (2018), 5432-5440. doi: 10.1109/TIT.2018.2837883.
[12]	S. Hodžić and E. Pasalic, Generalized bent functions—Some general construction methods and related necessary and sufficient conditions, Cryptogr. Commun., 7 (2015), 469-483. doi: 10.1007/s12095-015-0126-9.
[13]	N. Kolomeec and A. Pavlov, Bent Functions on the Minimal Distance, IEEE Region 8 SIBIRCON-2010, Irkutsk Listvyanka, Russia, 2010.
[14]	P. V. Kumar, R. A. Scholtz and L. R. Welch, Generalized bent functions and their properties, J. Combin Theory Ser. A, 40 (1985), 90-107. doi: 10.1016/0097-3165(85)90049-4.
[15]	T. Martinsen, W. Meidl, S. Mesnager and P. Stănică, Decomposing generalized bent and hyperbent functions, IEEE Trans. Inf. Theory, 63 (2017), 7804-7812. doi: 10.1109/TIT.2017.2754498.
[16]	T. Martinsen, W. Meidl, A. Pott and P. Stănică, On symmetry and differential properties of generalized Boolean functions, Arithmetic of Finite Fields, Lecture Notes in Comput. Sci., Springer, Cham, 11321 (2018), 207-223.
[17]	T. Martinsen, W. Meidl and P. Stănică, Generalized bent functions and their Gray images, Arithmetic of Finite Fields, Lecture Notes in Comput. Sci., Springer, Cham, 10064 (2017), 160-173.
[18]	T. Martinsen, W. Meidl and P. Stănică, Partial spread and vectorial generalized bent functions, Des. Codes Cryptogr., 85 (2017), 1-13. doi: 10.1007/s10623-016-0283-7.
[19]	S. Mesnager, Bent Functions. Fundamentals and Results, Springer-Verlag, 2016. doi: 10.1007/978-3-319-32595-8.
[20]	S. Mesnager, C. M. Tang, Y. F. Qi, L. B. Wang, B. F. Wu and K. Q. Feng, Further results on generalized bent functions and their complete characterization, IEEE Trans. Inform. Theory, 64 (2018), 5441-5452. doi: 10.1109/TIT.2018.2835518.
[21]	B. Preneel, R. Govaerts and J. Vandewalle, Cryptographic properties of quadratic Boolean functions, Int. Symp. Finite Fields and Appl., (1991), 9pp.
[22]	O. S. Rothaus, On "bent" functions, J. Combin. Theory Ser. A, 20 (1976), 300-305. doi: 10.1016/0097-3165(76)90024-8.
[23]	K. U. Schmidt, Quaternary constant-amplitude codes for multicode CDMA, IEEE Trans. Inf. Theory, 55 (2009), 1824-1832. doi: 10.1109/TIT.2009.2013041.
[24]	P. Solé and N. Tokareva, Connections between quaternary and binary bent functions, Prikl. Diskr. Mat., 1 (2009), 16–18, http://eprint.iacr.org/2009/544.pdf.
[25]	P. Stănică, Weak and strong $2^k$-bent functions, IEEE Trans. Inf. Theory, 62 (2016), 2827-2835.
[26]	P. Stănică, T. Martinsen, S. Gangopadhyay and B. K. Singh, Bent and generalized bent Boolean functions, Des. Codes Cryptogr., 69 (2013), 77-94. doi: 10.1007/s10623-012-9622-5.
[27]	C. M. Tang, C. Xiang, Y. F. Qi and K. Q. Feng, Complete characterization of generalized bent and $2^k$-bent Boolean functions, IEEE Trans. Inf. Theory, 63 (2017), 4668-4674. doi: 10.1109/TIT.2017.2686987.
[28]	N. Tokareva, Bent Functions. Results and Applications to Cryptography, Elsevier/Academic Press, Amsterdam, 2015.
[29]	F. Zhang, S. Xia, P. Stănică and Y. Zhou, Further results on constructions of generalized bent Boolean functions, Inf. Sciences-China, 59 (2016), 1-3.
[30]	X.-M. Zhang and Y. L. Zheng, GAC—the criterion for global avalanche characteristics of cryptographic functions, J. UCS, 1 (1995), 320-337.

[1]	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
[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]	Chunming Tang, Maozhi Xu, Yanfeng Qi, Mingshuo Zhou. A new class of $ p $-ary regular bent functions. Advances in Mathematics of Communications, 2021, 15 (1) : 55-64. doi: 10.3934/amc.2020042
[4]	Constanza Riera, Pantelimon Stănică. Landscape Boolean functions. Advances in Mathematics of Communications, 2019, 13 (4) : 613-627. doi: 10.3934/amc.2019038
[5]	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
[6]	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
[7]	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
[8]	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
[9]	Claude Carlet. Parameterization of Boolean functions by vectorial functions and associated constructions. Advances in Mathematics of Communications, 2022 doi: 10.3934/amc.2022013
[10]	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
[11]	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
[12]	Yongkuan Cheng, Yaotian Shen. Generalized quasilinear Schrödinger equations with concave functions $ l(s^2) $. Discrete and Continuous Dynamical Systems, 2019, 39 (3) : 1311-1343. doi: 10.3934/dcds.2019056
[13]	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
[14]	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
[15]	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
[16]	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
[17]	Kanat Abdukhalikov, Duy Ho. Vandermonde sets, hyperovals and Niho bent functions. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021048
[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]	Jiao Du, Longjiang Qu, Chao Li, Xin Liao. Constructing 1-resilient rotation symmetric functions over $ {\mathbb F}_{p} $ with $ {q} $ variables through special orthogonal arrays. Advances in Mathematics of Communications, 2020, 14 (2) : 247-263. doi: 10.3934/amc.2020018

American Institute of Mathematical Sciences

Gowers $ U_2 $ norm as a measure of nonlinearity for Boolean functions and their generalizations

References:

References:

Tools

Metrics

Other articles
by authors

Tools

Tools

Metrics

Other articles
by authors

American Institute of Mathematical Sciences

Gowers $ U_2 $ norm as a measure of nonlinearity for Boolean functions and their generalizations

References:

References:

Tools

Metrics

Other articlesby authors

Tools

Tools

Metrics

Other articlesby authors

Other articles
by authors

Other articles
by authors