Мінімізація BITSLICED-представлення 4×4 S-Boxes на базі тернарної логічної інструкції

Simple item page
dc.citation.epage113
dc.citation.issue1
dc.citation.journalTitleКомп'ютерні системи та мережі
dc.citation.spage103
dc.citation.volume5
dc.contributor.affiliationНаціональний університет “Львівська політехніка”
dc.contributor.affiliationLviv Polytechnic National University
dc.contributor.authorСовин, Я. Р.
dc.contributor.authorХома, В. В.
dc.contributor.authorОпірський, І. Р.
dc.contributor.authorSovyn, Ya.
dc.contributor.authorKhoma, V.
dc.contributor.authorOpirskyy, I.
dc.coverage.placenameЛьвів
dc.coverage.placenameLviv
dc.date.accessioned2025-07-23T09:11:01Z
dc.date.created2023-02-28
dc.date.issued2023-02-28
dc.description.abstractРозглянуто методи і засоби для генерації програмно-орієнтованих bitsliced-описів бієктивних 4×4 S-Boxes зі зменшеною кількістю інструкцій на базі тернарної логічної інструкції. Згенеровані запропонованим методом bitsliced-описи дають змогу підвищити продуктивність та безпеку програмних імплементацій криптоалгоритмів, що використовують 4×4 S-Boxes на різноманітних процесорних архітектурах та під час проєктування апаратних засобів шифрування. Розроблено евристичний метод мінімізації, що використовує тернарну логічну інструкцію, яка доступна в х86-64 процесорах із підтримкою розширення системи команд AVX-512 та деяких GPU-процесорах. Завдяки поєднанню у методі різних евристичних технік (попередніх обчислень, вичерпному пошуку на певну глибину, уточнювальному пошуку) вдалося зменшити кількість вентилів у bitsliced-описах S-Boxes, порівняно з іншими відомими методами. Розроблено відповідне програмне забезпечення у вигляді утиліти мовою Python і протестовано її роботу на 225 S-Boxes різноманітних криптоалгоритмів. Встановлено, що розроблений метод у 91,1% випадках генерує bitsliced-опис із меншою кількістю тернарних інструкцій, порівняно із найкращим відомим сьогодні методом, реалізованим в утиліті sboxgates.
dc.description.abstractThe 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 crypto-algorithms. 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.
dc.format.extent103-113
dc.format.pages11
dc.identifier.citationСовин Я. Р. Мінімізація BITSLICED-представлення 4×4 S-Boxes на базі тернарної логічної інструкції / Я. Р. Совин, В. В. Хома, І. Р. Опірський // Комп'ютерні системи та мережі. — Львів : Видавництво Львівської політехніки, 2023. — Том 5. — № 1. — С. 103–113.
dc.identifier.citationenSovyn Ya. Minimization of BITSLICED-representation of 4×4 S-Boxes based on ternary logic instruction / Ya. Sovyn, V. Khoma, I. Opirskyy // Computer Systems and Networks. — Lviv : Lviv Politechnic Publishing House, 2023. — Vol 5. — No 1. — P. 103–113.
dc.identifier.doidoi.org/10.23939/csn2023.01.103
dc.identifier.urihttps://ena.lpnu.ua/handle/ntb/111628
dc.language.isouk
dc.publisherВидавництво Львівської політехніки
dc.publisherLviv Politechnic Publishing House
dc.relation.ispartofКомп'ютерні системи та мережі, 1 (5), 2023
dc.relation.ispartofComputer Systems and Networks, 1 (5), 2023
dc.relation.references1. E. Biham, “A fast new DES implementation in software”, in International Workshop on Fast Software Encryption, 1997, 260–272. DOI: https://doi.org/10.1007/BFb0052352.
dc.relation.references2. E. Kasper and P. Schwabe, “Faster and timing-attack resistant AES-GCM”, in Proc. 11th International Workshop Cryptographic Hardware and Embedded Systems, 2009, 1–17. DOI: https://doi.org/10.1007/978-3-642-04138-9_1.
dc.relation.references3. 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), 402–425. DOI: https://doi.org/10.46586/tches.v2021.i1.402-425.
dc.relation.references4. P. Schwabe and K. Stoffelen, “All the AES you need on Cortex-M3 and M4” in International Conference on Selected Areas in Cryptography, 2016, 180–194. DOI: https://doi.org/10.1007/978-3-319-69453-5_10.
dc.relation.references5. J. Zhang, M. Ma, and P. Wang, “Fast implementation for SM4 cipher algorithm based on bitslice technology”, in International Conference on Smart Computing and Communication, 2018, 104-113. DOI: https://doi.org/10.1007/978-3-030-05755-8_11.
dc.relation.references6. 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, 273–287. DOI: https://doi.org/10.1007/978-3-319-64701-2_20.
dc.relation.references7. 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, 408–425. DOI: https://doi.org/10.1007/978-3-642-33027-8_24. (51).
dc.relation.references8. M. Kwan, “Reducing the Gate Count of Bitslice DES”, IACR Cryptology ePrint Archive, 2000 Available from: http://fgrieu.free.fr/Mattew%20Kwan%20-%20Reducing%20the%20Gate%20Count%20of%20Bitslice%20DES.pdf [Accessed: 03 October 2023].
dc.relation.references9. K. Stoffelen, “Optimizing S-Box Implementations for Several Criteria Using SAT Solvers”, in Proc. 23rd International Conference on Fast Software Encryption, 2016, 140–160. DOI: https://doi.org/10.1007/978-3-662-52993-5_8.
dc.relation.references10. 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, 165–176, 2013.
dc.relation.references11. 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.
dc.relation.references12. 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, 330–394, 2019. DOI: https://doi.org/10.13154/tosc.v2019.i1.330-394.
dc.relation.references13. D. Mercadier, “Usuba, Optimizing Bitslicing Compiler”, PhD Thesis, Sorbonne University, France, p. 195, 2020.
dc.relation.references14. M. Dansarie, “sboxgates: A program for finding low gate count implementations of S-boxes”, Journal of Open Source Software, 6(62), 2021, 1–3. DOI: https://doi.org/10.21105/joss.02946.
dc.relation.references15. Ya. Sovyn, “Bitsliced 4x4 S-Boxes Ternary Instruction 2023”, 2023. [Online]. Available: https://drive.google.com/drive/folders/1o4GKjb1bIWzHf0H3KmvH--2CxiDNKQmb?usp=drive_link [Accessed: 12 October 2023].
dc.relation.referencesen1. E. Biham, "A fast new DES implementation in software", in International Workshop on Fast Software Encryption, 1997, 260–272. DOI: https://doi.org/10.1007/BFb0052352.
dc.relation.referencesen2. E. Kasper and P. Schwabe, "Faster and timing-attack resistant AES-GCM", in Proc. 11th International Workshop Cryptographic Hardware and Embedded Systems, 2009, 1–17. DOI: https://doi.org/10.1007/978-3-642-04138-9_1.
dc.relation.referencesen3. 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), 402–425. DOI: https://doi.org/10.46586/tches.v2021.i1.402-425.
dc.relation.referencesen4. P. Schwabe and K. Stoffelen, "All the AES you need on Cortex-M3 and M4" in International Conference on Selected Areas in Cryptography, 2016, 180–194. DOI: https://doi.org/10.1007/978-3-319-69453-5_10.
dc.relation.referencesen5. J. Zhang, M. Ma, and P. Wang, "Fast implementation for SM4 cipher algorithm based on bitslice technology", in International Conference on Smart Computing and Communication, 2018, 104-113. DOI: https://doi.org/10.1007/978-3-030-05755-8_11.
dc.relation.referencesen6. 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, 273–287. DOI: https://doi.org/10.1007/978-3-319-64701-2_20.
dc.relation.referencesen7. 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, 408–425. DOI: https://doi.org/10.1007/978-3-642-33027-8_24. (51).
dc.relation.referencesen8. M. Kwan, "Reducing the Gate Count of Bitslice DES", IACR Cryptology ePrint Archive, 2000 Available from: http://fgrieu.free.fr/Mattew%20Kwan%20-%20Reducing%20the%20Gate%20Count%20of%20Bitslice%20DES.pdf [Accessed: 03 October 2023].
dc.relation.referencesen9. K. Stoffelen, "Optimizing S-Box Implementations for Several Criteria Using SAT Solvers", in Proc. 23rd International Conference on Fast Software Encryption, 2016, 140–160. DOI: https://doi.org/10.1007/978-3-662-52993-5_8.
dc.relation.referencesen10. 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, 165–176, 2013.
dc.relation.referencesen11. 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.
dc.relation.referencesen12. 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, 330–394, 2019. DOI: https://doi.org/10.13154/tosc.v2019.i1.330-394.
dc.relation.referencesen13. D. Mercadier, "Usuba, Optimizing Bitslicing Compiler", PhD Thesis, Sorbonne University, France, p. 195, 2020.
dc.relation.referencesen14. M. Dansarie, "sboxgates: A program for finding low gate count implementations of S-boxes", Journal of Open Source Software, 6(62), 2021, 1–3. DOI: https://doi.org/10.21105/joss.02946.
dc.relation.referencesen15. Ya. Sovyn, "Bitsliced 4x4 S-Boxes Ternary Instruction 2023", 2023. [Online]. Available: https://drive.google.com/drive/folders/1o4GKjb1bIWzHf0H3KmvH--2CxiDNKQmb?usp=drive_link [Accessed: 12 October 2023].
dc.relation.urihttps://doi.org/10.1007/BFb0052352
dc.relation.urihttps://doi.org/10.1007/978-3-642-04138-9_1
dc.relation.urihttps://doi.org/10.46586/tches.v2021.i1.402-425
dc.relation.urihttps://doi.org/10.1007/978-3-319-69453-5_10
dc.relation.urihttps://doi.org/10.1007/978-3-030-05755-8_11
dc.relation.urihttps://doi.org/10.1007/978-3-319-64701-2_20
dc.relation.urihttps://doi.org/10.1007/978-3-642-33027-8_24
dc.relation.urihttp://fgrieu.free.fr/Mattew%20Kwan%20-%20Reducing%20the%20Gate%20Count%20of%20Bitslice%20DES.pdf
dc.relation.urihttps://doi.org/10.1007/978-3-662-52993-5_8
dc.relation.urihttps://doi.org/10.13154/tosc.v2017.i4.130-168
dc.relation.urihttps://doi.org/10.13154/tosc.v2019.i1.330-394
dc.relation.urihttps://doi.org/10.21105/joss.02946
dc.relation.urihttps://drive.google.com/drive/folders/1o4GKjb1bIWzHf0H3KmvH--2CxiDNKQmb?usp=drive_link
dc.rights.holder© Національний університет “Львівська політехніка”, 2023
dc.rights.holder© Совин Я. Р., Хома В. В., Опірський І. Р., 2024
dc.subjectbitslicing
dc.subjectтернарна логічна інструкція
dc.subjectAVX-512
dc.subject4×4 S-Box
dc.subjectCPU
dc.subjectлогічна мінімізація
dc.subjectпрограмна імплементація
dc.subjectsboxgates
dc.subjectшвидкодія
dc.subjectbitslicing
dc.subjectternary logic instruction
dc.subjectAVX-512
dc.subject4×4 S-Box
dc.subjectCPU
dc.subjectlogic minimization
dc.subjectsoftware implementation
dc.subjectsboxgates
dc.subjectspeed
dc.subject.udc004.056
dc.subject.udc061.68
dc.titleМінімізація BITSLICED-представлення 4×4 S-Boxes на базі тернарної логічної інструкції
dc.title.alternativeMinimization of BITSLICED-representation of 4×4 S-Boxes based on ternary logic instruction
dc.typeArticle

Files

Original bundle

Now showing 1 - 2 of 2
Thumbnail Image
Name:
2023v5n1_Sovyn_Ya-Minimization_of_BITSLICED_103-113.pdf
Size:
8.55 MB
Format:
Adobe Portable Document Format
Download
Thumbnail Image
Name:
2023v5n1_Sovyn_Ya-Minimization_of_BITSLICED_103-113__COVER.png
Size:
422.58 KB
Format:
Portable Network Graphics
Download

License bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.82 KB
Format:
Plain Text
Description:
Download

Collections

Комп'ютерні системи та мережі. – 2023. – Том 5, № 1