Introduction

This document is a companion to the Post-Quantum Safety Analysis of the Blend Protocol, which identified the quantum-vulnerable components in the Blend Protocol and proposed a phased migration path. This document evaluates specific post-quantum candidate primitives for each component: Key Encapsulation Mechanisms (KEMs), digital signature schemes, and zero-knowledge proof systems.

The purpose of this document is to present the pros and cons of candidate primitives along the relevant trade-off axes — not to select one. Deployment decisions (security category per component, lattice-vs-non-lattice posture, specific candidate selection, compression strategy for ZK proofs) are deferred to dedicated decision documents and RFCs. The analysis below is intended as input to those decisions, providing a consistent comparison baseline and surfacing the trade-offs that the decision documents will need to navigate.

The evaluation criteria are driven by the Blend Protocol’s specific constraints:

• Per-message overhead: Every Blend message carries cryptographic material in its public header and up to $\beta_{\max} = 3$ blending headers. Size increases are multiplied by the number of layers. The relevant metric is how much each cryptographic field grows relative to its current size, multiplied across the 4 encapsulation layers (1 public + 3 blending). Throughout this document we therefore size each candidate by its per-layer and total header growth against the current Ed25519/X25519/Groth16 baseline.
• Per-connection (handshake) overhead: TLS-layer key exchange material is exchanged once per connection establishment (Phase 0 cost), amortized across all messages on that connection. This is a separate cost profile from per-message overhead.
• Verification throughput: Signature verification on the public header is performed inline during relaying — every core node verifies every relayed message’s signature. PoQ verification, on the other hand, is performed asynchronously rather than on the relay path. This means signature verification speed is critical (gating message propagation), while PoQ verification speed is less critical (it absorbs into an asynchronous pipeline) but still bounded by overall compute budget.
• Proving/signing latency: PoQ proofs and signatures must be generated during message construction. For data messages (block proposals), proving latency directly impacts consensus timeliness.
• Assumption diversity: If the primary candidate relies on lattice hardness (as most NIST-standardized PQ primitives do), backup candidates from different mathematical families (code-based, hash-based, isogeny-based) should be identified. This provides resilience against a potential breakthrough in any single hardness assumption.

<aside> 💡

On performance figures. Absolute timings are platform- and implementation-dependent and are therefore reported in the shared companion benchmark document — measured on a Raspberry Pi 5 and an Apple M3 MacBook, through three independent implementations (the liboqs C library, the pure-Rust RustCrypto crates, and aws-lc-rs) and two TLS stacks (OpenSSL and rustls) — not here. Throughout this document, performance is characterized only by order of magnitude (microsecond / millisecond / sub-second) and by relative comparison between candidates, both of which the benchmark shows to be stable across platforms and implementations. The benchmark additionally quantifies the worst-case latency of the intrinsically variable operations (rejection-sampled signing and key generation) — the figure that matters wherever an operation sits inside a deadline, such as message construction. Sizes (public key, secret key, ciphertext, signature, proof) are deterministic functions of the parameter set and are reported in full.

</aside>

Migration Phases

The companion analysis document defines four migration phases. Before listing them, we briefly summarize the two threat classes each phase targets, so that the migration phases can be read without consulting the companion document:

• Harvest Now, Decrypt Later (HNDL) — retroactive threat. An adversary records encrypted traffic today and decrypts it later, once a cryptographically relevant quantum computer (CRQC) becomes available. This threat applies to confidentiality primitives (key exchange and encryption). In Blend, two layers of encryption protect sender-to-proposal anonymity: the TLS tunnel between nodes (outer layer) and the per-hop Blend encapsulation (inner layer). Both layers must hold for HNDL protection to remain intact.
• Real-time forgery — active threat once CRQCs exist. An adversary with real-time CRQC access can forge signatures and zero-knowledge proofs, impersonating nodes and bypassing quota/access-control mechanisms. This threat applies to integrity and authentication primitives (signatures, ZK proofs). It is not retroactive — recording today's signatures or proofs provides no advantage to a future adversary.

Each migration phase targets a single security property at a specific layer of the stack, and the phases are separated as distinct infrastructure upgrades. Although Phases 0 and 1 both use a KEM, and Phases 2 and 3 both defend against real-time forgery, the layer each one protects — and therefore its size, performance, and deployment requirements — differs. For each phase we state what is replaced, what it protects, and the consequence of not doing it:

