Post-Quantum Cryptography

The Quantum Threat

Shor's Algorithm and Public-Key Cryptography

In 1994, Peter Shor demonstrated that a sufficiently large quantum computer can factor integers and compute discrete logarithms in polynomial time. Specifically, Shor's algorithm solves the following problems in $O((\log N)^3)$ quantum operations:

Integer Factorization

Given $N = p \cdot q$, find $p$ and $q$

Discrete Logarithm

Given $g$, $h = g^x \bmod p$, find $x$

Elliptic Curve DL

Given $P$, $Q = xP$ on curve $E$, find $x$

For Zentalk's cryptographic primitives, the implications are:

Algorithm	Classical Security	Quantum Security	Impact
X25519 (ECDH)	128-bit	0-bit (broken by Shor)	Key agreement compromised
Ed25519 (EdDSA)	128-bit	0-bit (broken by Shor)	Signatures forgeable
AES-256-GCM	256-bit	128-bit (Grover halves)	Still secure
SHA-256	128-bit collision	85-bit (Grover)	Still secure
HMAC-SHA256	256-bit	128-bit (Grover)	Still secure

Symmetric algorithms (AES, SHA, HMAC) lose at most half their security level against quantum attacks via Grover's search algorithm, which provides a quadratic speedup for unstructured search. A $256$-bit AES key retains $128$-bit security against quantum adversaries, which is considered adequate.

However, all public-key operations based on the hardness of the discrete logarithm problem -- including X25519, Ed25519, RSA, and all standard ECDH/ECDSA variants -- are completely broken by Shor's algorithm. A quantum computer with approximately $2{,}330$ logical qubits could break $256$-bit elliptic curve cryptography. While such machines do not exist today, the timeline for their development is measured in years to decades, not centuries.

The "Harvest Now, Decrypt Later" Threat

The most immediate quantum threat is not real-time decryption but retrospective decryption. State-level adversaries are known to collect and store encrypted communications with the expectation that future quantum computers will be able to decrypt them. For communications with long-term sensitivity -- political discussions, trade secrets, medical records, journalistic sources -- this threat is present today.

This means that data encrypted today using only classical algorithms may be retroactively compromised when large-scale quantum computers become available. The solution is to begin using quantum-resistant algorithms now, before quantum computers exist, to protect data that must remain confidential for decades.

NIST Post-Quantum Standardization

In response to the quantum threat, the U.S. National Institute of Standards and Technology (NIST) initiated a multi-year process to standardize post-quantum cryptographic algorithms. In 2024, NIST published three standards:

• FIPS 203 (ML-KEM): Module-Lattice-Based Key-Encapsulation Mechanism, based on CRYSTALS-Kyber. Three parameter sets: ML-KEM-512, ML-KEM-768, ML-KEM-1024.
• FIPS 204 (ML-DSA): Module-Lattice-Based Digital Signature Algorithm, based on CRYSTALS-Dilithium. Three parameter sets: ML-DSA-44, ML-DSA-65, ML-DSA-87.
• FIPS 205 (SLH-DSA): Stateless Hash-Based Digital Signature Algorithm, based on SPHINCS+. Backup signature scheme not based on lattice assumptions.

Zentalk implements ML-KEM-768 (formerly CRYSTALS-Kyber-768) for key encapsulation and ML-DSA-65 (Dilithium3) for digital signatures, both at NIST Security Level 3 (approximately $2^{183}$ classical operations, based on conservative core-SVP hardness estimates).

Lattice-Based Cryptography

Lattices and Hard Problems

A lattice in $\mathbb{R}^n$ is the set of all integer linear combinations of a set of basis vectors $\{\mathbf{b}_1, \mathbf{b}_2, \ldots, \mathbf{b}_n\}$:

$$\mathcal{L} = \left\{ \sum_{i=1}^{n} z_i \mathbf{b}_i : z_i \in \mathbb{Z} \right\}$$

The security of lattice-based cryptography rests on the computational hardness of finding short vectors in high-dimensional lattices. The two fundamental hard problems are:

Shortest Vector Problem (SVP): Given a basis $\mathbf{B}$ for a lattice $\mathcal{L}$, find the shortest nonzero vector in $\mathcal{L}$.

$$\text{Find } \mathbf{v} \in \mathcal{L} \text{ such that } \|\mathbf{v}\| = \lambda_1(\mathcal{L}) = \min_{\mathbf{w} \in \mathcal{L},\, \mathbf{w} \neq \mathbf{0}} \|\mathbf{w}\|$$

