Institutul de Matematică şi Informatică "Vladimir Andrunachievici"
Universitatea de Stat din MoldovaRO EN
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.
– 0.15 Mb
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:
the Russian Academy of Sciences (SPC RAS)
14 Liniya, 39, St.Petersburg, 199178
Russia
E-mail:
DOI
https://doi.org/10.56415/csjm.v30.14Fulltext
– 0.15 Mb
Contents
- On Elimination of Erasing Rules from E0S Grammars
- Vehicle Detection from Unmanned Aerial Images with Deep Mask R-CNN
- Identities and generalized derivatives of quasigroups
- Degree of favoring in apportionments
- Quadruplet loss and SqueezeNets for Covid-19 detection from Chest-X ray
- The Domination Parameters on a kind of the regular honeycomb structure
- Split logarithm problem and a candidate for a post-quantum signature scheme
- A Comparative study on classification performance of Emphysema with transfer learning methods in deep convolutional neural networks
- Svetlana Cojocaru - 70th anniversary
