SCIS 2022
2022 Symposium on
Cryptography and Information Security
Osaka, Japan & Online, Jan. 18 – 21, 2022
The Institute of Electronics,
Information and Communication Engineers

Copyright ©2022 The Institute of Electronics,
Information and Communication Engineers

Concurrent Group Operations on TreeKEM
Yugo Koyanagi ∗Masahiro Ishii ∗Keisuke Tanaka ∗Keywords: Secure group messaging, Messaging Layer Security, TreeKEM, Post-Compromise Security, concurrent operations

Abstract

Table 1: The order of concurrent group operations andDue to the COVID-19 that has been spreading worldcountermeasures to problems for two devices. ‘–’ meanswide since the end of 2019, the use of video callingthat concurrent group operations cannot be performed
applications is increasing to prevent infection. What
properly in this processing order.
is needed for video calls is the technology to exchange
after
video and audio in real time and securely. Therefore,
ADD U P DAT E REM OV E
beforeresearch and development of Messaging Layer Security
ADD
(i)
(i)
(i)(iv)(MLS) [2] which is designed as secure layer for endto-end encrypting messages in many groups has been
U P DAT E–(ii)(ii)
more active. We analyze and discuss TreeKEM, theREM OV E––(ii)(iii)
core protocol of MLS, with respect to its ability to han(i) Newly added device can’t recognize other operadle concurrent group operations.
tions. Information needs to be complemented.
In this paper, we discuss concurrent and auxiliary
operations in TreeKEM. Concurrent group operations(ii) If a device is compromised, PCS can’t be guarare more likely to occur in video calls, where the moveanteed. Further update is required.
ment of devices in a group (joining, leaving, etc.) ismore active than in messaging. Hence, our study will(iii) Devices need to be removed collectively due tobe useful for implement TreeKEM more eﬃciently andmultiple factors, such as device compromise.
securely.
Regarding the concurrent group operations of TreeKEM, (iv) There are exceptional patterns where concurrent
group operations cannot be processed.
Bhargavan et al [1] have shown ﬁve dangerous patterns
in previous studies. In this paper, we discuss all patterns including them and show three main things.
First, we show that the processing order of operations should be ADD → U P DAT E → REM OV E.
Second, we show that Post-Compromise Security (PCS)
protection after concurrent updates is possible for twodevices with the same countermeasures as in previous
studies, but does not work well for three or more devices, and then discuss countermeasures in those cases.
Third, we showed the exceptional patterns for cases
where auxiliary operations must be performed, or whereconcurrent group operations are not possible at all. Table 1 and the following enumaration outlines the problems and countermeasures for processing the concurrent execution of two devices. Those of three or more
devices can be handled by a combination of these, except for (ii).

References[1] Karthikeyan Bhargavan, Richard Barnes and EricRescorla, “TreeKEM: Asynchronous Decentralized
Key Management for Large Dynamic Groups,”
Messaging Layer Security mailing list, 2018.
[2] Richard Barnes, Benjamin Beurdouche, Raphael
Robert, Jon Millican, Emad Omara and Katriel Cohn-Gordon, “draft-ietf-mls-protocol-12- The Messaging Layer Security (MLS) Protocol,”https://datatracker.ietf.org/doc/
draft-ietf-mls-protocol/, 10/11/2021, (Accessed on 12/01/2021).

∗ Tokyo Institute of Technology, 2-12-1 Ookayama, Meguro-ku

Tokyo 152-8550 Japan1