Post-Quantum Cryptography

Protecting today's messages from tomorrow's quantum computers.

Why Post-Quantum Now

Quantum computers capable of breaking current public-key cryptography do not exist today. But that is not the threat model. The threat model is harvest now, decrypt later.

Intelligence agencies, state-sponsored actors, and well-funded adversaries are already intercepting and storing encrypted communications in bulk. They cannot decrypt these messages today. But encrypted data does not expire. If a cryptographically relevant quantum computer (CRQC) is built in 10, 15, or 20 years, every message encrypted with classical-only public-key cryptography becomes retroactively readable.

Timeline of the harvest-now-decrypt-later attack:

  2024: Adversary intercepts encrypted traffic
        - Stores ciphertext, public keys, key exchange parameters
        - Cannot decrypt (no quantum computer)

  2024-2040: Ciphertext sits in storage
        - Costs almost nothing to store
        - 1 TB of ciphertext = ~$5/year in cloud storage

  2040+: CRQC becomes available
        - Shor's algorithm breaks X25519 in polynomial time
        - Adversary decrypts all stored ciphertext
        - Every message, every conversation, retroactively exposed

If the information you are communicating today will still be sensitive in 15 years -- legal matters, journalistic sources, medical records, business strategy, personal privacy -- you need post-quantum protection now, not when quantum computers arrive.

What Quantum Computers Break

A sufficiently powerful quantum computer running Shor's algorithm can efficiently solve:

Symmetric algorithms (AES-256, SHA-256, HMAC) are affected by Grover's algorithm, which provides a quadratic speedup for brute-force search. This effectively halves the security level: AES-256 becomes equivalent to AES-128 against a quantum adversary. AES-128 (128-bit security → 64-bit against Grover's) would be insufficient. RVNT uses AES-256 (128-bit security against quantum) and SHA-256 throughout, which remain secure.

ML-KEM-768 (FIPS 203)

ML-KEM (Module Lattice-based Key Encapsulation Mechanism) is the primary post-quantum key encapsulation standard published by NIST in August 2024 as FIPS 203. It was previously known as CRYSTALS-Kyber during the NIST post-quantum standardization process.

How ML-KEM Works

ML-KEM is based on the Module Learning With Errors (MLWE) problem, a lattice-based hard problem believed to resist both classical and quantum attacks.

Key Generation:
  1. Sample a random matrix A ∈ R_q^{k×k}  (public parameter)
  2. Sample secret vector s ∈ R_q^k         (small coefficients)
  3. Sample error vector e ∈ R_q^k          (small coefficients)
  4. Compute t = A·s + e                    (public key component)
  5. Public key:  (A, t)                    [1184 bytes for k=3]
  6. Private key: s                         [2400 bytes for k=3]

Encapsulation (sender):
  1. Sample random message m ∈ {0,1}^256
  2. Derive (r, K) = G(m || H(pk))         // deterministic randomness
  3. Compute ciphertext c using r and pk
  4. Shared secret = K                      [32 bytes]
  5. Output: (ciphertext c, shared secret K)

Decapsulation (recipient):
  1. Decrypt m' from ciphertext c using secret key s
  2. Re-encapsulate using m' and pk
  3. If re-encapsulated ciphertext matches c:
       shared secret = K (derived from m')
     Else:
       shared secret = H(z || c)           // implicit rejection
  4. Output: shared secret K               [32 bytes]

The implicit rejection mechanism ensures that invalid ciphertexts
produce a random-looking output rather than an error, which prevents
certain oracle attacks.

ML-KEM-768 Parameters

RVNT's Hybrid Design

RVNT does not replace X25519 with ML-KEM. It combines both in a hybrid construction:

Session key derivation:

  Classical:   DH1 || DH2 || DH3 || DH4         (X25519)
  Post-quantum: PQ_SS                             (ML-KEM-768)

  Combined: SK = HKDF-SHA256(
      salt:  0xFF * 32,
      ikm:   DH1 || DH2 || DH3 || DH4 || PQ_SS,
      info:  "RVNT_X3DH_hybrid_v1",
      len:   32
  )

Security guarantee:
  The combined secret is at least as strong as the strongest component.
  An attacker must break BOTH X25519 AND ML-KEM-768 to recover SK.

Why Not Replace X25519 Entirely?

• Defense in depth: ML-KEM is newly standardized. While extensively analyzed during the 7-year NIST competition, it has far less deployment history than X25519. If a classical attack is found against ML-KEM, X25519 still protects the session.
• Implementation maturity: X25519 has been implemented, audited, and deployed in billions of devices over a decade. The risk of implementation bugs is lower.
• No downside: Adding ML-KEM increases initial message size by ~1088 bytes and adds ~0.1ms of computation. This is negligible.

What Happens If...

Quantum Computers Arrive

Scenario: CRQC breaks X25519

  Classical X3DH (Signal, etc.):
    - Adversary recovers all four DH shared secrets
    - Session key is compromised
    - All messages decryptable

  RVNT Hybrid X3DH:
    - Adversary recovers all four DH shared secrets
    - Adversary CANNOT recover ML-KEM shared secret (lattice-hard)
    - SK = HKDF(compromised_DH || secure_PQ_SS)
    - Session key remains secure
    - Messages remain confidential

ML-KEM Is Broken (Classical Attack)

Scenario: Classical cryptanalysis breaks ML-KEM

  RVNT Hybrid X3DH:
    - Adversary recovers ML-KEM shared secret
    - Adversary CANNOT recover X25519 DH secrets (ECDLP-hard)
    - SK = HKDF(secure_DH || compromised_PQ_SS)
    - Session key remains secure
    - Messages remain confidential

  RVNT would issue a protocol update to replace ML-KEM with the
  next best post-quantum KEM. Existing sessions remain secure.

Both Are Broken

Scenario: Both X25519 and ML-KEM-768 are broken simultaneously

  This requires:
    1. A CRQC that breaks X25519 (Shor's algorithm)
    2. A classical or quantum attack that breaks ML-KEM-768

  This is an extremely unlikely simultaneous event.
  If it occurs, all public-key cryptography is broken,
  and the entire internet has much bigger problems.

  RVNT's symmetric layer (AES-256-GCM) remains secure in this
  scenario -- messages already encrypted remain protected by the
  Double Ratchet's symmetric keys (which are not affected by
  quantum attacks beyond Grover's quadratic speedup).

Performance Impact

The overhead is entirely in the initial key exchange. Subsequent messages (Double Ratchet) use only AES-256-GCM and X25519 DH ratchet steps -- ML-KEM is not involved after the session is established. The ~1.1 KB overhead on the initial message is a one-time cost per conversation.

NIST Standardization Timeline

2016: NIST announces Post-Quantum Cryptography Standardization Project
2017: 69 candidate algorithms submitted
2019: Round 2 -- 26 candidates remain
2020: Round 3 -- 7 finalists + 8 alternates
2022: CRYSTALS-Kyber selected as primary KEM
2024: Published as FIPS 203 (ML-KEM)
      Published as FIPS 204 (ML-DSA, signatures)
      Published as FIPS 205 (SLH-DSA, stateless hash signatures)

ML-KEM has undergone 7 years of public cryptanalysis by the
global research community. No practical attack has been found.

Further Reading

• Key Exchange (X3DH) -- How ML-KEM integrates into the X3DH protocol
• Protocol Specification -- Wire formats including PQ key bundle and ciphertext
• Forward Secrecy -- How the Double Ratchet complements PQ protection