Fast ORAM with Server-Aided Preprocessing and Pragmatic Privacy-Efficiency Trade-Off

Vladimir Kolesnikov, Stanislav Peceny, Ni Trieu, Xiao Wang

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 \(\approx \)0.7 s per access to arrays of \(2^{30}\) entries. This plainly precludes using MPC in a number of settings.
BibTeX
@article{kolesnikov2023fast,
  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}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2023},
  doi = {10.1007/978-3-031-34671-2\_31},
}

Loading related content...

Figure