Learning With Errors (LWE): Given a matrix $\mathbf{A} \in \mathbb{Z}_q^{m \times n}$ and a vector $\mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e} \pmod{q}$, where $\mathbf{s}$ is a secret vector and $\mathbf{e}$ is a "small" error vector drawn from a discrete Gaussian distribution, find $\mathbf{s}$.

$$\begin{aligned} \text{Given: } & \mathbf{A} \in \mathbb{Z}_q^{m \times n},\quad \mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e} \pmod{q} \\ & \text{where } \mathbf{s} \in \mathbb{Z}_q^n,\; \mathbf{e} \sim \chi \text{ (discrete Gaussian, } \sigma \ll q\text{)} \\ \text{Find: } & \mathbf{s} \end{aligned}$$

The best known classical algorithms for LWE require time exponential in the lattice dimension $n$. The best known quantum algorithms (using quantum lattice sieving) also require exponential time, with a smaller constant factor. This is in stark contrast to the discrete logarithm problem, which Shor's algorithm solves in polynomial time.

Module-LWE: Kyber's Algebraic Structure

Kyber uses a structured variant called Module-LWE (MLWE), which operates over polynomial rings rather than integer vectors. This provides equivalent security with significantly smaller key sizes and faster operations.

The ring used is:

$$R_q = \mathbb{Z}_q[X] / (X^n + 1) \quad \text{where } q = 3329 \text{ (a prime) and } n = 256$$

Each element of $R_q$ is a polynomial of degree less than $256$ with coefficients in $\{0, 1, \ldots, 3328\}$. Arithmetic is performed modulo both $q$ and $(X^{256} + 1)$.

For Kyber-768 (Security Level 3), the module dimension is $k = 3$, so the "matrix" $\mathbf{A}$ is a $3 \times 3$ matrix of polynomials from $R_q$, the secret vector $\mathbf{s}$ consists of $3$ polynomials, and the error vector $\mathbf{e}$ consists of $3$ polynomials with small coefficients.

Kyber-768 Key Encapsulation Mechanism

Kyber-768 implements a key encapsulation mechanism (KEM) based on the Module-LWE problem. Key generation produces a public key (~1,184 bytes) and private key. Encapsulation generates a shared secret and ciphertext (~1,088 bytes) using the public key. Decapsulation recovers the shared secret using the private key. An implicit rejection mechanism ensures that invalid ciphertexts produce random-looking outputs, preventing chosen-ciphertext attacks. The complete specification is published as NIST FIPS 203 [NIST, 2024].

Key and ciphertext sizes for Kyber parameter sets:

Parameter	pk (bytes)	sk (bytes)	ct (bytes)	Security Level
Kyber-512	800	1,632	768	Level 1 (${\sim}2^{128}$)
Kyber-768	1,184	2,400	1,088	Level 3 (${\sim}2^{183}$ classical)
Kyber-1024	1,568	3,168	1,568	Level 5 (${\sim}2^{256}$)

Zentalk uses Kyber-768 as the optimal balance between security (NIST Level 3, approximately $2^{183}$ classical / $2^{161}$ quantum operations) and efficiency (1,184-byte public keys are practical for network transmission).

Hybrid X3DH Protocol

Design Rationale

Zentalk does not replace classical X25519 with Kyber-768. Instead, it combines both in a hybrid construction. The rationale is defense in depth during the transition period:

Kyber-768 Broken

X25519 continues to provide 128-bit classical security. The system degrades gracefully to the pre-quantum security level.

X25519 Broken

Kyber-768 provides NIST Level 3 quantum-resistant security (~183-bit classical, ~161-bit quantum). The system remains secure against quantum adversaries.

Neither Broken

Both contribute entropy. Security equals the stronger of the two components.

The hybrid approach ensures that the shared secret is at least as secure as the stronger component, regardless of which algorithm (if either) is eventually broken. This is formalized by the following security property:

$$\text{Security}(\text{Hybrid}) \geq \max\!\big(\text{Security}(\text{X25519}),\; \text{Security}(\text{Kyber-768})\big)$$

Hybrid Key Bundle

When PQC is enabled, the key bundle is extended with Kyber components:

