Cryptology ePrint Archive: Report 2018/549
Adaptive Garbled RAM from Laconic Oblivious Transfer
Sanjam Garg and 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.
Category / Keywords:
Original Publication (with minor differences): IACR-CRYPTO-2018
Date: received 2 Jun 2018, last revised 2 Jun 2018
Contact author: akshayaram at berkeley edu
Available format(s): PDF | BibTeX Citation
Version: 20180604:222941 (All versions of this report)
Short URL: ia.cr/2018/549
[ Cryptology ePrint archive ]