Paper 2023/991

Fast ORAM with Server-aided Preprocessing and Pragmatic Privacy-Efficiency Trade-off

Vladimir Kolesnikov, Georgia Institute of Technology
Stanislav Peceny, Georgia Institute of Technology
Ni Trieu, Arizona State University
Xiao Wang, Northwestern University
Abstract

Data-dependent accesses to memory are necessary for many real-world applications, but their cost remains prohibitive in secure computation. Prior work either focused on minimizing the need for data-dependent access in these applications, or reduced its cost by improving oblivious RAM for secure computation (SC-ORAM). Despite extensive efforts to improve SC-ORAM, the most concretely efficient solutions still require $\approx0.7$s per access to arrays of $2^{30}$ entries. This plainly precludes using MPC in a number of settings. In this work, we take a pragmatic approach, exploring how concretely cheap MPC RAM access could be made if we are willing to allow one of the participants to learn the access pattern. We design a highly efficient Shared-Output Client-Server ORAM (SOCS-ORAM) that has constant overhead, uses one round-trip of interaction per access, and whose access cost is independent of array size. SOCS-ORAM is useful in settings with hard performance constraints, where one party in the computation is more trust-worthy and is allowed to learn the RAM access pattern. Our SOCS-ORAM is assisted by a third helper party that helps initialize the protocol and is designed for the honest-majority semi-honest corruption model. We implement our construction in C++ and report its performance. For an array of length $2^{30}$ with $4$B entries, we communicate $13$B per access and take essentially no overhead beyond network latency.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. CSCML 2023
Keywords
Secure ComputationOblivious RAM
Contact author(s)
kolesnikov @ gatech edu
stan peceny @ gatech edu
nitrieu @ asu edu
wangxiao1254 @ gmail com
History
2023-06-26: approved
2023-06-26: received
See all versions
Short URL
https://ia.cr/2023/991
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/991,
      author = {Vladimir Kolesnikov and Stanislav Peceny and Ni Trieu and Xiao Wang},
      title = {Fast {ORAM} with Server-aided Preprocessing and Pragmatic Privacy-Efficiency Trade-off},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/991},
      year = {2023},
      url = {https://eprint.iacr.org/2023/991}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.