In this paper, we show how to use the Matrix Code Equivalence (MCE) problem as a new basis to construct signature schemes. This extends previous work on using isomorphism problems for signature schemes, a trend that has recently emerged in post-quantum cryptography. Our new formulation leverages a more general problem and allows for smaller data sizes, achieving competitive performance and great flexibility. Using MCE, we construct a zero-knowledge protocol which we turn into a signature scheme named Matrix Equivalence Digital Signature (MEDS). We provide an initial choice of parameters for MEDS, tailored to NIST’s Category 1 security level, yielding public keys as small as 2.8 kB and signatures ranging from 18 kB to just around 6.5 kB, along with a reference implementation in C.
We introduce the notion of sum-matroids and show its association with sum-rank metric codes. As a consequence, some results for sum-rank metric codes by Martínez-Peñas are generalized for sum-matroids. The sum-matroids generalize the notions of matroids and q-matroids. We define the generalized weights for sum-matroids and prove a Wei-type duality theorem which generalizes the analogous cases for matroids and q-matroids.
A recent paper by Zhang and Zhang claims to construct the first code-based non-interactive key exchange protocol, using a modified version of the Code Equivalence Problem. In this paper we explain why this approach is flawed. Namely, we describe an attack which involves only linear algebra and completely breaks the protocol with overwhelming probability. A simple Magma script confirms our results.