ИСТИНА

Булевы функции активно применяются в компьютерных системах в целях улучшения комбинаторных, криптографических и прочих свойств этих систем. Для соответствия булевой функции многим из указанных выше свойств важно, чтобы булева функция обладала оптимальным набором криптографических характеристик, среди которых существенную роль играет так называемый критерий распространения. Понятие критерия распространения булевых функций представляет собой множество векторов, для которых соответствующие им производные булевой функции являются уравновешенными функциями. Оно характеризует статистические свойства семейства производных булевой функции, играющих важную роль в анализе и синтезе криптосистем. Впервые понятие критерия распространения было введено Бартом Пренеелем и соавторами в работе [5] в целях характеризации стойкости применяемых в шифрах булевых функций к линейным и дифференциальным методам криптоанализа, успешное проведение которых дает много информации о секретном ключе (подробно об этих методах см. [1] и [3]). Кроме того, для некоторых классов булевых функций критерий распространения определяет их экстремальные свойства. Например, максимальное значение количества векторов, удовлетворяющих критерию распространения, имеет место лишь при чётном числе переменных и для экстремального класса булевых функций, называемых бент-функциями, а минимальное значение достигается только у аффинных функций. В работе получены точные значения и оценки количества векторов, удовлетворяющих критерию распространения булевых функций из известных криптографических классов, таких как платовидные функции, функции из класса Майорана-МакФарланда, квадратичные функции, алгебраически вырожденные функции и мультиаффинные функции. Также получены необходимые и достаточные условия принадлежности векторов множеству критерия распространения монотонно неубывающих функций, наименьший носитель которых состоит из одного или двух векторов, и соответствующих им монотонно невозрастающих функций.