Paper 2023/557
Detect, Pack and Batch: Perfectly-Secure MPC with Linear Communication and Constant Expected Time
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 first perfectly-secure optimal-resilient MPC protocol with linear communication complexity per gate and 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 $\Omega(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 "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)$ field elements 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)$ filed elements per secret. The best prior required $\Omega(n^3)$ communication per secret.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- A major revision of an IACR publication in EUROCRYPT 2023
- DOI
- 10.1007/978-3-031-30617-4_9
- Keywords
- MPCPerfect SecurityVerifiable Secret Sharing
- Contact author(s)
-
iabraham @ vmware com
Gilad Asharov @ biu ac il
shravanip @ iisc ac in
arpita @ iisc ac in - History
- 2023-04-24: approved
- 2023-04-19: received
- See all versions
- Short URL
- https://ia.cr/2023/557
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/557, author = {Ittai Abraham and Gilad Asharov and Shravani Patil and Arpita Patra}, title = {Detect, Pack and Batch: Perfectly-Secure {MPC} with Linear Communication and Constant Expected Time}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/557}, year = {2023}, doi = {10.1007/978-3-031-30617-4_9}, url = {https://eprint.iacr.org/2023/557} }