PhD candidate, UC Berkeley
Towards Secure Computation on Large Datasets
Secure multi-party computation (MPC) enables parties with private data to collaboratively compute a global function over their private data while keeping those data private. It has a wide range of practical applications, varying from simple tasks like coin tossing to more complex ones like electronic auctions, electronic voting, privacy-preserving data mining, etc.
Despite the theoretical feasibility of MPC protocols, big data has posed serious new challenges for the current cryptographic technology. In particular, cryptographic MPC protocols are typically devised only for Boolean circuits and require that both the computational complexity and communication complexity scale with the size of the input dataset, which makes it generally unsuitable for even moderate dataset sizes. Over the past few decades, substantial effort has been devoted towards realizing cryptographic primitives that overcome these challenges. However, the best-known protocols either have a favorable communication complexity yet incur a prohibitively large computational overhead, or have a favorable computational overhead but lack in terms of communication efficiency. Can we achieve the best of both worlds?
I will present our new techniques which address the above question and make concrete positive progress. We introduce a new primitive called laconic oblivious transfer that helps to strike a balance between the two seemingly opposing goals. We show various applications of this novel technique to secure multi-party computation on large inputs with better computational complexity and communication complexity. Additionally, we present the first multi-hop homomorphic encryption scheme for random access machine (RAM) programs.
Peihan Miao is a Ph.D. candidate in the Department of Electrical Engineering and Computer Sciences, University of California at Berkeley, where she is advised by Prof. Sanjam Garg. She received her B.S. degree in Computer Science from ACM Honors Class at Shanghai Jiao Tong University. Peihan is broadly interested in theoretical computer science, especially cryptography, algorithmic game theory, and combinatorial graph theory. Her current research focuses on building cryptographic tools for the random access machine (RAM) model of computation, and aims to bridge the gap between cryptography and real-world programs. She was a research assistant at Nanyang Technological University, Singapore, a visiting student at the Simons Institute, and a research intern at Microsoft Research, Redmond.