Resolving Concurrency in Group Ratcheting Protocols 🔐

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. Reaching PCS in group messaging protocols so far either bases on n parallel two-party messaging protocol executions between all pairs of group members in a group of n users (like in the Signal client), or on tree based group ratcheting protocols (e.g., developed in the context of the IETF Message Layer Security initiative). Both approaches have great restrictions: parallel pairwise executions induce for each state update a communication overhead of 'O(n)'. While tree based protocols reduce this overhead to 'O(log n)', they cannot handle concurrent state updates. For resolving such inevitably occurring concurrent updates, these protocols delay reaching PCS up to n communication time slots (potentially more in asynchronous settings such as messaging). Furthermore, a consensus mechanism (such as a central server) is needed in practice.

In this talk, based on a joint work with Alexander Bienstock and Yevgeniy Dodis, the speaker discusses the trade-off between PCS, concurrency, and communication overhead in the context of group ratcheting. In particular, he explains why state updates, concurrently initiated by 't' group members for reaching PCS immediately induce a communication overhead of 'Ω(t)' per message. He shows a new group ratcheting construction that resolves the aforementioned restriction of concurrency but reaches a communication overhead of only 'O(t + t\*log(n/t))', which smoothly increases from 'O(log n)' with no concurrency to 'O(n)' with unbounded concurrency. Thus, he presents a protocol in which each group member can (nearly) immediately recover from exposures independent of concurrency in the group with almost minimal communication overhead. He believes that this result is of interest for the IETF Message Layer Security (MLS) standardization effort; but more general and more importantly for distributed messaging environments where concurrency is unavoidable.