International Association
for Cryptologic Research

Recently, in post-quantum cryptography migration, it has been shown that an IND-1-CCA-secure key encapsulation mechanisms (KEM) is required for replacing an ephemeral Diffie-Hellman (DH) in widely-used protocols, e.g., TLS, Signal, and Noise. IND-1-CCA security is a notion similar to the traditional IND-CCA security except that the adversary is restricted to one single decapsulation query. At EUROCRYPT 2022, based on CPA-secure public-key encryption (PKE), Huguenin-Dumittan and Vaudenay presented two IND-1-CCA KEM constructions called $T_{CH}$ and $T_H$, which are much more efficient than the widely-used IND-CCA-secure Fujisaki-Okamoto (FO) KEMs. The security of $T_{CH}$ was proved in both random oracle model (ROM) and quantum random oracle model (QROM). However, the QROM proof of $T_{CH}$ requires that the ciphertext size of the resulting KEM is twice as large as the one of the underlying PKE. While, the security of $T_H$ was only proved in the ROM, and the QROM proof is left open.

In this paper, we present an IND-1-CCA KEM construction $T_{RH}$, which can be seen as an implicit variant $T_H$, and is as efficient as $T_H$. We prove the security of $T_{RH}$ in both ROM and QROM with much tighter reductions than Huguenin-Dumittan and Vaudenay's work. In particular, our proof will not lead to ciphertext expansion. Moreover, for $T_{RH}$, $T_H$ and $T_{CH}$, we also show that a $O(1/q)$ ($O(1/q^2)$, resp.) reduction loss is unavoidable in the ROM (QROM, resp.), and thus claim that our ROM proof is optimal in tightness. Finally, we make a comprehensive comparison among the relative strengths of IND-1-CCA and IND-CCA in the ROM and QROM.