Know-Thy-Basis: Decomposing F26 for Lightweight S-box Implementation

Abstract

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 F_2⁶ could be leveraged. An earlier well-known example is an efficient implementation of AES S-box using the tower field extension of F_2⁸ . The case of F_2^ab is completely different from any tower field as the implementation varies as per the choice of extension – for instance, F_(2^a)^b or F_(2^b)^a , where a and b are prime. Thus, it makes the implementation of S-boxes over F_2⁶ = F_2^(2×3) very interesting. In this work, we systematically study the composite field structure of F_2⁶ 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_(2²)³ or F_(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_(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.