Paper 2025/1028

Group Key Progression: Strong Security for Shared Persistent Data

David Balbás, IMDEA Software, Universidad Politécnica de Madrid

Miro Haller, University of California, San Diego

Abstract

End-to-end encryption allows data to be outsourced and stored on an untrusted server, such as in the cloud, without compromising data privacy. In the setting when this data is shared between a group of users, all members also share access to the key material used for data encryption. In existing solutions, this key material is static and not rotated when group membership changes. Thus, also removed members can decrypt shared data, precluding post-compromise security and cryptographic access control. We propose to move away from static keys and instead use a group key progression (GKP) scheme, a novel primitive that enables a dynamic group of users to agree on a persistent sequence of keys while keeping a compact local state. GKP ensures that group members can only derive keys within a certain interval of the sequence, a notion that we call interval access control (IAC), and also provides post-compromise security. Our GKP construction, called Grappa, combines continuous group key agreement (Alwen et al., 2020) with a new abstraction called an interval scheme. The latter is a symmetric-key primitive that can derive a sequence of keys from a compact state while preserving IAC. We explore different interval scheme constructions and simulate their storage and communication costs when used in group settings. The most efficient instantiation is a generalization of dual key regression (Shafagh et al., 2020), which we formalize and prove secure. Overall, our protocols offer a practical and robust solution to protect shared, persistent data.

Note: Improved introduction and explanations in response to reviewer feedback, and typo fixes.

@misc{cryptoeprint:2025/1028,
      author = {Matilda Backendal and David Balbás and Miro Haller},
      title = {Group Key Progression: Strong Security for Shared Persistent Data},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1028},
      year = {2025},
      doi = {10.1007/978-3-032-25317-0_2},
      url = {https://eprint.iacr.org/2025/1028}
}