О спектрах Уолша квадратичных APN функций

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

• ID статьи: 2510.12008
• Название: On the Walsh spectra of quadratic APN functions
• Авторы: Sophie Hannah Bénéteau (Университет Флориды), Nicolas Goluboff (Университет Массачусетса Амхёрст), Lukas Kölsch (Университет Южной Флориды), Divyesh Vaghasiya (Университет Южной Флориды)
• Классификация: math.CO cs.IT math.IT
• Дата публикации: 15 октября 2025 г. (препринт arXiv)
• Ссылка на статью: https://arxiv.org/abs/2510.12008

Аннотация

APN (Almost Perfect Nonlinear) функции играют центральную роль в проектировании блочных шифров и являются оптимальными функциями для защиты от дифференциальных атак. Одним из наиболее важных свойств APN функций является их линейность, которая напрямую связана со спектром Уолша функции. В данной работе устанавливаются две новые связи, позволяющие вывести сильные условия на спектр Уолша квадратичных APN функций. Статья доказывает, что преобразование Уолша квадратичной APN функции $F$, действующей на $n=2k$ битах, однозначно связано с разбиением векторного пространства $\mathbb{F}_2^n$ и специфическими блокирующими множествами в соответствующем проективном пространстве $PG(n-1,2)$. Эти связи позволяют доказать множество результатов о спектре Уолша функции $F$, например, что $F$ может иметь не более одной компонентной функции с амплитудой больше $2^{\frac{3}{4}n}$, и найти первую нетривиальную верхнюю границу для количества изогнутых компонентных функций квадратичных APN функций.

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

Важность проблемы

1. Криптографические приложения: APN функции являются ключевыми строительными блоками при проектировании симметричных криптосистем, особенно в сетях подстановки-перестановки (SPN) блочных шифров, обеспечивая оптимальную устойчивость к дифференциальным атакам.
2. Теоретические вызовы: Хотя распределение амплитуд квадратичных APN функций в случае нечётной размерности полностью определено (все нетривиальные компоненты имеют амплитуду $2^{\frac{n+1}{2}}$), случай чётной размерности остаётся открытой проблемой.
3. Существующие ограничения:
   • Для чётного $n$ единственное известное ограничение на амплитуду получается из характеризации четвёртого момента преобразования Уолша
   • Отсутствуют нетривиальные границы для количества изогнутых компонентных функций квадратичных APN функций
   • Недостаточно глубокого понимания структуры спектра Уолша

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

Данная работа направлена на глубокое понимание структурных свойств спектра Уолша квадратичных APN функций путём установления новых связей между этими функциями и геометрическими объектами (разбиениями векторного пространства и блокирующими множествами), а также вывода более сильных ограничивающих условий.

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

1. Установление связи с разбиениями векторного пространства: Доказано взаимно однозначное соответствие между распределением амплитуд квадратичной APN функции $F: \mathbb{F}_2^n \to \mathbb{F}_2^n$ (где $n$ чётно) и разбиениями векторного пространства $\mathbb{F}_2^n$.
2. Построение теории блокирующих множеств: Доказано, что множество нетривиальных неизогнутых компонентных функций $N_F$ образует специальное блокирующее множество в проективном пространстве $PG(n-1,2)$.
3. Вывод новых ограничивающих условий:
   • Доказано, что $F$ может иметь не более одной компонентной функции с амплитудой больше $2^{\frac{3}{4}n}$
   • Установлена первая нетривиальная верхняя граница для количества изогнутых компонентных функций
   • Предоставлены необходимые условия для CCZ эквивалентности функции перестановке
4. Полный анализ малых размерностей: Проведён полный анализ для размерностей 6, 8, 10, определены все возможные распределения амплитуд.

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

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

Исследование структуры спектра Уолша квадратичной APN функции $F: \mathbb{F}_2^n \to \mathbb{F}_2^n$ (где $n$ чётно), где:

• Входные данные: квадратичная APN функция $F$
• Выходные данные: ограничивающие условия и структурные свойства спектра Уолша
• Цель: понимание возможностей и ограничений распределения амплитуд

