1. Paper title:

Evolving Algebraic Constructions for Designing Bent Boolean Functions

-------------------------

2. Author contact details:

Stjepan Picek, Afdeling ESAT - COSIC, Kasteelpark Arenberg 10 - bus 2452, 3001 Heverlee, Belgium, stjepan@computer.org, 0038598226407

Domagoj Jakobovic, Dept. of Electronics, Microelectronics, Computer and Intelligent Systems Faculty of Electrical Engineering and Computing Unska 3, 10000 Zagreb, Croatia, domagoj.jakobovic@fer.hr, 0038516129967

-------------------------

3. Corresponding author:

Stjepan Picek

-------------------------

4. Paper abstract:

The evolution of Boolean functions that can be used in cryptography is a topic well studied in the last decades. 
Previous research, however, has focused on evolving Boolean functions directly, and not on general methods that are capable of generating the desired functions.
The former approach has the advantage of being able to produce a large number of functions in a relatively short time, but it directly depends on the size of the search space. In this paper, we present a method to evolve algebraic constructions for generation of bent Boolean functions. To strengthen our approach, we define three types of constructions and give experimental results for them. Our results show that this approach is able to produce a large number of constructions, which could in turn enable the construction of many more Boolean functions with a larger number of variables.

-------------------------

5. Relevant criteria:

D, E, G

-------------------------

6. Statement:

In our paper, we have shown that genetic programming is able to evolve algebraic constructions that are then used to generate bent Boolean functions of various sizes. This approach outperforms other methods (random search, GA) where some of them are the state of the art (e.g., CGP on clusters).
We use our approach for bent Boolean functions of sizes up to 24 inputs which makes the search space size of 2^(2^24)). We note that bent Boolean functions are relatively rare when compared with the whole search space which makes this needle in a haystack-like scenario. Our approach is extremely lightweight when compared with other heuristic techniques and has 100% success rate and it requires only up to 100 seconds on average for 18 inputs case on a single core.

-------------------------

7. Citation:

The paper is to be published at GECCO 2016 so there is no full citation of the paper at the moment.

-------------------------


8. Any prize money, if any, is to be divided equally among the co-authors.

-------------------------

9. "Best" statement:

Bent functions play an important role in cryptography since they have the maximal possible nonlinearity values. Our approach is easy to use and offers excellent results for large sizes (we tested up to 24 inputs in the paper, but we note that we easily found even larger bent functions where we checked dimensions up to 30 inputs). The same approach can be modified to produce balanced Boolean functions with large nonlinearity values. We note that all sizes are evolved on a regular desktop computer where the evolution process lasts only up to a few minutes on average. Actually, the most expensive part is the a posteriori testing of the nonlinearity property. As a comparison, at GECCO 2015, the bronze Humies award got a technique that was able to find bent Boolean functions with 18 inputs but the authors needed a cluster of 40 nodes and 600 seconds for a single run. To find an 18 inputs bent Boolean function, we require only up to 100 seconds on a single core processor.	
Our contribution was accepted by an prominent conference in the field of natural computing - GECCO 2016.

-------------------------

10. Method used: Genetic Programming