Welcome to the resource topic for 2016/1141
Title:
An Oblivious Parallel RAM with O(\log^2 N) Parallel Runtime Blowup
Authors: Kartik Nayak, 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.
ePrint: https://eprint.iacr.org/2016/1141
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .