Correlation Immunity of Boolean Functions
Stjepan Picek, Claude Carlet, Domagoj Jakobović, Julian Francis Miller, Lejla Batina · 2015
Boolean functions are essential in many stream ciphers. When used in combiner generators, they need to have sufficiently high values of correlation immunity, alongside other properties. In addition, correlation immune functions with small Hamming weight reduce the cost of masking countermeasures against side-channel attacks. Various papers have examined the applicability of evolutionary algorithms for evolving cryptographic Boolean functions. However, even when authors considered correlation immunity, it was not given the highest priority. Here, we examine the effectiveness of three different EAs, namely, Genetic Algorithms, Genetic Programming (GP) and Cartesian GP for evolving correlation immune Boolean functions. Besides the properties of balancedness and correlation immunity, we consider several other relevant cryptographic properties while maintaining the optimal trade-offs among them. We show that evolving correlation immune Boolean functions is an even harder objective than maximizing nonlinearity.