Paper 2022/982

Random-Index Oblivious RAM

Shai Halevi, Algorand Foundation
Eyal Kushilevitz, Technion – Israel Institute of Technology

We study the notion of Random-index ORAM (RORAM), which is a weak form of ORAM where the Client is limited to asking for (and possibly modifying) random elements of the $N$-items memory, rather than specific ones. 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 the limited functionality of RORAM still suffices for certain applications. 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. (TCC 2020). 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.

Available format(s)
Cryptographic protocols
Publication info
Oblivious RAM
Contact author(s)
shaih @ alum mit edu
eyalk @ cs technion ac il
2022-08-03: approved
2022-07-31: received
See all versions
Short URL
Creative Commons Attribution


      author = {Shai Halevi and Eyal Kushilevitz},
      title = {Random-Index Oblivious RAM},
      howpublished = {Cryptology ePrint Archive, Paper 2022/982},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.