### 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.

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
See all versions
Short URL
https://ia.cr/2022/973

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}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.