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.
Category / Keywords: foundations / Garbled RAM, Secure Computation Date: received 16 Nov 2014, last revised 16 Nov 2014 Contact author: stevelu8 at gmail com Available format(s): PDF | BibTeX Citation Version: 20141118:190536 (All versions of this report) Short URL: ia.cr/2014/941 Discussion forum: Show discussion | Start new discussion