In 2025, Signal deployed the Sparse Post-Quantum Ratchet (SPQR), an MLKEM-based post-quantum secure messaging protocol that was combined with the widely used Double Ratchet protocol to attain hybrid Forward Secrecy (FS) and Post-Compromise Security (PCS): FS and PCS hold unless both the classic Elliptic-Curve Diffie-Hellman and the post-quantum Key Encapsulation Mechanism constructions are broken. This paper presents the verification-driven process used to design SPQR and the first formal specification and security analysis of SPQR, along with formal guarantees for its implementation. We detail the modular design of the SPQR protocol in terms of a core Sparse Continuous Key Agreement (SCKA) component (as defined in [4] ). We evaluate a series of candidate protocols, including the deployed protocol, in various fine-grained compromise scenarios, using the ProVerif symbolic analyzer. Beyond design-time verification, we integrate the hax toolchain into Signal's continuous integration pipeline to prove runtime safety of the production implementation and to prove that the implementation meets the security goals of the protocol. The results of this work are now deployed in Signal Messenger and relied upon by millions of users.
In 2025, Signal deployed the Sparse Post-Quantum Ratchet (SPQR), an MLKEM-based post-quantum secure messaging protocol that was combined with the widely used Double Ratchet protocol to attain hybrid Forward Secrecy (FS) and Post-Compromise Security (PCS): FS and PCS hold unless both the classic Elliptic-Curve Diffie-Hellman and the post-quantum Key Encapsulation Mechanism constructions are broken. This paper presents the verification-driven process used to design SPQR and the first formal specification and security analysis of SPQR, along with formal guarantees for its implementation. We detail the modular design of the SPQR protocol in terms of a core Sparse Continuous Key Agreement (SCKA) component (as defined in [4] ). We evaluate a series of candidate protocols, including the deployed protocol, in various fine-grained compromise scenarios, using the ProVerif symbolic analyzer. Beyond design-time verification, we integrate the hax toolchain into Signal's continuous integration pipeline to prove runtime safety of the production implementation and to prove that the implementation meets the security goals of the protocol. The results of this work are now deployed in Signal Messenger and relied upon by millions of users.
The Signal Messenger recently introduced a new asynchronous key agreement protocol called PQXDH (Post-Quantum Extended Diffie-Hellman) that seeks to provide post-quantum forward secrecy, in addition to the authentication and confidentiality guaranteesalready provided by the previous X3DH (Extended Diffie-Hellman) protocol. More precisely, PQXDH seeks to protect the confidentiality of messages against harvest-now-decrypt-later attacks.In this work, we formally specify the PQXDH protocol and analyze its security using two formal verification tools, ProVerif and CryptoVerif. In particular, we ask whether PQXDH preserves the guarantees of X3DH, whether it provides post-quantum forward secrecy, and whether it can be securely deployed alongside X3DH. Our analysis identifies several flaws and potential vulnerabilities in the PQXDH specification, although these vulnerabilities are not exploitable in the Signal application, thanks to specific implementation choices which we describe in this paper. We collaborated with the protocol designers to develop an updated protocol specification based on our findings, where each change was formally verified and validated with a security proof. This work identifies some pitfalls that the community should be aware of when upgrading protocols to be post-quantum secure. It also demonstrates the utility of using formal verification hand-in-hand with protocol design.
Signal is a new security protocol and accompanying app that provides end-to-end encryption for instant messaging. The core protocol has recently been adopted by WhatsApp, Facebook Messenger, and Google Allo among many others, the first two of these have at least 1 billion active users. Signal includes several uncommon security properties (such as "future secrecy" or "post-compromise security"), enabled by a novel technique called ratcheting in which session keys are updated with every message sent. Despite its importance and novelty, there has been little to no academic analysis of the Signal protocol. We conduct the first security analysis of Signal's key agreement and double ratchet as a multi-stage key exchange protocol. We extract from the implementation a formal description of the abstract protocol, and define a security model which can capture the "ratcheting" key update structure. We then prove the security of Signal's core in our model, demonstrating several standard security properties. We have found no major flaws in the design, and hope that our presentation and results can serve as a starting point for other analyses of this widely adopted protocol.
With the rapid advancement of quantum computing, classical cryptographic protocols face an increasing risk of being broken. The Post-Quantum OpenPGP (PQ OpenPGP) protocol is an extension of the OpenPGP standard that incorporates hybrid cryptography by combining a classical key exchange and a post-quantum key encapsulation mechanism. This design aims to provide long-term security even in the presence of adversaries equipped with quantum computational capabilities and ensures backward compatibility while transitioning safely to the quantum era. This article presents a formal specification and verification of the PQ OpenPGP protocol using the algebraic specification language CafeOBJ. Our specification captures key aspects of the protocol, including hybrid key encapsulation using post-quantum Module-Lattice Key Encapsulation Mechanism (ML-KEM) and classical Elliptic Curve Diffie–Hellman (ECDH)-KEM, dual digital signatures using post-quantum Module-Lattice Digital Signature Algorithm (ML-DSA) and classical Edwards-curve Digital Signature Algorithm (EdDSA). To model adversarial behavior, we extend the standard Dolev-Yao intruder model, widely used in the analysis of security protocols, by incorporating quantum-enabled capabilities. Under our threat model, the intruder not only has full control over the network, as in the traditional Dolev-Yao setting, but is also capable of breaking classical public-key cryptographic primitives and compromising sensitive information, reflecting the realistic power of large-scale quantum computers. We successfully verify that the PQ OpenPGP protocol satisfies three essential security properties: secrecy of the session key, forward secrecy, and authenticity. The proofs are supported by ten auxiliary lemmas. Given the formal specification, security properties, and conjecture lemmas, the Invariant Proof Score Generator (IPSG) tool automatically generates proof scores to facilitate verification. This work contributes to the growing research on formal verification in post-quantum cryptographic protocols.
The Signal protocol provides end-to-end security even when service providers are only partially trusted; however, it still lacks deniable authentication and does not resist quantum attacks in the messaging phase. This paper therefore presents a post-quantum enhancement of Signal that is efficient in both communication cost and end-to-end message latency. In the key-agreement phase, a lattice-based Gandalf ring signature is combined with the Kyber-1024 KEM to construct a pre-key mechanism that provides both post-quantum security and deniable authentication. In the messaging phase, a pair of post-quantum ratchets is layered on top of the classical Double Ratchet to form a classical-post-quantum hybrid ratchet, while the Skye key-derivation function and erasure-code-based block encapsulation reduce communication overhead. Experimental and analytical results show that the scheme preserves Signal’s end-to- end, forward, and post-compromise security, achieves practical post-quantum security and deniable authentication, and keeps the additional cryptographic delay negligible compared with typical network latency.
In this paper, we propose our secure cloud-based mail ands messaging system Mail which uses a combination of hybrid post-quantum-cryptography (PQC) and classical elliptic-curve communication scheme in order to ensure long-term confidentiality as well as forward secrecy. The construction is based on X25519 and Kyber-768 in the form of hybrid key exchange, Ed25519 as digital signature, and ChaCha20-Poly1305 for authenticated encryption. For increased message confidentiality and post-compromise security, we employ a Double Ratchet mechanism inspired by the Signal protocol in conjunction with JWT authentication and MAC-level integrity protection. The prototype is implemented on the server side using a Flask (python) implementation with PostgreSQL as persistence similar to 38 and WatIO. React client handling the encryption, side key client. Experimental tests demonstrate that such a design effectively combines practical deployability and strong cryptographic security guarantees against classical, as well as quantum adversaries. This work attempts to bridge the gap between research-related PQC models and practical secure communication systems.
The Signal Protocol is a two-party secure messaging protocol used in applications such as Signal, WhatsApp, Google Messages and Facebook Messenger and is used by billions daily. It consists of two core components, one of which is the Double Ratchet protocol that has been the subject of a line of work that aims to understand and formalise exactly what security it provides. Existing models capture strong guarantees including resilience to state exposure in both forward security (protecting past secrets) and post-compromise security (restoring security), adaptive state corruptions, message injections and out-of-order message delivery. Due to this complexity, prior work has failed to provide security guarantees that do not degrade in the number of interactions, even in the single-session setting.