Paper 2016/1141

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

Kartik Nayak and Jonathan Katz


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.

Available format(s)
Publication info
Preprint. MINOR revision.
Oblivious RAMOblivious Parallel RAM
Contact author(s)
kartik @ cs umd edu
2016-12-14: received
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.