Об одном методе решения систем квадратичных булевых уравнений, использующем локальные аффинности

Информатика и ее применения. 2019. Т. 13. № 2. С. 37–46.

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

Как известно, вычислительная задача решения систем нелинейных уравнений над полем из двух элементов является NP-трудной. Этим обстоятельством обуславливается стремление исследователей разрабатывать алгоритмы ее решения, минимизирующие необходимые вычислительные ресурсы для тех или иных классов систем уравнений.
В статье предлагается метод решения систем квадратичных булевых уравнений, использующий представление функций их аффинными нормальными формами, то есть, в некотором смысле, аппроксимацию квадратичных функций кусочно-аффинными. Для каждого уравнения на основе такого представления строится набор систем небольшого числа линейных уравнений, а затем ищется совместная комбинация этих линейных систем для различных исходных уравнений. Исходная нелинейная задача, таким образом, сводится, по большому счету, к проверке совместности серии линейных систем от того же числа переменных. Метод может быть эффективно распараллелен и, несмотря на большую трудоемкость в худшем случае, допускает ряд эвристик, уменьшающих время его выполнения.

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