# American Institute of Mathematical Sciences

November  2020, 14(4): 651-676. doi: 10.3934/amc.2020036

## Three parameters of Boolean functions related to their constancy on affine spaces

 1 LAGA, Department of Mathematics, University of Paris 8 (and Paris 13 and CNRS), Saint–Denis cedex 02, France and University of Bergen, Norway 2 University of Yaoundé 1, Faculty of Sciences, Department of Mathematics, P.O.BOX 812 Yaoundé, Cameroon

* The work of this author was partially supported by PRMAIS

Received  November 2018 Revised  July 2019 Published  November 2020 Early access  November 2019

The $k$-normality of Boolean functions is an important notion initially introduced by Dobbertin and studied in several papers. The parameter related to this notion is the maximal dimension of those affine spaces contained in the support $supp(f)$ of the function or in its co-support $cosupp(f)$. We denote it by $norm\,(f)$ and call it the norm of $f$.

The norm concerns only the affine spaces contained in either the support or the co-support; the information it provides on $f$ is then somewhat incomplete (for instance, two functions constant on a hyperplane will have the same very large parameter value, while they can have very different complexities). A second parameter which completes the information given by the first one is the minimum between the maximal dimension of those affine spaces contained in $supp(f)$ and the maximal dimension of those contained in $cosupp(f)$ (while $norm\,(f)$ equals the maximum between these two maximal dimensions). We denote it by $cons\,(f)$ and call it the (affine) constancy of $f$.

The value of $cons\,(f)$ gives global information on $f$, but no information on what happens around each point of $supp(f)$ or $cosupp(f)$. We define then its local version, equal to the minimum, when $a$ ranges over $\Bbb{F}_2^n$, of the maximal dimension of those affine spaces which contain $a$ and on which $f$ is constant. We denote it by $stab\,(f)$ and call it the stability of $f$.

We study the properties of these three parameters. We have $norm\,(f)\geq cons\,(f)\geq stab\,(f)$, then for determining to which extent these three parameters are distinct, we exhibit four infinite classes of Boolean functions, which show that all cases can occur, where each of these two inequalities can be strict or large.

We consider the minimal value of $stab\, (f)$ (resp. $cons\,(f)$, $norm\,(f)$), when $f$ ranges over the Reed-Muller code $RM(r,n)$ of length $2^n$ and order $r$, and we denote it by $stab\, _{RM(r,n)}$ (resp. $cons\, _{RM(r,n)}$, $norm\, _{RM(r,n)}$). We give upper bounds for each of these three integer sequences, and determine the exact values of $stab\, _{RM(r,n)}$ and $cons\, _{RM(r,n)}$ for $r\in\{1,2,n-2,n-1,n\}$, and of $norm\, _{RM(r,n)}$ for $r = 1,2$.

