In cryptography, Post-Quantum Extended Diffie–Hellman (PQXDH) is a Kyber-based post-quantum key exchange method based on Diffie–Hellman key exchange. It has been a key part of the Signal Protocol, a popular end-to-end encryption protocol, since 2023.[1][2][3]
PQXDH is a variant of the X3DH protocol that uses both the quantum-resistant Kyber protocol as well as the classical elliptic curve X25519 protocol. This ensures that an attacker must break both of the encryption protocols to gain access to sensitive data. The protocol is designed for asynchronous communication where the clients exchange public keys through a server to derive a secure shared key which they can use to encrypt sensitive data without needing to constantly sync new keys with each other.[3][4]
In October 2023, the protocol underwent formal verification which managed to "prove all the desired security properties of the protocol" for its second revision.[5] However, PQXDH relies entirely on elliptic curve cryptography for authentication.[6]
Description
editPQXDH combines elliptic-curve cryptography (ECC) with a post-quantum key encapsulation mechanism (PQ-KEM) to derive a shared secret between two parties. In practice, Kyber is used as the PQ-KEM. PQXDH only requires a single message to be sent.[6][7]
Before the message is sent, the receiver must have published several public keys to the server: a long-term identity ECC key (IKB), a session ECC pre-key (SPKB), a series of one-time ECC pre-keys, and a series of one-time PQ-KEM pre-keys. Each of the receiver's session and one-time keys must be signed using the receiver's identity key. The sender should also have published a long-term identity ECC key (IKB).
To send a message, the sender retrieves the receiver's identity and session keys, one of the receiver's one-time ECC keys (PQOPKB), and one of the receiver's one-time PQ-KEM keys (PQOPKB) from the server. The server then deletes the one-time keys so they cannot be reused. The sender then performs the following computations (where DH is the elliptic-curve Diffie–Hellman function and KDF is a suitable key derivation function):
verify that the signatures on SPKB, OPKB, and PQPKB are valid using IKB generate an ephemeral ECC key EKA sign EKA using IKA generate a ciphertext CT and a shared secret SS using PQPKB DH1 := DH(IKA, SPKB) DH2 := DH(EKA, IKB) DH3 := DH(EKA, SPKB) DH4 := DH(EKA, OPKB) SK := KDF(DH1 || DH2 || DH3 || DH4 || SS) encrypt the message using SK
The sender then sends the message, along with EKA, CT and information to identify which one-time keys were used, to the receiver. The receiver can then use CT, along with their private keys, to decrypt the message:
verify that the signature on EKA is valid using IKA decode the shared secret SS from CT using PQPKB DH1 := DH(IKA, SPKB) DH2 := DH(EKA, IKB) DH3 := DH(EKA, SPKB) DH4 := DH(EKA, OPKB) SK := KDF(DH1 || DH2 || DH3 || DH4 || SS) decrypt the message using SK
The shared key (SK) may be used to encrypt further messages.
See also
edit- Diffie–Hellman key exchange
- End-to-end encryption
- Post-quantum cryptography
- Public-key cryptography
- Signal Protocol
References
edit- ^ Fiedler, Rune; Janson, Christian (2024). "A Deniability Analysis of Signal's Initial Handshake PQXDH". Proceedings on Privacy Enhancing Technologies. 2024 (4): 907–928. doi:10.56553/popets-2024-0051. ISSN 2299-0984.
- ^ Lakshmanan, Ravie (20 September 2023). "Signal Messenger Introduces PQXDH Quantum-Resistant Encryption". The Hacker News.
- ^ a b Claburn, Thomas (20 September 2023). "Signal adopts new alphabet jumble to protect chats from quantum computers". The Register.
- ^ Goodin, Dan (21 September 2023). "The Signal Protocol used by 1+ billion people is getting a post-quantum makeover". Ars Technica.
- ^ Bhargavan, Karthikeyan; Jacomme, Charlie; Kiefer, Franziskus; Schmidt, Rolfe (20 October 2023). "An Analysis of Signal's PQXDH". Cryspen Blog. Cryspen. Retrieved 2023-10-22.
- ^ a b Angom, Akash; Kar, Nirmalya; Debbarma, Tribid; Biswas, Priyanka (2025). "MLXDH: Security Hardening of Signal's Initial Key Establishment Using ML-KEM and ML-DSA". 2025 IEEE 6th India Council International Subsections Conference (INDISCON). pp. 1–6. doi:10.1109/INDISCON66021.2025.11254562. ISBN 979-8-3315-1504-1.
- ^ Kret, Ehren; Schmidt, Rolfe (23 January 2024). "The PQXDH Key Agreement Protocol" (PDF). Signal Foundation. Archived from the original (PDF) on 18 January 2025. Retrieved 8 January 2026.
