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.Category / Keywords: foundations / computation-trace indistinguishability obfuscation, indistinguishability obfuscation, computation trace, RAM, PRAM, randomized encoding Original Publication (with major differences): ACM Innovations in Theoretical Computer Science (ITCS) 2016 Date: received 29 Apr 2015, last revised 31 Dec 2015 Contact author: wycchen at iis sinica edu tw, sherman@ie cuhk edu hk, kmchung@iis sinica edu tw, wflai@ie cuhk edu hk, wklin@iis sinica edu tw, hszhou@vcu edu Available format(s): PDF | BibTeX Citation Note: Previous version of this paper is known as ``Computation-Trace Indistinguishability Obfuscation and its Applications''. Version: 20151231:192525 (All versions of this report) Short URL: ia.cr/2015/406 Discussion forum: Show discussion | Start new discussion