Evolutionary Construction of Perfectly Balanced Boolean Functions
Finding Boolean functions suitable for cryptographic primitives is a complex combinatorial optimization problem, since they must satisfy several properties to resist cryptanalytic attacks, and the space is very large, which grows super exponentially with the number of input variables. Recent research has focused on the study of Boolean functions that satisfy properties on restricted sets of inputs due to their importance in the development of the FLIP stream cipher. In this paper, we consider one such property, perfect balancedness, and investigate the use of Genetic Programming (GP) and Genetic Algorithms (GA) to construct Boolean functions that satisfy this property along with a good nonlinearity profile. We formulate the related optimization problem and define two encodings for the candidate solutions, namely the truth table and the weightwise balanced representations. Somewhat surprisingly, the results show that GA with the weightwise balanced representation outperforms GP with the classical truth table phenotype in finding highly nonlinear WPB functions. This finding is in stark contrast to previous findings on the evolution of globally balanced Boolean functions, where GP always performs best.
Code (0)
등록된 구현이 없습니다.
Tasks
Combinatorial OptimizationMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Evolving Constructions for Balanced, Highly Nonlinear Boolean Functions
Finding balanced, highly nonlinear Boolean functions is a difficult problem where it is not known what nonlinearity values are possible to be reached in general. At the same time, evolutionary computation is successfully…
Evolutionary AlgorithmsMonotone but Exciting: On Evolving Monotone Boolean Functions with High Nonlinearity
Monotone Boolean functions are a structurally important class of Boolean functions, but their restricted form imposes strong limitations on achievable nonlinearity. In this paper, we investigate whether evolutionary comp…
A Search for Nonlinear Balanced Boolean Functions by Leveraging Phenotypic Properties
In this paper, we consider the problem of finding perfectly balanced Boolean functions with high non-linearity values. Such functions have extensive applications in domains such as cryptography and error-correcting codin…
Look into the Mirror: Evolving Self-Dual Bent Boolean Functions
Bent Boolean functions are important objects in cryptography and coding theory, and there are several general approaches for constructing such functions. Metaheuristics proved to be a strong choice as they can provide ma…
Evolutionary AlgorithmsOn Counts and Densities of Homogeneous Bent Functions: An Evolutionary Approach
Boolean functions with strong cryptographic properties, such as high nonlinearity and algebraic degree, are important for the security of stream and block ciphers. These functions can be designed using algebraic construc…