HybridKeyBundle = {
  // Classical components (same as standard X3DH):
  address:          string
  identityKey:      Uint8Array(32)   // X25519 public
  ed25519PublicKey:  Uint8Array(32)
  signedPreKey:     SignedPreKey      // X25519 + Ed25519 signature

  // Post-quantum components:
  pqcEnabled:        boolean
  kyberIdentityKey:  Uint8Array(1184) // Kyber-768 public key
  kyberSignedPreKey: Uint8Array(1184) // Kyber-768 prekey public
  dilithiumPublicKey: Uint8Array(1952) // Dilithium3 public (for PQC signatures)

  // Hybrid signed prekey includes both classical and PQC signatures:
  hybridSignedPreKey: {
    keyId:           uint32
    x25519Public:    Uint8Array(32)
    kyberPublic:     Uint8Array(1184)
    ed25519Signature: Uint8Array(64)    // Ed25519 over (keyId || x25519 || kyber || timestamp)
    dilithiumSignature: Uint8Array(3293) // Dilithium3 over same data
    timestamp:       uint64
  }
}

Both signatures must verify for the bundle to be accepted. This prevents an attacker who can break one signature scheme from substituting prekeys.

Hybrid Initiator Protocol

Alice initiates a hybrid X3DH session with Bob:

The hybrid initiator extends the standard X3DH protocol with three additional Kyber-768 encapsulations -- one against each of Bob's post-quantum keys (identity, signed prekey, and optionally one-time prekey). The classical shared secret from X3DH and the post-quantum shared secrets from Kyber are concatenated and passed through HKDF-SHA256 to derive the hybrid shared secret. This ensures that the resulting key is at least as strong as the stronger of the two components.

Hybrid Post-Quantum Key Exchange

X25519 Key Pair

Elliptic Curve DH

Classical Secret (32 bytes)

Kyber-768 Key Pair

Lattice Encapsulation

PQ Secret (32 bytes)

Concatenate Secrets

HKDF-SHA256

Hybrid Shared Secret

Safe against classical computers

Safe against quantum computers

Both must be broken to compromise

Press enter or space to select a node. You can then use the arrow keys to move the node around. Press delete to remove it and escape to cancel.

Press enter or space to select an edge. You can then press delete to remove it or escape to cancel.

X25519 and Kyber-768 run in parallel; both shared secrets are concatenated and passed through HKDF-SHA256, ensuring security against classical and quantum adversaries.

The Double Ratchet is then initialized with $\text{RK}_0 = \text{hybrid\_secret}[0{:}32]$.

Hybrid Responder Protocol

The responder performs the corresponding Kyber-768 decapsulations using their private keys, derives the same shared secrets, and combines them identically via HKDF. The symmetry of the construction ensures both parties derive the same hybrid shared secret. The used Kyber one-time prekey is deleted after decapsulation to preserve forward secrecy.

Backward Compatibility

The hybrid protocol is fully backward compatible:

Scenario 1: Both parties support PQC
  → Full hybrid X3DH (X25519 + Kyber-768)
  → Maximum security: NIST Level 3 quantum-resistant (≈183-bit classical) + 128-bit classical

Scenario 2: Only initiator supports PQC
  → Standard X3DH (X25519 only)
  → Initiator detects missing kyber fields in Bob's bundle
  → Falls back to classical automatically

Scenario 3: Only responder supports PQC
  → Standard X3DH (X25519 only)
  → Initiator's message has no Kyber ciphertext
  → Responder processes classical-only path

Scenario 4: Neither supports PQC
  → Standard X3DH (X25519 only)
  → Identical to Chapter 3 protocol

The pqcEnabled boolean in the key bundle signals PQC support. The ToClassicalKeyBundle() function strips PQC fields for interoperability with non-PQC clients.

Dilithium3 Hybrid Signatures

Dual-Signature Authentication

For prekey authentication in hybrid mode, both Ed25519 and Dilithium3 signatures are required:

signature_data = keyId (4 bytes)
              || x25519_public (32 bytes)
              || kyber_public (1,184 bytes)
              || timestamp (8 bytes)

ed25519_sig    = Ed25519.Sign(identity_ed25519_private, signature_data)    // 64 bytes
dilithium_sig  = Dilithium3.Sign(identity_dilithium_private, signature_data)  // 3,293 bytes

Both signatures must verify:
  valid_classical = Ed25519.Verify(ed25519_public, signature_data, ed25519_sig)
  valid_pqc       = Dilithium3.Verify(dilithium_public, signature_data, dilithium_sig)
  
  accepted = valid_classical AND valid_pqc

The verification always evaluates both signatures to completion (no short-circuit evaluation), preventing timing side-channels that could reveal which signature failed.

Dilithium3 Parameters

Parameter	Value
Security level	NIST Level 3 (${\sim}2^{183}$ classical, ${\sim}2^{161}$ quantum)
Public key size	1,952 bytes
Private key size	4,000 bytes
Signature size	3,293 bytes
Underlying problem	Module-LWE + Module-SIS over $R_q$
Ring	$R_q = \mathbb{Z}_q[X]/(X^{256} + 1)$, $q = 8{,}380{,}417$

