Paper 2021/244

Forward Secret Encrypted RAM: Lower Bounds and Applications

Alexander Bienstock, Yevgeniy Dodis, and Kevin Yeo


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 $\Omega(\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.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in TCC 2021
forward secrecylower boundssymbolic modelcell-probe modelORAMmemory checkersmulticast encryption
Contact author(s)
abienstock @ cs nyu edu
dodis @ cs nyu edu
kwlyeo @ google com
2022-03-07: last of 5 revisions
2021-03-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Alexander Bienstock and Yevgeniy Dodis and Kevin Yeo},
      title = {Forward Secret Encrypted RAM: Lower Bounds and Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2021/244},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.