Paper 2015/406

Cryptography for Parallel RAM from Indistinguishability Obfuscation

Yu-Chi Chen, Sherman S. M. Chow, Kai-Min Chung, Russell W. F. Lai, Wei-Kai Lin, and Hong-Sheng Zhou

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.

Note: Previous version of this paper is known as ``Computation-Trace Indistinguishability Obfuscation and its Applications''.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Major revision. ACM Innovations in Theoretical Computer Science (ITCS) 2016
Keywords
indistinguishability obfuscationcomputation traceRAMPRAMrandomized encoding
Contact author(s)
wycchen @ 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
History
2015-12-31: revised
2015-05-01: received
See all versions
Short URL
https://ia.cr/2015/406
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/406,
      author = {Yu-Chi Chen and Sherman S.  M.  Chow and Kai-Min Chung and Russell W.  F.  Lai and Wei-Kai Lin and Hong-Sheng Zhou},
      title = {Cryptography for Parallel {RAM} from Indistinguishability Obfuscation},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/406},
      year = {2015},
      url = {https://eprint.iacr.org/2015/406}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.