Paper 2023/1573

Threshold Computation in the Head: Improved Framework for Post-Quantum Signatures and Zero-Knowledge Arguments

Abstract

The MPC-in-the-Head paradigm is instrumental in building zero-knowledge proof systems and post-quantum signatures using techniques from secure multi-party computation. Many recent works have improved the efficiency of this paradigm. In this work, we improve the recently proposed framework of MPC-in-the-Head based on threshold secret sharing (to appear at Asiacrypt 2023), here called Threshold Computation in the Head. We first address the two main limitations of this framework, namely the degradation of the communication cost and the constraint on the number of parties. Our tweak of this framework makes it applicable to the previous MPCitH schemes (and in particular post-quantum signature candidates recently submitted to NIST) for which we obtain up to 50% timing improvements without degrading the signature size. Then we extend the TCitH framework to support quadratic (or higher degree) MPC round functions instead of being limited to linear functions as in the original framework. We show the benefits of our extended framework with several applications. We first propose a generic proof system for polynomial constraints that outperforms the former MPCitH-based schemes for proving low-degree arithmetic circuits. Then we apply our extended framework to derive improved variants of the MPCitH candidates submitted to NIST. For most of them, we save between 9% and 35% of the signature size. In particular, we obtain 4.2 KB signatures based on the (non-structured) MQ problem. Finally, we propose a generic way to build efficient post-quantum ring signatures from any one-way function. When applying our TCitH framework to this design with the MQ problem, the obtained scheme outperforms all the previous proposals in the state of the art. For instance, our scheme achieves sizes below 6 KB and timings around 10 ms for a ring of 4000 users.