Paper 2014/759

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

Metadata
Available format(s)
PDF
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
2014-09-29: received
See all versions
Short URL
https://ia.cr/2014/759
License
Creative Commons Attribution
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.