UPPER BOUND ON THE COMPLEXITY OF A BITSLICED REPRESENTATION OF BIJECTIVE 4-BIT S-BOXES IN A TERNARY LOGIC BASIS

This paper addresses the logical complexity of bitsliced representations of 4-bit bijective S-boxes – a key non-linear component of lightweight block ciphers used to secure Internet of Things devices and embedded systems. We consider ternary logic instructions, operations capable of computing an arbitrary Boolean function of three variables in a single call, hardware-supported by, in particular, the vpternlogd instruction of the AVX-512 extension. We demonstrate that the logical complexity of the bitsliced description of any bijective 4-bit S-box does not exceed eight ternary instructions, thereby establishing a guaranteed upper bound for the entire class of such transformations. The proof relies on an analysis of the structural properties of this class of S-boxes through the complexity of individual 16-bit vectors and their mutually bijective pairs, with the most complex cases verified by means of GPU-accelerated computation. We further develop a computationally efficient software tool, based on a decomposition-based exhaustive search scheme, that is guaranteed to find the optimal (provably minimal) ternary representation of any given S-box. The method is applied to a number of widely used lightweight S-boxes (Piccolo, Present, GIFT, KLEIN, MIBS, and others), for which the minimal complexity is established and explicit bitsliced descriptions are provided. The proposed approach can be extended to complexity evaluation of S-boxes in other logical bases as well.