TY - JOUR
T1 - Beyond Honest Majority
T2 - The Round Complexity of Fair and Robust Multi-party Computation
AU - Patra, Arpita
AU - Ravi, Divya
N1 - Publisher Copyright:
© 2023, International Association for Cryptologic Research.
PY - 2023/7
Y1 - 2023/7
N2 - 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 generalized 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 ta+ tp< n , where ta, tp 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 (ta, tp) starting from (⌈n2⌉-1,⌊n2⌋) to (0 , n- 1) , the boundary corruption restricts the adversary only to the boundary cases of (⌈n2⌉-1,⌊n2⌋) 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 ⌈n2⌉-1 . We target the round complexity of fair and robust MPC tolerating dynamic and boundary adversaries. As it turns out, ⌈n2⌉+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 pairwise-private and broadcast channels and hold in the presence of correlated randomness setup (which subsumes 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 and GOD protocols.
AB - 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 generalized 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 ta+ tp< n , where ta, tp 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 (ta, tp) starting from (⌈n2⌉-1,⌊n2⌋) to (0 , n- 1) , the boundary corruption restricts the adversary only to the boundary cases of (⌈n2⌉-1,⌊n2⌋) 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 ⌈n2⌉-1 . We target the round complexity of fair and robust MPC tolerating dynamic and boundary adversaries. As it turns out, ⌈n2⌉+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 pairwise-private and broadcast channels and hold in the presence of correlated randomness setup (which subsumes 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 and GOD protocols.
KW - Boundary
KW - Dynamic
KW - Fairness
KW - Guaranteed output delivery
KW - MPC
KW - Round complexity
UR - http://www.scopus.com/inward/record.url?scp=85163771070&partnerID=8YFLogxK
U2 - 10.1007/s00145-023-09468-0
DO - 10.1007/s00145-023-09468-0
M3 - Journal article
AN - SCOPUS:85163771070
SN - 0933-2790
VL - 36
JO - Journal of Cryptology
JF - Journal of Cryptology
IS - 3
M1 - 30
ER -