Computation-sublinear refresh for forward-secure group messaging
Sublinear communication is achieved; sublinear computation for the same refresh operation is not
Motivation
Continuous group key agreement (CGKA) protocols let a dynamic group of users maintain a shared secret across joins and leaves, and forward secrecy needs an explicit key-rotation (“refresh”) step so that a later compromise of a user’s state cannot expose past group keys. Every known refresh mechanism able to guarantee forward secrecy has, until recently, forced communication linear in the group size. The source paper on this hub breaks that: it builds the first CGKA scheme with forward secrecy whose communication is worst-case sublinear — essentially independent of the group size — via a new primitive, updatable distributed broadcast encryption. But the same refresh algorithms still take time polynomial in the group size, because they take the entire current membership as an explicit input. Whether that remaining asymmetry between communication and computation can be removed is what this hub tracks.
Provenance and history
The statement comes from Bartusek, Bitansky, Dodis, Garg and Wu, Fair-Weather No More: Guaranteed Efficiency in Secure Group Messaging (IACR ePrint 2026/1677), which poses it directly (page 6, restated as Remark 5.7 on page 35) after presenting its own construction (Construction 5.10, built from a lattice-based matrix-commitment scheme under the decomposed learning-with-errors assumption, in the random oracle model). The source also raises a strictly stronger variant in a footnote — dropping the membership set as an input to the refresh algorithms entirely, rather than merely asking that they run faster while still reading it — and gives a concrete attack (its Appendix A) against a natural way of achieving that stronger property. The attack does not bear on the plain sublinear-refresh question this hub tracks, which still permits the refresh algorithms to take the membership as input.
What is settled and what is not
| Communication | Computation | |
|---|---|---|
| The source’s own construction | Sublinear (independent of group size) — achieved | Polynomial in group size — the remaining gap |
| Any scheme with the same security | Sublinear — achieved (this is what the succinctness requirement asks) | c/0065 — open: is sublinear-time refresh possible at all? |
| Refresh with no dependence on membership at all | — | A natural attempt is broken by the source’s own Appendix A attack; existence in general is not addressed by this hub’s statement |