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