Paper 2021/1519

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

David Heath, Vladimir Kolesnikov, and 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
MPCGarbled CircuitsOblivious RAMGarbled RAM
Contact author(s)
heath davidanthony @ gatech edu
History
2021-11-20: received
Short URL
https://ia.cr/2021/1519
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1519,
      author = {David Heath and Vladimir Kolesnikov and Rafail Ostrovsky},
      title = {Practical Garbled {RAM}: {GRAM} with $O(\log^2 n)$ Overhead},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/1519},
      year = {2021},
      url = {https://eprint.iacr.org/2021/1519}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.