Paper 2022/1512

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

Thibauld Feneuil, CryptoExperts (France), Sorbonne University

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 existing 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 focus 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).

Available format(s)
Public-key cryptography
Publication info
zero-knowledge proofs MPC-in-the-Head post-quantum signatures rank syndrome decoding MinRank multivariate quadratic
Contact author(s)
thibauld feneuil @ cryptoexperts com
2022-11-07: approved
2022-11-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Thibauld Feneuil},
      title = {Building MPCitH-based Signatures from MQ, MinRank, Rank SD and PKP},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1512},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.