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

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.