International Association for Cryptologic Research

International Association
for Cryptologic Research


Efficient Fully Secure Computation via Distributed Zero-Knowledge Proofs

Elette Boyle
Niv Gilboa
Yuval Ishai
Ariel Nof
DOI: 10.1007/978-3-030-64840-4_9
Search ePrint
Search Google
Abstract: Secure computation protocols enable mutually distrusting parties to compute a function of their private inputs while revealing nothing but the output. Protocols with {\em full security} (also known as {\em guaranteed output delivery}) in particular protect against denial-of-service attacks, guaranteeing that honest parties receive a correct output. This feature can be realized in the presence of an honest majority, and significant research effort has gone toward attaining full security with good asymptotic and concrete efficiency. We present a fully secure protocol for {\em any constant} number of parties $n$ and $t1$ corrupted parties. %Similarly to the recent fully secure 3-party protocol of Boyle {\em et al.} (CCS 2019), our protocol builds on the sublinear-communication distributed zero-knowledge proofs of Boneh {\em et al.} (Crypto 2019) to compile any ``natural'' semi-honest protocol into a fully secure protocol. However, applying this tool with $t>1$ corrupted parties introduces several nontrivial challenges that we overcome in this work. Our protocol relies on {\em replicated secret sharing} to minimize communication and simplify the mechanism for achieving full security. This results in computational cost that scales exponentially with $n$. Our main protocol builds on a new honest-majority protocol for verifying the correctness of multiplication triples by making a {\em general} use of distributed zero-knowledge proofs. While the protocol only achieves the weaker notion of {\em security with abort}, it applies to any linear secret-sharing scheme and provides a conceptually simpler, more general, and more efficient alternative to previous protocols from the literature. In particular, it can be combined with the Fiat-Shamir heuristic to simultaneously achieve logarithmic communication complexity and constant round complexity.
Video from ASIACRYPT 2020
  title={Efficient Fully Secure Computation via Distributed Zero-Knowledge Proofs},
  booktitle={Advances in Cryptology - ASIACRYPT 2020},
  author={Elette Boyle and Niv Gilboa and Yuval Ishai and Ariel Nof},