Cryptology ePrint Archive: Report 2014/759

How to Efficiently Evaluate RAM Programs with Malicious Security

Arash Afshar and Zhangxiang Hu and 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.

Category / Keywords: cryptographic protocols / secure computation, oblivious ram

Original Publication (with major differences): IACR-EUROCRYPT-2015

Date: received 28 Sep 2014, last revised 30 Jan 2015

Contact author: rosulekm at eecs oregonstate edu

Available format(s): PDF | BibTeX Citation

Note: Clarified references to SCVM

Version: 20150130:191311 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]