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