IMI/Publicaţii/CSJM/Ediţii/CSJM v.30, n.2 (89), 2022/

Split logarithm problem and a candidate for a post-quantum signature scheme

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.


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



Adobe PDF document0.15 Mb