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
Abstract

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
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
History
2022-11-10: approved
2022-11-09: received
See all versions
Short URL
https://ia.cr/2022/1559
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1559,
      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{https://eprint.iacr.org/2022/1559}},
      url = {https://eprint.iacr.org/2022/1559}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.