Keys Too Large to Share: Post-Quantum Key Establishment Without a Coordination Server

WireGuard's handshake relies on a static-static Diffie-Hellman operation for which no practical post-quantum analogue exists. PQ-WireGuard addresses this limitation by restructuring the handshake around key encapsulation mechanisms (KEMs) and leveraging WireGuard's assumption that peers' static public keys are distributed out of band. This approach keeps the handshake within a single unfragmented datagram despite large post-quantum public keys while preserving initiation-message authentication. However, these assumptions break down in mesh and peer-to-peer deployments, where peers are discovered dynamically, static public keys are public by design, and the resulting default pre-shared key is computable by any observer. As a result, deployed post-quantum VPNs disable mesh networking when post-quantum mode is enabled. This paper characterizes the problem as a fundamental trade-off between KEM selection, key distribution, and wire image, and presents PQ-MESH, a post-quantum key establishment protocol for dynamically discovered peers that provides confidentiality and authentication without a coordination server. PQ-MESH carries lattice-based static public keys inline, protects responder resources using a stateless address-validation token before fragment reassembly, and binds KEM and signature keys into a single node identity. We describe the protocol, provide a reference implementation, and evaluate its wire overhead. Our evaluation shows that carrying a complete peer identity inline requires 1,312 bytes and expands the initiation flight to 7,296 bytes over seven datagrams at a 1,200-byte MTU. Despite this larger wire image, responder cost before authentication remains bounded to 54 transmitted bytes, zero allocated state, and no public-key operations, yielding an amplification factor of 0.0450. We also report a negative result: supporting mesh networking necessarily moves the handshake away from the two-datagram post-quantum QUIC Initial profile rather than toward it. This work presents a protocol design, specification, and reference implementation. It does not include a mechanized formal security proof, traffic-classification analysis, or evaluation over real network paths.