Cryptology ePrint Archive: Report 2021/215

Limbo: Efficient Zero-knowledge MPCitH-based Arguments

Cyprien Delpech de Saint Guilhem and Emmanuela Orsini and Titouan Tanguy

Abstract: This work introduces a new interactive oracle proof system based on the MPC-in-the-Head paradigm. To improve concrete efficiency and offer flexibility between computation time and communication size, a generic proof construction based on multi-round MPC protocols is proposed, instantiated with a specific protocol and implemented and compared to similar proof systems. Performance gains over previous work derive from a multi-party multiplication check optimized for the multi-round and MPC-in-the-Head settings. Of most interest among implementation optimizations is the use of identical randomness across repeated MPC protocol executions in order to accelerate computation without excessive cost to the soundness error. The new system creates proofs of SHA-256 pre-images of 43KB in 53ms with 16 MPC parties, or 23KB in 188ms for 128 parties. As a signature scheme, the non-interactive variant produces signatures, based on the AES-128 circuit, of 19KB in 4.2ms; this is 35% faster and 33 % larger than the Picnic3 scheme (13kB in 5.3ms for 16 parties) which is based on the 90% smaller LowMC circuit.

Category / Keywords: cryptographic protocols / zero-knowledge; MPC-in-the-Head; post-quantum signatures

Date: received 26 Feb 2021, last revised 9 Mar 2021

Contact author: cyprien delpechdesaintguilhem at kuleuven be,emmanuela orsini@esat kuleuven be,titouan tanguy@kuleuven be

Available format(s): PDF | BibTeX Citation

Version: 20210309:164409 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]