HetAKE: Heterogeneous Authenticated Key Exchange for Post-quantum Migration

Post-quantum migration will be uneven: stacks and PKI will evolve on different timelines, producing deployments where peers authenticate with different long-term key types (e.g., a KEM certificate on one side and a signature certificate on the other, or PQC KEM versus PQC signature). Most mutually authenticated key-exchange (AKE) mechanisms assume homogeneous credentials, creating an interoperability gap precisely when operators need agility—the ability to phase in PQC without synchronized certificate changes. We address this need with HetAKE: two-message, mutually authenticated protocols (KEM–SIG and SIG–KEM) that establish secure channels across mixed key types using only standardized primitives (KEMs and signatures) and avoiding DH-like structures that are difficult to instantiate post-quantum. We prove security in the Quantum Random Oracle Model (QROM) under active attacks and state exposure, obtaining indistinguishability against active attacks (IND-AA) for KEM-SIG and the state-attack-excluding variant (IND-StAA) for SIG-KEM. We implement both variants with widely used PQC and classical libraries and benchmark them against practical baselines (FSXY and Signed-DH/KEM). Results show competitive performance and a tunable asymmetry that shifts compute and bandwidth between initiator and responder via the choice of KEM and signature instantiations, which is useful for IoT, mobile, and other resource-skewed settings. In sum, HetAKE advances migration agility by providing a practical, provably secure AKE core for mixed-credential deployments, enabling incremental, low-friction movement toward post-quantum readiness.