Paper 2022/1501
MinRank in the Head: Short Signatures from Zero-Knowledge Proofs
, Technology Innovation Institute, Technology Innovation Institute, Technology Innovation InstituteAbstract
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.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. AFRICACRYPT2023
- Keywords
- MinRankzero-knowledgeproof of knowledgeMPC-in-the-Head
- Contact author(s)
-
gora adj @ tii ae
luis zamarripa @ tii ae
javier verbel @ tii ae - History
- 2023-07-04: last of 2 revisions
- 2022-11-01: received
- See all versions
- Short URL
- https://ia.cr/2022/1501
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/1501,
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},
url = {https://eprint.iacr.org/2022/1501}
}
