Welcome to the resource topic for 2022/276
Title:
Hardness estimates of the Code Equivalence Problem in the Rank Metric
Authors: Krijn Reijnders, Simona Samardjiska, 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.
ePrint: https://eprint.iacr.org/2022/276
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .