Cryptology ePrint Archive: Report 2022/276

Hardness estimates of the Code Equivalence Problem in the Rank Metric

Krijn Reijnders and 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.

Category / Keywords: public-key cryptography / code-based cryptography, post-quantum, code equivalence,

Original Publication (with minor differences): WCC 2022

Date: received 1 Mar 2022

Contact author: krijn at cs ru nl, simonas at cs ru nl, mtrimoska at cs ru nl

Available format(s): PDF | BibTeX Citation

Version: 20220302:142019 (All versions of this report)

Short URL: ia.cr/2022/276