Paper 2026/1875

Equivalence Classes of BOGI-Based Ciphers for Differential and Linear Cryptanalysis

Abstract

BOGI-based ciphers extend the design space of GIFT by combining 4-bit S-boxes with bit permutations satisfying the ``Bad Output must go to Good Input'' principle. Prior work reduced this space to 41,472 parameter representatives, but did not determine whether their complete differential and linear trail spaces were distinct. We define DC/LC-equivalence in terms of weight-preserving bijections between the differential and linear trail sets of two ciphers for an arbitrary number of rounds, and give sufficient conditions based on permutation characteristics and trail reversal. For each pair of mixing permutations and each 4-bit permutation, we decide exactly whether the required initial word permutation exists. The relations generated by these transformations and trail reversal partition the 41,472 ciphers into 864 classes of size 48 for BOGI-64 and 5,184 classes of size 8 for BOGI-128. Using the BOGI-128 classification, we perform differential and linear best-trail searches through round 20, completing both searches for 5,081 classes. These results and additional threshold decisions show that the earliest round at which both best-trail weights reach 128 bits is round 19, attained by at least 59 classes. The class containing GIFT-128 reaches both thresholds at round 22. Thus, at least 59 classes reach both thresholds three rounds earlier than the GIFT-128 class. We also compare selected BOGI-64 and BOGI-128 instances with GIFT in hardware and software. The resulting security and implementation data can support component selection in future GIFT-based primitives.