2025-11-10T02:46:09.476031

On Sum-Free Functions

Ebeling, Hou, Rydell et al.
A function from $\Bbb F_{2^n}$ to $\Bbb F_{2^n}$ is said to be {\em $k$th order sum-free} if the sum of its values over each $k$-dimensional $\Bbb F_2$-affine subspace of $\Bbb F_{2^n}$ is nonzero. This notion was recently introduced by C. Carlet as, among other things, a generalization of APN functions. At the center of this new topic is a conjecture about the sum-freedom of the multiplicative inverse function $f_{\text{\rm inv}}(x)=x^{-1}$ (with $0^{-1}$ defined to be $0$). It is known that $f_{\text{\rm inv}}$ is 2nd order (equivalently, $(n-2)$th order) sum-free if and only if $n$ is odd, and it is conjectured that for $3\le k\le n-3$, $f_{\text{\rm inv}}$ is never $k$th order sum-free. The conjecture has been confirmed for even $n$ but remains open for odd $n$. In the present paper, we show that the conjecture holds under each of the following conditions: (1) $n=13$; (2) $3\mid n$; (3) $5\mid n$; (4) the smallest prime divisor $l$ of $n$ satisfies $(l-1)(l+2)\le (n+1)/2$. We also determine the ``right'' $q$-ary generalization of the binary multiplicative inverse function $f_{\text{\rm inv}}$ in the context of sum-freedom. This $q$-ary generalization not only maintains most results for its binary version, but also exhibits some extraordinary phenomena that are not observed in the binary case.
academic

О функциях без сумм

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

  • ID статьи: 2410.10426
  • Название: On Sum-Free Functions
  • Авторы: Alyssa Ebeling, Xiang-Dong Hou, Ashley Rydell, Shujun Zhao
  • Классификация: math.NT (теория чисел), cs.IT (теория информации), math.IT (математическая теория информации)
  • Дата публикации: октябрь 2024 г. (препринт arXiv)
  • Ссылка на статью: https://arxiv.org/abs/2410.10426

Аннотация

В данной работе исследуется концепция функций без сумм над конечными полями. Функция из F2n\mathbb{F}_{2^n} в F2n\mathbb{F}_{2^n} называется kk-порядка без сумм, если сумма её значений на каждом kk-мерном F2\mathbb{F}_2-аффинном подпространстве ненулевая. Это понятие было недавно введено К. Карле как обобщение APN-функций. Центральным вопросом исследования является гипотеза о свойствах функции мультипликативного обращения finv(x)=x−1f_{\text{inv}}(x)=x^{-1}. Известно, что finvf_{\text{inv}} является 2-порядка (эквивалентно, (n−2)(n-2)-порядка) без сумм тогда и только тогда, когда nn нечётно. Гипотеза утверждает, что для 3≤k≤n−33\le k\le n-3 функция finvf_{\text{inv}} никогда не является kk-порядка без сумм. Гипотеза доказана для чётных nn, но остаётся открытой для нечётных nn.

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

  1. Определение проблемы: Работа посвящена изучению свойств функций без сумм, в частности свойств функции мультипликативного обращения. Функция без сумм — это функция, у которой сумма значений на всех kk-мерных аффинных подпространствах ненулевая.
  2. Значимость:
    • Функции без сумм являются естественным обобщением почти совершенно нелинейных (APN) функций, которые широко изучаются в криптографии благодаря их устойчивости к дифференциальным атакам
    • Решают проблему уязвимости блочных шифров перед интегральными атаками, которые используют предсказуемость сумм значений S-блоков на аффинных подпространствах
    • С теоретической точки зрения концепция функций без сумм обладает богатым математическим содержанием
  3. Существующие ограничения:
    • Для нечётных nn центральная гипотеза (Гипотеза 1.1) о свойствах функции мультипликативного обращения остаётся полностью нерешённой
    • Отсутствуют исследования надлежащих обобщений на случай qq-ичных полей
  4. Исследовательская мотивация: Продвижение понимания теории функций без сумм, в частности решение важной гипотезы, связанной с функцией мультипликативного обращения, и исследование её обобщений на более общие конечные поля.

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

  1. Доказательство Гипотезы 1.1 при различных условиях:
    • Случай n=13n=13
    • Случай 3∣n3|n
    • Случай 5∣n5|n
    • Случай, когда наименьший простой делитель ll удовлетворяет (l−1)(l+2)≤(n+1)/2(l-1)(l+2)\le (n+1)/2
  2. Определение "правильного" qq-ичного обобщения двоичной функции мультипликативного обращения: Доказано, что функция gq−1(x)=1/xq−1g_{q-1}(x)=1/x^{q-1} является надлежащим qq-ичным обобщением finvf_{\text{inv}} в двоичном случае
  3. Предоставление новых методов доказательства: Использование границ Ланга-Вейля для нового доказательства того, что 4∈Kn4\in K_n (для всех n≥6n\ge 6)
  4. Обнаружение аномальных явлений в qq-ичном случае: Посредством компьютерного поиска обнаружено, что для q=3,5q=3,5 и n=7n=7 функция gq−1g_{q-1} является kk-порядка без сумм для всех 1≤k≤61\le k\le 6 над Fq7\mathbb{F}_{q^7}

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

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

Для функции f:Fqn→Fqnf: \mathbb{F}_{q^n} \to \mathbb{F}_{q^n} над конечным полем Fqn\mathbb{F}_{q^n} исследуется её свойство kk-порядка без сумм, то есть для всех kk-мерных Fq\mathbb{F}_q-аффинных подпространств AA выполняется ∑x∈Af(x)≠0\sum_{x\in A} f(x) \neq 0.

