Our paper answers the first question positively and gives partial answers to the second question. Specifically, we construct Circuit OPRAM, a new OPRAM scheme that makes the following contributions:
1. We achieve asymptotical improvement in terms of both total work and parallel runtime in comparison with known OPRAM schemes. More specifically, we improve the total work by a logarithmic factor and parallel runtime by poly-logarithmic factors.
2. We show that under sufficiently large block sizes, we can construct an OPRAM scheme that is asymptotically optimal both in total work and parallel runtime when the number of CPUs is not too small.
3. Our construction features a combination of novel techniques that enable us to (i) have asymptotically tight stochastic processes that do not suffer from worst-case and average-case discrepancies; and (ii) temporally reallocate work over offline and online stages of the algorithm such that we can achieve small parallel runtime overall. These techniques can be of independent interest in the design of of parallel oblivious algorithms in general.Category / Keywords: Oblivious RAM, parallel algorithm, PRAM Date: received 18 Nov 2016, last revised 22 Nov 2016 Contact author: runting at gmail com Available format(s): PDF | BibTeX Citation Version: 20161122:211211 (All versions of this report) Short URL: ia.cr/2016/1084 Discussion forum: Show discussion | Start new discussion