Постквантовый алгоритм ЭЦП на основе трудности решения степенных уравнений

Вычислительная сложность нахождения решений больших систем нелинейных уравнений (БСНУ) лежит в основе ряда постквантовых двухключевых криптосхем, включая алгебраические алгоритмы цифровой подписи с использованием матриц в качестве элементов секретного ключа. Такие алгоритмы относятся к вероятностным криптосхемам и характеризуются использованием некоторой матрицы S в качестве подгоночного элемента подписи. Последнее обусловливает актуальность рассмотрения стойкости к атакам, использующим известные подписи. При этом лобовой (прямой) атакой является атака на основе решения БСНУ. В известных алгебраических алгоритмах цифровой подписи в рамках лобовой атаки возникают недоопределенные БСНУ с большим числом решений, что создает предпосылки к атакам на основе эквивалентных ключей. В статье рассматривается построение постквантового алгоритма на конечных алгебрах квадратных матриц, при прямой атаке на который возникают близкие к сбалансированным (с равным числом уравнений и неизвестных) и переопределенные БСНУ (с числом уравнений, превышающим число неизвестных). Особенностью предложенного алгоритма является использование вспомогательных скрытых групп, вспомогательного параметра рандомизации ЭЦП, вычисляемого как значение сжимающей односторонней функции от значения S. Приводится оценка стойкости к лобовой атаке и нескольким вариантам атак на основе известных подписей.