Search

A recent trend has shown constructions of 6-bit S-boxes that are mostly focused on their cryptographic elegance, while their lightweight aspects have not really been addressed well. This paper attempts to plug-in this existing research gap where we show how the composite structure of the extension field F26 could be leveraged. An earlier well-known example is an efficient implementation of AES S-box using the tower field extension of F28 . The case of F2ab is completely different from any tower field as the implementation varies as per the choice of extension – for instance, F(2a)b or F(2b)a , where a and b are prime. Thus, it makes the implementation of S-boxes over F26 = F2(2×3) very interesting. In this work, we systematically study the composite field structure of F26 from a hardware standpoint for a class of S-boxes that are power mapping or their affine equivalents. We analyze the hardware efficiency with respect to different representations of the field extension, i.e., F(22)3 or F(23)2 . Furthermore, for each extension, we investigate the impact of various choices of bases – for instance, we present the evidence of the effect that normal or polynomial bases have on the implementation. This gives us further insight on the choice of basis with respect to the field extension. In the process, we present a special normal basis, when used in conjunction with F(23)2 results in the least (or very close to least) area in terms of GE for the 18 (6 quadratic and 12 cubic) S-boxes studied in this work. The special normal basis reported here has some algebraic properties which make it inherently hardware friendly and allow us to predict the area reduction, without running a tool. Overall, this work constitutes an extensive hardware characterization of a class of cryptographically significant 6-bit S-boxes giving us interesting insights into the systematic lightweight implementation of S-boxes without relying on an automated tool.

Reconstructing an S-box from a cryptographic table such as difference distribution table (DDT), linear approximation table (LAT), differential-linear connectivity table (DLCT) or boomerang connectivity table (BCT) is one of the fundamental problems in symmetric-key cryptography. Till now, there are only very few known methods which can reconstruct an S-box from a given table: guess-and-determine algorithms of Boura et al. (DCC 2019) and Tian et al. (DCC 2020), sign determination algorithm of Dunkelman et al. (ToSC 2019) and STP based approach of Lu et al. (DCC 2022). In this paper we consider the reconstruction problem in an even more challenging setup where one needs to reconstruct S-boxes from a partial cryptographic table. We are able to reconstruct S-boxes when only a few number of rows of a cryptographic table is given. This problem has never been studied in the literature. We apply mixed integer linear programming (MILP) as the key tool for solving this problem. Needless to say that we can solve the reconstruction problem when the full table is given and this is the first ever application of MILP tool in solving such fundamental problems. As a further application of our method, we provide the generic MILP models which can search for S-boxes with a given cryptographic property such as differential uniformity, linearity, differential-linear uniformity or boomerang uniformity. Additionally, our method can recover a Boolean function from a given Walsh spectrum or a Boolean function with a given nonlinearity. We also introduce a new heuristic called Optimistic MILP objective that guides the model towards obtaining multiple S-boxes or Boolean functions with the same cryptographic property. We give detailed experimental results for up to 6-bit S-boxes showing the effectiveness of our technique.