A post-quantum digital signature scheme on groups with four-dimensional cyclicity

Аннотация

Введение: разработка практичных постквантовых схем подписи является одним из вызовов прикладной криптографии. Несколько различных форм скрытой задачи дискретного логарифмирования были предложены недавно в качестве примитива схем подписи, стойких к квантовым атакам. Развитие этого подхода представляет существенный прикладной интерес, поскольку он позволяет разработать практичные схемы подписи, обладающие малыми размерами открытого ключа и подписи в сравнении с известными аналогами. Цель: разработка новой формы скрытой задачи дискретного логарифмирования, заданной в коммутативной группе, обладающей многомерной цикличностью, и метода построения постквантовых схем подписи. Результаты: предложена новая форма скрытой задачи дискретного логарифмирования в качестве базового примитива для практичных постквантовых алгоритмов цифровой подписи. Представлены две новые четырехмерные конечные коммутативные ассоциативные алгебры в качестве алгебраического носителя предложенной новой вычислительно трудной задачи. Разработан метод построения схем подписи на основе последней. Суть метода состоит в использовании удвоенного открытого ключа и двух одинаковых уравнений для проверки подлинности одной и той же подписи. Для генерации пары открытых ключей выбираются случайным образом два базиса <G, Q> и <H, V> двух различных конечных групп G_{<G, Q>} и G_{<H, V>}, обладающих двухмерной цикличностью. Первый открытый ключ (Y, Z, U) вычисляется следующим образом: Y = Gy¹Qy²a, Z = Gz¹Qz²b, U = Gu¹Qu²g, где набор целых чисел (y₁, y₂, a, z₁, z₂, b, u₁, u₂, g) является секретным ключом. Второй открытый ключ (Y¢, Z¢, U¢) вычисляется следующим образом: Y¢ = Hy¹Vy²a, Z¢ = Hz¹Vz²b, U¢ = Hu¹Vu²g. Использование одинаковых параметров для вычисления соответствующих друг другу элементов, принадлежащих разным открытым ключам, обеспечивает возможность вычисления единой подписи, удовлетворяющей двум сходным проверочным уравнениям, заданным в различных конечных коммутативных ассоциативных алгебрах. Практическая значимость: предложенная схема цифровой подписи представляет практический интерес для разработки постквантовых алгоритмов подписи, обладающих сравнтельно малыми размерами подписи, открытого и секретного ключей.