Title: Algebraic multivariate signature algorithm with two hidden groups

Authors: Khanh-Linh Dinh; Long-Giang Nguyen; Thi-Bac Do; Alexandr Andreevich Moldovyan; Dmitriy Nikolaevich Moldovyan; Anna Alexandrovna Kostina

Addresses: Thai Nguyen University of Information and Communication Technology, Z115 Street, Quyet Thang Commune, Thainguyen, Vietnam ' Institute of Information Technology, Vietnam Academy of Science and Technology, Hanoi, Vietnam ' Thai Nguyen University of Information and Communication Technology, Z115 Street, Quyet Thang Commune, Thainguyen, Vietnam ' Laboratory of Computer Security Problems, St. Petersburg Federal Research Center of the Russian Academy of Sciences, St. Petersburg, Russia ' Laboratory of Computer Security Problems, St. Petersburg Federal Research Center of the Russian Academy of Sciences, St. Petersburg, Russia ' Laboratory of Computer Security Problems, St. Petersburg Federal Research Center of the Russian Academy of Sciences, St. Petersburg, Russia

Abstract: In this paper we improve the performance of algebraic digital signature algorithms based on the computational difficulty of solving large systems of power equations. It is the first time the randomisation enhancement mechanism is implemented in the algebraic digital signature algorithm without using the doubling of the verification equation. The developed digital signature algorithm is distinguished by the use of two hidden groups for calculating a random fixator vector, by which the randomising element of the generated signature is calculated. The latter ensures increased randomisation not only for the signature values, but also for the value of the fixator vector. Due to this, the potentially achievable level of security is significantly increased. The sufficiency of performing the signature verification using only one verification equation is ensured by the following two techniques: 1) multiple entries of the tuning signature element S in the products that is exponentiated to a large power, which appear in the right-hand side of the verification equation; 2) using the value of the hash function, depending on the vector S, as the value of the degree of one of the exponentiation operations performed during the signature authenticity verification procedure.

Keywords: finite non-commutative algebra; associative algebra; computationally difficult problem; hidden commutative group; digital signature; signature randomisation; post-quantum cryptography.

DOI: 10.1504/IJICS.2026.153348

International Journal of Information and Computer Security, 2026 Vol.29 No.4, pp.451 - 467

Received: 07 Apr 2025
Accepted: 15 Nov 2025
Published online: 01 May 2026 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article