Method and utility for minimizing bitsliced representations of 4×4 S-boxes

: pp. 131 - 146
Lviv Polytechnic National University, Lviv, Ukraine
Opole University of Technology
Lviv Polytechnic National University, Ukraine, Department Information Security

The article is devoted to methods and tools for generating bitsliced descriptions of bijective 4×4 S-Boxes with a reduced number of gates/instructions. Bitsliced descriptions generated by the proposed method make it possible to improve the security and performance of both software implementations of cryptoalgorithms using 4×4 S-Boxes on various processor architectures, as well as FPGA and ASIC based hardware.

The paper develops a heuristic method of minimization that uses standard logical instructions AND, OR, XOR, NOT, which are available in most 8/16/32/64-bit processors. Due to the combination of different heuristic techniques (preliminary calculations, exhaustive search to a certain depth, DFS algorithm, refining search) in the method, it was possible to reduce the number of gates in bitsliced descriptions of S-Boxes compared to other known methods. The corresponding software in the form of a utility in the Python language was developed and its operation was tested on 225 S-Boxes of various cryptoalgorithms. It is found that the developed method generates a bitsliced description with a smaller number of gates in 57 % of cases compared to the best known methods implemented in the LIGHTER/Peigen utilities.

  1. Biham E. «A fast new DES implementation in software», in International Workshop on Fast Software Encryption, 1997. Pp. 260–272. DOI:
  2. Kasper E. and Schwabe P. «Faster and timing-attack resistant AES-GCM», in Proc. 11th International Workshop Cryptographic Hardware and Embedded Systems, 2009. Pp. 1–17. DOI: 642-04138-9_1.
  3. Adomnicai A. and Peyrin T. «Fixslicing AES-like ciphers: New bitsliced AES speed records on ARM-Cortex M and RISC-V», IACR Transactions on Cryptographic Hardware and Embedded Systems, 2021(1). Pp. 402–425. DOI:
  4. Schwabe P. and Stoffelen K. «All the AES you need on Cortex-M3 and M4», in International Conference on Selected Areas in Cryptography, 2016. Pp. 180–194. DOI:
  5. Zhang J., Ma M., and Wang P. «Fast implementation for SM4 cipher algorithm based on bit-slice technology», in International Conference on Smart Computing and Communication, 2018. Pp. 104–113. DOI:
  6. Nishikawa N., Amano H., and Iwai K., «Implementation of bitsliced AES encryption on CUDA-enabled GPU», in International Conference on Network and System Security, 2017. Pp. 273–287. DOI:
  7. Matsuda S.and Moriai S. «Lightweight cryptography for the cloud: exploit the power of bitslice implementation», in International Workshop on Cryptographic Hardware and Embedded Systems, 2012. Pp. 408– 425. DOI:
  8. Kwan M. «Reducing the Gate Count of Bitslice DES”, IACR Cryptology ePrint Archive, 2000 (51). URL:  %20Kwan   %20-   %20Reducing   %20the   %20Gate   %20Count   %20of   %20Bitslice%20DES.pdf [accessed: 24 October 2022].
  9. Dansarie M. «sboxgates: A program for finding low gate count implementations of S-boxes”, Journal of Open Source Software, 6(62), 2021. Pp. 1–3. DOI:
  10. Stoffelen K. «Optimizing S-Box Implementations for Several Criteria Using SAT Solvers», in Proc. 23rd International Conference on Fast Software Encryption, 2016. Pp. 140–160. DOI: 52993-5_8.
  11. Courtois N., Mourouzis T. and Hulme D. «Exact logic minimization and multiplicative complexity of concrete algebraic and cryptographic circuits", International Journal On Advances in Intelligent Systemsю Vol. 6. No. 3 and 4. Pp. 165–176, 2013.
  12. Jean J., Peyrin T.,. Sim S, Tourteaux J. «Optimizing Implementations of Lightweight Building Blocks”, IACR Transactions on Symmetric Cryptology, 2017(4), 130–168. DOI:
  13. Bao Z., Guo J., Ling S. and Sasaki Y. «Peigen – a platform for evaluation, implementation, and generation of S- boxes», IACR Transactions on Symmetric Cryptology. Pp. 330–394, 2019. DOI: tosc.v2019.i1.330-394.
  14. Ya. Sovyn, «Bitsliced sbox», 2022. [Online]. URL: 1Ae5lXvzhBcVAEq3VaB8lZvFL-gy_B4ZH?usp=sharing [accessed: 24 October 2022].