Post-Quantum Extended Diffie–Hellman
Post-quantum cryptographic protocol
From Wikipedia, the free encyclopedia
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
PQXDH 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.