Paper 2019/998
Beyond Honest Majority: The Round Complexity of Fair and Robust Multi-party Computation
Arpita Patra and Divya Ravi
Abstract
Two of the most sought-after properties of Multi-party Computation (MPC) protocols are fairness and guaranteed output delivery (GOD), the latter also referred to as robustness. Achieving both, however, brings in the necessary requirement of malicious-minority. In a generalised adversarial setting where the adversary is allowed to corrupt both actively and passively, the necessary bound for a $n$-party fair or robust protocol turns out to be $t_a + t_p < n$, where $t_a,t_p$ denote the threshold for active and passive corruption with the latter subsuming the former. Subsuming the malicious-minority as a boundary special case, this setting, denoted as dynamic corruption, opens up a range of possible corruption scenarios for the adversary. While dynamic corruption includes the entire range of thresholds for $(t_a,t_p)$ starting from $(\lceil \frac{n}{2} \rceil - 1 , \lfloor \frac{n}{2} \rfloor)$ to $(0,n-1)$, the boundary corruption restricts the adversary only to the boundary cases of $(\lceil \frac{n}{2} \rceil - 1, \lfloor \frac{n}{2} \rfloor)$ and $(0,n-1)$. Notably, both corruption settings empower an adversary to control majority of the parties, yet ensuring the count on active corruption never goes beyond $\lceil \frac{n}{2} \rceil - 1$. We target the round complexity of fair and robust MPC tolerating dynamic and boundary adversaries. As it turns out, $\lceil \frac{n}{2} \rceil + 1$ rounds are necessary and sufficient for fair as well as robust MPC tolerating dynamic corruption. The non-constant barrier raised by dynamic corruption can be sailed through for a boundary adversary. The round complexity of $3$ and $4$ is necessary and sufficient for fair and GOD protocols respectively, with the latter having an exception of allowing $3$ round protocols in the presence of a single active corruption. While all our lower bounds assume pair-wise private and broadcast channels and are resilient to the presence of both public (CRS) and private (PKI) setup, our upper bounds are broadcast-only and assume only public setup. The traditional and popular setting of malicious-minority, being restricted compared to both dynamic and boundary setting, requires $3$ and $2$ rounds in the presence of public and private setup respectively for both fair as well as GOD protocols.
Note: This article is a full and extended version of an earlier article to appear ASIACRYPT 2019.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- A major revision of an IACR publication in ASIACRYPT 2019
- Keywords
- Fairness and Guaranteed Output DeliveryMPCRound ComplexityDynamic and Boundary
- Contact author(s)
-
divyar @ iisc ac in
arpita @ iisc ac in
divya 18oct @ gmail com - History
- 2020-07-22: last of 3 revisions
- 2019-09-05: received
- See all versions
- Short URL
- https://ia.cr/2019/998
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2019/998, author = {Arpita Patra and Divya Ravi}, title = {Beyond Honest Majority: The Round Complexity of Fair and Robust Multi-party Computation}, howpublished = {Cryptology {ePrint} Archive, Paper 2019/998}, year = {2019}, url = {https://eprint.iacr.org/2019/998} }