Hardness estimates of the code equivalence problem in the rank metric

Abstract

Abstract In this paper, we analyze the hardness of the Matrix Code Equivalence () problem for matrix codes endowed with the rank metric, and provide the first algorithms for solving it. We do this by making a connection to another well-known equivalence problem from multivariate cryptography—the Isomorphism of Polynomials (). Under mild assumptions, we give tight reductions from to the homogenous version of the Quadratic Maps Linear Equivalence () problem, and vice versa. Furthermore, we present reductions to and from similar problems in the sum-rank metric, showing that is at the core of code equivalence problems. On the practical side, using birthday techniques known for , we present two algorithms: a probabilistic algorithm for running in time $$q^{\frac{2}{3}(n+m)}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>q</mml:mi> <mml:mrow> <mml:mfrac> <mml:mn>2</mml:mn> <mml:mn>3</mml:mn> </mml:mfrac> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>+</mml:mo> <mml:mi>m</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:msup> </mml:math> up to a polynomial factor, and a deterministic algorithm for with roots, running in time $$q^{\min \{m,n,k\}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>q</mml:mi> <mml:mrow> <mml:mo>min</mml:mo> <mml:mo>{</mml:mo> <mml:mi>m</mml:mi> <mml:mo>,</mml:mo> <mml:mi>n</mml:mi> <mml:mo>,</mml:mo> <mml:mi>k</mml:mi> <mml:mo>}</mml:mo> </mml:mrow> </mml:msup> </mml:math> up to a polynomial factor. Lastly, to confirm these findings, we solve randomly-generated instances of using these two algorithms.

Topics & Concepts