RUS  ENG
Полная версия
ЖУРНАЛЫ // Прикладная дискретная математика. Приложение // Архив

ПДМ. Приложение, 2021, выпуск 14, страницы 57–58 (Mi pdma531)

Дискретные функции

О производных булевых бент-функций

А. С. Шапоренкоabc

a Новосибирский государственный университет
b Лаборатория криптографии JetBrains Research, г. Новосибирск
c Институт математики им. С.Л. Соболева СО РАН, г. Новосибирск

Аннотация: Бент-функция может быть определена как булева функция $f(x)$ от $n$ переменных ($n$ чётно), такая, что для любого ненулевого вектора $y$ её производная $D_yf(x)=f(x)\oplus f(x\oplus y)$ сбалансирована  — принимает значения $0$ и $1$ одинаково часто. Справедливо ли, что любая сбалансированная функция  — производная некоторой бент-функции? Эта задача рассмотрена для частного случая  — аффинных функций. Доказано, что любая неконстантная аффинная функция от $n\geqslant4$ ($n$ чётно) переменных является производной для $(2^{n-1}-1)|\mathcal{B}_{n-2}|^2$ бент-функций, где $\mathcal{B}_{n-2}$  — класс бент-функций от $n-2$ переменных. Получены итерационные нижние границы для числа бент-функций.

Ключевые слова: бент-функции, булевы функции, производные бент-функций, нижние границы для числа бент-функций.

УДК: 519.7

DOI: 10.17223/2226308X/14/11



© МИАН, 2024