Материалы что дал Мухачев / Материалы что дал Мухачев / Білети_коротки_відповіді / Білети_відпові_УБДМ / Sp_Otvet18

№ 18. Перетворення Уолша-Адамара булєвої функції. Визначення нелінійності булевої функції та її вираз через коефіціенти Уолша-Адамара.

Линейная функция – функция вида вида , где - вектор коэффициентов, . Обозначим линейную функцию через . Введем аффинные функции вида , где . Множество аффинных булевых функций от n переменных обозначим через . В криптографии важное значение имеют функции, свойства которых исключают слабости, присущие функциям, близким к линейным. Весом функции называется количество единиц в векторе ее значений.

Как меру различия между булевыми функциями f (x) и от n переменных удобно использовать количество покоординатных несовпадений в векторах их значений. Данная мера называется расстоянием Хэмминга между функциями f и g.

Расстоянием Хэмминга от функции до заданного множества функций G называется значение .

Нелинейностью булевой функции f от n переменных называется параметр - расстояние от f до множества аффинных функций, т.е. значение , .

Параметр можен быть выражен с помощью преобразования Уолша-Адамара.

При преобразовании Уолша-Адамара булевой функции получается функция , , связанная с вектором значений функции . В этом векторе единицы соответствуют местам несовпадений правой части функции с правой частью линейной функции .

Значением является разность между числом нулей и числом единиц в векторе : , где пробегает все множество аргументов

В этом векторе элемент однозначно определяет расстояние Хэмминга между функциями и , а также количество аргументов, на которых они совпадают.

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

Поэтому выражение равно количеству нулей в векторе значений функции , либо функции .

Таким образом, чем больше абсолютное значение коэффициента Уолша-Адамара, тем меньше расстояние от функции f до множества аффинных функций.

Следовательно, , , .