2. Preliminaries

2.1. PQXDH parameters

An application using PQXDH must decide on several parameters:

For example, an application could choose curve as curve25519, hash as SHA-512, info as "MyProtocol", and pqkem as CRYSTALS-KYBER-1024.

The ranges of all encoding functions must be pairwise disjoint.

The recommended implementation of EncodeEC consists of a single-byte constant representation of curve followed by little-endian encoding of the u-coordinate as specified in [3]. The single-byte representation of curve is defined by the implementer. Similarly the recommended implementation of DecodeEC reads the first byte to determine the parameter curve. If the first byte does not represent a recognized curve, the function fails. Otherwise it applies the little-endian decoding of the u-coordinate for curve as specified in [3].

The recommended implementation of EncodeKEM consists of a single-byte constant representation of pqkem followed by the encoding of the pqkem public key specified by pqkem. The single-byte representation of pqkem is defined by the implementer. Similarly the recommended implementation of DecodeKEM reads the first byte to determine the parameter pqkem. If the first byte does not represent a recognized key encapsulation mechanism, the function fails. Otherwise it applies the decoding specified by the selected key encapsulation mechanism.

2.2. Cryptographic notation

Throughout this document, all public keys have a corresponding private key, but to simplify descriptions we will identify key pairs by the public key and assume that the corresponding private key can be accessed by the key owner.

This document will use the following notation:

• The concatenation of byte sequences X and Y is X || Y.

• DH(PK1, PK2) represents a byte sequence which is the shared secret output from an Elliptic Curve Diffie-Hellman function involving the key pairs represented by public keys PK1 and PK2. The Elliptic Curve Diffie-Hellman function will be either the X25519 or X448 function from [3], depending on the curve parameter.

• Sig(PK, M, Z) represents the byte sequence that is a curve XEdDSA signature on the byte sequence M which was created by signing M with PK's corresponding private key and using 64 bytes of randomness Z. This signature verifies with public key PK. The signing and verification functions for XEdDSA are specified in [1].

• KDF(KM) represents 32 bytes of output from the HKDF algorithm [4] using hash with inputs:

  • HKDF input key material = F || KM, where KM is an input byte sequence containing secret key material, and F is a byte sequence containing 32 0xFF bytes if curve is curve25519, and 57 0xFF bytes if curve is curve448. As in XEdDSA [1], F ensures that the first bits of the HKDF input key material are never a valid encoding of a scalar or elliptic curve point.
  • HKDF salt = A zero-filled byte sequence with length equal to the hash output length, in bytes.
  • HKDF info = The concatenation of string representations of the 4 PQXDH parameters info, curve, hash, and pqkem into a single string separated with '_' such as "MyProtocol_CURVE25519_SHA-512_CRYSTALS-KYBER-1024". The string representations of the PQXDH parameters are defined by the implementer.

• (CT, SS) = PQKEM-ENC(PK) represents a tuple of the byte sequence that is the KEM ciphertext, CT, output by the algorithm pqkem together with the shared secret byte sequence SS encapsulated by the ciphertext using the public key PK.

• PQKEM-DEC(PK, CT) represents the shared secret byte sequence SS decapsulated from a pqkem ciphertext using the private key counterpart of the public key PK used to encapsulate the ciphertext CT.

2.3. Roles

The PQXDH protocol involves three parties: Alice, Bob, and a server.

• Alice wants to send Bob some initial data using encryption, and also establish a shared secret key which may be used for bidirectional communication.

• Bob wants to allow parties like Alice to establish a shared key with him and send encrypted data. However, Bob might be offline when Alice attempts to do this. To enable this, Bob has a relationship with some server.

• The server can store messages from Alice to Bob which Bob can later retrieve. The server also lets Bob publish some data which the server will provide to parties like Alice. The amount of trust placed in the server is discussed in Section 4.9.

In some systems the server role might be divided between multiple entities, but for simplicity we assume a single server that provides the above functions for Alice and Bob.

2.4. Elliptic Curve Keys

PQXDH uses the following elliptic curve public keys:

The elliptic curve public keys used within a PQXDH protocol run must either all be in curve25519 form, or they must all be in curve448 form, depending on the curve parameter [3].

Each party has a long-term identity elliptic curve public key (IK_A for Alice, IK_B for Bob).

Bob also has a signed prekey SPK_B, which he changes periodically and signs each time with IK_B, and a set of one-time prekeys (OPK_B1, OPK_B2, ...), which are each used in a single PQXDH protocol run. For each signed prekey or one-time prekey, K, that Bob generates, he also computes an identifier, denoted IdEC(K), that uniquely identifies this key on Bob's device. ("Prekeys" are so named because they are essentially protocol messages which Bob publishes to the server, along with their corresponding identifiers, prior to Alice beginning the protocol run.) These keys will be uploaded to the server as described in Section 3.2.

During each protocol run, Alice generates a new ephemeral key pair with public key EK_A.

2.5. Post-Quantum Key Encapsulation Keys

PQXDH uses the following post-quantum key encapsulation public keys:

The pqkem public keys used within a PQXDH protocol run must all use the same pqkem parameter.

Bob has a signed last-resort post-quantum prekey PQSPK_B, which he changes periodically and signs each time with IK_B, and a set of signed one-time prekeys (PQOPK_B1, PQOPK_B2, ...) which are also signed with IK_B and each used in a single PQXDH protocol run. For each last-resort or ephemeral KEM key, K, that Bob generates, he also computes an identifier, denoted IdKEM(K), that uniquely identifies this key on Bob's device. These keys and their corresponding identifiers will be uploaded to the server as described in Section 3.2. The name "last-resort" refers to the fact that the last-resort prekey is only used when one-time pqkem prekeys are not available. This can happen when the number of prekey bundles downloaded for Bob exceeds the number of one-time pqkem prekeys Bob has uploaded (see Section 3 for details about the role of the server). An implementation should provide Bob a way to identify whether a pqkem public key corresponds to a one-time pqkem key or a last-resort pqkem key.