Welcome to the resource topic for 2022/191
Title:
NanoGRAM: Garbled RAM with \widetilde{O}(\log N) Overhead
Authors: Andrew Park, Wei-Kai Lin, 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} 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.
ePrint: https://eprint.iacr.org/2022/191
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .