Degree is Important: On Evolving Homogeneous Boolean Functions

• URL: http://arxiv.org/abs/2501.18407v1
• Date: Thu, 30 Jan 2025 15:04:14 GMT
• Title: Degree is Important: On Evolving Homogeneous Boolean Functions
• Authors: Claude Carlet, Marko Ðurasevic, Domagoj Jakobovic, Luca Mariot, Stjepan Picek,
• Abstract summary: This paper investigates the use of Evolutionary Algorithms to design homogeneous bent Boolean functions. While EAs manage to find quadratic homogeneous bent functions, none of the approaches result in cubic homogeneous bent functions.
• Score: 32.90791284928444
• License:
• Abstract: Boolean functions with good cryptographic properties like high nonlinearity and algebraic degree play an important in the security of stream and block ciphers. Such functions may be designed, for instance, by algebraic constructions or metaheuristics. This paper investigates the use of Evolutionary Algorithms (EAs) to design homogeneous bent Boolean functions, i.e., functions that are maximally nonlinear and whose algebraic normal form contains only monomials of the same degree. In our work, we evaluate three genotype encodings and four fitness functions. Our results show that while EAs manage to find quadratic homogeneous bent functions (with the best method being a GA leveraging a restricted encoding), none of the approaches result in cubic homogeneous bent functions.

Related papers

• Use of Simple Arithmetic Operations to Construct Efficiently Implementable Boolean functions Possessing High Nonlinearity and Good Resistance to Algebraic Attacks [28.8640336189986]
  We show that there are functions in the family achieving a combination of nonlinearity and (fast) algebraic immunity. The main novelty of our approach is to apply a judicious combination of simple integer and binary field arithmetic to Boolean function construction.
  arXiv  Detail & Related papers  (2024-08-21T12:46:50Z)
• Look into the Mirror: Evolving Self-Dual Bent Boolean Functions [35.305121158674964]
  This paper experiments with evolutionary algorithms with the goal of evolving (anti-)self-dual bent Boolean functions. We successfully construct self-dual bent functions for each dimension. We also tried evolving secondary constructions for self-dual bent functions, but this direction provided no successful results.
  arXiv  Detail & Related papers  (2023-11-20T16:20:16Z)
• Digging Deeper: Operator Analysis for Optimizing Nonlinearity of Boolean Functions [8.382710169577447]
  We investigate the effects of genetic operators for bit-string encoding in optimizing nonlinearity. By observing the range of possible changes an operator can provide, one can use this information to design a more effective combination of genetic operators.
  arXiv  Detail & Related papers  (2023-02-12T10:34:01Z)
• Generative Adversarial Neural Operators [59.21759531471597]
  We propose the generative adversarial neural operator (GANO), a generative model paradigm for learning probabilities on infinite-dimensional function spaces. GANO consists of two main components, a generator neural operator and a discriminator neural functional. We empirically study GANOs in controlled cases where both input and output functions are samples from GRFs and compare its performance to the finite-dimensional counterpart GAN.
  arXiv  Detail & Related papers  (2022-05-06T05:12:22Z)
• Evolving Constructions for Balanced, Highly Nonlinear Boolean Functions [37.84234862910533]
  We show that genetic programming can evolve constructions resulting in balanced Boolean functions with high nonlinearity. Our results show that GP can find constructions that generalize well, i.e., result in the required functions for multiple tested sizes. Interestingly, the simplest solution found by GP is a particular case of the well-known indirect sum construction.
  arXiv  Detail & Related papers  (2022-02-17T16:33:24Z)
• Evolutionary Construction of Perfectly Balanced Boolean Functions [7.673465837624365]
  We investigate the use of Genetic Programming (GP) and Genetic Algorithms (GA) to construct Boolean functions that satisfy a property, perfect balancedness, along with a good nonlinearity profile. 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.
  arXiv  Detail & Related papers  (2022-02-16T18:03:04Z)
• Finite-Function-Encoding Quantum States [52.77024349608834]
  We introduce finite-function-encoding (FFE) states which encode arbitrary $d$-valued logic functions. We investigate some of their structural properties.
  arXiv  Detail & Related papers  (2020-12-01T13:53:23Z)
• A Functional Perspective on Learning Symmetric Functions with Neural Networks [48.80300074254758]
  We study the learning and representation of neural networks defined on measures. We establish approximation and generalization bounds under different choices of regularization. The resulting models can be learned efficiently and enjoy generalization guarantees that extend across input sizes.
  arXiv  Detail & Related papers  (2020-08-16T16:34:33Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  We show that families of algorithms fail to produce nearly optimal solutions with high probability. For the case of Boolean circuits, our results improve the state-of-the-art bounds known in circuit complexity theory.
  arXiv  Detail & Related papers  (2020-04-25T05:45:59Z)
• Invariant Feature Coding using Tensor Product Representation [75.62232699377877]
  We prove that the group-invariant feature vector contains sufficient discriminative information when learning a linear classifier. A novel feature model that explicitly consider group action is proposed for principal component analysis and k-means clustering.
  arXiv  Detail & Related papers  (2019-06-05T07:15:17Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.