Article Contents
Article Contents

# Three basic questions on Boolean functions

*The work of this author was partially supported by the CETIC (Centre Africain d'Excellence en Technologies de l'Information et la Communication)

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

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

 Citation:

•  [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.