Paper 2022/276
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 $q^{\frac{2}{3}(n+m)}$ up to a polynomial factor, and a deterministic algorithm for MCE with roots, running in time $q^{\min\{m,n,k\}}$ up to a polynomial factor. Lastly, to confirm these findings, we solve randomly generated instances of MCE using these two algorithms.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. Designs, Codes and Cryptography
- Keywords
- code-based cryptographypost-quantumcode equivalencerank-based
- Contact author(s)
-
krijn @ cs ru nl
simonas @ cs ru nl
mtrimoska @ cs ru nl - History
- 2023-11-04: last of 2 revisions
- 2022-03-02: received
- See all versions
- Short URL
- https://ia.cr/2022/276
- License
-
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},
url = {https://eprint.iacr.org/2022/276}
}
