Paper 2025/1748

Post-Quantum TLS 1.3 Handshake from CPA-Secure KEMs with Tighter Reductions

Abstract

TLS 1.3 is at the heart of secure modern internet communications. With the rise of quantum attacks, post-quantum TLS 1.3, built on post-quantum key encapsulation mechanisms (KEMs), has naturally become a major research focus. At Eurocrypt 2022, Huguenin-Dumittan and Vaudenay demonstrated that KEMs secure against chosen-plaintext attacks (CPA) are sufficient to construct a secure TLS 1.3 handshake in the random oracle model (ROM), but their security reduction incurs an $\mathcal{O}(q^6)$ loss, where $q$ is the number of random oracle queries. Improving their security bounds was left as an open problem. To address this problem, Zhou et al. took the first step at Asiacrypt 2024, improving the loss factor to $\mathcal{O}(q^2)$ in the ROM and $\mathcal{O}(q^4)$ in the quantum ROM (QROM) for OW-CPA secure KEMs, and to $\mathcal{O}(q)$ (ROM) and $\mathcal{O}(q^2)$ (QROM) for IND-CPA secure KEMs. In this work, we advance the state-of-the-art by providing tighter security reductions for TLS 1.3 handshake based on CPA-secure KEMs. We introduce a new security notion, \textit{IND-1CCA-1MAC}, and show that with a slight ciphertext expansion, the reduction losses can be significantly improved to $\mathcal{O}(q)$ (ROM) and $\mathcal{O}(q^2)$ (QROM) for OW-CPA secure KEMs, and to only $\mathcal{O}(1)$ in both models for IND-CPA secure KEMs. Moreover, we prove that without additional modifications such as ciphertext expansion, the loss of $\mathcal{O}(q)$ (ROM) and $\mathcal{O}(q^2)$ (QROM) is unavoidable. Finally, we analyze the security of TLS 1.3 from CPA-secure KEMs in the hybrid key exchange setting, and provide experimental evidence that ciphertext expansion is a practical trade-off for mitigating reduction losses.

Note: Corrected minor typos.