(P)KT-IEE: Secure key transparency protocols for interoperable end-to-end encrypted message systems

End-to-End-Encrypted (E2EE) messaging services are a key privacy enhancing technology enabling free and open speech on the Internet. They are widely deployed and very popular with large userbases. E2EE relies critically on the trustworthy distribution and storage of users’ public keys. To that end, Key Transparency (KT) has been deployed by popular platforms (such as Whatsapp) and many designs and refinements have been proposed. However, KT in the interoperable E2EE setting has not yet been investigated. We address the challenge of distributing and trusting keys across platform boundaries and propose a Secure Key Transparency Protocol for Interoperable End-to-End Encrypted Message Systems ((P)KT-IEE). We also present a privacy preserving variant of our proposed protocol. This work is timely since the EU’s Digital Markets Act obliges E2EE messaging platforms to allow users from different services to be able to communicate with each other. Our security and performance analysis show that our protocols are secure, private, resist local surveillance, and practical (allowing for trade-offs between light-weight and privacy preservation).