Характеризация полуинволютивных MDS-матриц

Основная информация

• ID статьи: 2406.12842
• Название: A Characterization of Semi-Involutory MDS Matrices
• Авторы: Tapas Chatterjee (Indian Institute of Technology Ropar), Ayantika Laha (Indian Institute of Technology Ropar)
• Классификация: cs.CR (Криптография и безопасность)
• Дата публикации: 1 января 2025 г. (версия 2)
• Ссылка на статью: https://arxiv.org/abs/2406.12842

Аннотация

В симметричной криптографии матрицы максимального расстояния разделения (MDS) с простыми обратными матрицами имеют широкое применение. Многие блочные шифры, такие как AES, SQUARE, SHARK, а также хеш-функции, такие как PHOTON, используют MDS-матрицы в слое диффузии. В данной работе сначала характеризуются все 3×3 неприводимые полуинволютивные матрицы над конечными полями характеристики 2. На основе этой характеризации матриц мы предоставляем необходимые и достаточные условия для построения MDS полуинволютивных матриц, используя только диагональные элементы и элементы связанных диагональных матриц. Наконец, мы вычисляем количество 3×3 полуинволютивных MDS-матриц над произвольными конечными полями характеристики 2.

Исследовательский контекст и мотивация

Предпосылки проблемы

1. Важность слоя диффузии: В симметричной криптографии концепция "путаницы и диффузии", предложенная Шенноном, является основой криптографического проектирования. Слой диффузии отвечает за скрытие связи между шифротекстом и открытым текстом, а MDS-матрицы благодаря своему максимальному коэффициенту ветвления обеспечивают совершенную диффузию.
2. Требования вычислительной эффективности: В приложениях легковесной криптографии требуется не только обеспечение безопасности MDS-матрицами, но и эффективная реализация их обратных матриц. Инволютивные матрицы (A² = I) привлекают внимание благодаря тому, что их обратная матрица совпадает с самой матрицей.
3. Ограничения существующих методов:
   • Пространство поиска инволютивных MDS-матриц относительно ограничено
   • Циклические инволютивные матрицы определённых размеров не существуют
   • Требуется более широкий класс матриц для расширения вариантов проектирования

Мотивация исследования

В данной работе вводятся полуинволютивные матрицы как обобщение инволютивных матриц, определяемые как матрицы, для которых существуют невырожденные диагональные матрицы D₁ и D₂ такие, что M⁻¹ = D₁MD₂. Это обобщение значительно расширяет класс матриц, доступных для криптографического проектирования.

Основные вклады

1. Теоретическая характеризация: Полная характеризация структуры всех 3×3 неприводимых полуинволютивных матриц над конечными полями характеристики 2
2. Метод построения: Предоставление необходимых и достаточных условий для построения 3×3 полуинволютивных MDS-матриц, используя только 6 параметров (3 диагональных элемента + 3 элемента связанной диагональной матрицы)
3. Результаты подсчёта: Точное вычисление количества 3×3 полуинволютивных MDS-матриц над F₂ᵐ как (2ᵐ-1)⁵(2ᵐ-2)(2ᵐ-4)
4. Обобщение существующих результатов: Расширение результатов Güzel и др. об инволютивных MDS-матрицах на более широкий класс полуинволютивных матриц

Подробное описание методов

Определение задачи

Исследование 3×3 матриц A над конечными полями F₂ᵐ характеристики 2, требующих:

• Полуинволютивность: Существование невырожденной диагональной матрицы D такой, что ADA является диагональной матрицей
• MDS-свойство: Все квадратные подматрицы матрицы A невырождены
• Неприводимость: Матрица A не может быть приведена к редуцированной форме путём перестановочного подобия

Основные теоремы

Теорема 4.1 (Характеризация структуры)

Пусть A — 3×3 неприводимая полуинволютивная матрица со связанной диагональной матрицей D = diag(d₁,d₂,d₃), тогда внедиагональные элементы могут быть представлены как:

• a₁₂ = (a₁₁d₁ + a₃₃d₃)d₂⁻¹x
• a₁₃ = (a₁₁d₁ + a₂₂d₂)d₃⁻¹xy
• a₂₁ = (a₂₂d₂ + a₃₃d₃)d₁⁻¹x⁻¹
• a₂₃ = (a₂₂d₂ + a₁₁d₁)d₃⁻¹y
• a₃₁ = (a₃₃d₃ + a₂₂d₂)d₁⁻¹(xy)⁻¹
• a₃₂ = (a₃₃d₃ + a₁₁d₁)d₂⁻¹y⁻¹

где x,y ∈ F₂ᵐ* — ненулевые элементы.

Теорема 4.5 (Необходимые и достаточные условия MDS)

Матрица A указанной структуры является полуинволютивной MDS-матрицей тогда и только тогда, когда:

• a₁₁d₁ + a₂₂d₂ ≠ 0
• a₁₁d₁ + a₃₃d₃ ≠ 0
• a₂₂d₂ + a₃₃d₃ ≠ 0
• a₁₁d₁ + a₂₂d₂ + a₃₃d₃ ≠ 0

Технические инновации

1. Унифицированная структура: Представление инволютивных матриц как частного случая полуинволютивных матриц, обеспечивающее унифицированную аналитическую структуру
2. Параметризованное построение: Полная характеризация 3×3 полуинволютивных MDS-матриц через 8 параметров, значительно упрощающая пространство поиска
3. Техники подсчёта: Использование принципа включения-исключения для точного подсчёта количества параметрических комбинаций, удовлетворяющих условиям

