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]

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

[2]

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

[3]

Anna Capietto, Walter Dambrosio. A topological degree approach to sublinear systems of second order differential equations. Discrete & Continuous Dynamical Systems - A, 2000, 6 (4) : 861-874. doi: 10.3934/dcds.2000.6.861

[4]

Marc Henrard. Homoclinic and multibump solutions for perturbed second order systems using topological degree. Discrete & Continuous Dynamical Systems - A, 1999, 5 (4) : 765-782. doi: 10.3934/dcds.1999.5.765

[5]

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

[6]

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

[7]

Guillaume Duval, Andrzej J. Maciejewski. Integrability of potentials of degree $k \neq \pm 2$. Second order variational equations between Kolchin solvability and Abelianity. Discrete & Continuous Dynamical Systems - A, 2015, 35 (5) : 1969-2009. doi: 10.3934/dcds.2015.35.1969

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

Ayça Çeşmelioǧlu, Wilfried Meidl, Alexander Pott. On the dual of (non)-weakly regular bent functions and self-dual bent functions. Advances in Mathematics of Communications, 2013, 7 (4) : 425-440. doi: 10.3934/amc.2013.7.425

[14]

Joan-Josep Climent, Francisco J. García, Verónica Requena. On the construction of bent functions of $n+2$ variables from bent functions of $n$ variables. Advances in Mathematics of Communications, 2008, 2 (4) : 421-431. doi: 10.3934/amc.2008.2.421

[15]

Jyrki Lahtonen, Gary McGuire, Harold N. Ward. Gold and Kasami-Welch functions, quadratic forms, and bent functions. Advances in Mathematics of Communications, 2007, 1 (2) : 243-250. doi: 10.3934/amc.2007.1.243

[16]

Kanat Abdukhalikov, Sihem Mesnager. Explicit constructions of bent functions from pseudo-planar functions. Advances in Mathematics of Communications, 2017, 11 (2) : 293-299. doi: 10.3934/amc.2017021

[17]

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

[18]

Hongjie Dong, Seick Kim. Green's functions for parabolic systems of second order in time-varying domains. Communications on Pure & Applied Analysis, 2014, 13 (4) : 1407-1433. doi: 10.3934/cpaa.2014.13.1407

[19]

Benjamin Webb. Dynamics of functions with an eventual negative Schwarzian derivative. Discrete & Continuous Dynamical Systems - A, 2009, 24 (4) : 1393-1408. doi: 10.3934/dcds.2009.24.1393

[20]

Natalia Tokareva. On the number of bent functions from iterative constructions: lower bounds and hypotheses. Advances in Mathematics of Communications, 2011, 5 (4) : 609-621. doi: 10.3934/amc.2011.5.609

2017 Impact Factor: 0.564

Metrics

  • PDF downloads (44)
  • HTML views (383)
  • Cited by (0)

Other articles
by authors

[Back to Top]