[Resource Topic] 2021/1519: Practical Garbled RAM: GRAM with $O(\log^2 n)$ Overhead

Welcome to the resource topic for 2021/1519

Title:
Practical Garbled RAM: GRAM with O(\log^2 n) Overhead

Authors: David Heath, Vladimir Kolesnikov, Rafail Ostrovsky

Abstract:

Garbled RAM (GRAM) is a powerful technique introduced by Lu and Ostrovsky that equips Garbled Circuit (GC) with a sublinear cost RAM without adding rounds of interaction. While multiple GRAM constructions are known, none are suitable for practice, due to costs that have high constants and poor scaling. We present the first GRAM suitable for practice. For computational security parameter \kappa and for a size-n RAM that stores blocks of size w = \Omega(\log^2 n) bits, our GRAM incurs amortized O(w \cdot \log^2 n \cdot \kappa) communication and computation per access. We evaluate the concrete cost of our GRAM; our approach outperforms trivial linear-scan-based RAM for as few as 512 128-bit elements.

ePrint: https://eprint.iacr.org/2021/1519

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 .