### How to Efficiently Evaluate RAM Programs with Malicious Security

Arash Afshar, Zhangxiang Hu, Payman Mohassel, and Mike Rosulek

##### Abstract

Secure 2-party computation (2PC) is becoming practical for some applications. However, most approaches are limited by the fact that the desired functionality must be represented as a boolean circuit. In response, random-access machines (RAM programs) have recently been investigated as a promising alternative representation. In this work, we present the first practical protocols for evaluating RAM programs with security against malicious adversaries. A useful efficiency measure is to divide the cost of malicious-secure evaluation of $f$ by the cost of semi-honest-secure evaluation of $f$. Our RAM protocols achieve ratios matching the state of the art for circuit-based 2PC. For statistical security $2^{-s}$, our protocol without preprocessing achieves a ratio of $s$; our online-offline protocol has a pre-processing phase and achieves online ratio $\sim 2 s / \log T$, where $T$ is the total execution time of the RAM program. To summarize, our solutions show that the extra overhead" of obtaining malicious security for RAM programs (beyond what is needed for circuits) is minimal and does not grow with the running time of the program.

Note: Clarified references to SCVM

Available format(s)
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in EUROCRYPT 2015
Keywords
secure computationoblivious ram
Contact author(s)
rosulekm @ eecs oregonstate edu
History
2015-01-30: last of 3 revisions
See all versions
Short URL
https://ia.cr/2014/759

CC BY

BibTeX

@misc{cryptoeprint:2014/759,
author = {Arash Afshar and Zhangxiang Hu and Payman Mohassel and Mike Rosulek},
title = {How to Efficiently Evaluate RAM Programs with Malicious Security},
howpublished = {Cryptology ePrint Archive, Paper 2014/759},
year = {2014},
note = {\url{https://eprint.iacr.org/2014/759}},
url = {https://eprint.iacr.org/2014/759}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.