A search for additional structure: The case of cryptographic s-boxes

Claude Carlet, Marko Djurasevic, Domagoj Jakobovic, Stjepan Picek

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


We investigate whether it is possible to evolve cryptographically strong S-boxes that have additional constraints on their structure. We investigate two scenarios: where S-boxes additionally have a specific sum of values in rows, columns, or diagonals and the scenario where we check that the difference between the Hamming weights of inputs and outputs is minimal. The first case represents an interesting benchmark problem, while the second one has practical ramifications as such S-boxes could offer better resilience against side-channel attacks. We explore three solution representations by using the permutation, integer, and cellular automata-based encoding. Our results show that it is possible to find S-boxes with excellent cryptographic properties (even optimal ones) and reach the required sums when representing S-box as a square matrix. On the other hand, for the most promising S-box representation based on trees and cellular automata rules, we did not succeed in finding S-boxes with small differences in the Hamming weights between the inputs and outputs, which opens an interesting future research direction. Our results for this scenario and different encodings inspired a mathematical proof that the values reached by evolutionary algorithms are the best possible ones.

Original languageEnglish
Title of host publicationParallel Problem Solving from Nature – PPSN XVI
EditorsThomas Bäck, Mike Preuss, André Deutz, Michael Emmerich, Hao Wang, Carola Doerr, Heike Trautmann
Place of PublicationCham
Number of pages14
EditionPart II
ISBN (Electronic)978-3-030-58115-2
ISBN (Print)978-3-030-58114-5
Publication statusPublished - 2020
Event16th International Conference on Parallel Problem Solving from Nature, PPSN 2020 - Leiden, Netherlands
Duration: 5 Sep 20209 Sep 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


Conference16th International Conference on Parallel Problem Solving from Nature, PPSN 2020

Fingerprint Dive into the research topics of 'A search for additional structure: The case of cryptographic s-boxes'. Together they form a unique fingerprint.

Cite this