A Linear Algebraic Approach to the Conjugacy Search Problem in Matrix Groups over Finite Fields

Rameshwar Pandurang Maghade

Abstract: The Conjugacy Search Problem has been proposed as a foundation for several non-commutative cryptographic protocols. In this paper, we investigate the computational complexity of this problem in matrix groups over finite fields, specifically GL(n,Fq). We demonstrate that the conjugacy search problem in this setting reduces to solving a homogeneous linear system derived via tensor (Kronecker) products. This reduction enables efficient recovery of conjugating elements using standard linear algebra techniques. We provide both theoretical justification and computational evidence, implemented in SageMath, showing that conjugators can be recovered with high success rate across a wide range of parameters. Our results indicate that matrix groups over finite fields are unsuitable for cryptographic schemes based on conjugacy hardness.

Keywords: Cryptography, Conjugacy Search Problem, Matrix Groups, Finite Fields, Linear Algebra, Cryptrographic Security, Kronecker Product, Conjugacy-Based Cryptography, Non-Abelian Cryptography, SageMath