Limbo: Efficient Zero-knowledge MPCitH-based Arguments

Cyprien Delpech de Saint Guilhem; Emmanuela Orsini; Titouan Tanguy

Paper 2021/215

Limbo: Efficient Zero-knowledge MPCitH-based Arguments

Cyprien Delpech de Saint Guilhem, 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.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. Minor revision. ACM Conference on Computer and Communications Security (CCS) 2021
DOI: 10.1145/3460120.3484595
Keywords: zero-knowledge MPC-in-the-Head post-quantum signatures
Contact author(s): cyprien delpechdesaintguilhem @ kuleuven be
emmanuela orsini @ esat kuleuven be
titouan tanguy @ kuleuven be
History: 2022-02-28: last of 3 revisions; 2021-03-02: received; See all versions
Short URL: https://ia.cr/2021/215
License: CC BY

BibTeX

@misc{cryptoeprint:2021/215,
      author = {Cyprien Delpech de Saint Guilhem and Emmanuela Orsini and Titouan Tanguy},
      title = {Limbo: Efficient Zero-knowledge MPCitH-based Arguments},
      howpublished = {Cryptology ePrint Archive, Paper 2021/215},
      year = {2021},
      doi = {10.1145/3460120.3484595},
      note = {\url{https://eprint.iacr.org/2021/215}},
      url = {https://eprint.iacr.org/2021/215}
}