Paper 2022/973
MR-DSS – Smaller MinRank-based (Ring-)Signatures
, Technology Innovation Institute, Technology Innovation Institute, Politecnico di Torino, Technology Innovation InstituteAbstract
In the light of NIST’s announced reopening of the call for digital signature proposals in 2023 due to lacking diversity, there is a strong need for constructions based on other established hardness assumptions. In this work we construct a new post-quantum secure digital signature scheme based on the $MinRank$ problem, a problem with a long history of applications in cryptanalysis that led to a strong belief in its hardness. Initially following a design by Courtois (Asiacrypt '01) based on the Fiat--Shamir transform, we make use of several recent developments in the design of sigma protocols to reduce signature size and improve efficiency. This includes the recently introduced $sigma \; protocol \; with \; helper$ paradigm (Eurocrypt '19) and combinations with $cut$-$and$-$choose$ techniques (CCS '18). Moreover, we introduce several improvements to the core of the scheme to further reduce its signature size.
Note: (08-11-22) We consider the recent algorithm by Bardet et al. (https://eprint.iacr.org/2022/1031), and the recent complexity analysis by Bardet and Bertin (https://arxiv.org/abs/2208.01442). (08-12-22) Few more references are added, 2022/973. (09-10-22) fixed parameters choice.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- Fiat–Shamir MinRank post-quantum signature ring signature sigma protocols
- Contact author(s)
-
emanuele bellini @ tii ae
andre esser @ tii ae
carlo sanna @ polito it
javier verbel @ tii ae - History
- 2022-09-21: last of 4 revisions
- 2022-07-29: received
- See all versions
- Short URL
- https://ia.cr/2022/973
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/973,
author = {Emanuele Bellini and Andre Esser and Carlo Sanna and Javier Verbel},
title = {MR-DSS – Smaller MinRank-based (Ring-)Signatures},
howpublished = {Cryptology ePrint Archive, Paper 2022/973},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/973}},
url = {https://eprint.iacr.org/2022/973}
}
