Cut-and-Choose for Garbled RAM

Peihan Miao

Paper 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.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. Major revision. Cryptographers' Track RSA Conference (CT-RSA) 2020
Keywords: Garbled RAM Cut-and-Choose Black-Box Cryptography Secure Computation
Contact author(s): peihan @ berkeley edu
History: 2019-12-05: last of 5 revisions; 2016-09-16: received; See all versions
Short URL: https://ia.cr/2016/907
License: CC BY

BibTeX

@misc{cryptoeprint:2016/907,
      author = {Peihan Miao},
      title = {Cut-and-Choose for Garbled {RAM}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2016/907},
      year = {2016},
      url = {https://eprint.iacr.org/2016/907}
}