Colloquium Details
Cryptography for Parallel RAM from Indistinguishability Obfuscation
| Author: | Kai-Min Chung, Institute of Information Science, Academia Sinica, Taiwan |
|---|---|
| Date: | May 26, 2016 |
| Time: | 15:30 |
| Location: | 220 Deschutes |
Abstract
Since many cryptographic schemes are about performing computation on data, it is important to consider a computation model which captures the prominent features of modern system architecture. Parallel random access machine (PRAM) is such an abstraction which not only models multiprocessor platforms, but also new frameworks supporting massive parallel computation such as MapReduce.
In this work, we explore the feasibility of designing cryptographic solutions for the PRAM model of computation to achieve security while leveraging the power of parallelism and random data access. We demonstrate asymptotically optimal solutions for a wide-range of cryptographic tasks based on indistinguishability obfuscation. In particular, we construct the first publicly verifiable delegation scheme with privacy in the persistent database setting, which allows a client to privately delegate both computation and data to a server with optimal efficiency.
Specifically, the server can perform PRAM computation on private data with parallel efficiency preserved (up to poly-logarithmic overhead). Our results also cover succinct randomized encoding, searchable encryption, functional encryption, secure multiparty computation, and indistinguishability obfuscation for PRAM.
We obtain our results in a modular way through a notion of computational-trace indistinguishability obfuscation (CiO), which may be of independent interests.
Biography
Kai-Min Chung is an associate research fellow at Institute of Information Science (IIS), Academia Sinica in Taiwan. Prior to joining IIS, he was a postdoc at Cornell University supported by Simons Postdoctoral Fellowship in 2010-2013, and received his Ph.D. in computer science at Harvard University.
His research interests are in the fields of cryptography, complexity theory, and quantum cryptography with recent focus on developing cryptographic solutions suitable for cloud environments, and techniques for post-quantum cryptography against quantum side information. He has served on the program committees of cryptography conferences including CRYPTO, TCC, and Asiacrypt.