Fighting the Symmetries: The Structure of Cryptographic Boolean Function Spaces
Date
2015
Authors
Picek, Stjepan
McKay, Robert Ian
Santana, Roberto
Gedeon, Tamas (Tom)
Journal Title
Journal ISSN
Volume Title
Publisher
Association for Computing Machinery (ACM)
Abstract
We explore the problem space of maximum nonlinearity problems for balanced Boolean functions, examining the symmetry structure and fitness landscapes in the most common (bit string) representation. We present theoretical analyses of well understood aspects, together with detailed enumeration of the 4-bit problem, sampling of the 6-bit problem based on known optima, and sampling of the 8-bit problem based on its fittest known solutions. We show that these problems have many more symmetries than is generally noted, with implications for crossover and for distributional methods. We explore the large-scale plateau structure of the problem, with similar implications for local search. We show that symmetries yield additional information that may yield more effective search methods
Description
Keywords
Citation
Collections
Source
GECCO '15 Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation
Type
Conference paper
Book Title
Entity type
Access Statement
License Rights
Restricted until
2037-12-31
Downloads
File
Description