On Counts and Densities of Homogeneous Bent Functions: An Evolutionary Approach

• URL: http://arxiv.org/abs/2511.12652v1
• Date: Sun, 16 Nov 2025 15:33:40 GMT
• Title: On Counts and Densities of Homogeneous Bent Functions: An Evolutionary Approach
• Authors: Claude Carlet, Marko Ðurasevic, Domagoj Jakobovic, Luca Mariot, Stjepan Picek, Alexandr Polujan,
• Abstract summary: This paper examines the use of Evolutionary Algorithms (EAs) to evolve homogeneous bent Boolean functions.<n>We introduce the notion of density of homogeneous bent functions, facilitating the algorithmic design that results in finding quadratic and cubic bent functions in different numbers of variables.
• Score: 60.00535100780336
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 constructions or metaheuristics. This paper examines the use of Evolutionary Algorithms (EAs) to evolve homogeneous bent Boolean functions, that is, functions whose algebraic normal form contains only monomials of the same degree and that are maximally nonlinear. We introduce the notion of density of homogeneous bent functions, facilitating the algorithmic design that results in finding quadratic and cubic bent functions in different numbers of variables.

Related papers

• IDEM Enough? Evolving Highly Nonlinear Idempotent Boolean Functions [25.80284220818612]
  Idempotent Boolean functions are attractive as candidates for cryptographic design.<n>We show that idempotence can be enforced by encoding the truth table on orbits.<n>Next, we show that idempotence can be enforced by encoding the truth table on orbits, yielding a compact genome of size equal to the number of distinct squaring orbits.
  arXiv  Detail & Related papers  (2026-01-31T18:06:38Z)
• A Systematic Study on the Design of Odd-Sized Highly Nonlinear Boolean Functions via Evolutionary Algorithms [32.90791284928444]
  We show that genetic programming generally outperforms other evolutionary algorithms.<n>We show that a symmetric genetic algorithm with the bitstring encoding manages to evolve a $9$-variable Boolean function with nonlinearity 241.
  arXiv  Detail & Related papers  (2025-04-24T15:35:53Z)
• Degree is Important: On Evolving Homogeneous Boolean Functions [32.90791284928444]
  This paper investigates the use of Evolutionary Algorithms to design homogeneous bent Boolean functions.<n>While EAs manage to find quadratic homogeneous bent functions, none of the approaches result in cubic homogeneous bent functions.
  arXiv  Detail & Related papers  (2025-01-30T15:04:14Z)
• 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.<n>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)
• Transformers Implement Functional Gradient Descent to Learn Non-Linear Functions In Context [44.949726166566236]
  We show that (non-linear) Transformers naturally learn to implement gradient descent in function space. We also show that the optimal choice of non-linear activation depends in a natural way on the class of functions that need to be learned.
  arXiv  Detail & Related papers  (2023-12-11T17:05:25Z)
• 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)
• Measuring dissimilarity with diffeomorphism invariance [94.02751799024684]
  We introduce DID, a pairwise dissimilarity measure applicable to a wide range of data spaces. We prove that DID enjoys properties which make it relevant for theoretical study and practical use.
  arXiv  Detail & Related papers  (2022-02-11T13:51:30Z)
• The role of feature space in atomistic learning [62.997667081978825]
  Physically-inspired descriptors play a key role in the application of machine-learning techniques to atomistic simulations. We introduce a framework to compare different sets of descriptors, and different ways of transforming them by means of metrics and kernels. We compare representations built in terms of n-body correlations of the atom density, quantitatively assessing the information loss associated with the use of low-order features.
  arXiv  Detail & Related papers  (2020-09-06T14:12:09Z)
• 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)
• Space of Functions Computed by Deep-Layered Machines [74.13735716675987]
  We study the space of functions computed by random-layered machines, including deep neural networks and Boolean circuits. Investigating the distribution of Boolean functions computed on the recurrent and layer-dependent architectures, we find that it is the same in both models.
  arXiv  Detail & Related papers  (2020-04-19T18:31:03Z)
• 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.