Friday, Mar 17, 2017 at 12:30 PM in 373 Soda Hall
Title: Scalable and Secure Distributed Computing
Abstract: Today, decentralized systems such as Bitcoin require algorithms that can scale to thousands of nodes. Such systems are often geographically distributed across the world making them vulnerable to malicious faults from untrusted participants. Moreover, the dynamic nature of these systems requires tight and frequent coordination among the participants. Unfortunately, handling these challenges often incurs large communication and computation overheads limiting the scalability of the system. A natural approach to scaling decentralized computation is to divide the participants into smaller groups called committees, each of which is assigned a small portion of the overall computation. This approach increases parallelism and reduces the overheads of handling faults and coordination by avoiding all-to-all communication among the participants. There are two main challenges in creating and maintaining committees. First, each committee must have at most a fixed fraction of malicious parties so that the protocol can guarantee the security of operations performed by the committee. Second, the committees must remain robust against nodes joining and leaving the protocol, and an adaptive adversary who can take over a majority of the power in each committee. In this talk, we study these challenges in the context of three well-known problems: blockchain consensus, multi-party computation, and anonymous communication. While our solution to each problem shares some similarities with the others, unique difficulties must be addressed for each problem. Our solutions require a sublinear communication and computation cost and are provably secure against malicious faults from up to a 1/3 fraction of the participants. Although our schemes scale better than existing algorithms asymptotically, they still cannot be considered as practical solutions. In an ongoing work, we are implementing practical variants of our protocols for realistic scenarios.
Bio: Mahnush Movahedi is a Postdoctoral Associate in Computer Science at Yale University. She is currently working with Professor Mariana Raykova on secure computation algorithms. Mahnush is interested in developing scalable and secure distributed algorithms that can tolerate faults from malicious parties and noisy communication channels. She earned her PhD degree in Computer Science from the University of New Mexico in 2016 supervised by Professor Jared Saia. Mahnush received the Best Paper Award of ICDCN 2014, the 2015 Outstanding Graduate Student Award of UNM, and the 2012 (ISC)2 Foundation Graduate Research Scholarship in Information Security.