Аннотация
ВВЕДЕНИЕ 7
1 Постановка задачи 9
2 Синтез векторных булевых функций с невырожденными координатами 10
2.1 Свойства булевых функций с невырожденными координатами 10
2.2 Свойства векторных булевых функций с невырожденными
координатами 15
2.3 Алгоритм генерации векторных булевых функций с невырожденными
координатами 19
3 Генерация булевых функций с заданным числом фиктивных переменных 21
ЗАКЛЮЧЕНИЕ 30
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 31
Невырожденная булева функция - это функция, существенно зависящая от всех своих переменных.
Фиктивная переменная - это переменная, от которой функция существенно не зависит.
Векторная булева функция — F: {0,1} п ^ {0,1} п
F = (fi,.., /и), где fi,.., / — координаты.
Рассматриваем векторную булеву функцию, как упорядоченный набор булевых функций, где они являются координатами векторной булевой функции.
Векторную функцию называют невырожденной, если у нее все координаты невырожденные.
Мы будем рассматривать криптосистемы с функциональными ключами, где ключом является векторная булева функция F, открытым текстом является (%1,.. ,%п), шифртекстом - (у1,.. ,уп) (рисунок 1). Выбираем х, пропускаем через шифратор и на выходе получаем y = F(x).
Рассмотрим функции, которые используются в криптографии в качестве компонент шифрования.
В криптографии важно, чтобы каждый выходной бит существенно зависел от всех входных, потому что если зависимости нет, то сложность атаки грубой силы сокращается вдвое. Вдвое сократится перебор, а при решении систем уравнений снизится количество переменных в уравнениях. Из этого делаем вывод: как бы атакующий не действовал, сложность атаки будет меньше.
Для работы нам надо компактно задаваемую и быстро вычисляемую функцию. Один из способов достижения этой цели - использование функций, зависящих от небольшого количества существенных переменных.
В работе рассматривается как из данной функции минимальным числом изменений построить функцию, имеющую фиктивные переменные и сохранить вес.
Таким образом, решено разработать алгоритм генерации векторных булевых функций с невырожденными координатами и научиться генерировать булевы функции с заданным числом фиктивных переменных.
Разработан алгоритм генерации векторных булевых функций с невырожденными координатами. Для его обоснования доказаны 6 предложений: 2 утверждения о булевых функциях, одна лемма и 3 утверждения о векторных булевых функциях с невырожденными координатами.
Сформулировано необходимое и достаточное условие, при котором можно изменением двух значений из функции сделать функцию с хотя бы одной фиктивной переменной. Сформулированы достаточные условия, при которых можно из невырожденной уравновешенной функции изменением двух значений сделать функцию с ровно одной фиктивной переменной.
Описан метод получения таких функций.
Эти результаты могут быть применены для построения ключей в криптосистемах на булевых функциях .
Часть результатов работы представлены на Международной школе- семинаре SIBECRYPT’22, и опубликованы в её трудах
