DIP-308 Post-Quantum Cryptography Support

[wesbiggs]

Abstract

This proposal adds optional post-quantum cryptography (PQC) support to DSNP, addressing the long-term vulnerability of the current X25519/Ed25519/XSalsa20-Poly1305 constructions to quantum attacks. It introduces:

1. Optional ML-KEM-768 (mlkem768-pub) keys for key agreement, alongside the existing X25519 keys
2. Optional ML-DSA-65 (mldsa65-pub) keys for digital signatures, alongside the existing Ed25519 keys
3. A post-quantum PRId scheme using a HMAC-SHA2-256 Merkle accumulator with ML-KEM-768-encrypted off-chain witnesses
4. New privateFollowsPQ and privateConnectionsPQ User Data types encrypted with the X-Wing hybrid KEM (X25519 + ML-KEM-768) and ChaCha20-Poly1305

All changes are backward-compatible; existing classical types and implementations are unaffected.

Motivation

Current DSNP cryptography relies on elliptic-curve algorithms (X25519, Ed25519) that are broken by Shor's algorithm on a cryptographically-relevant quantum computer. NIST completed standardization of post-quantum algorithms in 2024 (FIPS 203 ML-KEM, FIPS 204 ML-DSA). This proposal enables implementations to begin publishing PQ keys and using PQ-protected data types while preserving full interoperability with classical-only implementations during a transition period.

Specification Pull Request

Current change pull request: #307

Rationale

Algorithm choices:

• ML-KEM-768 (FIPS 203, security level 3) is chosen for key encapsulation over ML-KEM-1024 (level 5) because it is the variant used by the X-Wing hybrid KEM standard, providing consistency across constructions. Level 3 is considered adequate against quantum adversaries.
• ML-DSA-65 (FIPS 204, security level 3) is chosen for signatures for consistency with the security level of ML-KEM-768.
• X-Wing (draft-connolly-cfrg-xwing-kem) is a standards-track hybrid KEM combining X25519 and ML-KEM-768 into a single shared secret. It provides security if either X25519 or ML-KEM-768 is secure, hedging against future cryptanalytic advances. Public key size: 1,216 bytes (32 B X25519 + 1,184 B ML-KEM-768). Ciphertext size: 1,120 bytes (32 B ephemeral X25519 + 1,088 B ML-KEM-768 ciphertext).
• ChaCha20-Poly1305 is chosen for AEAD encryption of privateFollowsPQ/privateConnectionsPQ, as the closest modern counterpart to the existing XSalsa20-Poly1305 construction.
• HKDF-SHA2-256 and HMAC-SHA2-256 are used in the PRId accumulator for consistency with the rest of the DSNP specification, which already relies on SHA2-256; SHA3 is not required by any NIST PQC standard.

Post-quantum PRId design:

The classical PRId algorithm relies on X25519 ECDH, a Non-Interactive Key Exchange (NIKE) with the commutative property ECDH(A_secret, B_public) = ECDH(B_secret, A_public). No NIST-approved post-quantum NIKE exists (CSIDH would provide this but is not standardized). The post-quantum algorithm instead uses a unilateral keyed-hash construction:

• Alice derives a PRId master key k_A from her ML-KEM-768 secret key via HKDF-SHA2-256(ikm=A_mlkem_secret, info="DSNPPRIdMasterKey").
• For each connection Bob, a leaf value L_A→B,C = HMAC-SHA2-256(key=k_A, message=LE64(Id_B) || ctx) is computed. The leaf is 32 bytes; no truncation is applied.
• A SHA2-256 Merkle tree is built over the sorted leaf set, padded to a power of two with SHA2-256("DSNPPRIdPadding"). Internal nodes use a 0x01 || prefix for domain separation.
• The 32-byte Merkle root is published on-chain in a PRIdAccumulator Avro record alongside a CIDv1 content address pointing to an off-chain Parquet witness file.
• Each witness record contains Bob's leaf value and Merkle proof path, encrypted to Bob's ML-KEM-768 public key using ML-KEM-768.Encapsulate + AES-256-GCM (12-byte random nonce; format: kem_ct [1,088 B] || nonce [12 B] || encrypted).
• The witness file is uploaded to IPFS (or equivalent) in randomized record order so position reveals no relationship information. It is fully regenerable by Alice from her ML-KEM-768 secret key, her privateConnections list, and each connection's published ML-KEM-768 public key, so it does not require on-chain durability.

