eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2022/1501

MinRank in the Head: Short Signatures from Zero-Knowledge Proofs

Gora Adj, Technology Innovation Institute
Luis Rivera-Zamarripa, Technology Innovation Institute
Javier Verbel, Technology Innovation Institute

In recent years, many digital signature scheme proposals have been built from the so-called MPC-in-the-head paradigm. This has shown to be an outstanding way to design efficient signatures with security based on hard problems. MinRank is an NP-complete problem extensively studied due to its applications to cryptanalysis since its introduction in 1999. However, only a few schemes base their security on its intractability, and their signature size is large compared with other proposals based on NP problems. This paper introduces the first MinRank-based digital signature scheme that uses the MPC-in-the-head, enabling it to achieve small signature sizes and running times. For NIST's category I parameter set, we obtain signatures of 6.5KB, which is competitive with the shortest proposals in the literature that are based on non-structured problems.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. AFRICACRYPT2023
MinRankzero-knowledgeproof of knowledgeMPC-in-the-Head
Contact author(s)
gora adj @ tii ae
luis zamarripa @ tii ae
javier verbel @ tii ae
2023-07-04: last of 2 revisions
2022-11-01: received
See all versions
Short URL
Creative Commons Attribution


      author = {Gora Adj and Luis Rivera-Zamarripa and Javier Verbel},
      title = {MinRank in the Head: Short Signatures from Zero-Knowledge Proofs},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1501},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1501}},
      url = {https://eprint.iacr.org/2022/1501}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.