Paper 2022/276

Hardness estimates of the Code Equivalence Problem in the Rank Metric

Krijn Reijnders, Simona Samardjiska, and Monika Trimoska

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). We show that MCE is equivalent to the homogeneous version of the Quadratic Maps Linear Equivalence (QMLE) problem. Using the same birthday techniques known for IP, we present an algorithm for MCE running in time $\mathcal{O}^*( q^{\frac{2}{3}(n+m)})$, and an algorithm for MCE with roots, running in time $\mathcal{O}^*(q^{m})$. We verify these algorithms in practice.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. MINOR revision.WCC 2022
Keywords
code-based cryptographypost-quantumcode equivalence
Contact author(s)
krijn @ cs ru nl
simonas @ cs ru nl
mtrimoska @ cs ru nl
History
2022-03-02: received
Short URL
https://ia.cr/2022/276
License
Creative Commons Attribution
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.