The design of Boolean functions which exhibit high-quality cryptography properties is a crucial aspect when implementing secure stream ciphers. To this end, several methods have been proposed to search for secure Boolean functions, and, among those, evolutionary algorithms play a prominent role. In this paper, Genetic Programming (GP) is applied for the evolution of Boolean functions in order to maximize one essential property for strong cryptography functions, namely non-linearity. Differently from other approaches, the evolution happens in the space of Walsh Transforms, instead of using a direct representation of the Boolean functions. Specifically, we evolve coefficients of the Walsh Transform to obtain a generic Walsh spectrum, from which it is possible, through spectral inversion, to obtain a pseudo-Boolean function that, consequently, can be mapped to (one of) the nearest Boolean one. Since that function might not be unique, we propose a strategy in which balancedness, another important cryptography property, is preserved as much as possible. To show that the evolutionary search is actually effective in this task, we evolved Boolean functions from 6 to 16 variables. The results show that not only GP is effective in evolving Boolean functions with high non-linearity, but also that balanced functions are discovered.

Evolution of Walsh Transforms with Genetic Programming

Luigi Rovito
;
Andrea De Lorenzo
;
Luca Manzoni
2023-01-01

Abstract

The design of Boolean functions which exhibit high-quality cryptography properties is a crucial aspect when implementing secure stream ciphers. To this end, several methods have been proposed to search for secure Boolean functions, and, among those, evolutionary algorithms play a prominent role. In this paper, Genetic Programming (GP) is applied for the evolution of Boolean functions in order to maximize one essential property for strong cryptography functions, namely non-linearity. Differently from other approaches, the evolution happens in the space of Walsh Transforms, instead of using a direct representation of the Boolean functions. Specifically, we evolve coefficients of the Walsh Transform to obtain a generic Walsh spectrum, from which it is possible, through spectral inversion, to obtain a pseudo-Boolean function that, consequently, can be mapped to (one of) the nearest Boolean one. Since that function might not be unique, we propose a strategy in which balancedness, another important cryptography property, is preserved as much as possible. To show that the evolutionary search is actually effective in this task, we evolved Boolean functions from 6 to 16 variables. The results show that not only GP is effective in evolving Boolean functions with high non-linearity, but also that balanced functions are discovered.
2023
https://dl.acm.org/doi/abs/10.1145/3583133.3596317
File in questo prodotto:
File Dimensione Formato  
GP_and_spectral_inversion_for_Students_Workshop.pdf

Accesso chiuso

Tipologia: Documento in Versione Editoriale
Licenza: Copyright Editore
Dimensione 547.1 kB
Formato Adobe PDF
547.1 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
cover program.pdf

accesso aperto

Tipologia: Altro materiale allegato
Licenza: Digital Rights Management non definito
Dimensione 631.18 kB
Formato Adobe PDF
631.18 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11368/3053858
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact