On the Construction of Lightweight S-Boxes

S-Boxes are essential objects in the conception of blockciphers. Typically, an S-Box is simply a permutation (bijective function) on n bits, with n small (usually 4 or 8). Its role in a blockcipher is to bring nonlinearity to the cipher, thus an S-Box must be highly nonlinear. Several parameters of a function are used to measure nonlinearity, among which the most important are differential uniformity and nonlinearity. Although we know a few permutations with good differential uniformity and nonlinearity any number of bits, implementing such S-Boxes has a high cost in general. Therefore, an important problem in symmetric cryptography is to find S-Boxes with good cryptographic parameters (differential uniformity, nonlinearity) with a low implementation cost (which implies a structure). In this presentation, we will address this problem by analyzing a few structures (Feistel, MISTY, Butterfly) which yield a low implementation cost while allowing for some cryptographically strong S-Boxes.