On the price of concurrency in group ratcheting protocols
Bienstock A, Dodis Y, Rösler P (2020)
Publication Type: Conference contribution
Publication year: 2020
Journal
Publisher: Springer Science and Business Media Deutschland GmbH
Book Volume: 12551 LNCS
Pages Range: 198-228
Conference Proceedings Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Event location: Durham
ISBN: 9783030643775
DOI: 10.1007/978-3-030-64378-2_8
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. 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.
Authors with CRIS profile
Involved external institutions
Germany (DE)How to cite
APA:
Bienstock, A., Dodis, Y., & Rösler, P. (2020). On the price of concurrency in group ratcheting protocols. In Rafael Pass, Krzysztof Pietrzak (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 198-228). Durham, US: Springer Science and Business Media Deutschland GmbH.
MLA:
Bienstock, Alexander, Yevgeniy Dodis, and Paul Rösler. "On the price of concurrency in group ratcheting protocols." Proceedings of the 18th International Conference on Theory of Cryptography, TCCC 2020, Durham Ed. Rafael Pass, Krzysztof Pietrzak, Springer Science and Business Media Deutschland GmbH, 2020. 198-228.
BibTeX: Download