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 $\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).