Paper 2025/1755 Original: eprint.iacr.org/2025/1755 ↗

DAKE: Bandwidth-Efficient (U)AKE from Double-KEM

Abstract

Bandwidth remains a major bottleneck in post-quantum cryptography, particularly for authenticated key exchange (AKE) protocols. In this work, we present DAKE, a bandwidth-efficient AKE framework built from double-KEM constructions. DAKE comes in two main versions achieving, respectively, weak and full perfect forward secrecy, as well as explicit authentication. It further admits two variants: a unilateral version, and another where a signature scheme replaces a KEM. They are proven secure in the standard model under eCKw and eCK-PFS, two strong variants of the extended Canetti–Krawczyk framework. DAKE employs a double-KEM, a primitive that encapsulates a single key under two public keys simultaneously. Such constructions can achieve smaller encapsulation sizes than two independent KEM encapsulations, offering a significant bandwidth advantage. To facilitate the design of double-KEMs compatible with DAKE, we introduce a chosen-key Fujisaki–Okamoto (CK-FO) transform proven in the QROM, which upgrades IND-CPA double-PKEs to IND-CCA double-KEMs while ensuring the one-sided chosen-key security required by DAKE. As a concrete instantiation, we propose Maul, a compact double-KEM derived from ML-KEM under the Hint-MLWE assumption. Maul reuses ciphertext components to cut encapsulation size by up to 42% compared to two parallel ML-KEMs. When instantiated with Maul, DAKE achieves overall communication reductions of about 16% (mutual authentication) and 21% (unilateral), outperforming both the double-KEM AKE of Xue et al. (ASIACRYPT 2018) and standard ML-KEM-based AKEs.