# American Institute of Mathematical Sciences

November  2017, 11(4): 837-855. doi: 10.3934/amc.2017061

## Three basic questions on Boolean functions

 1 LAGA, Department of Mathematics, University of Paris 8 (and Paris 13 and CNRS), Saint-Denis cedex 02, France 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 the CETIC (Centre Africain d'Excellence en Technologies de l'Information et la Communication)

Received  April 2017 Published  November 2017

In a first part of this paper, we investigate those Boolean functions satisfying two apparently related, but in fact distinct conditions concerning the algebraic degree:

1. we study those Boolean functions $f$ whose restrictions to all affine hyperplanes have the same algebraic degree (equal to $deg(f)$, the algebraic degree of $f$),

2. we study those functions whose derivatives $D_af(x)=f(x)+ f(x+a)$, $a≠ 0$, have all the same (optimal) algebraic degree $deg(f)-1$.

For determining to which extent these two questions are related, we find three classes of Boolean functions: the first class satisfies both conditions, the second class satisfies the first condition but not the second and the third class satisfies the second condition but not the first. We also give for any fixed positive integer $k$ and for all integers $n$, $p$, $s$ such that $p≥q k+1$, $s≥q k+1$ and $n≥q ps$, a class (denoted by $C_{n,p,s}$) of functions whose restrictions to all $k$-codimensional affine subspaces of ${\Bbb F}_2^n$ have the same algebraic degree as the function.

In a second part of the paper, we introduce the notion of second-order-bent function, whose second order derivatives $D_aD_bf(x)=f(x)+f(x+a)+f(x+b)+f(x+a+b)$, $a≠ 0, b≠ 0, a≠ b$, are all balanced. We exhibit an example in 3 variables and we prove that second-order-bent functions cannot exist if $n$ is not congruent with 3 mod 4. We characterize second-order-bent functions by the Walsh transform, state some of their properties and prove the non existence of such functions for algebraic degree 3 when $n>3$. We leave open the question whether second-order-bent functions can exist for $n$ larger than $3$.

