Appears in collection : 2024 - T3 - WS2 - Emerging topics in design and cryptanalysis of post-quantum schemes

The MPC-in-the-Head (MPCitH) paradigm is a versatile framework to design zero-knowledge proofs of knowledge, by relying on secure multi-party computation (MPC) techniques. Combined with the Fiat-Shamir transform, the MPCitH paradigm provides a useful tool for building practical signatures. Since 2016, the framework has been improved in a series of works which makes it a practical and tunable tool. Moreover, while it was first used to build signatures based only on symmetric primitives, it has been shown showed that it can be also useful in other research fields of post-quantum cryptography. Since 2022, the MPC-in-the-Head framework has found a lot of interest in code-based, rank-based, and multivariate cryptography, in addition to symmetric-based cryptography. For this reason, this paradigm has been utilized in 9 out of the 40 candidates selected for the first round of the recent NIST call for additional post-quantum signatures. In this talk, I will speak about the latest MPC-in-the-Head techniques. In 2023, two new techniques have been proposed: the VOLE-in-the-Head (VOLEitH) and Threshold-Computation-in-the-Head (TCitH) frameworks. We can observe that these frameworks can be interpreted in another formalism that is very popular in the SNARK state of the art, namely the formalism of the Polynomial Interactive Oracle Proofs (P-IOP). In this talk, I will present the VOLEitH and TCitH frameworks in a unified way using this alternative formalism. The main difference between the techniques used for signatures and those for SNARK is how the underlying polynomials are committed. After presenting the zero-knowledge protocol, I will thus discuss how to commit to polynomials when building signatures. Finally, I will provide an overview of how those recent frameworks impact the performance of the MPCitH signature schemes submitted to the NIST call for additional post-quantum signatures.