Paper 2025/1909

Weak Instances of the Two Matrix Code Equivalence Problem

Abstract

Nowadays, the Matrix Code Equivalence Problem shows potential applicability in constructing efficient and secure advanced digital signatures, focusing on linkable ring signatures, threshold signatures, and blind signatures. Current constructions of these advanced signatures rely on relaxed instantiations of the Matrix Code Equivalence Problem (namely, the 2-MCE problem): given two pairs of equivalent matrix codes, find (if it exists) the secret isometry connecting the pairs. For example, the linkable ring signature construction by Chou et al. (AFRICACRYPT, 2023) builds on top of the Inverse Matrix Code Equivalence Problem: given three equivalent matrix codes, where one pair of the codes is connected by the secret isometry and another by the inverse of that isometry, find the secret isometry. This paper studies the 2-MCE problem, focusing on the family of instances where the secret isometry is (skew) symmetric. Our main contribution is a polynomial-time algorithm for these instances of the 2-MCE problem. We prove that the algorithm returns a valid solution whenever an explicit invertibility condition and two kernel-dimension conditions hold. Our results have a crucial security impact on the recent blind signature construction proposed by Kuchta, LeGrow, and Persichetti (Cryptography and Communications, 2026), whose security relies on the hardness of solving these kinds of instance of the Inverse Matrix Code Equivalence Problem: we show that this problem reduces to the instances we solve. More precisely, we show that we can recover the secret key of the blind signature construction by Kuchta, LeGrow, and Persichetti (Cryptography and Communications, 2026), with an estimated security of 128 bits, in less than a minute.

Note: Major changes: separating proven results from heuristics; main algorithm has been improved; new section about experiments on the heuristics was added.