Paper 2022/191

NanoGRAM: Garbled RAM with $\widetilde{O}(\log N)$ Overhead

Andrew Park, Wei-Kai Lin, and Elaine Shi


We propose a new garbled RAM construction called NanoGRAM, which achieves an amortized cost of $\widetilde{O}(\lambda \cdot (W \log N + \log^3 N))$ bits per memory access, where $\lambda$ is the security parameter, $W$ is the block size, and $N$ is the total number of blocks, and $\widetilde{O}(\cdot)$ hides $poly\log\log$ factors. For sufficiently large blocks where $W = \Omega(\log^2 N)$, our scheme achieves $\widetilde{O}(\lambda \cdot W \log N)$ cost per memory access, where the dependence on $N$ is optimal (barring $poly\log\log$ factors), in terms of the evaluator's runtime. Our asymptotical performance matches even the {\it interactive} state-of-the-art (modulo $poly\log\log$ factors), that is, running Circuit ORAM atop garbled circuit, and yet we remove the logarithmic number of interactions necessary in this baseline. Furthermore, we achieve asymptotical improvement over the recent work of Heath et al. Our scheme adopts the same assumptions as the mainstream literature on practical garbled circuits, i.e., circular correlation-robust hashes or a random oracle. We evaluate the concrete performance of NanoGRAM and compare it with a couple of baselines that are asymptotically less efficient. We show that NanoGRAM starts to outperform the naive linear-scan garbled RAM at a memory size of $N = 2^9$ and starts to outperform the recent construction of Heath et al. at $N = 2^{13}$. Finally, as a by product, we also show the existence of a garbled RAM scheme assuming only one-way functions, with an amortized cost of $\widetilde{O}(\lambda^2 \cdot (W \log N + \log^3 N))$ per memory access. Again, the dependence on $N$ is nearly optimal for blocks of size $W = \Omega(\log^2 N)$ bits.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
garbled circuitgarbled ramsecure multiparty computation
Contact author(s)
ahp2 @ andrew cmu edu
weikaili @ cs cmu edu
runting @ gmail com
2022-03-30: last of 2 revisions
2022-02-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Andrew Park and Wei-Kai Lin and Elaine Shi},
      title = {NanoGRAM: Garbled RAM with $\widetilde{O}(\log N)$ Overhead},
      howpublished = {Cryptology ePrint Archive, Paper 2022/191},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.