2
$\begingroup$

"There are 536 class of quartic forms Q (header) [in 8 boolean variables] providing bent functions of the form Q+f where f is a cubic functions." Philippe Langevin, 2008.

What is the current prospect of enumerating the extended affine equivalence classes of the bent functions of degree 4 in 8 boolean variables? Is the problem hopelessly large? Has anyone made an attack on it? Are the methods used by Fuller in her thesis still the state of the art? Could the methods used by Langevin et al. contribute to such an attack?

"Analysis of Affine Equivalent Boolean Functions for Cryptography, Joanne Fuller, 2003"

$\endgroup$
1
  • $\begingroup$ (as I recall "bent function" = function to $\pm1$ whose discrete Fourier transform has constant magnitude.) $\endgroup$ Commented Oct 10, 2016 at 13:25

1 Answer 1

1
$\begingroup$

I asked the question to Philippe Langevin by e-mail, here's his answer, hopefully it will help--I am not very au fait with the technicalities of this topic. Here is the link to his projects page referred to below.

I guess you speak about the affine classification of bent functions ?

(1) In my page projects, I give the FULL classification of quartic forms, that is the class by means of a representative but also, the most important (and the meaning of FULL), the stabilizer groups.

I precise this point because without group theory you can not do miracle! By the way, the full classification of B(6) is also on my website project.

After that, you can effectively enumerate the classes of bent functions, the job is done in our article with Pascal, Jean-Pierre, and Gregor.

writing a bent function as :

$H + C + Q$

where H is homogeneous of degree 4, C of degree C and Q of degree 2, We start from 536 quartic forms H, then we have to discover the full classification of the H+C, and finaly the H+C+Q parts.

typically, one H provides about 10^6 class of bent functions.

If I remember correctely the classification of H tooks two years of research with Zanotti, Veron, and finaly 4 months of computations on a single but good machine.

The classification tooks also two years with Leander, and 6 month of computations involving 50-60 processors on network.

(2) The job is done. But it is not the only way to do it. One can also start from the affine classification of semi-bent function in 7 variables (on my site) to discover all the bent in 8 variables. I dont know the thesis. Since the very important papers of Hou on the number of class of RM(k,m)/RM(s,m) are not in the references I understand that probably the job of classification can not be a direct consequence of her work.

$\endgroup$
2
  • $\begingroup$ Thank you for that. I understand from that answer that there are "about" 536 million extended affine classes of bent functions in 8 dimensions. Langevin states that the job is done. If so why isn't the exact number published, let alone (e.g.) Sage code that would allow straightforward enumeration without having to reproduce the entire computation from scratch? $\endgroup$
    – Penguian
    Commented Nov 17, 2016 at 21:53
  • $\begingroup$ I will ask this and point him to this question $\endgroup$
    – kodlu
    Commented Nov 18, 2016 at 5:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .