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 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, 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. CanteautC. CarletP. 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. CanteautC. CarletP. 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]

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

[3]

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

[4]

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

[5]

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

[6]

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

[7]

Karla L. Cortez, Javier F. Rosenblueth. Normality and uniqueness of Lagrange multipliers. Discrete & Continuous Dynamical Systems - A, 2018, 38 (6) : 3169-3188. doi: 10.3934/dcds.2018138

[8]

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

[9]

Anton Petrunin. Harmonic functions on Alexandrov spaces and their applications. Electronic Research Announcements, 2003, 9: 135-141.

[10]

Feng Luo. Geodesic length functions and Teichmuller spaces. Electronic Research Announcements, 1996, 2: 34-41.

[11]

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

[12]

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

[13]

Claude Carlet, Khoongming Khoo, Chu-Wee Lim, Chuan-Wen Loe. On an improved correlation analysis of stream ciphers using multi-output Boolean functions and the related generalized notion of nonlinearity. Advances in Mathematics of Communications, 2008, 2 (2) : 201-221. doi: 10.3934/amc.2008.2.201

[14]

Rafael De La Llave, R. Obaya. Regularity of the composition operator in spaces of Hölder functions. Discrete & Continuous Dynamical Systems - A, 1999, 5 (1) : 157-184. doi: 10.3934/dcds.1999.5.157

[15]

Hugo Beirão da Veiga. Elliptic boundary value problems in spaces of continuous functions. Discrete & Continuous Dynamical Systems - S, 2016, 9 (1) : 43-52. doi: 10.3934/dcdss.2016.9.43

[16]

Wolfgang Arendt, Patrick J. Rabier. Linear evolution operators on spaces of periodic functions. Communications on Pure & Applied Analysis, 2009, 8 (1) : 5-36. doi: 10.3934/cpaa.2009.8.5

[17]

Tao Chen, Linda Keen. Slices of parameter spaces of generalized Nevanlinna functions. Discrete & Continuous Dynamical Systems - A, 2019, 39 (10) : 5659-5681. doi: 10.3934/dcds.2019248

[18]

Guoshan Zhang, Shiwei Wang, Yiming Wang, Wanquan Liu. LS-SVM approximate solution for affine nonlinear systems with partially unknown functions. Journal of Industrial & Management Optimization, 2014, 10 (2) : 621-636. doi: 10.3934/jimo.2014.10.621

[19]

Guizhen Cui, Yunping Jiang, Anthony Quas. Scaling functions and Gibbs measures and Teichmüller spaces of circle endomorphisms. Discrete & Continuous Dynamical Systems - A, 1999, 5 (3) : 535-552. doi: 10.3934/dcds.1999.5.535

[20]

Yunho Kim, Luminita A. Vese. Image recovery using functions of bounded variation and Sobolev spaces of negative differentiability. Inverse Problems & Imaging, 2009, 3 (1) : 43-68. doi: 10.3934/ipi.2009.3.43

2018 Impact Factor: 0.879

Metrics

  • PDF downloads (23)
  • HTML views (28)
  • Cited by (0)

Other articles
by authors

[Back to Top]