Paper 2022/1512

Building MPCitH-based Signatures from MQ, MinRank, Rank SD and PKP

Thibauld Feneuil, CryptoExperts (France), Sorbonne University
Abstract

The MPC-in-the-Head paradigm is a useful tool to build practical signature schemes. Many such schemes have been already proposed, relying on different assumptions. Some are relying on standard symmetric primitives like AES, some are relying on MPC-friendly primitives like LowMC or Rain, and some are relying on well-known hard problems like the syndrome decoding problem. This work focuses on the third type of MPCitH-based signatures. Following the same methodology as the work of Feneuil, Joux and Rivain (CRYPTO'22), we apply the MPC-in-the-Head paradigm to several problems: the multivariate quadratic problem, the MinRank problem, the rank syndrome decoding problem and the permuted kernel problem. Our goal is to study how this paradigm behaves for each of those problems. For the multivariate quadratic problem, our scheme outperforms slightly the existing schemes when considering large fields (as $\mathbb{F}_{256}$), and for the permuted kernel problem, we obtain larger sizes. Even if both schemes do not outperform the existing ones according to the communication cost, they are highly parallelizable and compatible with some MPC-in-the-Head techniques (like fast signature verification) while the former proposals were not. Moreover, we propose two efficient MPC protocols to check that the rank of a matrix over a field $\mathbb{F}_q$ is upper bounded by a public constant. The first one relies on the rank decomposition while the second one relies on $q$-polynomials. We then use them to build signature schemes relying on the MinRank problem and the rank syndrome decoding problem. Those schemes outperform the former schemes, achieving sizes below $6$ KB (while using only 256 parties for the MPC protocol).

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Major revision. ACNS 2024
DOI
10.1007/978-3-031-54770-6_16
Keywords
zero-knowledge proofsMPC-in-the-Headpost-quantum signaturesrank syndrome decodingMinRankmultivariate quadratic
Contact author(s)
thibauld feneuil @ cryptoexperts com
History
2024-03-11: last of 2 revisions
2022-11-02: received
See all versions
Short URL
https://ia.cr/2022/1512
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1512,
      author = {Thibauld Feneuil},
      title = {Building MPCitH-based Signatures from MQ, MinRank, Rank SD and PKP},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1512},
      year = {2022},
      doi = {10.1007/978-3-031-54770-6_16},
      note = {\url{https://eprint.iacr.org/2022/1512}},
      url = {https://eprint.iacr.org/2022/1512}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.