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 RAMCut-and-ChooseBlack-Box CryptographySecure 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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2016/907}},
      url = {https://eprint.iacr.org/2016/907}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.