Citation: 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
##### References:
 [1] C. Carlet, Recursive lower bounds on the nonlinearity profile of Boolean Functions and their applications, IEEE Transactions on information Theory, 54 (2008), 1262-1272.  doi: 10.1109/TIT.2007.915704. [2] C. Carlet, Boolean and vectorial plateaued functions, and APN functions, IEEE Transactions on Informations Theory, 61 (2015), 6272-6289.  doi: 10.1109/TIT.2015.2481384. [3] C. Carlet, Boolean functions for cryptography and error correcting codes, Chapter of the Monography Boolean Models and Methods in Mathematics, Computer Science, and Engineering, Y. Crama and P. Hammer eds, Cambridge University Press, (2010), 257{397, Preliminary version available at http://www.math.univ-paris13.fr/~carlet/chap-fcts-Bool-corr.pdf [4] C. Carlet and S. Mesnager, Four decades of research on bent functions, Designs, Codes and Cryptography, 78 (2016), 5-50.  doi: 10.1007/s10623-015-0145-8. [5] C. Carlet and E. Prouff, On plateaued Boolean functions and theirs constructions, Proceeding of Fast Software Encryption 2003, Lecture Notes in Computer Science, 2887 (2003), 54-73. [6] X. Hou and P. Langevin, H-codes and Derivations, Research note, Université de Toulon, France, 2005. [7] P. Langevin and P. Solé, Kernels and defaults, Finite Fields and Applications, Contemporary Mathematics, 225 (1999), 77-85. [8] R. J. McEliece, Weight congruence for $p-$ary cyclic codes, Discrete Mathematics, 3 (1972), 177-192.  doi: 10.1016/0012-365X(72)90032-5. [9] S. Mesnager, Bent Functions: Fundamentals and Results, Springer Verlag, 2016, Version available at http://www.math.univ-paris13.fr/~mesnager/Publications/Contents-Book-bent-Mesnager---copie---copie.pdf [10] F. Rodier, Asymptotic nonlinearity of Boolean functions, Designs, Codes and Cryptography, 40 (2006), 59-70.  doi: 10.1007/s10623-005-6363-8. [11] O. S. Rothaus, On "bent" functions, J. Comb. Theory, 20 (1976), 300-305.  doi: 10.1016/0097-3165(76)90024-8. [12] A. Salagean and M. Mandache-Salagean, Counting and characterizing functions with "fast points" for differential attacks, Cryptography and Communications, 9 (2017), 217-239.  doi: 10.1007/s12095-015-0166-1.

show all references

##### References:
 [1] C. Carlet, Recursive lower bounds on the nonlinearity profile of Boolean Functions and their applications, IEEE Transactions on information Theory, 54 (2008), 1262-1272.  doi: 10.1109/TIT.2007.915704. [2] C. Carlet, Boolean and vectorial plateaued functions, and APN functions, IEEE Transactions on Informations Theory, 61 (2015), 6272-6289.  doi: 10.1109/TIT.2015.2481384. [3] C. Carlet, Boolean functions for cryptography and error correcting codes, Chapter of the Monography Boolean Models and Methods in Mathematics, Computer Science, and Engineering, Y. Crama and P. Hammer eds, Cambridge University Press, (2010), 257{397, Preliminary version available at http://www.math.univ-paris13.fr/~carlet/chap-fcts-Bool-corr.pdf [4] C. Carlet and S. Mesnager, Four decades of research on bent functions, Designs, Codes and Cryptography, 78 (2016), 5-50.  doi: 10.1007/s10623-015-0145-8. [5] C. Carlet and E. Prouff, On plateaued Boolean functions and theirs constructions, Proceeding of Fast Software Encryption 2003, Lecture Notes in Computer Science, 2887 (2003), 54-73. [6] X. Hou and P. Langevin, H-codes and Derivations, Research note, Université de Toulon, France, 2005. [7] P. Langevin and P. Solé, Kernels and defaults, Finite Fields and Applications, Contemporary Mathematics, 225 (1999), 77-85. [8] R. J. McEliece, Weight congruence for $p-$ary cyclic codes, Discrete Mathematics, 3 (1972), 177-192.  doi: 10.1016/0012-365X(72)90032-5. [9] S. Mesnager, Bent Functions: Fundamentals and Results, Springer Verlag, 2016, Version available at http://www.math.univ-paris13.fr/~mesnager/Publications/Contents-Book-bent-Mesnager---copie---copie.pdf [10] F. Rodier, Asymptotic nonlinearity of Boolean functions, Designs, Codes and Cryptography, 40 (2006), 59-70.  doi: 10.1007/s10623-005-6363-8. [11] O. S. Rothaus, On "bent" functions, J. Comb. Theory, 20 (1976), 300-305.  doi: 10.1016/0097-3165(76)90024-8. [12] A. Salagean and M. Mandache-Salagean, Counting and characterizing functions with "fast points" for differential attacks, Cryptography and Communications, 9 (2017), 217-239.  doi: 10.1007/s12095-015-0166-1.
 [1] Sihong Su. A new construction of rotation symmetric bent functions with maximal algebraic degree. Advances in Mathematics of Communications, 2019, 13 (2) : 253-265. doi: 10.3934/amc.2019017 [2] Wenying Zhang, Zhaohui Xing, Keqin Feng. A construction of bent functions with optimal algebraic degree and large symmetric group. Advances in Mathematics of Communications, 2020, 14 (1) : 23-33. doi: 10.3934/amc.2020003 [3] 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 [4] 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 [5] 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 [6] 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, 2022, 16 (3) : 485-501. doi: 10.3934/amc.2020121 [7] 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 [8] Marc Henrard. Homoclinic and multibump solutions for perturbed second order systems using topological degree. Discrete and Continuous Dynamical Systems, 1999, 5 (4) : 765-782. doi: 10.3934/dcds.1999.5.765 [9] Anna Capietto, Walter Dambrosio. A topological degree approach to sublinear systems of second order differential equations. Discrete and Continuous Dynamical Systems, 2000, 6 (4) : 861-874. doi: 10.3934/dcds.2000.6.861 [10] Constanza Riera, Pantelimon Stănică. Landscape Boolean functions. Advances in Mathematics of Communications, 2019, 13 (4) : 613-627. doi: 10.3934/amc.2019038 [11] Jacques Wolfmann. Special bent and near-bent functions. Advances in Mathematics of Communications, 2014, 8 (1) : 21-33. doi: 10.3934/amc.2014.8.21 [12] Guillaume Duval, Andrzej J. Maciejewski. Integrability of potentials of degree $k \neq \pm 2$. Second order variational equations between Kolchin solvability and Abelianity. Discrete and Continuous Dynamical Systems, 2015, 35 (5) : 1969-2009. doi: 10.3934/dcds.2015.35.1969 [13] Claude Carlet, Fengrong Zhang, Yupu Hu. Secondary constructions of bent functions and their enforcement. Advances in Mathematics of Communications, 2012, 6 (3) : 305-314. doi: 10.3934/amc.2012.6.305 [14] Sihem Mesnager, Fengrong Zhang, Yong Zhou. On construction of bent functions involving symmetric functions and their duals. Advances in Mathematics of Communications, 2017, 11 (2) : 347-352. doi: 10.3934/amc.2017027 [15] Claude Carlet. Parameterization of Boolean functions by vectorial functions and associated constructions. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022013 [16] Sihem Mesnager, Fengrong Zhang. On constructions of bent, semi-bent and five valued spectrum functions from old bent functions. Advances in Mathematics of Communications, 2017, 11 (2) : 339-345. doi: 10.3934/amc.2017026 [17] Ayça Çeşmelioğlu, Wilfried Meidl. Bent and vectorial bent functions, partial difference sets, and strongly regular graphs. Advances in Mathematics of Communications, 2018, 12 (4) : 691-705. doi: 10.3934/amc.2018041 [18] Doyoon Kim, Seungjin Ryu. The weak maximum principle for second-order elliptic and parabolic conormal derivative problems. Communications on Pure and Applied Analysis, 2020, 19 (1) : 493-510. doi: 10.3934/cpaa.2020024 [19] Samir Hodžić, Enes Pasalic. Generalized bent functions -sufficient conditions and related constructions. Advances in Mathematics of Communications, 2017, 11 (3) : 549-566. doi: 10.3934/amc.2017043 [20] Claude Carlet, Juan Carlos Ku-Cauich, Horacio Tapia-Recillas. Bent functions on a Galois ring and systematic authentication codes. Advances in Mathematics of Communications, 2012, 6 (2) : 249-258. doi: 10.3934/amc.2012.6.249

2021 Impact Factor: 1.015