Abstract
We show how to garble a large database and then a sequence of adaptively and adversarially chosen RAM programs that query and modify the database in arbitrary ways. The security property is that the garbled database and programs reveal only the outputs of the programs when run in sequence on the database. The runtime, space requirements and description size of the garbled programs are proportional only to those of the plaintext programs and the security parameter. The construction is based on indistinguishability obfuscation for circuits and poly-to-one collision-resistant hash functions.
As an immediate application, our scheme is the first to provide a way to outsource large databases to untrusted servers, and later query and update the database over time in a private and verifiable way, with complexity and description size proportional to those of the unprotected queries.
Joint work with Ran Canetti, Yilei Chen and Justin Holmgren