Wednesday, April 6, 2016 at 3: 30 PM in Rice 242
Advisor: David Evans
Committee Members: Westley Weimer (Committee Chair), Mohammad Mahmoody, Denis Nekipelov (Minor Representative, Economics), Bryan Parno (Microsoft Research).
Title: Demystifying secure computation: familiar abstractions for efficient protocols
Over the past few years, secure multi-party computation (MPC) has been transformed from a research tool to a practical one with numerous interesting applications in practice. MPC is a cryptographic technique that allows two or more parties to collaboratively perform a computation without revealing their own private inputs to each other (other than what can be inferred from the output result). Example uses include private auctions where all the participants keep their bids private, private aggregation of corporate-internal data for economic analysis, and private set intersection.
However, we still have significant challenges to overcome before MPC gains widespread acceptance. Most of it boils down to the fact that a diverse set of specialized expertise is required to write efficient MPC programs. Depending on the application, it may require expertise in cryptography or circuit design optimization, even for fairly simple programs. Moreover, keeping all intermediate values of an MPC computation private makes it hard for a programmer to efficiently perform random memory access locations. This dissertation lowers the barriers to general-purpose MPC by presenting a new programming language for writing MPC without cryptographic expertise, as well as improvements to the state of the art in the various components around it. We also present new constructions for basic data structures that are efficient in the MPC context, and new efficient constructions of Oblivious RAM (ORAM) that hides input-dependent memory access patterns.