Архитектура основных методов

  1. Метод определителя Мура:
    • Использование определителя Мура Δ(X1,…,Xk)\Delta(X_1,\ldots,X_k) для характеризации линейной независимости
    • Установление связи между свойством без сумм и нулями определителя Мура
  2. Метод симметрических многочленов:
    • Переформулировка критерия Карле в виде симметрических многочленов
    • Введение многочлена Θk(X1,…,Xk)\Theta_k(X_1,\ldots,X_k)
  3. Метод границ Ланга-Вейля:
    • Использование границ Ланга-Вейля из алгебраической геометрии для оценки числа точек алгебраических многообразий над конечными полями
    • Доказательство абсолютной неприводимости Θ4\Theta_4

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

  1. Единая теоретическая база:
    • Установление единой теоретической базы от двоичного к qq-ичному случаю
    • Доказательство того, что большинство двоичных результатов обобщаются на qq-ичный случай
  2. Новые методы конструирования:
    • Теорема 3.3 предоставляет систематический метод конструирования новых нарушений из известных нарушений свойства без сумм
    • Использование структуры подполей для рекурсивного конструирования
  3. Доказательство абсолютной неприводимости:
    • В приложении приводится техническое доказательство абсолютной неприводимости многочлена Θ4\Theta_4
    • Это является ключевым шагом для применения границ Ланга-Вейля

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

Центральные теоремы

Теорема 3.6: Пусть n≥3n\ge 3 — нечётное число, ll — наименьший простой делитель nn. Если (l−1)(l+2)≤(n+1)/2(l-1)(l+2)\le (n+1)/2, то Гипотеза 1.1 верна для nn.

Теорема 4.6 (qq-ичный вариант критерия): Функция gq−1g_{q-1} не является kk-порядка без сумм тогда и только тогда, когда существуют v1,…,vk∈Fqnv_1,\ldots,v_k\in \mathbb{F}_{q^n} такие, что Δ(v1,…,vk)≠0\Delta(v_1,\ldots,v_k)\neq 0, но Δ1(v1,…,vk)=0\Delta_1(v_1,\ldots,v_k)=0.

Важные следствия

Следствие 3.7: Если 3∣n3|n, то Гипотеза 1.1 верна для nn.

Теорема 3.13: Если 5∣n5|n, то Гипотеза 1.1 верна для nn.

Результаты qq-ичного обобщения

Предложение 4.7:

  • gq−1g_{q-1} является 1-порядка без сумм
  • При n≥2n\ge 2 функция gq−1g_{q-1} является 2-порядка без сумм тогда и только тогда, когда nn нечётно

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

Вычислительная верификация

  1. Случай n=13n=13: Посредством компьютерного поиска верифицирована справедливость Гипотезы 1.1 для n=13n=13
  2. Численные результаты для qq-ичного случая: Проведена систематическая вычислительная верификация для q=3,5q=3,5 и 7≤n≤117\le n\le 11

Основные находки

  • Для q=3,5q=3,5 и n=7n=7 функция gq−1g_{q-1} является kk-порядка без сумм для всех 1≤k≤61\le k\le 6
  • Такое явление никогда не наблюдалось в двоичном случае, демонстрируя уникальные свойства qq-ичного случая

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

Данная работа основана на следующих важных исследованиях:

  1. Пионерская работа Карле: Введение концепции функций без сумм и основная теория
  2. Теория APN-функций: Функции без сумм являются обобщением APN-функций
  3. Теория определителя Мура над конечными полями: Предоставляет важные технические инструменты
  4. Методы алгебраической геометрии: Применение границ Ланга-Вейля и других инструментов

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

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

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

Ограничения

  1. Гипотеза 1.1 для общего нечётного nn остаётся полностью нерешённой
  2. Наиболее сложные случаи — когда nn является простым числом или произведением двух близких простых чисел
  3. Теоретическое объяснение аномальных явлений в qq-ичном случае требует дальнейшего исследования

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

  1. Полное решение Гипотезы 1.1
  2. Глубокое понимание специальных свойств qq-ичного случая
  3. Исследование применений функций без сумм в криптографии
  4. Изучение неприводимости более общих многочленов Θk\Theta_k

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

Преимущества

  1. Значительный теоретический вклад: Достигнут существенный прогресс в решении важной открытой проблемы
  2. Методологические инновации: Комбинирование теории чисел, алгебраической геометрии и вычислительных методов
  3. Полнота результатов: Наличие как теоретических доказательств, так и вычислительной верификации
  4. Ценность обобщений: Установление единой базы от двоичного к qq-ичному случаю

Недостатки

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

Влияние

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

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

  1. Проектирование и анализ S-блоков в криптографии
  2. Исследование алгебраических свойств функций над конечными полями
  3. Проектирование криптографических систем, устойчивых к интегральным атакам

Дополнительные технические детали

Роль определителя Мура

Определитель Мура Δ(X1,…,Xk)=det⁡(Xjqi−1)1≤i,j≤k\Delta(X_1,\ldots,X_k) = \det(X_j^{q^{i-1}})_{1\le i,j\le k} играет ключевую роль в определении линейной независимости векторов. Свойства нулей его модификации Δ1\Delta_1 напрямую связаны с нарушением свойства без сумм.

Представление симметрическими многочленами

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

Применение границ Ланга-Вейля

Доказав абсолютную неприводимость Θ4\Theta_4, авторы могут применить границы Ланга-Вейля для точной оценки числа точек соответствующих алгебраических многообразий, завершив новое доказательство того, что 4∈Kn4\in K_n.

Данная работа вносит значительный вклад в новую область функций без сумм, не только продвигая теоретическое понимание центральной гипотезы, но и устанавливая базу для обобщений на более общие случаи, создавая прочный фундамент для последующих исследований.