Forward Secret Encrypted RAM: Lower Bounds and Applications

Alexander Bienstock, Yevgeniy Dodis, Kevin Yeo

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

Abstract

In this paper, we study forward secret encrypted RAMs (FS eRAMs) which enable clients to outsource the storage of an n-entry array to a server. In the case of a catastrophic attack where both client and server storage are compromised, FS eRAMs guarantee that the adversary may not recover any array entries that were deleted or overwritten prior to the attack. A simple folklore FS eRAM construction with O(log n) overhead has been known for at least two decades. Unfortunately, no progress has been made since then. We show the lack of progress is fundamental by presenting an Ω(log n) lower bound for FS eRAMs proving that the folklore solution is optimal. To do this, we introduce the symbolic model for proving cryptographic data structures lower bounds that may be of independent interest. Given this limitation, we investigate applications where forward secrecy may be obtained without the additional O(log n) overhead. We show this is possible for oblivious RAMs, memory checkers, and multicast encryption by incorporating the ideas of the folklore FS eRAM solution into carefully chosen constructions of the corresponding primitives.

Original languageEnglish (US)
Title of host publicationTheory of Cryptography - 19th International Conference, TCC 2021, Proceedings
EditorsKobbi Nissim, Brent Waters, Brent Waters
PublisherSpringer Science and Business Media Deutschland GmbH
Pages62-93
Number of pages32
ISBN (Print)9783030904555
DOIs
StatePublished - 2021
Event19th International Conference on Theory of Cryptography, TCC 2021 - Raleigh, United States
Duration: Nov 8 2021Nov 11 2021

Publication series

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

Conference

Conference19th International Conference on Theory of Cryptography, TCC 2021
Country/TerritoryUnited States
CityRaleigh
Period11/8/2111/11/21

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Forward Secret Encrypted RAM: Lower Bounds and Applications'. Together they form a unique fingerprint.

Cite this