Citation: Claude Carlet, Serge Feukoua. Three parameters of Boolean functions related to their constancy on affine spaces. Advances in Mathematics of Communications, 2020, 14 (4) : 651-676. doi: 10.3934/amc.2020036
##### References:
 [1] E. F. Assmus Jr., On the Reed-Muller codes, Discrete Math., 106-107 (1992), 25-33.  doi: 10.1016/0012-365X(92)90526-L.  Google Scholar [2] J. Boyar and M. G. Find, Constructive relationships between algebraic thickness and normality, in Fundamentals of Computation Theory, Lecture Notes in Comput. Sci., 9210, Springer, Cham, 2015,106–117. doi: 10.1007/978-3-319-22177-9_9.  Google Scholar [3] A. Canteaut, C. Carlet, P. Charpin and C. Fontaine, On cryptographic properties of the cosets of $R(1, m)$, IEEE Trans. Inform. Theory, 47 (2001), 1494-1513.  doi: 10.1109/18.923730.  Google Scholar [4] A. Canteaut, M. Daum, H. Dobbertin and G. Leander, Normal and non-normal bent functions, Proceedings of the Workshop on Coding and Cryptography, 2003, 91–100. Google Scholar [5] C. Carlet, Two new classes of bent functions, in Advances in Cryptology, Lecture Notes in Comput. Sci., 765, Springer, Berlin, 1994, 77–101. doi: 10.1007/3-540-48285-7_8.  Google Scholar [6] C. Carlet, On cryptographic complexity of Boolean functions, Finite Fields with Applications to Coding Theory, Cryptography and Related Areas, Springer, Berlin, 2002, 53–69. doi: 10.1007/978-3-642-59435-9_4.  Google Scholar [7] C. Carlet, Recursive lower bounds on the nonlinearity profile of Boolean functions and their applications, IEEE Trans. Inform. Theory, 54 (2008), 1262-1272.  doi: 10.1109/TIT.2007.915704.  Google Scholar [8] C. Carlet, Boolean functions for cryptography and error-correcting codes, in Monography Boolean Models and Methods in Mathematics, Computer Science, and Engineering, Cambridge University Press, 2010, 257-397. Preliminary version available at: http://www.math.univ-paris13.fr/~carlet/chap-fcts-Bool-corr.pdf. doi: 10.1017/CBO9780511780448.011.  Google Scholar [9] C. Carlet, Boolean and vectorial plateaued functions, and APN functions, IEEE Trans. Inform. Theory, 61 (2015), 6272-6289.  doi: 10.1109/TIT.2015.2481384.  Google Scholar [10] C. Carlet and S. Feukoua, Three basic questions on Booleans functions, Adv. Math. Commun., 11 (2017), 837-855.  doi: 10.3934/amc.2017061.  Google Scholar [11] 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 [12] P. Charpin, Normal Boolean functions, J. Complexity, 20 (2004), 245-265.  doi: 10.1016/j.jco.2003.08.010.  Google Scholar [13] G. Cohen and A. Tal, Two structural results for low degree polynomials and applications, in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Leibniz Int. Proc. Inform., 40, Schloss Dagstuhl, Leibniz-Zent. Inform., Wadern, 2015,680–709.  Google Scholar [14] J. F. Dillon, Elementary Hadamard Difference Sets, Ph.D thesis, University of Maryland in College Park, 1974.  Google Scholar [15] H. Dobbertin, Construction of bent functions and balanced Boolean functions with high nonlinearity, in Fast Software Encryption, Lecture Notes in Comput. Sci., 1008, Springer, Berlin, 1995, 61–74. doi: 10.1007/3-540-60590-8_5.  Google Scholar [16] R. E. Jamison, Covering finite field with cosets of subspaces, J. Combinatorial Theory Ser. A, 22 (1977), 253-266.  doi: 10.1016/0097-3165(77)90001-2.  Google Scholar [17] T. Kasami and N. Tokura, On the weight structure of Reed-Muller codes, IEEE Trans. Information Theory, 16 (1970), 752-759.  doi: 10.1109/tit.1970.1054545.  Google Scholar [18] A. Logachev, V. Yashchenko and M. Denisenko, Local affinity of Boolean mappings, in Boolean Functions in Cryptology and Information Security, NATO Sci. Peace Secur. Ser. D Inf. Commun. Secur., 18, IOS, Amsterdam, 2008,148–172.  Google Scholar [19] F. J. MacWilliams and N. J. Sloane, The Theory of Error-Correcting Codes, North-Holland Mathematical Library, 16, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977.  Google Scholar [20] R. L. McFarland., A family of difference sets in non-cyclic groups, J. Combinatorial Theory Ser. A, 15 (1973), 1-10.  doi: 10.1016/0097-3165(73)90031-9.  Google Scholar [21] J. C. C. McKinsey, On Boolean Functions of Many Variables, Ph.D thesis, University of California in Berkeley, 1936.  Google Scholar [22] S. Mesnager, Bent Functions: Fundamentals and Results, Springer, Cham, 2016. doi: 10.1007/978-3-319-32595-8.  Google Scholar [23] O. S. Rothaus, On "bent" functions, J. Combinatorial Theory Ser. A, 20 (1976), 300-305.  doi: 10.1016/0097-3165(76)90024-8.  Google Scholar [24] Zheng and Zhang, Maiorana-McFarland construction of plateaued functions, IEEE Trans. Inform. Theory, 47 (2001), 1215-1223.   Google Scholar

