Paper 2024/1878

Tighter Provable Security for TreeKEM

Abstract

The Messaging Layer Security (MLS) protocol, recently standardized in RFC 9420, aims to provide efficient asynchronous group key establishment with strong security guarantees. The main component of MLS, which is the source of its key efficiency and security properties, is a protocol called TreeKEM. Given that a major vision for the MLS protocol is for it to become the new standard for messaging applications like WhatsApp, Facebook Messenger, Signal, etc., it has the potential to be used by a huge number of users. Thus, it is important to better understand the security of MLS and hence also of TreeKEM. In previous work, TreeKEM was proven adaptively secure in the Random Oracle Model (ROM) with a polynomial loss in security by proving a result about the security of an arbitrary IND-CPA secure public-key encryption scheme in a public-key version of a security game called GSD. Unfortunately, the concrete security guarantees implied by this line of work are not sufficient for parameters used in practice. In this work, we prove a tighter bound for the security of TreeKEM when DHIES is used for public-key encryption; DHIES is currently the only standardized scheme in MLS. Our bound implies meaningful security guarantees even for small practical parameters. We follow the above approach and first introduce a modified version of the public-key GSD game better suited for analyzing TreeKEM. We then provide a simple and detailed proof of security for DHIES in this game in the ROM and achieve a smaller security loss compared to the previous best result. Finally, we state the result on the security of TreeKEM implied by this bound and give an interpretation of the result with protocol parameters used in practice.