Building MPCitH-Based Signatures from MQ, MinRank, and Rank SD

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, and the rank syndrome decoding 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 former schemes when considering large fields (as GF(256)). Even if the scheme does not always outperform the existing ones according to the communication cost, they are compatible with some MPC-in-the-Head techniques 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).