Design and Comparative Evaluation of a Hybrid Post-Quantum Key Exchange Protocol for Quantum-Resistant Onion Routing Networks

Abstract

The migration from classically secure key agreement to post-quantum cryptography (PQC) is now a practical engineering problem rather than a distant theoretical one and anonymity networks face a particularly acute version of it. Traffic captured today on the Tor network can be archived and decrypted years later once a cryptographically relevant quantum computer becomes available, an attack pattern commonly described as Harvest-Now-Decrypt-Later (HNDL). Because anonymity is meant to be a long-lived property, the consequences of retrospective de-anonymisation are severe. This paper presents the design and comparative evaluation of a hybrid circuit-extension handshake that combines the existing X25519-based ntor v3 key exchange with the NIST-standardised ML-KEM (FIPS 203) key-encapsulation mechanism, using the same concatenate-then-derive combiner construction adopted by the IETF's hybrid TLS 1.3 key agreement, for which a formal security reduction is known. The central engineering obstacle we address is that ML-KEM public keys and ciphertexts are an order of magnitude larger than the 509-byte fixed Tor cell payload, which forces a fragmentation and reassembly layer onto a protocol that was never designed to carry multi-cell handshake material. We describe a concrete integration into the CREATE2/CREATED2 and EXTEND2/EXTENDED2 message flow and a cell-packing scheme aligned with the direction of Tor proposals 340 and 355. We benchmark the cryptographic core directly using the Open Quantum Safe library (liboqs) and OpenSSL, measure the real memory footprint of in-flight handshake state and compose the measured costs into a perhop and circuit-level model with an explicit component-level breakdown. We extend the evaluation beyond a single server platform: we cross-compile and functionally verify the same primitives for ARM64/NEON and we implement, functionally verify against an independent reference model and synthesise on a real FPGA target a representative ML-KEM arithmetic datapath, reporting genuine place-and-route resource and timing results. Our measurements yield a result that reframes the problem: every ML-KEM operation, at all three parameter sets, is faster on commodity hardware than a single X25519 scalar multiplication, so the per-hop handshake computation grows by only about twelve percent when ML-KEM-768 is added. The dominant cost of the migration is therefore not computation, on any of the platforms we examined, but the fragmentation of large key material across fixed cells, which triples the number of cells per circuit-extension event and interacts with congestion and loss.