Visible to the public Design of S-Boxes Defined with Cellular Automata Rules

TitleDesign of S-Boxes Defined with Cellular Automata Rules
Publication TypeConference Paper
Year of Publication2017
AuthorsPicek, Stjepan, Mariot, Luca, Yang, Bohan, Jakobovic, Domagoj, Mentens, Nele
Conference NameProceedings of the Computing Frontiers Conference
Conference LocationNew York, NY, USA
ISBN Number978-1-4503-4487-6
Keywordscellular automata, composability, compositionality, genetic programming, implementation, lightweight cryptography, pubcrawl, S-boxes, theoretical cryptography

The aim of this paper is to find cellular automata (CA) rules that are used to describe S-boxes with good cryptographic properties and low implementation cost. Up to now, CA rules have been used in several ciphers to define an S-box, but in all those ciphers, the same CA rule is used. This CA rule is best known as the one defining the Keccak $\chi$ transformation. Since there exists no straightforward method for constructing CA rules that define S-boxes with good cryptographic/implementation properties, we use a special kind of heuristics for that - Genetic Programming (GP). Although it is not possible to theoretically prove the efficiency of such a method, our experimental results show that GP is able to find a large number of CA rules that define good S-boxes in a relatively easy way. We focus on the 4 x 4 and 5 x 5 sizes and we implement the S-boxes in hardware to examine implementation properties like latency, area, and power. Particularly interesting is the internal encoding of the solutions in the considered heuristics using combinatorial circuits; this makes it easy to approximate S-box implementation properties like latency and area a priori.

Citation Keypicek_design_2017