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 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 starting from to , the boundary corruption restricts the adversary only to the boundary cases of and . Notably, both corruption settings empower an adversary to control majority of the parties, yet ensuring the count on active corruption never goes beyond . We target the round complexity of fair and robust MPC tolerating dynamic and boundary adversaries. As it turns out, 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 and is necessary and sufficient for fair and GOD protocols respectively, with the latter having an exception of allowing 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 and 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)
PDF
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.