Дискретный анализ и исследование операций
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Дискретн. анализ и исслед. опер.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Дискретный анализ и исследование операций, 2022, том 29, выпуск 4, страницы 38–58
DOI: https://doi.org/10.33048/daio.2022.29.730
(Mi da1308)
 

Применение 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-функция.
Финансовая поддержка Номер гранта
Министерство науки и высшего образования Российской Федерации FWNF-2022-0018
Исследование выполнено в рамках государственного задания Института математики им. С. Л. Соболева (проект № FWNF–2022–0018).
Статья поступила: 30.12.2021
Переработанный вариант: 11.04.2022
Принята к публикации: 15.04.2022
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.7
Образец цитирования: А. Е. Доронин, К. В. Калгин, “Применение SAT-решателей к задаче поиска векторных булевых функций с требуемыми криптографическими свойствами”, Дискретн. анализ и исслед. опер., 29:4 (2022), 38–58
Цитирование в формате AMSBIB
\RBibitem{DorKal22}
\by А.~Е.~Доронин, К.~В.~Калгин
\paper Применение SAT-решателей к~задаче поиска векторных булевых функций с~требуемыми криптографическими свойствами
\jour Дискретн. анализ и исслед. опер.
\yr 2022
\vol 29
\issue 4
\pages 38--58
\mathnet{http://mi.mathnet.ru/da1308}
\crossref{https://doi.org/10.33048/daio.2022.29.730}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4523642}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/da1308
  • https://www.mathnet.ru/rus/da/v29/i4/p38
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Дискретный анализ и исследование операций
    Статистика просмотров:
    Страница аннотации:92
    PDF полного текста:61
    Список литературы:23
    Первая страница:5
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024