NanoGRAM: Garbled RAM with O(logN) Overhead
Andrew Park
Abstract:
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 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}$.
Bio:
Andrew is currently a research engineer with MongoDB’s Cryptography Research Group, where he works on research and engineering problems related to encrypted search. Prior to that, he was a PhD student at CMU advised by Elaine Shi and Wenting Zheng. His research has focused on the practical design of cryptographic protocols, such as ORAM and PIR, as well as their applications to solve interesting real-world problems. He is broadly interested in cryptography, security, and related areas.