Основная теоретическая база

1. Теория разбиений векторного пространства

Определение дифференциальной функции: Для ненулевого $a \in \mathbb{F}_2^n$ определяется $D_{F,a}(x) = F(x) + F(x+a)$.

Построение векторных пространств: Определяются

• $T_b = \{a \in \mathbb{F}_2^n : \text{Im}(D_{F,a}) = H_b\} \cup \{0\}$
• $\overline{T_b} = \{a \in \mathbb{F}_2^n : \text{Im}(D_{F,a}) = \overline{H_b}\}$
• $V_b = T_b \cup \overline{T_b}$

где $H_b = \{x \in \mathbb{F}_2^n : \langle b,x \rangle = 0\}$.

Основная теорема (Теорема 2.4): Амплитуда $F_b$ равна $2^{\frac{n+\dim(V_b)}{2}}$.

2. Теория блокирующих множеств

Свойства блокирующих множеств: Множество нетривиальных неизогнутых компонентных функций $N_F$ образует блокирующее множество в $PG(n-1,2)$ относительно $(n/2)$-пространств, причём размер пересечения с каждым $(n/2)$-пространством нечётен.

Ключевой результат: Применение теоремы Govaerts-Storme о размере минимальных нетривиальных блокирующих множеств позволяет получить верхнюю границу для количества изогнутых компонентных функций.

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

1. Геометризация метода: Впервые задача о спектре Уолша квадратичных APN функций преобразована в геометрическую задачу о разбиениях векторного пространства и блокирующих множествах.
2. Структурная характеризация: Амплитуда компонентной функции $F_b$ непосредственно определяется через $\dim(V_b)$, устанавливая прямую связь между алгебраической структурой и спектральными свойствами.
3. Междисциплинарное применение: Искусное применение глубокой теории разбиений векторного пространства и блокирующих множеств из конечной геометрии.

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

Методы теоретической верификации

Работа является в основном теоретическим исследованием, результаты проверяются следующим образом:

1. Полный анализ малых размерностей:
   • Размерность 6: верификация того, что все возможные типы разбиений векторного пространства соответствуют известным квадратичным APN функциям
   • Размерность 8: определение 18 возможных распределений амплитуд
   • Размерность 10: анализ всех теоретически возможных случаев
2. Верификация известных функций:
   • Проверка классических функций со спектром Уолша
   • Анализ функций с максимальной линейностью
   • Верификация свойств блокирующих множеств для функции $x^3$

Вычислительные инструменты

Статья использует компьютерную верификацию для:

• Перечисления всех возможных разбиений векторного пространства в случае малых размерностей
• Проверки согласованности теоретических результатов с известными APN функциями

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

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

1. Ограничения на амплитуды (Теорема 2.10)

Результат: Пусть $n$ чётно, $F: \mathbb{F}_2^n \to \mathbb{F}_2^n$ — квадратичная APN функция, линейность $L(F) = 2^{\frac{n+l}{2}}$ и $l > n/2$, тогда:

• $F$ имеет ровно одну компонентную функцию с амплитудой $2^{\frac{n+l}{2}}$
• Все остальные компоненты имеют амплитуду не более $2^{\frac{2n-l}{2}}$
• В частности, любая квадратичная APN функция имеет не более одной компонентной функции с амплитудой больше $2^{\frac{3n}{4}}$

2. Верхняя граница для изогнутых компонентных функций (Теорема 3.9)

Результат: Пусть $n \geq 6$ чётно, $F: \mathbb{F}_2^n \to \mathbb{F}_2^n$ — квадратичная APN функция, тогда: $|N_F| \geq 2^{n/2} + 2^{n/2-2} + 2^{n/2-3} - 1$ где равенство возможно только при $n=8$.

3. Полная классификация для размерности 8 (Теорема 4.5)

Для $F: \mathbb{F}_2^8 \to \mathbb{F}_2^8$ квадратичной APN функции возможные распределения амплитуд:

• $[0^{190}, 2^{64}, 6^1]$
• $[0^{238-4i}, 2^{5i}, 4^{17-i}]$, где $1 \leq i \leq 17$

