Search Algorithms for Highly Non-Linear Boolean Functions

The purpose of this research work is finding efficient methods for the search of Boolean functions with high non-linearity. For this we use four main algorithms: the hill-climbing algorithm, the simulated annealing algorithm, the genetic algorithm and the genetic algorithm mixed with the hill-climbing algorithm. The hill climbing algorithm accepts higher values as the iterations went by and at a point it would stick to a value thinking that it was the best solution when it wasn't. The simulated annealing algorithm takes lower solutions than the current one with a certain probability. The genetic algorithm creates a population of genes that can be crossbred or mutated with a certain probability. By using C++ programming language we implemented these algorithms and determined which one of them had the best cryptographic properties. The algorithm with the best properties was the genetic algorithm mixed with the hill-climbing algorithm, this one created sequences at each iteration and if the solution of that sequence was higher than the last one we accept it, if not, we discard it. After finding the highest solution in a determined number of iterations, the sequence with the best solution is taken and evaluated with the genetic algorithm saving us time and number of runs. The research work consists in finding new ways of implementing algorithms to make password encryptions more efficient and make passwords more secure. Finally, we are experimenting with an inverse method of searching where we apply the mentioned search heuristics on spectrums (rather than Boolean functions).