The Path-ORAM construction assumes that the data outsourced into the ORAM scheme is split into blocks of size $\Omega(\log^2{n})$. With respect to this assumption the authors state that their storage overhead is $20N$ and their bandwidth overhead is $\mathcal{O}(\log{N})$.

How would those those performance metrics be influenced if I do not make this assumption about the block size, e.g. I assume that the blocks are of constant size (and in particular independent of N). What would be the asymptotic/practical server-side storage overhead and what would be the bandwidth overhead in this case?

  • $\begingroup$ In general, if an ORAM claims c overhead for block size at least l, the actual cost is O(c(l+B)). $\endgroup$ – redplum Jan 30 '18 at 16:30

The smallest block size that is reasonable to consider is at least $\log N$, since the headers of blocks in server storage need to contain their virtual address and position (according to the position map). The idea behind path ORAM (and most tree-based ORAMs) is to maintain the position map using a recursive ORAM. The "data units" in the position map are of size $\log N$ (a position in $[N]$), therefore the recursion will not work for a block size $O(\log N)$ since in such case you will not reduce the number of blocks in the recursion. We now understand that for the scheme to actually work, we need a block size $k\log N$ for non constant $k$. For such a block size, the overhead will be $\log N + (\log^2 N)/k$ (I know this doesn't align with the original paper, but a better parameterization of the recursion with the same construction gives this overhead. See "Circuit ORAM" paper for more details).

  • $\begingroup$ I think saying that the block size has to be at least logN is more like a constraint for tree based ORAM. It is always possible to implement the ORAM as a simple linear scan. In this case the cost is NB, while tree orams gives logNB + polylogN. For B=1, linear scan can be better for some N. $\endgroup$ – redplum Jan 30 '18 at 16:27
  • $\begingroup$ @redplum 100%, the statement should be put in the context where the data is tagged with virtual addresses. In the trivial linear ORAM, this is not necessary (I can't see how you can avoid that in known better upper bounds). $\endgroup$ – T.elMorr Jan 30 '18 at 17:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.