1. CSN
  2. All Volumes and Issues
  3. Volume 5, Number 1, 2023
  4. Minimization of BITSLICED-representation of 4×4 s-Boxes based on ternary logic instruction

Minimization of BITSLICED-representation of 4×4 s-Boxes based on ternary logic instruction

CSN.
2023;
Volume 5, Number 1
: pp. 103 - 113
https://doi.org/10.23939/csn2023.01.103
Authors:
  1. Yaroslav R. Sovyn
  2. Volodymyr Khoma
  3. Ivan Opirskyy
1
Lviv Polytechnic National University, Lviv, Ukraine
2
Opole University of Technology
3
Lviv Polytechnic National University, Ukraine, Department Information Security

The article is devoted to methods and tools for generating software-oriented bitsliced descriptions of bijective 4×4 S-Boxes with a reduced number of instructions based on a ternary logical instruction. Bitsliced descriptions generated by the proposed method make it possible to improve the performance and security of software implementations of crypto-algorithms using 4×4 S-Boxes on various processor architectures and when designing encryption hardware.

The paper develops a heuristic method of minimization using a ternary logical instruction, which is available in x86-64 processors with support AVX-512 instruction system extension and some GPU processors. Thanks to the combination of various heuristic techniques (preliminary calculations, exhaustive search to a certain depth, 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 was found that the developed method generates a bitsliced description with fewer ternary instructions in 91.1% of cases, compared to the best known method implemented in the sboxgates utility.

bitslicing
ternary logic instruction
AVX-512
4×4 S-Box
CPU
logic minimization
software implementation
sboxgates
speed
  1. E. Biham, “A fast new DES implementation in software,” in International Workshop on Fast Software Encryption, 1997, pp. 260–272. DOI: https://doi.org/10.1007/BFb0052352.
  2. E. Kasper and P. Schwabe, “Faster and timing-attack resistant AES-GCM,” in Proc. 11th International Workshop Cryptographic Hardware and Embedded Systems, 2009, pp. 1–17. DOI: https://doi.org/10.1007/978-3- 642-04138-9_1.
  3. A. Adomnicai and T. Peyrin, “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: https://doi.org/10.46586/tches.v2021.i1.402-425.
  4. P. Schwabe and K. Stoffelen, “All the AES you need on Cortex-M3 and M4,” in International Conference on Selected Areas in Cryptography, 2016, pp. 180–194. DOI: https://doi.org/10.1007/978-3- 319-69453-5_10.
  5. J. Zhang, M. Ma, and P. Wang, “Fast implementation for SM4 cipher algorithm based on bit- slice technology,” in International Conference on Smart Computing and Communication, 2018, pp. 104– 113. DOI: https://doi.org/10.1007/978-3-030-05755-8_11.
  6. N. Nishikawa, H. Amano, and K. Iwai, “Implementation of bitsliced AES encryption on CUDA- enabled GPU,” in International Conference on Network and System Security, 2017, pp. 273–287. DOI: https://doi.org/10.1007/978-3-319-64701-2_20.
  7. S. Matsuda and S. Moriai, “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: https://doi.org/10.1007/978-3-642-33027-8_24.
  8. M. Kwan, “Reducing the Gate Count of Bitslice DES”, IACR Cryptology ePrint Archive, 2000 (51). Available from: http://fgrieu.free.fr/Mattew%20Kwan%20-%20Reducing%20the%20Gate% 20Count%20of%20Bitslice%20DES.pdf [Accessed: 03 October 2023]
  9. K. Stoffelen, "Optimizing S-Box Implementations for Several Criteria Using SAT Solvers", in Proc. 23rd International Conference on Fast Software Encryption, 2016, pp. 140-160. DOI: https://doi.org/10.1007/978-3-662- 52993-5_8.
  10. N. Courtois, T. Mourouzis, and D. Hulme, "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.
  11. J. Jean, T. Peyrin, S. Sim, J. Tourteaux, “Optimizing Implementations of Lightweight Building Blocks”, IACR Transactions on Symmetric Cryptology, 2017(4), 130-168. DOI: https://doi.org/10.13154/tosc.v2017.i4.130-168.
  12. Z. Bao, J. Guo, S. Ling, and Y. Sasaki, “Peigen – a platform for evaluation, implementation, and generation of S-boxes,” IACR Transactions on Symmetric Cryptology, pp. 330–394, 2019. DOI: https://doi.org/10.13154/ tosc.v2019.i1.330-394.
  13. D. Mercadier, “Usuba, Optimizing Bitslicing Compiler”, PhD Thesis, Sorbonne University, France, p. 195, 2020.
  14. M. Dansarie, “sboxgates: A program for finding low gate count implementations of S-boxes”, Journal of Open Source Software, 6(62), 2021, pp. 1-3. DOI: https://doi.org/10.21105/joss.02946.
  15. Ya.  Sovyn,  “Bitsliced  4x4  S-Boxes  Ternary  Instruction  2023”,  2023.  [Online].  Available: https://drive.google.com/drive/folders/1o4GKjb1bIWzHf0H3KmvH--2CxiDNKQmb... [Accessed: 12 October 2023]