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

Классы подстановок абелевых групп с высокой нелинейностью и низкой разностной $\delta$-равномерностью

Д. А. Буров, Д. А. Кононов


Аннотация: Работа посвящена построению и изучению разностной $\delta$-равномерности $\delta(f)$ и нелинейности $\mathcal{NL}(f)$ подстановок на абелевых группах. Пусть $q = p^n$, где $p$  — простое число; $n\in\mathbb{N}$; $\mathbb{F}_q$  — поле из $q$ элементов; $\mathbb{F}_q^{\ast}$  — мультипликативная группа поля $\mathbb{F}_q$. Под дефицитом $D(f)$ отображения $f$ абелевых групп понимается число нулей в его разностной матрице. Доказано, что $\mathcal{NL}(f) \geq 1 - \dfrac{1}{n}\sqrt{2 + 2D(f)}$ для любого биективного отображения $f$ абелевых групп порядка $n$. Для логарифмической подстановки $f\in S(\mathbb{F}_q^{\ast})$ доказана оценка $\mathcal{NL}(f)\geq \dfrac{q- \sqrt{q}-2}{q-1}$. На основе отображения $(x,y)\mapsto x+y$, $x,y\in\mathbb{F}_q$, построены разностно $5$-равномерные подстановки на группе $\mathbb{F}_{17}^{\ast}\times \mathbb{F}_{17}^{\ast}$. Построены классы разностно $3$-равномерных подстановок на $\mathbb{F}_{q}^{\ast}$, полученные модификацией логарифмических подстановок на $\mathbb{F}_q^{\ast}$. Для таких подстановок доказана оценка $\mathcal{NL}(f) \geq 1 - \dfrac{\sqrt{q^m} + 2q - 1}{q^m - 1}$. За счёт дополнения логарифмической подстановки на $\mathbb{Z}_{q-1}$ двоичной функцией подстроены классы разностно $6$- и $5$-равномерных подстановок на аддитивной группе кольца $\mathbb{Z}_2\times \mathbb{Z}_{q-1}$. Доказано, что $\mathcal{NL}(f) \geq 1 - \dfrac{3\sqrt{2^n}}{2^n-1}$ для подстановок группы $\mathbb{F}_{2^n}^{\ast}$, задаваемых многочленом $x^4 + ax^2 +bx$, $\delta(f) \leq 3$.

Ключевые слова: подстановка конечного поля, $s$-бокс, нелинейность, разностная $\delta$-равномерность, логарифмическая подстановка.

УДК: 519.7

DOI: 10.17223/2226308X/18/1