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

В области постквантовой двухключевой криптографии значительный интерес представляет разработка практичных алгебраических схем электронной цифровой подписи (ЭЦП) с секретной группой, стойкость которых базируется на вычислительной сложности решения систем степенных уравнений с многими неизвестными. В качестве алгебраического носителя в таких криптосхемах используются ассоциативные некоммутативные конечные алгебры (АНКА). Специфическим моментом, связанным с обеспечением стойкости к атакам на основе известных подписей при разработке схем ЭЦП данного типа, является наличие проблемы совершенствования механизма рандомизации подгоночного элемента цифровой подписи, представляющего собой вектор S, многократно входящий в уравнение верификации в качестве множителя. Известное решение этой проблемы на основе вычисления S в зависимости от двух векторов, выбираемых случайным образом из двух коммутативных секретных групп, таких, что элементы одной из них некоммутативны с элементами другой, при использовании в проверочном уравнении значения хеш-функции от S приводит к увеличению размера ЭЦП, обусловленного необходимостью задания двух вспомогательных подгоночных элементов подписи. В статье предлагается новый механизм рандомизации подписи, отличающийся вычислением значения S в зависимости от двух векторов, выбираемых случайным образом из одной коммутативной секретной группы. Предложенный механизм обеспечивает приемлемый уровень стойкости к атакам на основе известных подписей и может быть положен в основу разработки схем ЭЦП с одним уравнением верификации и одним вспомогательным подгоночным элементом подписи. Разработан новый алгебраический алгоритм ЭЦП, представляющий интерес как прототип практичного постквантового стандарта ЭЦП. Даны оценки его параметров при реализации на четырехмерных АНКА и на алгебре матриц 3×3, заданных над простым конечным полем.