### On the Price of Concurrency in Group Ratcheting Protocols

Alexander Bienstock, Yevgeniy Dodis, and Paul Rösler

##### 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 $\mathcal{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 $\mathcal{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 $\Omega(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 $\mathcal{O}(t\cdot(1+\log(n/t)))$, which smoothly increases from $\mathcal{O}(\log n)$ with no concurrency, to $\mathcal{O}(n)$ with unbounded concurrency, matching the previously known protocols.

Available format(s)
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in TCC 2020
Keywords
Group ratchetinggroup messagingcontinuous group key agreementCGKAcommunication complexityconcurrent updateslower boundupper boundpost-compromise securitysymbolic proof
Contact author(s)
paul roesler @ rub de
History
2021-05-19: last of 3 revisions
See all versions
Short URL
https://ia.cr/2020/1171

CC BY

BibTeX

@misc{cryptoeprint:2020/1171,
author = {Alexander Bienstock and Yevgeniy Dodis and Paul Rösler},
title = {On the Price of Concurrency in Group Ratcheting Protocols},
howpublished = {Cryptology ePrint Archive, Paper 2020/1171},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/1171}},
url = {https://eprint.iacr.org/2020/1171}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.