Adaptive Garbled RAM from Laconic Oblivious Transfer

Sanjam Garg; Rafail Ostrovsky; Akshayaram Srinivasan

Paper 2018/549

Adaptive Garbled RAM from Laconic Oblivious Transfer

Sanjam Garg, Rafail Ostrovsky, and Akshayaram Srinivasan

Abstract

We give a construction of an adaptive garbled RAM scheme. In the adaptive setting, a client first garbles a ``large'' persistent database which is stored on a server. Next, the client can provide multiple adaptively and adversarially chosen RAM garbled programs that execute and modify the stored database arbitrarily. The garbled database and the garbled program should reveal nothing more than the running time and the output of the computation. Furthermore, the sizes of the garbled database and the garbled program grow only linearly in the size of the database and the running time of the executed program respectively (up to polylogarithmic factors). The security of our construction is based on the assumption that laconic oblivious transfer (Cho et al., CRYPTO 2017) exists. Previously, such adaptive garbled RAM constructions were only known using indistinguishability obfuscation or in random oracle model. As an additional application, we note that this work yields the first constant round secure computation protocol for persistent RAM programs in the malicious setting from standard assumptions. Prior works did not support persistence in the malicious setting.

Metadata

Available format(s): PDF
Publication info: A minor revision of an IACR publication in CRYPTO 2018
Contact author(s): akshayaram @ berkeley edu
History: 2018-06-04: received
Short URL: https://ia.cr/2018/549
License: CC BY

BibTeX

@misc{cryptoeprint:2018/549,
      author = {Sanjam Garg and Rafail Ostrovsky and Akshayaram Srinivasan},
      title = {Adaptive Garbled RAM from Laconic Oblivious Transfer},
      howpublished = {Cryptology ePrint Archive, Paper 2018/549},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/549}},
      url = {https://eprint.iacr.org/2018/549}
}