Cryptography for Parallel RAM from Indistinguishability Obfuscation

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. ∗This is the full version of the extended abstract to appear at ACM Innovations in Theoretical Computer Science (ITCS) 2016. Previous version of this paper is known as “Computation-Trace Indistinguishability Obfuscation and its Applications”. †Academia Sinica, Taiwan (wycchen@iis.sinica.edu.tw). This work is partially supported by Academia Sinica Postdoctoral Fellowship. ‡The Chinese University of Hong Kong, Hong Kong (sherman@ie.cuhk.edu.hk). This work is supported in part by the Early Career Award and the grants from the Research Grants Council, Hong Kong (CUHK 439713 & 14201914). Part of this work was done while the author was visiting Academia Sinica. §Academia Sinica, Taiwan (kmchung@iis.sinica.edu.tw). This work is partially supported by Ministry of Science and Technology, Taiwan, under Grant no. MOST 103-2221-E-001-022-MY3. This work was done in part while the author was visiting the Simons Institute for the Theory of Computing, supported by the Simons Foundation and by the DIMACS/Simons Collaboration in Cryptography through NSF grant #CNS-1523467; and while the author was visiting The Chinese University of Hong Kong. ¶The Chinese University of Hong Kong, Hong Kong (wflai@ie.cuhk.edu.hk). ‖Academia Sinica, Taiwan (wklin@iis.sinica.edu.tw). ∗∗Virginia Commonwealth University, VA, USA (hszhou@vcu.edu). 1