show all references

##### References:
 [1] E. F. Assmus Jr., On the Reed-Muller codes, Discrete Math., 106-107 (1992), 25-33.  doi: 10.1016/0012-365X(92)90526-L.  Google Scholar [2] J. Boyar and M. G. Find, Constructive relationships between algebraic thickness and normality, in Fundamentals of Computation Theory, Lecture Notes in Comput. Sci., 9210, Springer, Cham, 2015,106–117. doi: 10.1007/978-3-319-22177-9_9.  Google Scholar [3] A. Canteaut, C. Carlet, P. Charpin and C. Fontaine, On cryptographic properties of the cosets of $R(1, m)$, IEEE Trans. Inform. Theory, 47 (2001), 1494-1513.  doi: 10.1109/18.923730.  Google Scholar [4] A. Canteaut, M. Daum, H. Dobbertin and G. Leander, Normal and non-normal bent functions, Proceedings of the Workshop on Coding and Cryptography, 2003, 91–100. Google Scholar [5] C. Carlet, Two new classes of bent functions, in Advances in Cryptology, Lecture Notes in Comput. Sci., 765, Springer, Berlin, 1994, 77–101. doi: 10.1007/3-540-48285-7_8.  Google Scholar [6] C. Carlet, On cryptographic complexity of Boolean functions, Finite Fields with Applications to Coding Theory, Cryptography and Related Areas, Springer, Berlin, 2002, 53–69. doi: 10.1007/978-3-642-59435-9_4.  Google Scholar [7] C. Carlet, Recursive lower bounds on the nonlinearity profile of Boolean functions and their applications, IEEE Trans. Inform. Theory, 54 (2008), 1262-1272.  doi: 10.1109/TIT.2007.915704.  Google Scholar [8] C. Carlet, Boolean functions for cryptography and error-correcting codes, in Monography Boolean Models and Methods in Mathematics, Computer Science, and Engineering, Cambridge University Press, 2010, 257-397. Preliminary version available at: http://www.math.univ-paris13.fr/~carlet/chap-fcts-Bool-corr.pdf. doi: 10.1017/CBO9780511780448.011.  Google Scholar [9] C. Carlet, Boolean and vectorial plateaued functions, and APN functions, IEEE Trans. Inform. Theory, 61 (2015), 6272-6289.  doi: 10.1109/TIT.2015.2481384.  Google Scholar [10] C. Carlet and S. Feukoua, Three basic questions on Booleans functions, Adv. Math. Commun., 11 (2017), 837-855.  doi: 10.3934/amc.2017061.  Google Scholar [11] 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 [12] P. Charpin, Normal Boolean functions, J. Complexity, 20 (2004), 245-265.  doi: 10.1016/j.jco.2003.08.010.  Google Scholar [13] G. Cohen and A. Tal, Two structural results for low degree polynomials and applications, in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Leibniz Int. Proc. Inform., 40, Schloss Dagstuhl, Leibniz-Zent. Inform., Wadern, 2015,680–709.  Google Scholar [14] J. F. Dillon, Elementary Hadamard Difference Sets, Ph.D thesis, University of Maryland in College Park, 1974.  Google Scholar [15] H. Dobbertin, Construction of bent functions and balanced Boolean functions with high nonlinearity, in Fast Software Encryption, Lecture Notes in Comput. Sci., 1008, Springer, Berlin, 1995, 61–74. doi: 10.1007/3-540-60590-8_5.  Google Scholar [16] R. E. Jamison, Covering finite field with cosets of subspaces, J. Combinatorial Theory Ser. A, 22 (1977), 253-266.  doi: 10.1016/0097-3165(77)90001-2.  Google Scholar [17] T. Kasami and N. Tokura, On the weight structure of Reed-Muller codes, IEEE Trans. Information Theory, 16 (1970), 752-759.  doi: 10.1109/tit.1970.1054545.  Google Scholar [18] A. Logachev, V. Yashchenko and M. Denisenko, Local affinity of Boolean mappings, in Boolean Functions in Cryptology and Information Security, NATO Sci. Peace Secur. Ser. D Inf. Commun. Secur., 18, IOS, Amsterdam, 2008,148–172.  Google Scholar [19] F. J. MacWilliams and N. J. Sloane, The Theory of Error-Correcting Codes, North-Holland Mathematical Library, 16, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977.  Google Scholar [20] R. L. McFarland., A family of difference sets in non-cyclic groups, J. Combinatorial Theory Ser. A, 15 (1973), 1-10.  doi: 10.1016/0097-3165(73)90031-9.  Google Scholar [21] J. C. C. McKinsey, On Boolean Functions of Many Variables, Ph.D thesis, University of California in Berkeley, 1936.  Google Scholar [22] S. Mesnager, Bent Functions: Fundamentals and Results, Springer, Cham, 2016. doi: 10.1007/978-3-319-32595-8.  Google Scholar [23] O. S. Rothaus, On "bent" functions, J. Combinatorial Theory Ser. A, 20 (1976), 300-305.  doi: 10.1016/0097-3165(76)90024-8.  Google Scholar [24] Zheng and Zhang, Maiorana-McFarland construction of plateaued functions, IEEE Trans. Inform. Theory, 47 (2001), 1215-1223.   Google Scholar
 [1] Constanza Riera, Pantelimon Stănică. Landscape Boolean functions. Advances in Mathematics of Communications, 2019, 13 (4) : 613-627. doi: 10.3934/amc.2019038 [2] 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 [3] 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 [4] 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 [5] Jian Liu, Sihem Mesnager, Lusheng Chen. Variation on correlation immune Boolean and vectorial functions. Advances in Mathematics of Communications, 2016, 10 (4) : 895-919. doi: 10.3934/amc.2016048 [6] Rui Zhang, Sihong Su. A new construction of weightwise perfectly balanced Boolean functions. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021020 [7] Yu Zhou. On the distribution of auto-correlation value of balanced Boolean functions. Advances in Mathematics of Communications, 2013, 7 (3) : 335-347. doi: 10.3934/amc.2013.7.335 [8] 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 [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] 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 [11] Tingting Pang, Nian Li, Li Zhang, Xiangyong Zeng. Several new classes of (balanced) Boolean functions with few Walsh transform values. Advances in Mathematics of Communications, 2021, 15 (4) : 757-775. doi: 10.3934/amc.2020095 [12] Karla L. Cortez, Javier F. Rosenblueth. Normality and uniqueness of Lagrange multipliers. Discrete & Continuous Dynamical Systems, 2018, 38 (6) : 3169-3188. doi: 10.3934/dcds.2018138 [13] Sigurdur F. Hafstein, Christopher M. Kellett, Huijuan Li. Computing continuous and piecewise affine lyapunov functions for nonlinear systems. Journal of Computational Dynamics, 2015, 2 (2) : 227-246. doi: 10.3934/jcd.2015004 [14] Anton Petrunin. Harmonic functions on Alexandrov spaces and their applications. Electronic Research Announcements, 2003, 9: 135-141. [15] Feng Luo. Geodesic length functions and Teichmuller spaces. Electronic Research Announcements, 1996, 2: 34-41. [16] Wen Zhang, Lily Li Liu. Asymptotic normality of associated Lah numbers. Mathematical Foundations of Computing, 2021, 4 (3) : 185-191. doi: 10.3934/mfc.2021011 [17] Yang Yang, Xiaohu Tang, Guang Gong. Even periodic and odd periodic complementary sequence pairs from generalized Boolean functions. Advances in Mathematics of Communications, 2013, 7 (2) : 113-125. doi: 10.3934/amc.2013.7.113 [18] Bingxin Wang, Sihong Su. A New Construction of odd-variable Rotation symmetric Boolean functions with good cryptographic properties. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020115 [19] 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 [20] 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

2020 Impact Factor: 0.935