CryptoDB
Beyond Honest Majority: The Round Complexity of Fair and Robust Multi-party Computation
| Authors: | |
|---|---|
| Download: | |
| 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 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 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 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. |
BibTeX
@article{asiacrypt-2019-30024,
title={Beyond Honest Majority: The Round Complexity of Fair and Robust Multi-party Computation},
booktitle={Advances in Cryptology – ASIACRYPT 2019},
series={Advances in Cryptology – ASIACRYPT 2019},
publisher={Springer},
volume={11921},
pages={456-487},
doi={10.1007/978-3-030-34578-5_17},
author={Arpita Patra and Divya Ravi},
year=2019
}