An Entry for THE 11th ANNUAL (2014) "HUMIES" AWARDS FOR HUMAN-COMPETITIVE RESULTS PRODUCED BY GENETIC AND EVOLUTIONARY COMPUTATION HELD AT THE GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE GECCO 2014

(1) the complete title of one (or more) paper(s) published in the open literature describing the work that the author claims describes a human-competitive result: 

*Bent Function Synthesis by Means of Cartesian Genetic Programming*

(2) the name, complete physical mailing address, e-mail address, and phone number of EACH author of EACH paper: 

Radek Hrbacek
Faculty of Information Technology
Brno University of Technology
Bozetechova 2, 612 66 Brno
Czech Republic
ihrbacek@fit.vutbr.cz
http://www.fit.vutbr.cz/~ihrbacek/
+420 541141352

Vaclav Dvorak
Faculty of Information Technology
Brno University of Technology
Bozetechova 2, 612 66 Brno
Czech Republic
dvorak@fit.vutbr.cz
http://www.fit.vutbr.cz/~dvorak/
+420 541141149

(3) the name of the corresponding author (i.e., the author to whom notices will be sent concerning the competition):

Radek Hrbacek

(4) the abstract of the paper(s):

In this paper, a new approach to synthesize bent Boolean functions by means of Cartesian Genetic Programming (CGP) is proposed. Bent functions have important applications in cryptography due to their high nonlinearity. However, they are very rare and their discovery using conventional brute force methods is not efficient enough. We show that by using CGP we can routinely design bent functions of up to 16 variables. The evolutionary approach exploits parallelism in both the fitness calculation and the search algorithm.

(5) a list containing one or more of the eight letters (A, B, C, D, E, F, G, or H) that correspond to the criteria (see above) that the author claims that the work satisfies:

D, E, G

(6) a statement stating why the result satisfies the criteria that the contestant claims (see examples of statements of human-competitiveness as a guide to aid in constructing this part of the submission):

While the use of computers and communication networks is becoming more and more popular, one has to seriously deal with the security of the data being stored or transferred. In cryptography, the two most fundamental techniques to achieve security in systems are confusion and diffusion. Confusion refers to making a complex relationship between the ciphertext and the key. Thanks to diffusion, the statistical structure of the plain text is dissipated over significant part of the ciphertext, which prevents from reconstructing the original statistical information. In real cryptographic systems, the cipher key is much shorter than the message being encrypted and thus the key has to be reused in some way, often by applying a Boolean function to the key all over again. To avoid decryption by an attacker, the key sequence has to be random. If the Boolean function used to generate the key stream is close to linear, the message can be possibly deciphered. By using functions that are as far from linear as possible, one can build more secure cryptographic systems. These functions, called *bent* functions, are very rare.

In our paper, we have shown that using CGP, we are able to routinely synthesize bent Boolean functions of up to 16 variables, while the state of the art methods (e.g. brute force search, genetic algorithms) are only applicable to functions of no more than 8 variables. The search space grows enormously (2^(2^N)), while the relative frequency of bent functions is rapidly decreasing with the number of variables N, which makes the problem similar to looking for a needle in a haystack.

Because of a very high computational effort required to evaluate a CGP individual in this case, variety of software optimizations and algorithm modifications have been applied in order to speed up the evolutionary design process. The parallelism at the data level enables to process up to 256 test cases simultaneously, the population can be evaluated in multiple threads and even the EA can be spatially structured, in total enabling the EA to run on a computer cluster.

Note: In our subsequent research, we have invented a new approach to evaluate the candidate functions more efficiently; this approach enables to scale the fitness calculation to a high number of threads. The latest implementation can be run on the Intel Xeon Phi coprocessor (up to 61 cores, 244 threads) as well as on a computer cluster. Preliminary results show that a single Xeon Phi coprocessor card significantly outperforms the results achieved with the former implementation published in our paper. For the 16-variable bent function case, the novel implementation needs only 33 seconds in average to find a bent function, in comparison with 636.13 seconds achieved with the distributed version running on 40 hosts. We are also able to find bent functions of 18 variables. These results have not been published so far.

To summarize:
E, D:
We have shown that using CGP, we are able to routinely synthesize bent Boolean functions of up to 16 (18) variables, while the state of the art methods are only applicable to functions of no more than 8 variables. Such solution is publishable in its own field as a new scientific result because a clear improvement in the number of variables and the synthesis time can be demonstrated with respect to the state of the art methods. Because the results of our approach are better than the results obtained using the state of the art methods, we claim that our solution is equal to or better than the most recent human-created solution to a long-standing problem for which there has been a succession of increasingly better human-created solutions.

G:
Since the search space grows enormously (2^(2^N)) and the relative frequency of bent functions is rapidly decreasing with the number of variables N, finding such functions is considered as very difficult. We claim that the proposed method solves a problem of indisputable difficulty in its field.

(7) a full citation of the paper (that is, author names; publication date; name of journal, conference, technical report, thesis, book, or book chapter; name of editors, if applicable, of the journal or edited book; publisher name; publisher city; page numbers, if applicable):

Hrbacek R., Dvorak V.: Bent Function Synthesis by Means of Cartesian Genetic Programming. In proceedings of the 13th International Conference on Parallel Problem Solving from Nature, 2014, to appear, accepted on May 19, 2014.

(8) a statement either that "any prize money, if any, is to be divided equally among the co-authors" OR a specific percentage breakdown as to how the prize money, if any, is to be divided among the co-authors:

Any prize money is to be divided equally among the co-authors.

(9) a statement stating why the judges should consider the entry as "best" in comparison to other entries that may also be "human-competitive": 

We demonstrated a significant contribution to the bent Boolean functions design: In comparison with the state of the art brute force methods (even employing a lot of mathematical knowledge to reduce the search space), our approach based on CGP is applicable to bent functions of much more variables (8 vs. 18). Our contribution was accepted by an prominent conference in the field of natural computing - Parallel Problem Solving from Nature.

We demonstrated a notable contribution which has a great impact to cryptography: Bent functions have applications in cryptography due to their significant properties - when used in a cipher, their nonlinearity makes cryptanalysis harder. The proposed approach can be easily extended to track other properties of the Boolean functions, such as the number of 0s and 1s in its truth table in order to find balanced functions. We claim that with our approach, one can routinely design cryptographic systems with a high degree of security.

(10) an indication of the general type of genetic or evolutionary computation used:

CGP