**Authors:** A.A. Moldovyan, N.A. Moldovyan

**Keywords:** finite associative algebra, non-commutative algebra, finite cyclic group, discrete logarithm problem, hidden logarithm problem, public key,
digital signature, post-quantum cryptosystem.

### Abstract

A new form of the hidden discrete logarithm problem, called split logarithm problem, is introduced as primitive of practical post-quantum digital signature schemes, which is characterized in using two non-permutable elements $A$ and $B$ of a finite non-commutative associative algebra, which are used to compute generators $Q=AB$ and $G=BQ$ of two finite cyclic groups of prime order $q$. The public key is calculated as a triple of vectors $(Y,Z,T)$: $Y=Q^x$, $Z=G^w$, and $T=Q^aB^{-1}G^b$, where $x$, $w$, $a$, and $b$ are random integers. Security of the signature scheme is defined by the computational difficulty of finding the pair of integers $(x,w)$, although, using a quantum computer, one can easily find the ratio $x/w\bmod q$.

St. Petersburg Federal Research Center of

the Russian Academy of Sciences (SPC RAS)

14 Liniya, 39, St.Petersburg, 199178

Russia

E-mail:

### DOI

https://doi.org/10.56415/csjm.v30.14
### Fulltext

–

0.15 Mb