IMI/Publicaţii/CSJM/Ediţii/CSJM v.29, n.2 (86), 2021/

A practical digital signature scheme based on the hidden logarithm problem

Authors: D. N. Moldovyan
Keywords: finite associative algebra, non-commutative algebra, commutative finite group, discrete logarithm problem, hidden logarithm problem, public key, digital signature, post-quantum cryptosystem.


A candidate for practical post-quantum digital signature algorithm based on computational difficulty of the hidden discrete logarithm problem is introduced. The used algebraic carrier represents a 4-dimensional finite non-commutative associative algebra defined over the field $GF(p)$, which is caracterized in using a sparse basis vector multiplication table for defining the vector multiplication operation. Structure of the algebra is studied. Three types of the commutative groups are contained in the algebra and formulas for number of groups of every type are obtained. One of the types represents groups of the order $(p-1)^2$, possessing 2-dimensional cyclicity, and one of them is used as a hidden group in the signature scheme developed using a new method for implementing a general criterion of post-quantum resistance proposed earlier.

St. Petersburg Federal Research Center of
the Russian Academy of Sciences (SPC RAS),
St. Petersburg Institute for Informatics and
Automation of the Russian Academy of Sciences
14 Liniya, 39, St.Petersburg, 199178


Adobe PDF document0.15 Mb