Cryptology ePrint Archive: Report 2016/907

Cut-and-Choose for Garbled RAM

Peihan Miao

Abstract: Garbled RAM, introduced by Lu and Ostrovsky (Eurocrypt 2013), provides a novel method for secure computation on RAM (Random Access Machine) programs directly. It can be seen as a RAM analogue of Yao's garbled circuits such that the computational complexity and communication complexity only grow with the running time of the RAM program, avoiding the inefficient process of first converting it into a circuit. It allows for executing multiple RAM programs on a persistent database, but is secure only against semi-honest adversaries.

In this work we provide a cut-and-choose technique for garbled RAM. This gives the first constant-round two-party RAM computation protocol secure against malicious adversaries which allows for multiple RAM programs being executed on a persistent database. Our protocol makes black-box use of the one-way functions, and security of our construction is argued in the random oracle model.

Category / Keywords: Garbled RAM, Cut-and-Choose, Black-Box Cryptography, Secure Computation

Date: received 16 Sep 2016, last revised 8 Feb 2017

Contact author: peihan at berkeley edu

Available format(s): PDF | BibTeX Citation

Version: 20170208:225950 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]