**Evolutionary Design of Trace Form Bent Functions**

*Min yang and Qingshu Meng and Huanguo Zhang*

**Abstract: **In order to design bent functions, evolutionary algorithm
based on truth table, algebraic normal form or Walsh spectra are already known. Evolutionary algorithm based on trace function form is not known to authors' knowledge. In this paper, we give an evolutionary algorithm based on the trace representation of boolean function. With the algorithm, we constructed many bent functions and made some analysis work. First we observe that all 4 affinely inequivalent bent classes in 6-variable can be written as the linear sum of 2 or 3 monomial trace functions. We make a conclusion that affine transform can be used to change the linear span, which lead to a method constructing perfect nonlinear s-box of non-Niho type; Second, we find that some exponents take more chances to construct bent functions while some exponents take less. By this observation,
we give each exponent a cost function, which make our algorithm more efficient than exhaustive searching algorithm or random algorithm. This is also the advantage over the algorithms based on the algebraic normal form, truth table, or Walsh spectra because we don't know what kinds of algebraic normal form, truth table, Walsh spectra are more possible to be used to construct bent functions; Third, we classify the obtained bent functions into affinely inequivalent classes and the number of classes is reported.

**Category / Keywords: **foundations / evolutionary algorithm, trace function, bent functions

**Date: **received 11 Sep 2005, last revised 24 Sep 2005

**Contact author: **mqseagle at sohu com

**Available format(s): **PDF | BibTeX Citation

**Version: **20050925:030208 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]