Cryptology ePrint Archive: Report 2012/574
Quantum algorithm for the discrete logarithm problem for matrices over finite group rings
A. D. Myasnikov and A. Ushakov
Abstract: We propose a polynomial time quantum algorithm for solving the
discrete logarithm problem in matrices over finite group rings.
The hardness of this problem was recently employed in the design
of a key-exchange protocol proposed by D. Kahrobaei, C. Koupparis,
and V. Shpilrain. Our result implies that the Kahrobaei et al.
protocol does not belong to the realm of post-quantum cryptography.
Category / Keywords: public-key cryptography / Group-based cryptography, semidirect product, matrix monoids, group-rings, Diffie-Hellman, key-exchange, discrete logarithm problem, quantum algorithms, post-quantum cryptography
Publication Info: Not yet submitted
Date: received 9 Oct 2012
Contact author: amyasnik at stevens edu
Available formats: PDF | BibTeX Citation
Version: 20121014:144002 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]