• Phase 0 — Connection-level HNDL protection (TLS key exchange).
  • What is replaced: the ECDHE key exchange in inter-node TLS connections, upgraded to a hybrid PQ KEM (e.g., X25519+ML-KEM-768). Affects only the TLS handshake — a per-connection cost amortized across all messages on that connection. Because this cost is amortized rather than paid per message, the size and performance constraints on the KEM at this layer are looser than at Phase 1. Library support already exists (e.g., rustls-post-quantum via aws-lc-rs), making this the most easily deployable phase.
  • What it protects: the confidentiality of connection-level metadata — which node is talking to which at the IP level, and in particular the first hop from an original sender to its first blend node. That first-hop observation is what links a (public, on-chain) block proposal back to the network identity of its proposer; TLS encryption is what denies a network observer that link.
  • If not done: an adversary recording inter-node traffic today can, once a CRQC exists, break the recorded TLS key exchange, decrypt the transport layer, and recover the IP-level flow — including first-hop emission patterns. Because the harvesting starts now, the exposure is retroactive and cannot be undone later.
• Phase 1 — Message-level HNDL protection (Blend message KEM).
  • What is replaced: the X25519 static-ephemeral key agreement in Blend's per-hop message encapsulation, replaced with a post-quantum KEM (or hybrid). This is a per-message cost rather than a per-connection one, so although it reuses the same class of primitive as Phase 0, its size and performance constraints are tighter — it is a distinct requirement, not a repeat of Phase 0.
  • What it protects: the confidentiality of the Blend message content and the blending path independently of the transport layer. TLS protects a message only while it is inside a tunnel between two nodes; at every node on the path the message leaves that tunnel, so transport encryption alone never keeps the content and onward routing hidden end-to-end. The per-hop Blend encapsulation is what protects them at each hop. The clearest case is a relaying core node, which terminates the TLS connection from its predecessor and therefore holds the Blend ciphertext directly — but the same applies to any adversary who obtains the Blend-layer ciphertext, including one who has broken the transport layer.
  • If not done: anyone holding a recorded Blend-layer ciphertext can, once a CRQC exists, break the X25519 agreement on the layers they hold and recover the corresponding content and routing. A relaying core node can do this for the layers it processes without any network vantage point or any need to break TLS; an adversary who has broken the transport layer can do it for the ciphertexts that flow through the connections they observe. Because the ciphertext can be harvested today, the exposure is retroactive.
• Phase 2 — Message integrity and authentication (signatures).
  • What is replaced: Ed25519 signatures — the Blend message signatures in the public and blending headers, and the TLS authentication signature — with a PQ signature scheme (e.g., ML-DSA).
  • What it protects: the integrity and authenticity of messages and the authentication of node identity — preventing an adversary from forging the signatures that bind a message to a signing identity, or impersonating a node at the transport-authentication layer.
  • If not done: once a CRQC exists, an adversary forges Ed25519 signatures in real time to tamper with or inject messages and to impersonate nodes. There is no harvesting component — recording today's signatures gives no advantage — so the migration must be complete before a CRQC arrives but carries no retroactive risk. (Signature forgery is necessary but not sufficient to inject a valid message: a forged PoQ, addressed in Phase 3, is also required.)
• Phase 3 — Proof unforgeability (ZK proof system).
  • What is replaced: the Groth16/BN254 proof system used for the PoQ — together with the ZkSignature and PoSel that inherit from it — replaced with a post-quantum ZK system (e.g., STARKs or lattice-based SNARKs). This is the most invasive migration in per-message overhead; the proof size dominates the Phase 3 cost.
  • What it protects: the soundness (unforgeability) of the PoQ — preventing an adversary from fabricating quota, core-membership, or leadership proofs and thereby bypassing rate-limiting and access control. The PoQ's zero-knowledge (witness-hiding) property is information-theoretic and is not at risk; only soundness is computational, so the threat is forgery, never retroactive extraction.
  • If not done: once a CRQC exists, an adversary forges PoQ proofs in real time to bypass quota, extract blending rewards without doing relay work, and mount targeted or network-wide DoS. As with Phase 2, there is no harvesting component.

Phases 0 and 1 together cover the full HNDL (retroactive) surface — connection-level and message-level confidentiality — while Phases 2 and 3 cover real-time forgery (signatures and proofs). All four phases defend against attacks that require a CRQC to execute; the distinction is when the adversary must act. The HNDL threats (Phases 0–1) are retroactive — the adversary harvests traffic today and decrypts it once a CRQC exists — so the protection must be in place before the traffic is sent. The real-time forgery threats (Phases 2–3) have no harvesting phase: they can only be mounted while a CRQC is operating, so those migrations must be complete before a CRQC arrives but protect nothing in retrospect.