[Resource Topic] 2019/1379: Systematic and Random Searches for Compact 4-Bit and 8-Bit Cryptographic S-Boxes

Welcome to the resource topic for 2019/1379

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

Authors: Christophe Clavier, Léo Reynaud


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.

ePrint: https://eprint.iacr.org/2019/1379

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .