International Association
for Cryptologic Research

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 compuation may read and modify the database and the modifications persist between computations. For the efficiency of the server, it is important that computations are modeled as RAM programs, for their runtime may be sub-linear in the size of the database.

Two security needs arise in this context: Ensuring {\\em Intergrity}, by designing means for the server to compute short proofs that allows the user to efficiently verify the correctness of the server computation, and {\\em privacy}, providing means for the user to hide his private databases and programs from a malicious server. In this work, we aim to address both security needs, especially in the stringent, {\\em adaptive}, setting, where the sequence of RAM

computations are (potentially) chosen adaptively by a malicious server depending on the messages from an honest user.

To this end, we construct the first RAM delegation scheme achieving both {\\em adaptive integrity} (a.k.a.\\ soundness) and {\\em adaptive privacy}, assuming the existence of indistinguishability obfuscation for circuits and a variant of the two-to-one somewhere perfectly binding hash [Okamoto et al. ASIACRYPT\'15] (the latter can be based on the decisional Diffie-Hellman assumption). Prior works focused either only on adaptive soundness [Kalai and Paneth, ePrint\'15] or on the weaker variant, selective soundness and privacy [Chen et al. ITCS\'16, Canetti and Holmgren ITCS\'16]. Our result extends to delegate parallel RAM (PRAM) computation as well.

At a high-level, our result is obtained by applying a generic ``{\\em security lifting technique}\'\' to the delegation scheme of Chen et al.\\ and its proof of selective soundness and privacy. The security lifting technique formalizes an abstract framework of selective security proofs, and generically ``lifts\'\' such proofs into proofs of adaptive security. We believe that this technique can potentially be applied to other cryptographic schemes and is of independent interest.