Paper 2016/1141

An Oblivious Parallel RAM with $O(\log^2 N)$ Parallel Runtime Blowup

Kartik Nayak and Jonathan Katz

Abstract

Oblivious RAM (ORAM) is a cryptographic primitive that allows a client to access memory locations from a server without revealing its access patterns. Oblivious Parallel RAM (OPRAM) is a PRAM counterpart of Oblivious RAM, i.e., it allows $m$ clients that trust each other to simultaneously access data from a server without revealing their access patterns. The best known OPRAM scheme achieves amortized client-server bandwidth of $O(\log^2 N)$ per lookup, but they do not achieve perfectly linear access time speedup with clients. In fact, for each access, the blowup for the slowest client (also known as parallel runtime blowup) is $O(f(m)\log m\log^2 N), f(m) = \omega(1)$. This implies that, for most accesses, some clients remain idle while others are accessing data. In this work, we show an OPRAM scheme that has parallel runtime blowup of $O(\log^2 N)$ while maintaining $O(\log^2 N)$ client-server bandwidth blowup for each client.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Oblivious RAMOblivious Parallel RAM
Contact author(s)
kartik @ cs umd edu
History
2016-12-14: received
Short URL
https://ia.cr/2016/1141
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/1141,
      author = {Kartik Nayak and Jonathan Katz},
      title = {An Oblivious Parallel RAM with $O(\log^2 N)$ Parallel Runtime Blowup},
      howpublished = {Cryptology ePrint Archive, Paper 2016/1141},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/1141}},
      url = {https://eprint.iacr.org/2016/1141}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.