RUS  ENG
Полная версия
ЖУРНАЛЫ // Информатика и её применения // Архив

Информ. и её примен., 2019, том 13, выпуск 1, страницы 67–74 (Mi ia580)

Эта публикация цитируется в 1 статье

Полиномиальные алгоритмы вычисления локальных аффинностей квадратичных булевых функций

О. А. Логачевab, А. А. Сукаевa, С. Н. Федоровa

a Московский государственный университет им. М. В. Ломоносова
b Институт проблем информатики Федерального исследовательского центра «Информатика и управление» Российской академии наук

Аннотация: Аффинная нормальная форма позволяет рассматривать произвольную булеву функцию на определенных плоскостях (так называемых локальных аффинностях) как аффинную. Данное представление — по сути, аффинная аппроксимация — булевых функций может помочь в решении систем нелинейных уравнений над полем из двух элементов. Задача решения таких систем (специального вида), среди прочего, используется в ряде методов синтеза и анализа средств обеспечения информационной безопасности. В статье описывается способ нахождения локальных аффинностей для квадратичных булевых функций, основанный на теореме Диксона. Тем самым решается задача построения аффинных нормальных форм для таких функций. Кроме того, обсуждаются вопросы эффективности подобных алгоритмов. Основная цель данной статьи — подготовить базу для готовящейся к публикации работы, предлагающей метод решения систем квадратичных булевых уравнений с помощью «аппроксимирования» соответствующих функций их аффинными нормальными формами.

Ключевые слова: булева функция, система квадратичных булевых уравнений, разбиение векторного пространства, плоскость, локальная аффинность, теорема Диксона, аффинная нормальная форма, алгебраический криптоанализ.

Поступила в редакцию: 11.01.2019

DOI: 10.14357/19922264190110



Реферативные базы данных:


© МИАН, 2024