International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Detect, Pack and Batch: Perfectly-Secure MPC with Linear Communication and Constant Expected Time

Authors:
Ittai Abraham , VMWare Research
Gilad Asharov , Bar-Ilan University
Shravani Patil , IISc Bangalore
Arpita Patra , Google and IISc Bangalore
Download:
DOI: 10.1007/978-3-031-30617-4_9 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2023
Abstract: We prove that perfectly-secure optimally-resilient secure Multi-Party Computation (MPC) for a circuit with $C$ gates and depth $D$ can be obtained in $O((Cn+n^4 + Dn^2)\log n)$ communication complexity and $O(D)$ expected time. For $D \ll n$ and $C\geq n^3$, this is the \textbf{first} perfectly-secure optimal-resilient MPC protocol with \textbf{linear} communication complexity per gate and \textbf{constant} expected time complexity per layer. Compared to state-of-the-art MPC protocols in the player elimination framework [Beerliova and Hirt TCC'08, and Goyal, Liu, and Song CRYPTO'19], for $C>n^3$ and $D \ll n$, our results significantly improve the run time from $\Theta(n+D)$ to expected $O(D)$ while keeping communication complexity at $O(Cn\log n)$. Compared to state-of-the-art MPC protocols that obtain an expected $O(D)$ time complexity [Abraham, Asharov, and Yanai TCC'21], for $C>n^3$, our results significantly improve the communication complexity from $O(Cn^4\log n)$ to $O(Cn\log n)$ while keeping the expected run time at $O(D)$. One salient part of our technical contribution is centered around a new primitive we call \textit{detectable secret sharing}. It is perfectly-hiding, weakly-binding, and has the property that either reconstruction succeeds, or $O(n)$ parties are (privately) detected. On the one hand, we show that detectable secret sharing is sufficiently powerful to generate multiplication triplets needed for MPC. On the other hand, we show how to share $p$ secrets via detectable secret sharing with communication complexity of just $O(n^4\log n+p \log n)$. When sharing $p\geq n^4$ secrets, the communication cost is amortized to just $O(1)$ per secret. Our second technical contribution is a new Verifiable Secret Sharing protocol that can share $p$ secrets at just $O(n^4\log n+pn\log n)$ word complexity. When sharing $p\geq n^3$ secrets, the communication cost is amortized to just $O(n)$ per secret. The best prior required $O(n^3)$ communication per secret.
BibTeX
@inproceedings{eurocrypt-2023-32963,
  title={Detect, Pack and Batch: Perfectly-Secure MPC with Linear Communication and Constant Expected Time},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-30617-4_9},
  author={Ittai Abraham and Gilad Asharov and Shravani Patil and Arpita Patra},
  year=2023
}