The problem of evaluating the computational complexity of certain classes of substitutions with a TU-representation is considered. The metrics used include combinatorial complexity and the depth of the function that defines the substitution. To obtain these evaluations, the representation of field elements in various bases is investigated, including polynomial, normal, mixed, as well as PRR and RRB representations. The primary focus is on analyzing different representations of field elements and their impact on computational complexity. The combinatorial complexity is assessed based on the number of elementary operations required to implement the substitution, while the function depth is determined by the maximum number of logical levels in the circuit. The use of different bases allows us to identify the most effective representation methods that help minimize computational complexity. As an example, we provide an evaluation of the specified characteristics for the substitution used in Russian standardized symmetric algorithms. The lowest known estimate of combinatorial complexity has been obtained, which equals 169.
Download file
Counter downloads: 6
- Title Computational work for some TU-based permutations
- Headline Computational work for some TU-based permutations
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 68
- Date:
- DOI 10.17223/20710410/68/3
Keywords
permutation, combinational complexity, circuit depth, butterfly, TU-decompositionAuthors
References
Ullrich M., De Canni'ere, C., Indesteege S., et al. Finding Optimal Bitsliced Implementations of 4 x 4-bit S-boxes. Ecrypt II. 2011. http://skew2011.mat.dtu.dk/proceedings/Finding_Optimal_Bitsliced_Implementations_of_4_to_04-bit_S-boxes.pdf.
Чичаеѳа А. А. Поиск эффективно реализуемых подстановок с оптимальными криптографическими характеристиками. Рускрипто'21. Солнечногорск, 2021. https://ruscrypto.ru/resource/archive/rc2021/files/02_chichayeva.pdf.
Jean J., Peyrin T., Sim S. M., and Tourteaux J. Optimizing implementations of lightweight building blocks // IACR Trans. Symmetric Crvptol. 2017. V. 4. P. 130-168.
Rudell R. L. Multiple-Valued Logic Minimization for PLA Synthesis. Technical Report. EECS Department, University of California, 1986. https://www2.eecs.berkeley.edu/Pubs/TechRpts/1986/ERL-86-65.pdf.
Hlavicka J. and Ficer P. A heuristic Boolean minimizer // Proc ICCAD'01. San Jose, California, 2001. P.439-442.
Avraamova O. D., Fomin D. B., Serov V. A., et al. A compact bit-sliced representation of Kuznvechik S-box j j Ma гем. вопр. криптогр. 2021. T. 12. №2. С. 21-38.
Dansarie М. sboxgates: A program for Ending low gate count implementations of s-boxes // J. Open Source Software. 2021. No.6(62). https://joss.theoj.org/papers/.
Nogami Y., Nekado K., Toyota T., et al. Mixed bases for efficient inversion in GF((22)2)2 and conversion matrices of subbvtes of AES // LNCS. 2010. V.6225. P.234-247.
Turan M. S., McKay K., Chang D., et al. Status Report on the Second Round of the NIST Lightweight Cryptography Standardization Process. NIST, 2021.
Сэвидж Д. Э. Сложность вычислений. M.: Факториал, 1998. 368 с.
M. Morris R. Mano, Charles R. Kime Logic and Computer Design Fundamentals. Prentice Hah Press, 2007. 672 p.
Boot T.L. Digital Networks and Computer Systems. N.Y.: Wiley, 1971. 451 p.
Лупапов О. Б. О реализации функции алгебры логики формулами из конечных классов (формулами ограниченной глубины) в базисе &, V,_// Проблемы кибернетики. 1961. Т. 6. С. 5-14.
Canteaut A. and Perrin L. On CCZ-equivalence, extended-affine equivalence, and function twisting // Finite Fields Appl. 2018. V.56. P.209-246.
Olofsson M. VLSI Aspects on Inversion in Finite Fields. PhD Thesis. Linkoping, Sweden, 2002.
Drolet G. A new representation of elements of finite fields GF(2m) yielding small complexity arithmetic circuits // IEEE Trans.Computers. 1998. V. 47. No. 9. P.938-946.
Wu H. Low complexity bit-parallel Unite held arithmetic using polynomial basis // LNCS. 1999. V. 1717. P.280-291.
Ueno R., Нотта N., Nogami Y., et al. Highly efficient GF(28) inversion circuit based on hybrid GF representations // J. Crvptogr. Engin. 2019. V. 9. No. 2. P. 101-113.
Nekado K., Nogami Y., and Iokibe K. Very short critical path implementation of AES with direct logic gates // LNCS. 2012. V. 7631.'P. 51-68.
Fomin D. B. New classes of 8-bit permutations based on a butterfly structure // Матем. вопр. криптогр. 2019. T. 10. №2. С. 169-180.
Фомин Д. Б. Построение подстановок пространства V2m с использованием (2m,m)-функций // Матем. вопр. криптогр. 2020. Т. 11. №3. С. 121-138.
Фомин Д. Б. Об алгебраической степени и дифференциальной равномерности подстановок пространства построенных с использованием (2m, ш)-функций // Матем. вопр. криптогр. 2020. Т. 11. №4. С. 133-149.
Fomin D. В. and Kovrizhnykh М. A. On differential uniformity of permutations derived using a generalized construction // Матем. вопр. криптогр. 2022. T. 13. №2. С. 37-52.
Фомин Д. Б., Трифонов Д. И. Об аппаратной реализации одного класса байтовых подстановок // Прикладная дискретная математика. Приложение. 2019. №12. С. 134-137.
Rebeiro С., Selvakumar A. D., and Devi A. S. L. Bitslice implementation of AES // LNCS. 2006. V.4301. P.203-212.
Grosso V., Leurent G., Standaert F., and Varici K. LS-designs: Bitslice encryption for efficient masked software implementations // LNCS. 2014. V. 8540. P. 18-37.
Коврижных M. А., Фомин Д. Б. Об эвристическом алгоритме построения подстановок с заданными криптографическими характеристиками с использованием обобщённой конструкции // Прикладная дискретная математика. 2022. Т. 57. С. 5-21.
Saarinen M.-J. О. Cryptographic analysis of all 4 x 4-bit S-Boxes // LNCS. 2011. V. 7118. P.118-133.
Biryukov A., Perrin L., and Udovenko A. Reverse-engineering the S-Box of Streebog, Kuznvechik and STRIBOBrl // LNCS. 2016. V.9665. P.372-402.
De la Cruz Jimenez R. A. Generation of 8-bit s-boxes having almost optimal cryptographic properties using smaller 4-bit s-boxes and finite field multiplication // LNCS. 2017. V. 11368. P. 191-206.
Lidl R. and Niederreiter H. Finite Fields. Cambridge: Cambridge University Press, 1997. 755 p.
Canright D. A very compact s-box for AES // LNCS. 2005. V. 3659. P.441-455.
Morioka S. and Satoh A An optimized s-box circuit architecture for low power AES design // LNCS. 2002. V. 2523. P. 172-186.
Itoh T. and Tsujii S. A fast algorithm for computing multiplicative inverses in GF(2m) using normal bases // Information and Computation. 1988. V. 78. No. 3. P.171-177.
Puente O.C., Leal R.F., and de la Cruz Jimenez R. A. On the Bit-Slice Representations of Some Nonlinear Bijective Transformations. CTCrvpt'23. Волгоград, 2023. https://ctcrypt.ru/files/files/2023/08/03.pdf.
Puente O.C., Leal R.F., and de la Cruz Jimenez R. A. On the Bit-Slice representations of some nonlinear bijective transformations // Матем. вопр. криптогр. 2024. T. 15. №1. С.97-125.
Computational work for some TU-based permutations | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2025. № 68. DOI: 10.17223/20710410/68/3
Download full-text version
Counter downloads: 68