Paper 2016/907 Original: eprint.iacr.org/2016/907 ↗
Cut-and-Choose for Garbled RAM
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
- Preprint.
- History
- 2019-12-05: last updated
- 2016-09-16: published
- Short URL
- https://ia.cr/2016/907
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}