Cryptanalysis of a Matrix-based MOR System

Abstract

We cryptanalyze a recently proposed matrix-based MOR cryptosystem. The security of the system depends on the difficulty of solving the following discrete logarithm problem: given an inner automorphism φ of SL(d, 𝔽 _q ) and φ ^a (each given in terms of their images on generators of SL(d, 𝔽 _q )), find a. We show that this problem can be reduced to a small number of similar problems in quotients of polynomial rings and solved in subexponential-time.

Key Words:

• Discrete logarithm problem
• MOR cryptosystem
• Special linear groups

2010 Mathematics Subject Classification:

• 11T70
• 15A99

Notes

Communicated by M. Kambites.