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

doi:10.17223/20710410/68/3

Эндаумент фонд ТГУ!
Впиши своё имя в историю университета
- Сделать пожертвование -

Add to "Quick Collection"

Description	Size	Format
Сложность вычисления некоторых подстановок, имеющих TU-представление	1 MB	Adobe Acrobat PDF	Read	Download
DOI Доступ к ресурсу на сайте издателя			10.17223/20710410/68/3

#подстановки

#комбинационная сложность

#глубина функции

#конструкция типа "бабочка"

#TU-представление

Title: Сложность вычисления некоторых подстановок, имеющих TU-представление
Title: Computational work for some TU-based permutations
Creator: Фомин, Денис Бониславович
|
Трифонов, Дмитрий Игоревич
Date: 2025
DOI: 10.17223/20710410/68/3
Description: Рассматривается проблема оценки вычислительной сложности определенных классов подстановок, обладающих TU-представлением. В качестве метрик выбраны комбинационная сложность и глубина функции, задающей данную подстановку. Для получения оценок исследуется представление элементов поля в различных базисах: полиномиальном, нормальном, смешанном, а также с использованием PRR- и RRB-представлений элементов поля. Основное внимание уделяется анализу различных представлений элементов поля и их влиянию на вычислительную сложность. Комбинационная сложность оценивается на основе количества элементарных операций, необходимых для реализации подстановки; глубина функции определяется как максимальное количество логических уровней в схеме. Изучение различных базисов позволяет выявить наиболее эффективные способы представления, способствующие минимизации вычислительной сложности. В качестве примера приводится оценка указанных характеристик для подстановки пространства F|8,2, используемой в отечественных стандартизированных симметричных криптографических алгоритмах. Получена минимальная из известных оценка комбинационной сложности, равная 169.