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

Claude Carlet; Serge Feukoua

doi:10.3934/amc.2020036

Article Contents

2020, Volume 14, Issue 4: 651-676. Doi: 10.3934/amc.2020036

This issue Previous Article Abelian non-cyclic orbit codes and multishot subspace codes Next Article Composite constructions of self-dual codes from group rings and new extremal self-dual binary codes of length 68

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

Claude Carlet^1, and
Serge Feukoua^2,*,

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: October 31, 2018

Revised: June 30, 2019

Early access: November 2019

Published: November 2020

Abstract Full Text(HTML) Related Papers Cited by

Abstract

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 $.

Keywords:

Mathematics Subject Classification: 06E30, 94C10, 94A60, 11T71, 05E99.

Citation:

Full Text(HTML)

Related Papers

Cited by

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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[10]	C. Carlet and S. Feukoua, Three basic questions on Booleans functions, Adv. Math. Commun., 11 (2017), 837-855. doi: 10.3934/amc.2017061.
[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.
[12]	P. Charpin, Normal Boolean functions, J. Complexity, 20 (2004), 245-265. doi: 10.1016/j.jco.2003.08.010.
[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.
[14]	J. F. Dillon, Elementary Hadamard Difference Sets, Ph.D thesis, University of Maryland in College Park, 1974.
[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.
[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.
[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.
[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.
[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.
[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.
[21]	J. C. C. McKinsey, On Boolean Functions of Many Variables, Ph.D thesis, University of California in Berkeley, 1936.
[22]	S. Mesnager, Bent Functions: Fundamentals and Results, Springer, Cham, 2016. doi: 10.1007/978-3-319-32595-8.
[23]	O. S. Rothaus, On "bent" functions, J. Combinatorial Theory Ser. A, 20 (1976), 300-305. doi: 10.1016/0097-3165(76)90024-8.
[24]	Zheng and Zhang, Maiorana-McFarland construction of plateaued functions, IEEE Trans. Inform. Theory, 47 (2001), 1215-1223.