@inproceedings{183aa7206f1f43c4b1ae8b858267dc5b,
title = "EpiGRAM: Practical Garbled RAM",
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 κ and for a size-n RAM that stores blocks of size w= Ω(log2n) bits, our GRAM incurs amortized O(w· log2n· κ) 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.",
keywords = "Garbled RAM, Garbled circuits, MPC, Oblivious RAM",
author = "David Heath and Vladimir Kolesnikov and Rafail Ostrovsky",
note = "This work was supported in part by NSF award #1909769, by a Facebook research award, a Cisco research award, and by Georgia Tech{\textquoteright}s IISP cyber-security seed funding (CSF) award. This material is also based upon work supported in part by DARPA under Contract No. HR001120C0087. Work of the third author is supported in part by DARPA under Cooperative Agreement HR0011-20-2-0025, NSF grant CNS-2001096, US-Israel BSF grant 2015782, Google Faculty Award, JP Morgan Faculty Award, IBM Faculty Research Award, Xerox Faculty Research Award, OKAWA Foundation Research Award, B. John Garrick Foundation Award, Teradata Research Award, Lockheed-Martin Research Award and Sunday Group. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies, either expressed or implied, of DARPA, the Department of Defense, or the U.S. Government. Distribution Statement “A” (Approved for Public Release, Distribution Unlimited). The U.S. Government is authorized to reproduce and distribute reprints for governmental purposes not withstanding any copyright annotation therein.; 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2022 ; Conference date: 30-05-2022 Through 03-06-2022",
year = "2022",
doi = "10.1007/978-3-031-06944-4_1",
language = "English (US)",
isbn = "9783031069437",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "3--33",
editor = "Orr Dunkelman and Stefan Dziembowski",
booktitle = "Advances in Cryptology – EUROCRYPT 2022 - 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2022, Proceedings",
address = "Germany",
}