Classification of 4-bit S-Boxes for BOGI Permutation

Abstract

Bad Output must go to Good Input (BOGI) is the primary design strategy of GIFT, a lightweight block cipher that was presented at CHES 2017. Because this strategy obviates the need to adhere to the required conditions of S-boxes when adopting bit-permutation, cryptographic designers have more S-box choices. In this paper, we classify all 4-bit S-boxes that support BOGI, called ``BOGI-applicable S-boxes,'' and evaluate them in terms of the cryptographic strength and efficiency. First, we exhaustively show that only 2413 Permutation-XOR-Equivalence (PXE) classes over 4-bit S-boxes are BOGI-applicable. After refining the PXE classes with respect to the differential uniformity (U) and linearity (L), we suggest 20 "Optimal BOGI-applicable'' PXE classes that provide the best (U, L). Our security evaluations revealed that all optimal BOGI-applicable S-boxes fulfill the security properties considered by the designers of GIFT and that the differences between them exist in the other properties. Moreover, we explore the resistance of GIFT variants against differential and linear cryptanalysis by replacing the existing S-box with other optimal BOGI-applicable S-boxes. Based on the results, we identify the best attainable resistance with the bitpermutation of GIFT-64. Lastly, we suggest notable S-boxes that support competitive performance, jointly considering the cryptographic strength and efficiency for GIFT-64 and GIFT-128 structures, respectively.