Bent functions, semi-bent functions and o-polynomials
  • FENS
  • Bent functions, semi-bent functions and o-polynomials

You are here

Speaker: Claude Carlet (Université Paris 8)
Date/Time: 22 March 2012, Thursday, 16:00
Place: Sabanci University, FENS 2019
Title: Bent functions, semi-bent functions and o-polynomials

Bent functions, semi-bent functions and
with S. Mesnager
Boolean functions are called bent when they lie at maximal distance to
the rst order Reed-Muller code RM(1; n) (n even). This distance is called
the nonlinearity of the function. Bent functions are characterized by the fact
that their Walsh transform takes values 2n=2. play roles not only in coding
theory but also in cryptography (where they can be used to design balanced
functions with high nonlinearity), designs, di erence sets in elementary Abelian
2-groups... Their study has been initiated in the 70's by Dillon and Rothaus in
parallel with the design of the DES. One of the classes of bent Boolean functions
introduced by John Dillon in his thesis is family H. While this class corresponds
to a nice original construction of bent functions in bivariate form, Dillon could
exhibit in it only functions which already belonged to the well-known Maiorana-
McFarland class. After noticing that H can be extended to a slightly larger class
that we shall denote by H, we shall observe that the bent functions constructed
via Niho power functions, which four examples are known, due to Dobbertin et
al. and to Leander-Kholosha, are the univariate form of the functions of class
H. Their restrictions to the vector spaces uF2n=2 , u 2 F?
2n, are linear. We shall
answer to the open question raised by Dobbertin et al. on whether the duals
of the Niho bent functions introduced in the paper are Niho bent as well. The
fact that this Niho function also belongs to the Maiorana-McFarland class will
bring us back to the problem of knowing whether H (or H) is a subclass of the
Maiorana-McFarland completed class. We shall then show that the condition
for a function in bivariate form to belong to class H is equivalent to the fact
that a polynomial directly related to its de nition is an o-polynomial (a notion
from discrete geometry) and deduce several new cases of bent functions in H
which are potentially new bent functions and probably not ane equivalent to
Maiorana-McFarland functions.
Semi-bent functions in n variables (n even) are those Boolean functions
whose Walsh transforms take values in f0;2n=2g. They do not have optimal
nonlinearity but, contrarily to bent functions, they can be balanced, which is
interesting from cryptographic viewpoint. We shall show how obtaining semi-
bent functions from a function belonging to class H and a function from the
so-called PSap class of bent functions.