Crypto/Applied Crypto Seminar

Thursday, December 2, 2021 - 4:30pm to 5:30pm


In Person Group View and Virtual Presentation - ET Gates Hillman 7102 and Zoom


DAVID HEATH, Ph.D. Candidate

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

Garbled RAM (GRAM) is a powerful technique that equips Garbled Circuit (GC) with a sublinear cost RAM without adding rounds of interaction. While 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(log2 n) bits, our GRAM incurs only amortized O(w log2 n \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.

Zoom Participation. See announcement.

Event Website:

For More Information, Contact:


Seminar Series