Paper 2022/1512
Building MPCitH-based Signatures from MQ, MinRank, Rank SD and PKP
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
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
-
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}, url = {https://eprint.iacr.org/2022/1512} }