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

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. (, and the recent complexity analysis by Bardet and Bertin ( (12-11-22) Few more references are added.

Available format(s)
Cryptographic protocols
Publication info
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
2022-08-12: last of 2 revisions
2022-07-29: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.