Paper 2025/1872

Interoperable Symmetric Message Franking

Abstract

The recent Digital Markets Act (DMA), a regulation passed by the European Union in 2022, requires messaging applications with large user bases to support interoperable end-to-end encrypted (E2EE) communication. This raises numerous questions about how to adapt cryptographic protocols to this setting in a way that preserves security and privacy. This question is not only limited to the main messaging protocols, but also extends to protocols for abuse mitigation such as the symmetric message franking protocol first proposed by Facebook. The latter uses symmetric cryptography to enable reporting abusive E2EE messages in a way that allows the platform to cryptographically verify the report's veracity. In this paper, we initiate a formal treatment of interoperable symmetric message franking (IMF). We focus on a server-to-server messaging flow, where messages are routed sequentially through the sender's and recipient's service providers, but allow the recipient to dynamically choose who to send a report to. We formalize the security definitions for IMF including adapting the sender and recipient binding definitions into various reportability and unforgeability definitions that take into account one of the service providers misbehaving. We also prove relations among these new definitions. Finally, we detail an IMF construction that satisfies the security definitions, and include a discussion of users' identity privacy goals and deployment considerations.