Paper 2014/941

Garbled RAM From One-Way Functions

Sanjam Garg, Steve Lu, Rafail Ostrovsky, and Alessandra Scafuro

Abstract

Yao's garbled circuit construction is a fundamental construction in cryptography and recent efficiency optimizations have brought it much closer to practice. However these constructions work only for circuits and garbling a RAM program involves the inefficient process of first converting it into a circuit. Towards the goal of avoiding this inefficiency, Lu and Ostrovsky (Eurocrypt 2013) introduced the notion of ``garbled RAM'' as a method to garble RAM programs directly. It can be seen as a RAM analogue of Yao's garbled circuits such that, the size of the garbled program and the time it takes to create and evaluate it, is proportional only to the running time on the RAM program rather than its circuit size. Known realizations of this primitive, either need to rely on strong computational assumptions or do not achieve the aforementioned efficiency (Gentry, Halevi, Lu, Ostrovsky, Raykova and Wichs, EUROCRYPT 2014). In this paper we provide the first construction with strictly poly-logarithmic overhead in both space and time based only on the minimal and necessary assumption that one-way functions exist. Our scheme allows for garbling multiple programs being executed on a persistent database, and has the additional feature that the program garbling is decoupled from the database garbling. This allows a client to provide multiple garbled programs to the server as part of a pre-processing phase and then later determine the order and the inputs on which these programs are to be executed, doing work independent of the running times of the programs itself.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Garbled RAMSecure Computation
Contact author(s)
stevelu8 @ gmail com
History
2014-11-18: received
Short URL
https://ia.cr/2014/941
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/941,
      author = {Sanjam Garg and Steve Lu and Rafail Ostrovsky and Alessandra Scafuro},
      title = {Garbled RAM From One-Way Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2014/941},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/941}},
      url = {https://eprint.iacr.org/2014/941}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.