|
Применение SAT-решателей к задаче поиска векторных булевых функций с требуемыми криптографическими свойствами
А. Е. Доронинa, К. В. Калгинbc a Новосибирский гос. университет, ул. Пирогова, 2, 630090 Новосибирск, Россия
b Институт математики им. С. Л. Соболева, пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
c Институт вычислительной математики и математической геофизики, пр. Акад. Лаврентьева, 6, 630090 Новосибирск, Россия
Аннотация:
Представлен подход к решению задачи поиска почти совершенно нелинейной (APN) функции, основанный на её сведении к классической задаче выполнимости и использовании SAT-решателей. Описано построение формул, определяющих APN-функцию. Введены два представления функции: разреженное и плотное, в которых описана задача поиска взаимно однозначной векторной булевой функции и APN-функции. Также в работе представлен новый подход к решению задачи построения векторных булевых APN-функций, обладающих дополнительными свойствами. В основе подхода лежит идея представления неизвестной векторной булевой функции в виде суммы известной APN-функции и двух неизвестных булевых функций: $\mathbf{G} = \mathbf{F}\oplus \mathbf{c}\cdot g_1 \oplus \mathbf{d}\cdot g_2$, где $\mathbf{F}$ — известная APN-функция. Показано, что для функций от $n=6,7$ переменных такой подход имеет большую эффективность в сравнении с прямым построением APN-функции при помощи SAT. Как итог, описанным в работе методом удалось показать отсутствие кубических APN-функций от 7 переменных, представимых в виде описанной выше суммы. Табл. 3, библиогр. 21.
Ключевые слова:
SAT-решатель, криптография, булева функция, APN-функция.
Статья поступила: 30.12.2021 Переработанный вариант: 11.04.2022 Принята к публикации: 15.04.2022
Образец цитирования:
А. Е. Доронин, К. В. Калгин, “Применение SAT-решателей к задаче поиска векторных булевых функций с требуемыми криптографическими свойствами”, Дискретн. анализ и исслед. опер., 29:4 (2022), 38–58
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da1308 https://www.mathnet.ru/rus/da/v29/i4/p38
|
Статистика просмотров: |
Страница аннотации: | 92 | PDF полного текста: | 61 | Список литературы: | 23 | Первая страница: | 5 |
|