Paper 2022/191
NanoGRAM: Garbled RAM with $\widetilde{O}(\log N)$ Overhead
Andrew Park, WeiKai Lin, and Elaine Shi
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 {\it interactive} stateoftheart (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 correlationrobust 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 linearscan 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 oneway 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.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Preprint. MINOR revision.
 Keywords
 garbled circuitgarbled ramsecure multiparty computation
 Contact author(s)

ahp2 @ andrew cmu edu
weikaili @ cs cmu edu
runting @ gmail com  History
 20220330: last of 2 revisions
 20220220: received
 See all versions
 Short URL
 https://ia.cr/2022/191
 License

CC BY
BibTeX
@misc{cryptoeprint:2022/191, author = {Andrew Park and WeiKai 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{https://eprint.iacr.org/2022/191}}, url = {https://eprint.iacr.org/2022/191} }