American Institute of Mathematical Sciences

Advanced
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  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.  Google Scholar

[2]

C. Carlet, Boolean functions for cryptography and error correcting codes, Boolean Methods and Models, Cambridge Univ. Press, Cambridge, (2010), 257–397. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[5]

V. Y.-W. Chen, The Gowers Norm in the Testing of Boolean Functions, Ph.D. Thesis, Massachusetts Institute of Technology, June 2009.  Google Scholar

[6] T. W. Cusick and P. Stănică, Cryptographic Boolean Functions and Applications, Elsevier/Academic Press, Amsterdam, 2009.   Google Scholar
[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[13]

N. Kolomeec and A. Pavlov, Bent Functions on the Minimal Distance, IEEE Region 8 SIBIRCON-2010, Irkutsk Listvyanka, Russia, 2010. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[19]

S. Mesnager, Bent Functions. Fundamentals and Results, Springer-Verlag, 2016. doi: 10.1007/978-3-319-32595-8.  Google Scholar

[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.  Google Scholar

[21]

B. Preneel, R. Govaerts and J. Vandewalle, Cryptographic properties of quadratic Boolean functions, Int. Symp. Finite Fields and Appl., (1991), 9pp. Google Scholar

[22]

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

[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.  Google Scholar

[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. Google Scholar

[25]

P. Stănică, Weak and strong $2^k$-bent functions, IEEE Trans. Inf. Theory, 62 (2016), 2827-2835.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[28] N. Tokareva, Bent Functions. Results and Applications to Cryptography, Elsevier/Academic Press, Amsterdam, 2015.   Google Scholar
[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.   Google Scholar

[30]

X.-M. Zhang and Y. L. Zheng, GAC—the criterion for global avalanche characteristics of cryptographic functions, J. UCS, 1 (1995), 320-337.   Google Scholar

show all references

References:
[1]

L. Budaghyan, Construction and Analysis of Cryptographic Functions, Springer, Cham, 2014. doi: 10.1007/978-3-319-12991-4.  Google Scholar

[2]

C. Carlet, Boolean functions for cryptography and error correcting codes, Boolean Methods and Models, Cambridge Univ. Press, Cambridge, (2010), 257–397. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[5]

V. Y.-W. Chen, The Gowers Norm in the Testing of Boolean Functions, Ph.D. Thesis, Massachusetts Institute of Technology, June 2009.  Google Scholar

[6] T. W. Cusick and P. Stănică, Cryptographic Boolean Functions and Applications, Elsevier/Academic Press, Amsterdam, 2009.   Google Scholar
[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[13]

N. Kolomeec and A. Pavlov, Bent Functions on the Minimal Distance, IEEE Region 8 SIBIRCON-2010, Irkutsk Listvyanka, Russia, 2010. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[19]

S. Mesnager, Bent Functions. Fundamentals and Results, Springer-Verlag, 2016. doi: 10.1007/978-3-319-32595-8.  Google Scholar

[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.  Google Scholar

[21]

B. Preneel, R. Govaerts and J. Vandewalle, Cryptographic properties of quadratic Boolean functions, Int. Symp. Finite Fields and Appl., (1991), 9pp. Google Scholar

[22]

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

[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.  Google Scholar

[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. Google Scholar

[25]

P. Stănică, Weak and strong $2^k$-bent functions, IEEE Trans. Inf. Theory, 62 (2016), 2827-2835.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[28] N. Tokareva, Bent Functions. Results and Applications to Cryptography, Elsevier/Academic Press, Amsterdam, 2015.   Google Scholar
[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.   Google Scholar

[30]

X.-M. Zhang and Y. L. Zheng, GAC—the criterion for global avalanche characteristics of cryptographic functions, J. UCS, 1 (1995), 320-337.   Google Scholar

[1]

Qian Liu. The lower bounds on the second-order nonlinearity of three classes of Boolean functions. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020136
[2]

Ruonan Liu, Run Xu. Hermite-Hadamard type inequalities for harmonical $ (h1,h2)- $convex interval-valued functions. Mathematical Foundations of Computing, 2021  doi: 10.3934/mfc.2021005
[3]

Raj Kumar, Maheshanand Bhaintwal. Duadic codes over $ \mathbb{Z}_4+u\mathbb{Z}_4 $. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020135
[4]

Muhammad Aslam Noor, Khalida Inayat Noor. Properties of higher order preinvex functions. Numerical Algebra, Control & Optimization, 2021, 11 (3) : 431-441. doi: 10.3934/naco.2020035
[5]

Chaoqian Li, Yajun Liu, Yaotang Li. Note on $ Z $-eigenvalue inclusion theorems for tensors. Journal of Industrial & Management Optimization, 2021, 17 (2) : 687-693. doi: 10.3934/jimo.2019129
[6]

Caili Sang, Zhen Chen. Optimal $ Z $-eigenvalue inclusion intervals of tensors and their applications. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021075
[7]

Denis Bonheure, Silvia Cingolani, Simone Secchi. Concentration phenomena for the Schrödinger-Poisson system in $ \mathbb{R}^2 $. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1631-1648. doi: 10.3934/dcdss.2020447
[8]

Lei Liu, Li Wu. Multiplicity of closed characteristics on $ P $-symmetric compact convex hypersurfaces in $ \mathbb{R}^{2n} $. Discrete & Continuous Dynamical Systems, 2021, 41 (6) : 2635-3652. doi: 10.3934/dcds.2020378
[9]

Wei Liu, Pavel Krejčí, Guoju Ye. Continuity properties of Prandtl-Ishlinskii operators in the space of regulated functions. Discrete & Continuous Dynamical Systems - B, 2017, 22 (10) : 3783-3795. doi: 10.3934/dcdsb.2017190
[10]

Jianfeng Lv, Yan Gao, Na Zhao. The viability of switched nonlinear systems with piecewise smooth Lyapunov functions. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1825-1843. doi: 10.3934/jimo.2020048
[11]

Lei Lei, Wenli Ren, Cuiling Fan. The differential spectrum of a class of power functions over finite fields. Advances in Mathematics of Communications, 2021, 15 (3) : 525-537. doi: 10.3934/amc.2020080
[12]

Shixiong Wang, Longjiang Qu, Chao Li, Shaojing Fu, Hao Chen. Finding small solutions of the equation $ \mathit{{Bx-Ay = z}} $ and its applications to cryptanalysis of the RSA cryptosystem. Advances in Mathematics of Communications, 2021, 15 (3) : 441-469. doi: 10.3934/amc.2020076
[13]

Davide La Torre, Simone Marsiglio, Franklin Mendivil, Fabio Privileggi. Public debt dynamics under ambiguity by means of iterated function systems on density functions. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021070
[14]

Dariusz Idczak. A Gronwall lemma for functions of two variables and its application to partial differential equations of fractional order. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021019
[15]

Mengjie Zhang. Extremal functions for a class of trace Trudinger-Moser inequalities on a compact Riemann surface with smooth boundary. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021038
[16]

Isabeau Birindelli, Françoise Demengel, Fabiana Leoni. Boundary asymptotics of the ergodic functions associated with fully nonlinear operators through a Liouville type theorem. Discrete & Continuous Dynamical Systems, 2021, 41 (7) : 3021-3029. doi: 10.3934/dcds.2020395
[17]

Jong Yoon Hyun, Yoonjin Lee, Yansheng Wu. Connection of $ p $-ary $ t $-weight linear codes to Ramanujan Cayley graphs with $ t+1 $ eigenvalues. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020133
[18]

Jennifer D. Key, Bernardo G. Rodrigues. Binary codes from $ m $-ary $ n $-cubes $ Q^m_n $. Advances in Mathematics of Communications, 2021, 15 (3) : 507-524. doi: 10.3934/amc.2020079
[19]

Dean Crnković, Nina Mostarac, Bernardo G. Rodrigues, Leo Storme. $ s $-PD-sets for codes from projective planes $ \mathrm{PG}(2,2^h) $, $ 5 \leq h\leq 9 $. Advances in Mathematics of Communications, 2021, 15 (3) : 423-440. doi: 10.3934/amc.2020075
[20]

Shihu Li, Wei Liu, Yingchao Xie. Large deviations for stochastic 3D Leray-$ \alpha $ model with fractional dissipation. Communications on Pure & Applied Analysis, 2019, 18 (5) : 2491-2509. doi: 10.3934/cpaa.2019113

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (146)
  • HTML views (573)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences