Paper 2022/1559

Take your MEDS: Digital Signatures from Matrix Code Equivalence

Tung Chou, Academia Sinica, Taipei, Taiwan
Ruben Niederhagen, Academia Sinica, Taipei, Taiwan, University of Southern Denmark, Odense, Denmark
Edoardo Persichetti, Florida Atlantic University, Boca Raton, USA
Tovohery Hajatiana Randrianarisoa, Umea University, Umea, Sweden
Krijn Reijnders, Radboud Universiteit, Nijmegen, The Netherlands
Simona Samardjiska, Radboud Universiteit, Nijmegen, The Netherlands
Monika Trimoska, Radboud Universiteit, Nijmegen, The Netherlands

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.7 kB and signatures ranging from 18.8 kB to just around 10 kB, along with a reference implementation in C.

Available format(s)
Public-key cryptography
Publication info
group actionsignature schemecode-based cryptographypost-quantum cryptographymatrix codes
Contact author(s)
blueprint @ crypto tw
ruben @ polycephaly org
epersichetti @ fau edu
tovo @ aims ac za
krijn @ cs ru nl
simonas @ cs ru nl
mtrimoska @ cs ru nl
2022-11-10: approved
2022-11-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Tung Chou and Ruben Niederhagen and Edoardo Persichetti and Tovohery Hajatiana Randrianarisoa and Krijn Reijnders and Simona Samardjiska and Monika Trimoska},
      title = {Take your MEDS: Digital Signatures from Matrix Code Equivalence},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1559},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.