Take your MEDS: Digital Signatures from Matrix Code Equivalence

Tung Chou; Ruben Niederhagen; Edoardo Persichetti; Tovohery Hajatiana Randrianarisoa; Krijn Reijnders; Simona Samardjiska; Monika Trimoska

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

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: group action signature scheme code-based cryptography post-quantum cryptography matrix 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: 2023-04-20: revised; 2022-11-09: received; See all versions
Short URL: https://ia.cr/2022/1559
License: 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}
}