Поиск линеаризующих множеств в алгебраическом криптоанализе как задача псевдобулевой оптимизации

Вводится понятие линеаризующего множества, которое можно рассматривать как обобщение известного понятия линеаризационного множества. Линеаризующие множества используются в основе алгебраических атак, относящихся к классу «угадывай и определяй» (guess-and-determine). В таких атаках угадываются значения переменных из некоторого множества, затем эти значения подставляются в систему алгебраических уравнений, которая связывает входные и выходные данные рассматриваемого шифра. В некоторых случаях результатом такой подстановки является линейная система, которая решается эффективно. Рассматриваются алгебраические уравнения над полем GF(2). Значения переменных из линеаризующего множества (в отличие от линеаризационного) линеаризуют систему уравнений с некоторой вероятностью, которая, вообще говоря, может быть существенно меньше 1. Оценка трудоёмкости атаки на основе конкретного линеаризующего множества строится через специально определяемую псевдобулеву функцию. Минимальное значение этой функции даёт оценку трудоёмкости лучшей по эффективности атаки. Для минимизации таких функций используется метаэвристический алгоритм из класса «поиск с запретами». На данном этапе построены атаки описанного типа для ряда криптографических генераторов. В частности, для известного генератора A5/1 построена атака с оценкой трудоёмкости в 4,5 раз ниже трудоёмкости известной атаки Андерсона.