A practical digital signature scheme based on the hidden logarithm problem

Abstract

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.

Keywords

• finite associative algebra
• non-commutative algebra
• commutative finite group
• discrete logarithm problem
• hidden logarithm problem
• public key
• digital signature
• post-quantum cryptosystem