Third-party proofs require Bob's active participation in two steps: (1) prove DSNP identity by signing a verifier-supplied challenge with his ML-DSA-65 key; (2) reveal his leaf value and Merkle proof path. Embedding Bob's DSNP User Id in any signed or published artifact is explicitly prohibited, as it would allow an observer to brute-force check membership over the known user space.

Backward compatibility:

Implementations that do not support PQ algorithms MUST ignore unrecognized multicodec key identifiers. privateFollowsPQ and privateConnectionsPQ use distinct system names from privateFollows and privateConnections so both may be stored simultaneously. Either or both classical and PQ types MAY be enabled by an implementation; the goal is eventual transition to PQ-only.

Backwards Compatibility

All new User Data types and key types are additive. No existing type, schema, or algorithm is modified. A classical-only implementation:

• Will ignore mlkem768-pub and mldsa65-pub keys (unrecognized multicodec values)
• Will not read or write privateFollowsPQ, privateConnectionsPQ, or privateConnectionPRIdsPQ
• Will continue to function identically for all v1.2 and v1.3 data types

Reference Implementation and/or Tests

A conforming implementation should demonstrate:

• Key generation and multicodec encoding for mlkem768-pub (1,184-byte raw key, varint prefix per multicodec table) and mldsa65-pub (1,952-byte raw key)
• X-Wing encapsulation/decapsulation producing a deterministic shared secret from a known key pair
• ChaCha20-Poly1305 round-trip on a sample privateFollowsPQ payload
• PRId accumulator construction for a set of N connections: leaf computation, Merkle tree, witness record encryption, Parquet file generation, and successful Bob-side decryption and proof verification
• Third-party proof: Bob signs a challenge with ML-DSA-65; verifier confirms leaf + Merkle path against published merkleRoot

Security Considerations

• Hybrid security: x25519mlkem768chacha20poly1305 (X-Wing) is secure if either X25519 or ML-KEM-768 is secure. A classical-only attacker cannot break it; a quantum attacker capable of breaking X25519 still faces ML-KEM-768.
• PRId privacy: The on-chain Merkle root reveals nothing about individual relationships. The off-chain witness file records are in random order with no indexed metadata. An observer cannot determine which leaf corresponds to which counterparty without Alice's master key k_A.
• Brute-force resistance: No signed or published artifact encodes a counterparty's DSNP User Id. Third-party proofs require Bob's active participation per instance and cannot be delegated or reused.
• Key compromise: Compromise of Alice's ML-KEM-768 secret key exposes k_A and all leaf values, and allows re-encryption of witness records to new recipients. This is the same threat model as compromise of the classical X25519 secret key for privateConnections. Key rotation follows existing DSNP conventions (publish a new key; re-encrypt data).
• ML-KEM-768 security level: NIST security level 3 (conjectured hardness ≥ 2^178 classical, ≥ 2^178 quantum for ML-KEM). Considered sufficient for medium- to long-term post-quantum security.
• ML-DSA-65 security level: NIST security level 3 (signature security ≥ 2^128 quantum). Consistent with ML-KEM-768.

Dependencies

• None. Implementations MAY adopt any subset of the new types independently.

References

• NIST FIPS 203 — ML-KEM
• NIST FIPS 204 — ML-DSA
• X-Wing: General-Purpose Hybrid Post-Quantum KEM
• RFC 8439 — ChaCha20 and Poly1305
• multicodec table

Copyright

Copyright and related rights waived via CC0.