Paper 2022/1559 Original: eprint.iacr.org/2022/1559 ↗
Take your MEDS: Digital Signatures from Matrix Code Equivalence
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.
- History
- 2023-04-20: last updated
- 2022-11-09: published
- Short URL
- https://ia.cr/2022/1559
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2022/1559}
}