Exploring semi-bent Boolean functions arising from cellular automata

DOI10.1007/978-3-030-69480-7_7zbMATH Open1492.68092arXiv2005.08300OpenAlexW3135749679MaRDI QIDQ831678FDOQ831678

Authors: Luca Mariot, Martina Saletta, Alberto Leporati, Luca Manzoni 

Publication date: 24 March 2022

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/2005.08300

Recommendations

• scientific article; zbMATH DE number 1024089
• A note on semi-bent and hyper-bent Boolean functions
• scientific article; zbMATH DE number 2092211
• Characterisation and enumeration of a class of semi-bent quadratic Boolean functions
• Autocorrelation coefficients of two classes of semi-bent functions

zbMATH Keywords

balancednesscellular automatanonlinearitylinear structuresstream cipherscombinatorial searchsemi-bent functions

Mathematics Subject Classification ID

Cryptography (94A60) Cellular automata (computational aspects) (68Q80) Boolean functions (94D10)

Cites Work

• Keccak
• Title not available (Why is that?)
• On ``bent functions
• A secret sharing scheme based on cellular automata
• Cellular automata based S-boxes
• Mutually orthogonal Latin squares based on cellular automata
• Cryptographic properties of bipermutive cellular automata rules
• Advances on random sequence generation by uniform cellular automata
• Cryptographically Strong S-Boxes Based on Cellular Automata
• Cellular Automata Pseudo-Random Number Generators and Their Resistance to Asynchrony
• Computing the periods of preimages in surjective cellular automata

Cited In (4)

• Heuristic search of (semi-)bent functions based on cellular automata
• Evolutionary strategies for the design of binary linear codes
• Exploring Lightweight S-boxes Using Cellular Automata and Reinforcement Learning
• A survey of metaheuristic algorithms for the design of cryptographic Boolean functions

Uses Software

• Keccak

This page was built for publication: Exploring semi-bent Boolean functions arising from cellular automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q831678)