## 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

Short URL: ia.cr/2014/759

[ Cryptology ePrint archive ]