Quantum algorithm for discrete logarithm problem for matrices overfinite group rings

Alexey D. Myasnikov, Alexander Ushakov

Research output: Contribution to journalArticlepeer-review

12 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)31-36
Number of pages6
JournalGroups, Complexity, Cryptology
Volume6
Issue number1
DOIs
StatePublished - May 2014

Keywords

  • Diffie-Hellman
  • Discrete logarithm problem
  • Group rings
  • Group-based cryptography
  • Key-exchange
  • Matrix monoids
  • Post-quantum cryptography
  • Quantum algorithms
  • Semidirect product

Fingerprint

Dive into the research topics of 'Quantum algorithm for discrete logarithm problem for matrices overfinite group rings'. Together they form a unique fingerprint.

Cite this