2-Pass Key Exchange Protocols from CPA-Secure KEM

Baoping Tian, Fushan Wei, Chuangui Ma

Yuting Xiao, Rui Zhang, Hui Ma

Jinrong Chen, Biming Zhou, Rongmao Chen +5 more

Jinrong Chen, Wei Peng, Yi Wang +1 more

TLS 1.3 is a crucial protocol for securing modern internet communications. To facilitate a smooth transition to post-quantum security, hybrid key exchange, which combines classical key exchange algorithms with post-quantum key encapsulation mechanisms (KEMs), is proposed to enhance the security of the current TLS 1.3 handshake. However, existing drafts and implementations of hybrid key exchange for TLS 1.3 primarily rely on CCA-secure KEMs (i.e., secure against chosen-ciphertext attacks) based on the Fujisaki-Okamoto (FO) transform. The re-encryption step in their decapsulation algorithms not only introduces additional performance overhead but also raises the risk of side-channel attacks. Although Huguenin-Dumittan and Vaudenay (Eurocrypt 2022) and Zhou et al. (Asiacrypt 2024) demonstrated that the weaker CPA-secure KEMs (i.e., secure against chosen-plaintext attacks) suffice for constructing a secure TLS 1.3 handshake, their analyses were limited to single-KEM settings and did not consider the hybrid key exchange scenario. This work challenges the necessity of CCA security by proving that CPA-secure KEMs are sufficient for the TLS 1.3 handshake even in the hybrid key exchange setting. We provide the first formal security proofs for this claim, covering both the classical random oracle model (ROM) and the quantum random oracle model (QROM), thereby ensuring security against quantum adversaries. To validate the practical benefits, we conduct an extensive performance evaluation based on the latest OpenSSL implementation. Our results show that using CPA-secure KEMs yields up to 44.8% performance improvement at the key exchange layer and up to approximately 9% acceleration for the full TLS 1.3 handshake. Beyond performance gains, this approach reduces the codebase's attack surface by eliminating the re-encryption step, thereby mitigating a class of side-channel vulnerabilities. Our work positions CPA-secure KEMs as a secure, efficient, and practical alternative for standardizing and deploying post-quantum TLS 1.3 even with hybrid key exchange.

Randy Kuang, Daniel Johnson, Daniel Panario

The approaching threat of quantum computing to conventional cryptography underscores the urgent need to reassess information security and develop practical quantum-safe primitives. In this paper, we present concrete implementations of Zero-Knowledge Arguments (ZKAs), analogous to but distinct from traditional Σ-protocols. Our implementation, termed the Cryptographic Primitive Argument (CPA), can be realized securely using any post-quantum Key Exchange Mechanism (KEM) and Digital Signature (DS) scheme. We describe two variants: one with dynamic public key encapsulation (CPA-DE) and another that is non-interactive (CPA-NI). We further detail efficient, NIST-standard-compliant CPAs instantiated with ML-KEM and ML-DSA, and provide a comparison with a post-quantum Σ-protocol. The lightweight and modular nature of our CPAs makes them suitable for a wide range of applications, including quantum-secure authentication, blockchain systems, and digital currencies.

Kazuki Yoneyama