Paper 2022/973

MR-DSS – Smaller MinRank-based (Ring-)Signatures

Emanuele Bellini, Technology Innovation Institute
Andre Esser, Technology Innovation Institute
Carlo Sanna, Politecnico di Torino
Javier Verbel, Technology Innovation Institute
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). (12-11-22) Few more references are added.

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-08-12: last of 2 revisions
2022-07-29: received
See all versions
Short URL
https://ia.cr/2022/973
License
Creative Commons Attribution
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.