### Systematic and Random Searches for Compact 4-Bit and 8-Bit Cryptographic S-Boxes

Christophe Clavier and Léo Reynaud

##### Abstract

Obtaining compact, while cryptographically strong, S-boxes is a challenging task required for hardware implementations of lightweight cryptography. Contrarily to 4-bit permutations design which is somewhat well understood, 8-bit permutations have mainly been investigated only through structured S-boxes built from 4-bit ones by means of Feistel, MISTY or SPN schemes. In this paper, we depart from this common habit and search for compact designs directly in the space of 8-bit permutations. We propose two methods for searching good and compact 8-bit S-boxes. One is derived from an adaptation to 8-bit circuits of a systematic bottom-up exploration already used in previous works for 4-bit permutations. The other is the use of a genetic algorithm that samples solutions in the 8-bit permutations space and makes them evolve toward predefined criteria. Contrarily to similar previous attempts, we chose to encode permutations by their circuits rather than by their tables, which allows to optimize non only w.r.t the cryptographic quality but also w.r.t. compactness. We obtain results which show competitive compared to structured designs and we provide an overview of the relation between quality and compactness in the range of rather small 8-bit circuits. Beside, we also exhibit a 8-gate circuit made of only AND and XOR gates that represents a 4-bit permutation belonging to an optimal equivalence class. This shows that such optimal class can be instantiated by threshold implementation friendly circuits with no extra cost compared to previous works.

Available format(s)
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
block cipherscryptanalysisimplementation
Contact author(s)
christophe clavier @ unilim fr
leo reynaud @ unilim fr
History
Short URL
https://ia.cr/2019/1379

CC BY

BibTeX

@misc{cryptoeprint:2019/1379,
author = {Christophe Clavier and Léo Reynaud},
title = {Systematic and Random Searches for Compact 4-Bit and 8-Bit Cryptographic S-Boxes},
howpublished = {Cryptology ePrint Archive, Paper 2019/1379},
year = {2019},
note = {\url{https://eprint.iacr.org/2019/1379}},
url = {https://eprint.iacr.org/2019/1379}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.