Exploring Semi-bent Boolean Functions Arising from Cellular Automata

Luca Mariot, Martina Saletta, Alberto Leporati, Luca Manzoni

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review


Semi-bent Boolean functions are interesting from a cryptographic standpoint, since they possess several desirable properties such as having a low and flat Walsh spectrum, which is useful to resist linear cryptanalysis. In this paper, we consider the search of semi-bent functions through a construction based on cellular automata (CA). In particular, the construction defines a Boolean function by computing the XOR of all output cells in the CA. Since the resulting Boolean functions have the same algebraic degree of the CA local rule, we devise a combinatorial algorithm to enumerate all quadratic Boolean functions. We then apply this algorithm to exhaustively explore the space of quadratic rules of up to 6 variables, selecting only those for which our CA-based construction always yields semi-bent functions of up to 20 variables. Finally, we filter the obtained rules with respect to their balancedness, and remark that the semi-bent functions generated through our construction by the remaining rules have a constant number of linear structures.

Original languageEnglish
Title of host publicationCellular Automata
Subtitle of host publication14th International Conference on Cellular Automata for Research and Industry, ACRI 2020, Proceedings
EditorsTomasz M. Gwizdałła, Luca Manzoni, Georgios Ch. Sirakoulis, Stefania Bandini, Krzysztof Podlaski
Place of PublicationCham
Number of pages11
ISBN (Electronic)978-3-030-69480-7
ISBN (Print)978-3-030-69479-1
Publication statusPublished - 2021
Event14th International Conference on Cellular Automata for Research and Industry, ACRI 2020 - Online, Poland
Duration: 2 Dec 20204 Dec 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference14th International Conference on Cellular Automata for Research and Industry, ACRI 2020


  • Balancedness
  • Cellular automata
  • Combinatorial search
  • Linear structures
  • Nonlinearity
  • Semi-bent functions
  • Stream ciphers


Dive into the research topics of 'Exploring Semi-bent Boolean Functions Arising from Cellular Automata'. Together they form a unique fingerprint.

Cite this