Экспериментальная установка

Теоретическая верификация

Работа в основном является теоретической, с верификацией результатов на конкретных примерах:

Пример 4.6: Построение полуинволютивной MDS-матрицы над F₂₄

• Порождающий полином: x⁴ + x³ + 1
• Выбор параметров: a₁₁=1, a₂₂=α, a₃₃=α², d₁=α, d₂=α, d₃=α³+1, x=1, y=α
• Верификация выполнения всех условий MDS

Верификация подсчёта

Проверка формулы подсчёта на конкретных вычислениях:

• F₂₂: 0 полуинволютивных MDS-матриц
• F₂₃: 403,368 полуинволютивных MDS-матриц
• F₂₄: 127,575,000 полуинволютивных MDS-матриц

Экспериментальные результаты

Основные результаты

1. Структурная полнота: Успешная характеризация структуры всех 3×3 полуинволютивных матриц, доказывающая их полное определение 8 параметрами
2. Определение MDS-свойства: Предоставление лаконичных условий для определения, когда полуинволютивная матрица обладает MDS-свойством
3. Рост количества: Значительное увеличение количества полуинволютивных MDS-матриц по сравнению с инволютивными MDS-матрицами:
   • Инволютивные MDS-матрицы над F₂₃: 1,176
   • Полуинволютивные MDS-матрицы над F₂₃: 403,368 (рост примерно в 343 раза)

Теоретические открытия

1. Обобщающий характер: Полуинволютивность действительно обобщает инволютивность, существуют полуинволютивные, но не инволютивные MDS-матрицы
2. Вычислительные преимущества: Обратная матрица полуинволютивной MDS-матрицы по-прежнему может быть получена путём простого умножения на диагональную матрицу, сохраняя вычислительную эффективность
3. Существование: Над F₂₂ не существует полуинволютивных MDS-матриц, удовлетворяющих условиям, однако над F₂ᵐ (m≥3) существует большое количество таких матриц

Связанные работы

Историческое развитие

1. Исследование инволютивных матриц: Youssef и др. (2007) впервые ввели инволютивные линейные преобразования в криптографию
2. Методы построения MDS: Gupta и Ray (2013) предоставили различные методы построения MDS-матриц
3. Ограничения циклических матриц: Gupta и др. доказали несуществование циклических инволютивных матриц
4. Концепция полуинволютивности: Cheon и др. (2021) ввели концепцию полуинволютивных матриц

Вклад данной работы

По сравнению с существующими работами, данная статья:

• Впервые применяет концепцию полуинволютивности к построению MDS-матриц
• Предоставляет более широкое пространство проектирования по сравнению с инволютивными матрицами
• Даёт точные результаты подсчёта

Заключение и обсуждение

Основные выводы

1. Полная характеризация алгебраической структуры 3×3 полуинволютивных матриц
2. Установление связи между полуинволютивностью и MDS-свойством
3. Доказательство практической ценности полуинволютивных MDS-матриц в криптографическом проектировании

Ограничения

1. Ограничение по размерности: Текущие результаты применимы только к матрицам размера 3×3
2. Ограничение по характеристике: Теория в основном ориентирована на конечные поля характеристики 2
3. Неприводимость: Требуется неприводимость матрицы

Направления будущих исследований

1. Обобщение на матрицы более высокой размерности (особенно чётного порядка или порядка, являющегося степенью 2)
2. Исследование случаев конечных полей других характеристик
3. Изучение приложений полуинволютивных матриц в практических криптографических системах

Глубокая оценка

Достоинства

1. Теоретическая полнота: Предоставление полной характеризации 3×3 полуинволютивных MDS-матриц с строгими теоретическими результатами
2. Практическая ценность: Предоставление новых инструментов для криптографического проектирования, расширение пространства проектирования
3. Вычислительная эффективность: Сохранение простоты вычисления обратной матрицы, пригодность для легковесных приложений
4. Точный подсчёт: Предоставление точного количества существующих матриц, способствующее случайному выбору

Недостатки

1. Ограничение по размерности: Рассмотрение только матриц размера 3×3, обобщение на более высокие размерности остаётся открытой проблемой
2. Сложность построения: Хотя предоставлена параметризованная форма, практическое построение всё ещё требует выполнения нескольких условий ограничения
3. Верификация приложений: Отсутствие анализа безопасности в практических криптографических системах

Влияние

1. Теоретический вклад: Предоставление новых идей для теории матриц над конечными полями
2. Криптографические приложения: Предоставление новых кандидатов матриц для проектирования легковесных шифров
3. Методологические инновации: Методы подсчёта могут быть обобщены на другие аналогичные задачи

Сценарии применения

1. Легковесная криптография: Применение при проектировании блочных шифров в средах с ограниченными ресурсами
2. Хеш-функции: Использование при построении хеш-функций, требующих эффективного слоя диффузии
3. Теоретические исследования: Предоставление основы для дальнейшего исследования случаев более высокой размерности

Библиография

Статья цитирует 25 связанных источников, включая в основном:

• Фундаментальные работы Шеннона по теории криптографии
• Классические криптографические алгоритмы, такие как AES
• Важные теоретические результаты по построению MDS-матриц
• Последние достижения в исследовании полуинволютивных матриц

Данная работа достигает существенного прогресса на основе существующей теории, обеспечивая прочную основу для теории и приложений полуинволютивных MDS-матриц.