View all Seminars  |  Download ICal for this event

On the Round Complexity Landscape of Secure Multi-party Computation

Series: Ph.D. Colloquium

Speaker: Ms. Divya Ravi Ph.D student Dept. of CSA

Date/Time: Feb 26 10:00:00

Location: CSA Seminar Hall (Room No. 254, First Floor)

Faculty Advisor: Dr. Arpita Patra

In secure multi-party computation (MPC), n parties wish to jointly perform a computation on their private inputs in a secure way, so that no adversary A corrupting a coalition of t among the n parties can learn more information than their outputs (privacy), nor can they affect the outputs of the computation other than by choosing their own inputs (correctness). The round complexity of MPC protocols is a fundamental question in the area of secure computation and its study constitutes a phenomenal body of work in the MPC literature. The research goal of this thesis is to advance the state of the art by expanding this study of round complexity to various adversarial settings and network models. The questions addressed in the thesis are of both theoretical and practical importance. In this talk, we first present a high-level overview of our results which involves establishing new lower bounds on the round complexity of MPC under various settings and constructing upper bounds with optimal round complexity. We then elaborate on one of our recent results that focuses on the exact round complexity of fair and robust MPC protocols in a generalized adversarial setting. Fairness (adversary obtains the output iff honest parties do) and Robustness (adversary cannot prevent honest parties from obtaining the output) are two of the most sought-after properties of MPC protocols. Achieving both, however, brings in the necessary requirement that only upto minority of the parties can be actively corrupt (where actively corrupt parties are allowed to deviate from the protocol in any arbitrary manner). In a generalized adversarial setting where the adversary is allowed to corrupt both actively and passively (weaker adversarial model where corrupt parties follow protocol specifications but try to learn more information than they are supposed to know), 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 active 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 (ceil(n/2) – 1, floor(n/2)) to (0, n − 1), the boundary corruption restricts the adversary only to the boundary cases of (ceil(n/2) – 1, floor(n/2)) 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 ceil(n/2) – 1. We target the round complexity of fair and robust MPC tolerating dynamic and boundary adversaries. References: [1] Arpita Patra, Divya Ravi. On the Power of Hybrid Networks in Multi-Party Computation. IEEE Transactions on Information Theory 2018. [2] Arpita Patra, Divya Ravi. On the Exact Round Complexity of Secure Three-Party Computation. CRYPTO 2018. [3] Megha Byali, Arun Joseph, Arpita Patra, Divya Ravi. Fast Secure Computation for Small Population over the Internet. ACM CCS 2018. [4] Arpita Patra, Divya Ravi, Swati Singla. On the Exact Round Complexity of Best-of-both-Worlds Multi-party Computation. Under Submission. [5] Arpita Patra, Divya Ravi. Beyond Honest Majority: The Round Complexity of Fair and Robust Multi-party Computation. ASIACRYPT 2019.

Speaker Bio:

Host Faculty: