TY - GEN
T1 - Forward Secret Encrypted RAM
T2 - 19th International Conference on Theory of Cryptography, TCC 2021
AU - Bienstock, Alexander
AU - Dodis, Yevgeniy
AU - Yeo, Kevin
N1 - Publisher Copyright:
© 2021, International Association for Cryptologic Research.
PY - 2021
Y1 - 2021
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85120084778&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85120084778&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-90456-2_3
DO - 10.1007/978-3-030-90456-2_3
M3 - Conference contribution
AN - SCOPUS:85120084778
SN - 9783030904555
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 62
EP - 93
BT - Theory of Cryptography - 19th International Conference, TCC 2021, Proceedings
A2 - Nissim, Kobbi
A2 - Waters, Brent
A2 - Waters, Brent
PB - Springer Science and Business Media Deutschland GmbH
Y2 - 8 November 2021 through 11 November 2021
ER -