Paper 2022/1501 Original: eprint.iacr.org/2022/1501 ↗
MinRank in the Head: Short Signatures from Zero-Knowledge Proofs
Abstract
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
- Preprint.
- History
- 2023-07-04: last updated
- 2022-11-01: published
- Short URL
- https://ia.cr/2022/1501
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}