Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.


An Efficient and Generic Construction for Signal’s Handshake (X3DH): Post-Quantum, State Leakage Secure, and Deniable

December 1, 2022


Thomas Prest - PQShield


The Signal protocol is a secure instant messaging protocol that underlies the security of numerous applications such as WhatsApp, Skype, Facebook Messenger among many others. The Signal protocol consists of two sub-protocols known as the X3DH protocol and the double ratchet protocol, where the latter has recently gained much attention. For instance, Alwen, Coretti, and Dodis (Eurocrypt’19)provided a concrete security model along with a generic construction based on simple building blocks that are instantiable from versatile assumptions, including post-quantum ones. In contrast, works focusing on the X3DH protocol are limited, and a post-quantum secure Signal protocol is yet to be known.

In this work, we cast the X3DH protocol as a specific type of authenticated key exchange (AKE) protocol, which we call a Signal-conforming AKE protocol, and formally define its security model based on the vast prior works on AKE protocols. We then provide the first efficient generic construction of a Signal-conforming AKE protocol based on standard cryptographic primitives such as key encapsulation mechanisms (KEM) and signature schemes. This results in the first post-quantum secure replacement of the X3DH protocol based on well-established assumptions. Combined with a post-quantum secure double ratchet protocol, this leads to the first post-quantum secure Signal protocol. 

While our first protocol already satisfies a weak flavor of deniability, we show how to progressively strengthen it using ring signatures in a second protocol, then by adding non-interactive zero-knowledge proof systems in a third protocol. Finally, we provide a full-fledged, generic C implementation of our first protocol. We instantiate it with the currently selected NIST PQC standards (Kyber, Dilithium, Falcon and SPHINCS+) and compare the resulting bandwidth and computation performances. Our implementation is publicly available in Github.

Event Details



Related Topics

Security and Privacy: post-quantum cryptography

Created November 29, 2022, Updated December 06, 2022