CryptoDB
Random-Index Oblivious RAM
| Authors: |
|
|---|---|
| Download: | |
| Presentation: | Slides |
| Conference: | TCC 2022 |
| Abstract: | We study the notion of {\em Random-index ORAM} (RORAM), which is a weak form of ORAM where the Client is limited to asking for random elements of the $N$-items memory rather than specific ones (and, possibly, modify them). That is, whenever the client issues a request, it gets in return a pair $(r,x_r)$ where $r\in_R[N]$ is a random index and $x_r$ is the content of the $r$-th memory item. Then, the client can also modify the content to some new value $x'_r$. We first argue that for certain applications the limited functionality of RORAM still suffices. These include various applications of sampling (or sub-sampling), and in particular the very-large-scale MPC application in the setting of~ Benhamouda et al. \cite{BGG+20}. Clearly, RORAM can be implemented using any ORAM scheme (by the Client selecting the random $r$'s by himself), but the hope is that the limited functionality of RORAM can make it faster and easier to implement than ORAM. Indeed, our main contributions are several RORAM schemes (both of the hierarchical-type and the tree-type) of lighter complexity than that of ORAM. |
BibTeX
@inproceedings{tcc-2022-32550,
title={Random-Index Oblivious RAM},
publisher={Springer-Verlag},
author={Shai Halevi and Eyal Kushilevitz},
year=2022
}