Signal's PQXDH: post-quantum key agreement for messaging

Short answer: PQXDH is Signal's upgrade to its X3DH key agreement protocol, adding a post-quantum key encapsulation mechanism alongside the classical elliptic-curve exchange. Signal's specification says it provides post-quantum forward secrecy and a form of deniability, but that mutual authentication in this revision still relies on the discrete log problem. These are Signal's own claims about its design, and this article does not endorse or test any product.

What problem does PQXDH address?

Signal's blog says the motivation for PQXDH is the potential future threat of quantum computers powerful enough to break current encryption standards. Current cryptographic algorithms rely on mathematical problems that quantum computers could solve more efficiently. To address this, new post-quantum cryptosystems have been created to implement one-way functions that cannot be advantageously reversed by a quantum computer.

The specification says it provides post-quantum forward secrecy. The protocol also provides a form of cryptographic deniability. However, in this revision of the protocol, mutual authentication still relies on the hardness of the discrete log problem. In other words, the authentication layer is not post-quantum in this revision.

How does the protocol structure work?

PQXDH is designed for asynchronous settings where one user, referred to as "Bob," is offline but has published information to a server. Another user, "Alice," uses that published information to send encrypted data to Bob. Simultaneously, Alice and Bob establish a shared secret key for future communication.

The protocol defines several specific components required for its operation: * Curve: A Montgomery curve for which XEdDSA is specified. At present, this is one of curve25519 or curve448. * Hash: A 256 or 512-bit hash function, such as SHA-256 or SHA-512. * Info: An ASCII string identifying the application, with a minimum length of 8 bytes. * PQKEM: A post-quantum key encapsulation mechanism (KEM) that has IND-CCA post-quantum security. An example cited is Crystals-Kyber-1024. * AEAD: A scheme for authenticated encryption with associated data that has IND-CPA and INT-CTXT post-quantum security.

The protocol uses encoding and decoding functions for both the elliptic curve components and the KEM components. These functions allow the parties to process the public keys and encapsulated keys necessary to derive the shared secret.

What security properties are claimed?

Signal's specification claims post-quantum forward secrecy. It also claims a form of cryptographic deniability.

However, the specification states that this revision of the protocol still relies on the hardness of the discrete log problem for mutual authentication. This means the authentication mechanism is not post-quantum secure in this version. The post-quantum security applies to the key agreement and forward secrecy aspects, but the initial identification and authentication steps depend on classical elliptic curve cryptography.

The post-quantum key encapsulation mechanism (PQKEM) used in the protocol is required to have IND-CCA post-quantum security. IND-CCA stands for Indistinguishability under Chosen Ciphertext Attack. This is a strong security notion for key encapsulation, ensuring that the encapsulated key remains secure even if an adversary can choose ciphertexts to be decrypted.

How does this relate to standardization?

Signal's blog credits innovation from cryptographic researchers and the NIST Standardization Process for Post-Quantum Cryptography for giving stable options for post-quantum primitives.

The specification gives Crystals-Kyber-1024 as an example of the post-quantum KEM. Signal's blog describes PQXDH as an upgrade to its X3DH specification, and calls it the first step in advancing quantum resistance for the Signal Protocol.

FAQ

What is PQXDH?

Signal's name for "Post-Quantum Extended Diffie-Hellman", a key agreement protocol that establishes a shared secret between two parties who authenticate each other using public keys.

What does it add over X3DH?

Signal's blog describes it as an upgrade to X3DH that adds a layer of protection against a future quantum computer powerful enough to break current encryption standards.

What security properties does it claim?

Post-quantum forward secrecy and a form of cryptographic deniability, according to Signal's specification.

Is authentication post-quantum too?

No, not in this revision. The specification says mutual authentication still relies on the hardness of the discrete log problem.

What post-quantum component does it use?

A post-quantum key encapsulation mechanism with IND-CCA post-quantum security. The specification gives Crystals-Kyber-1024 as an example.