Paper 2024/914

Compact Key Storage: A Modern Approach to Key Backup and Delegation

Yevgeniy Dodis, New York University
Daniel Jost, New York University
Antonio Marcedone, Zoom Video Communications

End-to-End (E2E) encrypted messaging, which prevents even the service provider from learning communication contents, is gaining popularity. Since users care about maintaining access to their data even if their devices are lost or broken or just replaced, these systems are often paired with cloud backup solutions: Typically, the user will encrypt their messages with a fixed key, and upload the ciphertexts to the server. Unfortunately, this naive solution has many drawbacks. First, it often undermines the fancy security guarantees of the core application, such as forward secrecy (FS) and post-compromise security (PCS), in case the single backup key is compromised. Second, they are wasteful for backing up conversations in large groups, where many users are interested in backing up the same sequence of messages. Instead, we formalize a new primitive called Compact Key Storage (CKS) as the "right" solution to this problem. Such CKS scheme allows a mutable set of parties to delegate to a server storage of an increasing set of keys, while each client maintains only a small state. Clients update their state as they learn new keys (maintaining PCS), or whenever they want to forget keys (achieving FS), often without the need to interact with the server. Moreover, access to the keys (or some subset of them) can be efficiently delegated to new group members, who all efficiently share the same server's storage. We carefully define syntax, correctness, privacy, and integrity of CKS schemes, and build two efficient schemes provably satisfying these notions. Our line scheme covers the most basic "all-or-nothing" flavor of CKS, where one wishes to compactly store and delegate the entire history of past secrets. Thus, new users enjoy the efficiency and compactness properties of the CKS only after being granted access to the entire history of keys. In contrast, our interval scheme is only slightly less efficient but allows for finer-grained access, delegation, and deletion of past keys.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2024
BackupSecure MessagingContinuous Key Agreement (CKA)
Contact author(s)
dodis @ cs nyu edu
daniel jost @ cs nyu edu
antonio marcedone @ zoom us
2024-06-08: approved
2024-06-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yevgeniy Dodis and Daniel Jost and Antonio Marcedone},
      title = {Compact Key Storage: A Modern Approach to Key Backup and Delegation},
      howpublished = {Cryptology ePrint Archive, Paper 2024/914},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.