International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: EpiGRAM: Practical Garbled RAM

David Heath , Georgia Institute of Technology
Vladimir Kolesnikov , Georgia Institute of Technology
Rafail Ostrovsky , UCLA
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2022
Award: Best Paper Award
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 only 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.
Video from EUROCRYPT 2022
  title={EpiGRAM: Practical Garbled RAM},
  author={David Heath and Vladimir Kolesnikov and Rafail Ostrovsky},