Seminars

View all Seminars  |  Download ICal for this event

Fully-Secure MPC with Minimal Trust

Series: Department Seminar

Speaker: Divya Ravi Postdoctoral Researcher Aarhus University Denmark

Date/Time: Oct 14 11:30:00

Location: Microsoft Teams - ON-LINE

Abstract:
The task of achieving full security (with guaranteed output delivery) in secure multiparty computation (MPC) is a long-studied problem. Known impossibility results (Cleve, STOC 86) rule out general solutions in the dishonest majority setting. In this work, we consider solutions that use an external trusted party (TP) to bypass the impossibility results, and study the minimal requirements needed from this trusted party. In particular, we restrict ourselves to the extreme setting where the size of the TP is independent of the size of the functionality to be computed (called ??small? TP) and this TP is invoked only once during the protocol execution.
We present several positive and negative results for fully-secure MPC in this setting.
-- For a natural class of protocols, specifically, those with a universal output decoder, we show that the size of the TP must necessarily be exponential in the number of parties. This result holds irrespective of the computational assumptions used in the protocol. We additionally rule out the possibility of achieving information-theoretic full security (without the restriction of using a universal output decoder) using a ??small? TP in the plain model (i.e., without any setup).
-- In order to get around the above negative result, we consider protocols without a universal output decoder. The main positive result in our work is a construction of such a fully-secure MPC protocol assuming the existence of a succinct Functional Encryption scheme.
-- Finally, we explore the possibility of achieving full-security with a semi-honest TP that could collude with other malicious parties (which form a dishonest majority). In this setting, we show that even fairness is impossible to achieve regardless of the ??small TP? requirement.

Speaker Bio:
Divya Ravi is currently a postdoctoral researcher at Aarhus University, Denmark. She received her PhD from the Indian Institute of Science, Bangalore, India under the guidance of Dr. Arpita Patra. Her primary research interests include Secure Multiparty Computation and Distributed Computing. More specifically, she has worked on several research problems that investigate feasibility of tasks related to secure multiparty computation (MPC) under different settings of network and computational models. Microsoft teams link: https://teams.microsoft.com/l/meetup-join/19%3ameeting_N2I5M2FjMWEtODA2YS00ZWFmLTkyNDItOGExY2MyZDBiZjkz%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%22f8aaf4da-ac16-401f-a953-eeb416835728%22%7d

Host Faculty: Prof. Arpita Patra and Prof. Chaya Ganesh