Delegating RAM Computations with Adaptive Soundness and Privacy
We consider the problem of delegating RAM computations over persistent databases. A user wishes to delegate a sequence of computations over a database to a server, where each computation may read and modify the database and the modifications persist betwe
- PDF / 570,092 Bytes
- 28 Pages / 439.37 x 666.142 pts Page_size
- 69 Downloads / 206 Views
Center for Encrypted Functionalities, University of California Los Angeles, Los Angeles, USA [email protected] 2 Academia Sinica, Taipei, Taiwan {wycchen,kmchung}@iis.sinica.edu.tw 3 University of California, Santa Barbara, USA [email protected] 4 Cornell University, Ithaca, USA [email protected] Abstract. We consider the problem of delegating RAM computations over persistent databases. A user wishes to delegate a sequence of computations over a database to a server, where each computation may read and modify the database and the modifications persist between computations. Delegating RAM computations is important as it has the distinct feature that the run-time of computations maybe sub-linear in the size of the database. We present the first RAM delegation scheme that provide both soundness and privacy guarantees in the adaptive setting, where the sequence of delegated RAM programs are chosen adaptively, depending potentially on the encodings of the database and previously chosen programs. Prior works either achieved only adaptive soundness without privacy [Kalai and Paneth, ePrint’15], or only security in the selective setting where all RAM programs are chosen statically [Chen et al. ITCS’16, Canetti and Holmgren ITCS’16]. Our scheme assumes the existence of indistinguishability obfuscation (iO) for circuits and the decisional Diffie-Hellman (DDH) assumption. However, our techniques are quite general and in particular, might be applicable even in settings where iO is not used. We provide a “security lifting technique” that “lifts” any proof of selective security satisfying certain special properties into a proof of adaptive security, for arbitrary cryptographic schemes. We then apply this technique to the delegation scheme of Chen et al. and its selective security proof, obtaining that their scheme is essentially already adaptively secure. Because of the general approach, we can also easily extend to delegating parallel RAM (PRAM) computations. We believe that the security lifting technique can potentially find other applications and is of independent interest. This paper was presented jointly with “Adaptive Succinct Garbled RAM, or How To Delegate Your Database” by Ran Canetti, Yilei Chen, Justin Holmgren, and Mariana Raykova. The full version of this paper is available on ePrint [2]. Information about the grants supporting the authors can be found in “Acknowledgements” section. c International Association for Cryptologic Research 2016 M. Hirt and A. Smith (Eds.): TCC 2016-B, Part II, LNCS 9986, pp. 3–30, 2016. DOI: 10.1007/978-3-662-53644-5 1
4
1
P. Ananth et al.
Introduction
In the era of cloud computing, it is of growing popularity for users to outsource both their databases and computations to the cloud. When the databases are large, it is important that the delegated computations are modeled as RAM programs for efficiency, as computations maybe sub-linear, and that the state of a database is kept persistently across multiple (sequential) computations to support continuous updates to the databa
Data Loading...
