TY - GEN
T1 - Compact Key Storage
T2 - 44th Annual International Cryptology Conference, CRYPTO 2024
AU - Dodis, Yevgeniy
AU - Jost, Daniel
AU - Marcedone, Antonio
N1 - Publisher Copyright:
© International Association for Cryptologic Research 2024.
PY - 2024
Y1 - 2024
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85202294270&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85202294270&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-68379-4_3
DO - 10.1007/978-3-031-68379-4_3
M3 - Conference contribution
AN - SCOPUS:85202294270
SN - 9783031683787
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 75
EP - 109
BT - Advances in Cryptology – CRYPTO 2024 - 44th Annual International Cryptology Conference, Proceedings
A2 - Reyzin, Leonid
A2 - Stebila, Douglas
PB - Springer Science and Business Media Deutschland GmbH
Y2 - 18 August 2024 through 22 August 2024
ER -