Subject: [MLS] Concurrency in MLS: Lower and Upper Bound of Communication Overhead

From: Paul Rösler <[email-masked]>
Date: Mon, 28 Sep 2020 11:59:23 +0200

Hi everyone,

some of you may have seen my talk on concurrency in group ratcheting at
the secure messaging summit already. The full paper by Alexander,
Yevgeniy, and me is now available as well [1]. In Section 6.5 we collect
some points relevant for practice.

I want to shortly summarize the interesting parts for MLS:

1. Lower Bound: "It will be hard to become better"

For our lower bound, we assume that members in static groups send in
rounds (i.e., in separated time slots during the execution). The number
of senders in a round i is defined as t_i. Naturally, members can decide
to send whenever (i.e., in which round) they want without being
scheduled by anyone. We only require from group ratcheting constructions
in this setting PCS against passive adversaries.
Our lower bound on communication overhead shows that every such group
ratcheting protocol, using as building blocks dual PRFs, broadcast
encryption, and hierarchical identity based encryption (thereby
key-updatable public key encryption), must let every sender in a round i
send at least t_{i-1} messages.
We note that there exists another lower bound on communication overhead
for group key exchange under FS [2] (allowing for the use of weaker
cryptographic building blocks only), showing that at least log(n)
messages must be sent per round if only one user sends.

We conclude that sending less than t messages per sender under
t-concurrency (i.e., t members send in every round) requires the use of
more powerful tools (potentially exotic ones like multi-party
non-interactive key exchange) or weaker required PCS guarantees.

It might actually be worse: In case the two mentioned lower bounds
simultaneously apply, t*log(n/t) could be the minimal communication
overhead per sender in a round. We did not formally analyze this.

2. Upper Bound: "It is achievable"

For static groups under PCS and FS we provide a group ratcheting
construction that has communication overhead of only t*(1+log(n/t))
under t-concurrency. Based on a TreeKEM-tree, the construction lets
every sender in a round firstly only update their own leaf key pair.
Secondly, senders update the paths of senders from the last round.
Although we originally didn't think of it as such (and the basic
concepts are actually closer to broadcast encryption literature), one
can intuitively view the protocol in the notation of Tainted TreeKEM [3]
as follows.
When sending:
1. Propose a new key-pair for only your own leaf and "taint" the entire
path from it to the root.
2. Commit by updating the key pairs on all paths that were tainted in
the last round and untaint them immediately.
3. All receivers agree which of all (concurrently) sent commits they
will apply (e.g., lexicographic).

We know that this simple protocol is insecure with respect to the
double-join issue. However, we think that many practical groups are
indeed static, and applying the other concepts of Tainted TreeKEM can
fix this issue. Also the issue of synchronizing rounds is only relevant
in a setting without a central server and can then be solved by weakly
synchronous clocks such that rounds have rather long periods (as
processing concurrent updates already saves a lot of time in reaching PCS).

We conclude that our idea may help to maintain a balanced tree and
speed-up path updates under almost optimal communication overhead for
users who want to reach PCS in a concurrent setting.

We are happy about any discussion, comment, or question (both on this
list and private). :)

Cheers,
Paul

[1] https://eprint.iacr.org/2020/1171.pdf
[2] https://cseweb.ucsd.edu/~daniele/papers/OptimalMulticast.pdf
[3] https://eprint.iacr.org/2019/1489.pdf

-- 
M.Sc. Paul Rösler
Horst Görtz Institute for IT-Security
Chair for Network and Data Security
Ruhr University Bochum, Germany

Universitätsstr. 150, ID 2/405
D-44801 Bochum, Germany

Telefon: +49 (0) 234 / 32-26728
https://nds.rub.de
@roeslpa