Теоретические основы прикладной дискретной математики

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

Д. Б. Фомин^a, Д. И. Трифонов<sup>b

a</sup> Академия криптографии Российской Федерации, г. Москва, Россия
^b Технический комитет по стандартизации «Криптографическая защита информации», г. Москва, Россия

Аннотация: Рассматривается проблема оценки вычислительной сложности определённых классов подстановок, обладающих $TU$-представлением. В качестве метрик выбраны комбинационная сложность и глубина функции, задающей данную подстановку. Для получения оценок исследуется представление элементов поля в различных базисах: полиномиальном, нормальном, смешанном, а также с использованием PRR- и RRB-представлений элементов поля. Основное внимание уделяется анализу различных представлений элементов поля и их влиянию на вычислительную сложность. Комбинационная сложность оценивается на основе количества элементарных операций, необходимых для реализации подстановки; глубина функции определяется как максимальное количество логических уровней в схеме. Изучение различных базисов позволяет выявить наиболее эффективные способы представления, способствующие минимизации вычислительной сложности. В качестве примера приводится оценка указанных характеристик для подстановки пространства $\mathbb{F}_2^8$, используемой в отечественных стандартизированных симметричных криптографических алгоритмах. Получена минимальная из известных оценка комбинационной сложности, равная $169$.

Ключевые слова: подстановка, комбинационная сложность, глубина функции, конструкция типа «бабочка», $TU$-представление.

УДК: 519.719.2

DOI: 10.17223/20710410/68/3