Multi-Party Computation in the Head – an Introduction
In 2016, the National Institute of Standards and Technology (NIST) announced a standardization process for quantum-secure cryptographic primitives. The goal was to find secure key encapsulation mechanisms (KEM) and signature schemes. One unique approach was the PICNIC signature scheme, a scheme utilizing the MPC-in-the-Head (MPCitH) paradigm. This made PICNIC an interesting approach, since its security relies on well researched block ciphers and hash functions. PICNIC was announced as an alternative candidate by NIST. A lot of follow-up schemes based on PICNIC, like BBQ, Banquet, and FEAST, were proposed using different block ciphers and variations on the original construction paradigm. In 2022, NIST announced a second call specifically for signature schemes. MPC-in-the-Head-based signature schemes became their own category, with multiple submissions in this call. This articel explains the core idea and functionality of early MPCitH based signature schemes and how we at Fraunhofer AISEC make use of the concepts.