-
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
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 |
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 [
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. 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. |
[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. |
[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. 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. |
[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. 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. |
[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. 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. |
[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. 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.
|
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. 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. |
[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. |
[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. 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. |
[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. 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. |
[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. 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. |
[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. 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.
|
[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, 2020 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] |
Yuan Cao, Yonglin Cao, Hai Q. Dinh, Ramakrishna Bandi, Fang-Wei Fu. An explicit representation and enumeration for negacyclic codes of length $ 2^kn $ over $ \mathbb{Z}_4+u\mathbb{Z}_4 $. Advances in Mathematics of Communications, 2021, 15 (2) : 291-309. doi: 10.3934/amc.2020067 |
[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] |
Andreas Koutsogiannis. Multiple ergodic averages for tempered functions. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1177-1205. doi: 10.3934/dcds.2020314 |
[7] |
Guoyuan Chen, Yong Liu, Juncheng Wei. Nondegeneracy of harmonic maps from $ {{\mathbb{R}}^{2}} $ to $ {{\mathbb{S}}^{2}} $. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3215-3233. doi: 10.3934/dcds.2019228 |
[8] |
Mathew Gluck. Classification of solutions to a system of $ n^{\rm th} $ order equations on $ \mathbb R^n $. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5413-5436. doi: 10.3934/cpaa.2020246 |
[9] |
Huu-Quang Nguyen, Ya-Chi Chu, Ruey-Lin Sheu. On the convexity for the range set of two quadratic functions. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2020169 |
[10] |
Xinpeng Wang, Bingo Wing-Kuen Ling, Wei-Chao Kuang, Zhijing Yang. Orthogonal intrinsic mode functions via optimization approach. Journal of Industrial & Management Optimization, 2021, 17 (1) : 51-66. doi: 10.3934/jimo.2019098 |
[11] |
Lars Grüne. Computing Lyapunov functions using deep neural networks. Journal of Computational Dynamics, 2020 doi: 10.3934/jcd.2021006 |
[12] |
Peter Giesl, Sigurdur Hafstein. System specific triangulations for the construction of CPA Lyapunov functions. Discrete & Continuous Dynamical Systems - B, 2020 doi: 10.3934/dcdsb.2020378 |
[13] |
Hai Q. Dinh, Bac T. Nguyen, Paravee Maneejuk. Constacyclic codes of length $ 8p^s $ over $ \mathbb F_{p^m} + u\mathbb F_{p^m} $. Advances in Mathematics of Communications, 2020 doi: 10.3934/amc.2020123 |
[14] |
Denis Bonheure, Silvia Cingolani, Simone Secchi. Concentration phenomena for the Schrödinger-Poisson system in $ \mathbb{R}^2 $. Discrete & Continuous Dynamical Systems - S, 2020 doi: 10.3934/dcdss.2020447 |
[15] |
Michal Fečkan, Kui Liu, JinRong Wang. $ (\omega,\mathbb{T}) $-periodic solutions of impulsive evolution equations. Evolution Equations & Control Theory, 2021 doi: 10.3934/eect.2021006 |
[16] |
Aihua Fan, Jörg Schmeling, Weixiao Shen. $ L^\infty $-estimation of generalized Thue-Morse trigonometric polynomials and ergodic maximization. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 297-327. doi: 10.3934/dcds.2020363 |
[17] |
Lihong Zhang, Wenwen Hou, Bashir Ahmad, Guotao Wang. Radial symmetry for logarithmic Choquard equation involving a generalized tempered fractional $ p $-Laplacian. Discrete & Continuous Dynamical Systems - S, 2020 doi: 10.3934/dcdss.2020445 |
[18] |
Lei Liu, Li Wu. Multiplicity of closed characteristics on $ P $-symmetric compact convex hypersurfaces in $ \mathbb{R}^{2n} $. Discrete & Continuous Dynamical Systems - A, 2020 doi: 10.3934/dcds.2020378 |
[19] |
Wenqiang Zhao, Yijin Zhang. High-order Wong-Zakai approximations for non-autonomous stochastic $ p $-Laplacian equations on $ \mathbb{R}^N $. Communications on Pure & Applied Analysis, 2021, 20 (1) : 243-280. doi: 10.3934/cpaa.2020265 |
[20] |
Yu Zhou, Xinfeng Dong, Yongzhuang Wei, Fengrong Zhang. A note on the Signal-to-noise ratio of $ (n, m) $-functions. Advances in Mathematics of Communications, 2020 doi: 10.3934/amc.2020117 |
2019 Impact Factor: 0.734
Tools
Article outline
[Back to Top]