CryptoDB
Fully Secure MPC and zk-FLIOP Over Rings: New Constructions, Improvements and Extensions
| Authors: |
|
|---|---|
| Download: | |
| Conference: | CRYPTO 2024 |
| Abstract: | We revisit the question of the overhead to achieve full security (i.e., guaranteed output delivery) in secure multiparty computation (MPC). Recent works have closed the gap between full security and semi-honest security, by introducing protocols where the parties first compute the circuit using a semi-honest protocol and then run a verification step with sublinear communication in the circuit size. However, the number of interaction rounds in the verification step is also sublinear in the circuit's size. Unlike communication, the round complexity typically grows with the circuit's \textit{depth} and not its size. Hence, for large but shallow circuits, this may yield a significant overhead. Motivated by this gap, we make the following contributions: (1) We present a new MPC framework to obtain full security, compatible with effectively \emph{any} ring, that has an additive communication overhead of only $O(\log |C|)$, where $|C|$ is the number of multiplication gates in the circuit, and a \textit{constant} number of additional rounds beyond the underlying semi-honest protocol. Our framework works with any linear secret sharing scheme and relies on a new to utilize the machinery of \textit{zero-knowledge fully linear interactive oracle proofs} (zk-FLIOP) in a black-box way. We present several instantiations to the building blocks of our compiler, from which we derive concretely efficient protocols in different settings. (2) We present extensions to the zk-FLIOP primitive for very general settings: one for proving statements over potentially non-commutative rings that only require certain commutative properties of its largest exceptional set; and one for proving statements over Galois Rings. For Galois rings, we present concrete improvements on the current state-of-the-art for the case of constant-round proofs, by making use of \emph{Reverse Multiplication Friendly Embeddings} (RMFEs). |
BibTeX
@inproceedings{crypto-2024-34264,
title={Fully Secure MPC and zk-FLIOP Over Rings: New Constructions, Improvements and Extensions},
publisher={Springer-Verlag},
author={Anders Dalskov and Daniel Escudero and Ariel Nof},
year=2024
}