Paper 2022/973
MR-DSS – Smaller MinRank-based (Ring-)Signatures
Abstract
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)
- 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}, url = {https://eprint.iacr.org/2022/973} }