Evolutionary Approach for Finding Correlation Immune Boolean Functions of Order t with Minimal Hamming Weight

摘要

The role of Boolean functions is prominent in several areas like cryptography, sequences and coding theory. Therefore, various methods to construct Boolean functions with desired properties are of direct interest. When concentrating on Boolean functions and their role in cryptography, we observe that new motivations and hence new properties have emerged during the years. It is important to note that there are still many design criteria left unexplored and this is where Evolutionary Computation can play a distinct role. One combination of design criteria that has appeared recently is finding Boolean functions that have various orders of correlation immunity and minimal Hamming weight. Surprisingly, most of the more traditionally used methods for Boolean function generation are inadequate in this domain. In this paper, we concentrate on a detailed exploration of several evolutionary algorithms and their applicability for this problem. Our results show that such algorithms are a viable choice when evolving Boolean functions with minimal Hamming weight and certain order of correlation immunity. This approach is also successful in obtaining Boolean functions with several values that were known previously to be theoretically optimal, but no one succeeded in finding actual Boolean functions with such values.