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-knowledgeMPC-in-the-Headpost-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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.