Paper 2022/276

Hardness estimates of the Code Equivalence Problem in the Rank Metric

Krijn Reijnders, Radboud University Nijmegen
Simona Samardjiska, Radboud University Nijmegen
Monika Trimoska, Radboud University Nijmegen

In this paper, we analyze the hardness of the Matrix Code Equivalence (MCE) 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 (IP). Under mild assumptions, we give tight reductions from MCE to the homogenous version of the Quadratic Maps Linear Equivalence (QMLE) problem, and vice versa. Furthermore, we present reductions to and from similar problems in the sum-rank metric, showing that MCE is at the core of code equivalence problems. On the practical side, using birthday techniques known for IP, we present two algorithms: a probabilistic algorithm for MCE running in time $\mathcal{O}^*( q^{\frac{2}{3}(n+m)})$, and a deterministic algorithm for MCE with roots, running in time $\mathcal{O}^*(q^{m})$. Lastly, to confirm these findings, we solve randomly-generated instances of MCE using these two algorithms.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. WCC 2022
code-based cryptography post-quantum code equivalence rank-based
Contact author(s)
krijn @ cs ru nl
simonas @ cs ru nl
mtrimoska @ cs ru nl
2022-08-29: revised
2022-03-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Krijn Reijnders and Simona Samardjiska and Monika Trimoska},
      title = {Hardness estimates of the Code Equivalence Problem in the Rank Metric},
      howpublished = {Cryptology ePrint Archive, Paper 2022/276},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.