ГлавнаяАрхивСложность вычисления некоторых подстановок, имеющих TU-представление

Сложность вычисления некоторых подстановок, имеющих TU-представление | Прикладная дискретная математика. 2025. № 68. DOI: 10.17223/20710410/68/3

Рассматривается проблема оценки вычислительной сложности определённых классов подстановок, обладающих TU-представлением. В качестве метрик выбраны комбинационная сложность и глубина функции, задающей данную подстановку. Для получения оценок исследуется представление элементов поля в различных базисах: полиномиальном, нормальном, смешанном, а также с использованием PRR- и RRB-представлений элементов поля. Основное внимание уделяется анализу различных представлений элементов поля и их влиянию на вычислительную сложность. Комбинационная сложность оценивается на основе количества элементарных операций, необходимых для реализации подстановки; глубина функции определяется как максимальное количество логических уровней в схеме. Изучение различных базисов позволяет выявить наиболее эффективные способы представления, способствующие минимизации вычислительной сложности. В качестве примера приводится оценка указанных характеристик для подстановки пространства F82, используемой в отечественных стандартизированных симметричных криптографических алгоритмах. Получена минимальная из известных оценка комбинационной сложности, равная 169.
  • Title Сложность вычисления некоторых подстановок, имеющих TU-представление
  • Headline Сложность вычисления некоторых подстановок, имеющих TU-представление
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 68
  • Date:
  • DOI 10.17223/20710410/68/3
Ключевые слова
подстановка, комбинационная сложность, глубина функции, конструкция типа «бабочка», TU-представление
Авторы
Ссылки
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.
Сложность вычисления некоторых подстановок, имеющих <i>TU</i>-представление | Прикладная дискретная математика. 2025. № 68. DOI: 10.17223/20710410/68/3
Сложность вычисления некоторых подстановок, имеющих TU-представление | Прикладная дискретная математика. 2025. № 68. DOI: 10.17223/20710410/68/3