On the price of concurrency in group ratcheting protocols

Alexander Bienstock, Yevgeniy Dodis, Paul Rösler

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Post-Compromise Security, or PCS, refers to the ability of a given protocol to recover—by means of normal protocol operations—from the exposure of local states of its (otherwise honest) participants. While PCS in the two-party setting has attracted a lot of attention recently, the problem of achieving PCS in the group setting—called group ratcheting here—is much less understood. On the one hand, one can achieve excellent security by simply executing, in parallel, a two-party ratcheting protocol (e.g., Signal) for each pair of members in a group. However, this incurs O(n) communication overhead for every message sent, where n is the group size. On the other hand, several related protocols were recently developed in the context of the IETF Messaging Layer Security (MLS) effort that improve the communication overhead per message to O(log n). However, this reduction of communication overhead involves a great restriction: group members are not allowed to send and recover from exposures concurrently such that reaching PCS is delayed up to n communication time slots (potentially even more). In this work we formally study the trade-off between PCS, concurrency, and communication overhead in the context of group ratcheting. Since our main result is a lower bound, we define the cleanest and most restrictive setting where the tension already occurs: static groups equipped with a synchronous (and authenticated) broadcast channel, where up to t arbitrary parties can concurrently send messages in any given round. Already in this setting, we show in a symbolic execution model that PCS requires Ω(t) communication overhead per message. Our symbolic model permits as building blocks black-box use of (even “dual”) PRFs, (even key-updatable) PKE (which in our symbolic definition is at least as strong as HIBE), and broadcast encryption, covering all tools used in previous constructions, but prohibiting the use of exotic primitives. To complement our result, we also prove an almost matching upper bound of O(t· (1 + log (n/ t))), which smoothly increases from O(log n) with no concurrency, to O(n) with unbounded concurrency, matching the previously known protocols.

Original languageEnglish (US)
Title of host publicationTheory of Cryptography - 18th International Conference, TCC 2020, Proceedings
EditorsRafael Pass, Krzysztof Pietrzak
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages31
ISBN (Print)9783030643775
StatePublished - 2020
Event18th International Conference on Theory of Cryptography, TCCC 2020 - Durham, United States
Duration: Nov 16 2020Nov 19 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12551 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference18th International Conference on Theory of Cryptography, TCCC 2020
Country/TerritoryUnited States

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'On the price of concurrency in group ratcheting protocols'. Together they form a unique fingerprint.

Cite this