TY - JOUR
T1 - Quantum algorithm for discrete logarithm problem for matrices overfinite group rings
AU - Myasnikov, Alexey D.
AU - Ushakov, Alexander
PY - 2014/5
Y1 - 2014/5
N2 - We propose a polynomial time quantum algorithm for solving the discrete logarithm problem (DLP) in matrices over finite group rings. The hardness of this problemwas recently employed in the design of a keyexchange protocol proposed by D. Kahrobaei, C. Koupparis and V. Shpilrain [4]. Our result implies that the Kahrobaei-Koupparis-Shpilrain protocol does not belong to the realm of post-quantum cryptography.
AB - We propose a polynomial time quantum algorithm for solving the discrete logarithm problem (DLP) in matrices over finite group rings. The hardness of this problemwas recently employed in the design of a keyexchange protocol proposed by D. Kahrobaei, C. Koupparis and V. Shpilrain [4]. Our result implies that the Kahrobaei-Koupparis-Shpilrain protocol does not belong to the realm of post-quantum cryptography.
KW - Diffie-Hellman
KW - Discrete logarithm problem
KW - Group rings
KW - Group-based cryptography
KW - Key-exchange
KW - Matrix monoids
KW - Post-quantum cryptography
KW - Quantum algorithms
KW - Semidirect product
UR - http://www.scopus.com/inward/record.url?scp=84900827555&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84900827555&partnerID=8YFLogxK
U2 - 10.1515/gcc-2014-0003
DO - 10.1515/gcc-2014-0003
M3 - Article
AN - SCOPUS:84900827555
SN - 1867-1144
VL - 6
SP - 31
EP - 36
JO - Groups, Complexity, Cryptology
JF - Groups, Complexity, Cryptology
IS - 1
ER -