Finding bent functions using genetic algorithms

Abstract

In this thesis, a generic genetic algorithm (GA) is presented that is implemented on a reconfigurable computer. Our GA is implemented such that many problems can be solved by simply adapting the problem to the GA. For example, part of this process involves the customization of the fitness function of the given problem to the GA. The size of the problem is limited by the capacity of a field programmable gate array that is part of the reconfigurable computer. We apply this to bent functions, which are Boolean functions that are well suited for cryptographical applications and are extremely rare. Experimental results show the effectiveness of this technique. Different methods are used to discover bent functions. These methods take advantage of the properties of bent functions to reduce the total search space. This allows a brute force search to be conducted on the reduced search space to locate the set of bent functions in that search space. Two different methods are used to reduce the search space. The first is through rotationally symmetric functions, which reduces the number of bent function that can be found, while the second is by the degree of the function, which locates all bent functions.