EpiGRAM: Practical Garbled RAM

David Heath, Vladimir Kolesnikov, Rafail Ostrovsky

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – EUROCRYPT 2022 - 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2022, Proceedings
EditorsOrr Dunkelman, Stefan Dziembowski
PublisherSpringer
Pages3-33
Number of pages31
ISBN (Print)9783031069437
DOIs
StatePublished - 2022
Externally publishedYes
Event41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2022 - Trondheim, Norway
Duration: May 30 2022Jun 3 2022

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13275 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2022
Country/TerritoryNorway
CityTrondheim
Period5/30/226/3/22

Keywords

  • Garbled RAM
  • Garbled circuits
  • MPC
  • Oblivious RAM

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'EpiGRAM: Practical Garbled RAM'. Together they form a unique fingerprint.

Cite this