Paper 2014/148

Outsourcing Private RAM Computation

Craig Gentry, Shai Halevi, Mariana Raykova, and Daniel Wichs

Abstract

We construct the first schemes that allow a client to privately outsource arbitrary program executions to a remote server while ensuring that: (I) the client's work is small and essentially independent of the complexity of the computation being outsourced, and (II) the server's work is only proportional to the run-time of the computation on a random access machine (RAM), rather than its potentially much larger circuit size. Furthermore, our solutions are non-interactive and have the structure of reusable garbled RAM programs, addressing an open question of Lu and Ostrovsky (Eurocrypt 2013). We also construct schemes for an augmented variant of the above scenario, where the client can initially outsource a large private and persistent database to the server, and later outsource arbitrary program executions with read/write access to this database. Our solutions are built from non-reusable garbled RAM in conjunction with new types of reusable garbled circuits that are more efficient than prior solutions but only satisfy weaker security. For the basic setting without a persistent database, we can instantiate the required reusable garbled circuits using indistinguishability obfuscation. For the more complex setting with a persistent database we need stronger notions of obfuscation. Our basic solution also requires the client to perform a one-time preprocessing step to garble a program at the cost of its RAM run-time, and we can avoid this cost using stronger notions of obfuscation. It remains an open problem to instantiate these new types of reusable garbled circuits under weaker assumptions, possibly avoiding obfuscation altogether.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. MAJOR revision.FOCS 2014
Contact author(s)
wichs @ ccs neu edu
History
2014-08-25: revised
2014-02-27: received
See all versions
Short URL
https://ia.cr/2014/148
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/148,
      author = {Craig Gentry and Shai Halevi and Mariana Raykova and Daniel Wichs},
      title = {Outsourcing Private RAM Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2014/148},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/148}},
      url = {https://eprint.iacr.org/2014/148}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.