| Abstract: |
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 (e.g., in the Signal messenger), or on so-called 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 we discuss the trade-off between PCS, concurrency, and communication overhead in the context of group ratcheting. In particular, we will explain why state updates, concurrently initiated by t group members for reaching PCS immediately, necessarily induce a communication overhead of Ω(t) per message. This result is based on an analysis of generic group ratcheting constructions in a symbolic execution model. Secondly, we will present a new group ratcheting construction that resolves the aforementioned problems with concurrency but reaches a communication overhead of only O(t∙(1+log(n/t))), which smoothly increases from O(log n) with no concurrency, to O(n) with unbounded concurrency. Thus, we present a protocol in which each group member can (nearly) immediately recover from exposures independent of concurrency in the group with almost minimal communication overhead. We believe that this result, beyond its applicability to the IETF Message Layer Security (MLS) standardization effort, more generally and more importantly is of interest for (distributed) messaging environments where concurrency is unavoidable.
Although all three considered properties (fast recovery from exposures, little induced communication, and handling of concurrency) are indeed desired by practical messengers, our short review of current real-world protocols and academic proposals at the beginning of this talk reveals (that and) where these approaches fail. Hence, our results, if being deployed, can enhance messaging for a large audience.
While the formal execution of our results is theoretic and partially complex, the high-level ideas and concepts, summarized in this talk, are simple and intuitive. We think that our plain results are interesting for practitioners and the combination of different theoretic approaches to derive these results are insightful to real-world crypto researchers.
Our primary submission are the presentation slides. For further details and background information, imparted in the talk but maybe not entirely clear from only the slides, we provide a short extended abstract (see the second slide for the URL). |