Security Analysis

Concrete Security Estimates

The security of Kyber-768 against the best known quantum attacks (lattice sieving using the BKZ algorithm with quantum speedups) has been evaluated by NIST during the Post-Quantum Cryptography standardization process [NIST 2024]:

$$\begin{aligned} \text{Classical security:} &\geq 183 \text{ bits (core-SVP hardness, Becker-Ducas-Gama-Laarhoven sieve)} \\ \text{Quantum security:} &\geq 161 \text{ bits (quantum core-SVP, Laarhoven quantum sieve)} \end{aligned}$$

These concrete estimates are conservative lower bounds. NIST classifies Kyber-768 at Security Level 3, which is defined as "at least as hard to break as AES-192" -- a computational threshold rather than a precise bit-security target. The concrete estimates of $183$/$161$ bits exceed the Level 3 threshold (which requires only that the best attack costs more than $2^{143}$ operations for the "NIST gates" metric). The distinction between the classification level (Level 3) and the concrete estimate ($183$ bits classical) reflects different measurement methodologies [Laarhoven 2015, Albrecht et al. 2019].

Hybrid Security Proof Sketch

Theorem: If the hybrid HKDF combiner is modeled as a random oracle, then the hybrid shared secret is computationally indistinguishable from random as long as at least one of the two component secrets is computationally indistinguishable from random.

Proof sketch: Assume for contradiction that an adversary $\mathcal{A}$ can distinguish the hybrid secret from random. Consider two games:

Game 1

classical_secret is real, pqc_secret is random. By the random oracle model of HKDF, $\mathcal{A}$ cannot distinguish the hybrid output.

Game 2

classical_secret is random, pqc_secret is real. Same argument applies.

If $\mathcal{A}$ can distinguish in the real game (both real), then by a hybrid argument, $\mathcal{A}$ can either distinguish the classical secret from random (contradicting ECDH security) or the PQC secret from random (contradicting Kyber IND-CCA2 security). This contradiction proves the theorem.

Performance Impact

Hybrid X3DH introduces additional computation and bandwidth:

Computation overhead per session establishment:

Operation	Time (M3 Pro)	Additional vs. classical
Kyber keypair generation	~0.1 ms	+0.1 ms
Kyber encapsulation (x2-3)	~0.2-0.3 ms	+0.3 ms
Kyber decapsulation (x2-3)	~0.2-0.3 ms	+0.3 ms
HKDF combination	~0.01 ms	negligible
Total additional		~0.7 ms

Bandwidth overhead per InitialMessage:

Component	Classical	Hybrid	Delta
Identity key	32 bytes	32 + 1,184 bytes	+1,184
Ephemeral key	32 bytes	32 bytes	0
Kyber ciphertext	0	2,176-3,264 bytes	+2,176-3,264
Total InitialMessage	~100 bytes	~3,500-4,500 bytes	+3,400-4,400

The bandwidth overhead occurs only once per conversation (during session establishment). Subsequent messages use the Double Ratchet with standard-sized DH public keys ($32$ bytes), so there is no ongoing overhead. The ${\sim}4$ KB InitialMessage is well within practical limits for any network connection, including mobile data.

Migration and Transition Strategy

Zentalk implements a phased migration strategy:

Current

Hybrid mode optional. Non-PQC clients communicate via classical X3DH.

2026

Hybrid mode default for new key bundles. Existing conversations continue with classical protocol.

2027

Classical-only key bundles deprecated. Warning displayed to users with non-PQC peers.

2028+

Classical-only connections rejected. Full quantum resistance mandated.

The PQCMigrationStatus tracker monitors migration progress across the network:

PQCMigrationStatus {
  totalKeys:           int      // All key bundles in system
  hybridKeys:          int      // Classical + PQC bundles
  classicalOnlyKeys:   int      // Classical-only bundles
  migrationPercentage: float64  // (hybridKeys / totalKeys) * 100
}

The cryptographic protocols specified in this part -- symmetric encryption, elliptic curve key agreement, the Signal Protocol's Double Ratchet, and the hybrid post-quantum constructions described above -- operate within a distributed network infrastructure that must route, store, and deliver encrypted payloads without introducing the centralized points of failure that the cryptography is designed to eliminate. The following part describes how that infrastructure is designed: the mesh networking foundations, node architecture, relay topology, distributed storage with erasure coding, and the offline mesh communication layer that extends Zentalk's reach beyond the internet.