### Hardness estimates of the Code Equivalence Problem in the Rank Metric

##### Abstract

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)
Category
Public-key cryptography
Publication info
Published elsewhere. WCC 2022
Keywords
code-based cryptography post-quantum code equivalence rank-based
Contact author(s)
krijn @ cs ru nl
simonas @ cs ru nl
mtrimoska @ cs ru nl
History
2022-08-29: revised
See all versions
Short URL
https://ia.cr/2022/276

CC BY

BibTeX

@misc{cryptoeprint:2022/276,
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{https://eprint.iacr.org/2022/276}},
url = {https://eprint.iacr.org/2022/276}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.