Анализ чувствительности

1. Сравнение границ (Предложение 4.4)

Сравнение трёх различных нижних границ для $|N_F|$:

• Граница разбиения векторного пространства: наиболее сильная при $k < n/2$
• Граница блокирующего множества: наиболее сильная при $k = n/2$
• Граница размерности: наиболее сильная при $k > n/2$

2. Анализ эквивалентности

Доказано, что при EA эквивалентности:

• Разбиения векторного пространства сохраняют эквивалентность (Теорема 5.2)
• Блокирующие множества сохраняют эквивалентность (Теорема 5.1)

Важные находки

1. Структурные ограничения: Спектр Уолша квадратичных APN функций подчиняется строгим геометрическим ограничениям и не является произвольным.
2. Эффект размерности: С увеличением размерности количество возможных распределений амплитуд резко уменьшается.
3. Условия CCZ эквивалентности: Если квадратичная функция CCZ эквивалентна перестановке, то $|N_F| \geq 3(2^{n/2} - 1)$.

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

Основные направления исследований

1. Классификация APN функций: Работы Carlet, Charpin, Zinoviev и др.
2. Теория спектра Уолша: Методы четвёртого момента и границы линейности
3. Разбиения векторного пространства: Теория конструкций Heden, Bu и др.
4. Теория блокирующих множеств: Оптимальные границы Govaerts-Storme

Преимущества данной работы

• Впервые установлена прямая связь между спектром Уолша и геометрическими объектами
• Предоставлены более сильные ограничивающие условия по сравнению с классическим методом четвёртого момента
• Объединены алгебраический и геометрический подходы

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

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

1. Спектр Уолша квадратичных APN функций обладает глубокой геометрической структурой
2. Разбиения векторного пространства и блокирующие множества предоставляют мощные инструменты для понимания спектра Уолша
3. Большинство теоретически возможных распределений амплитуд не реализуются на практике

Ограничения

1. Конструктивные проблемы: Теория исключает множество возможностей, но не предоставляет новых методов конструирования
2. Ограничения по размерности: Основные результаты сосредоточены на чётных размерностях
3. Вычислительная сложность: Полный анализ для высоких размерностей остаётся сложной задачей

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

Статья предлагает 6 открытых проблем, включая:

1. Поиск примеров отсутствующих распределений амплитуд в размерности 8
2. Улучшение границ для $|N_F|$
3. Поиск дополнительных нереализуемых типов разбиений векторного пространства

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

Достоинства

1. Теоретическая новизна: Установлена совершенно новая геометрическая перспектива для понимания спектра Уолша
2. Систематичность методов: Систематическое исследование с двух углов зрения — разбиений векторного пространства и блокирующих множеств
3. Глубина результатов: Получены несколько первых нетривиальных границ
4. Полнота анализа: Детальный анализ малых размерностей

Недостатки

1. Отсутствие конструкций: Основные результаты носят исключающий характер, отсутствуют новые конструкции APN функций
2. Зависимость от вычислений: Некоторые результаты опираются на компьютерную верификацию, теоретические доказательства неполны
3. Ограниченность приложений: В основном теоретический вклад, практическая ценность для криптографии требует дальнейшей проверки

Влияние

1. Академическая ценность: Предоставляет новые инструменты и перспективы для теории APN функций
2. Методологический вклад: Геометризация может вдохновить исследования других криптографических задач
3. Открытые проблемы: Предложенные вопросы указывают направления для дальнейших исследований

Области применения

• Теоретический анализ квадратичных APN функций
• Проектирование и анализ S-блоков в криптографии
• Исследование приложений конечной геометрии в криптографии
• Исследование структуры спектра Уолша булевых функций

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

Статья цитирует 25 важных работ, охватывающих теорию APN функций, разбиения векторного пространства, теорию блокирующих множеств и другие области, что отражает междисциплинарный характер исследования. Ключевые ссылки включают монографию Carlet по булевым функциям, работы Govaerts-Storme о блокирующих множествах и исследования Heden и др. о разбиениях векторного пространства.