# American Institute of Mathematical Sciences

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

 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.

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

2021 Impact Factor: 1.015