Discovering Non-Linear Boolean Functions by Evolving Walsh Transforms with Genetic Programming
Created by W.Langdon from
gp-bibliography.bib Revision:1.8098
- @Article{rovito:2023:Algorithms,
-
author = "Luigi Rovito and Andrea {De Lorenzo} and
Luca Manzoni",
-
title = "Discovering {Non-Linear} Boolean Functions by Evolving
Walsh Transforms with Genetic Programming",
-
journal = "Algorithms",
-
year = "2023",
-
volume = "16",
-
number = "11",
-
pages = "Article No. 499",
-
keywords = "genetic algorithms, genetic programming",
-
ISSN = "1999-4893",
-
URL = "https://www.mdpi.com/1999-4893/16/11/499",
-
DOI = "doi:10.3390/a16110499",
-
abstract = "Stream ciphers usually rely on highly secure Boolean
functions to ensure safe communication within unsafe
channels. However, discovering secure Boolean functions
is a non-trivial optimisation problem that has been
addressed by many optimisation techniques: in
particular by evolutionary algorithms. We investigate
in this article the employment of Genetic Programming
(GP) for evolving Boolean functions with large
non-linearity by examining the search space consisting
of Walsh transforms. Especially, we build generic Walsh
spectra starting from the evolution of Walsh transform
coefficients. Then, by leveraging spectral inversion,
we build pseudo-Boolean functions from which we are
able to determine the corresponding nearest Boolean
functions, whose computation involves filling via a
random criterion a certain amount of {"}uncertain{"}
positions in the final truth table. We show that by
using a balancedness-preserving strategy, it is
possible to exploit those positions to obtain a
function that is as balanced as possible. We perform
experiments by comparing different types of symbolic
representations for the Walsh transform, and we analyse
the percentage of uncertain positions. We
systematically review the outcomes of these comparisons
to highlight the best type of setting for this problem.
We evolve Boolean functions from 6 to 16 bits and
compare the GP-based evolution with random search to
show that evolving Walsh transforms leads to highly
non-linear functions that are balanced as well.",
-
notes = "also known as \cite{a16110499}",
- }
Genetic Programming entries for
Luigi Rovito
Andrea De Lorenzo
Luca Manzoni
Citations