[Resource Topic] 2023/007: Post-Quantum Security of Key Encapsulation Mechanism against CCA Attacks with a Single Decapsulation Query

Welcome to the resource topic for 2023/007

Post-Quantum Security of Key Encapsulation Mechanism against CCA Attacks with a Single Decapsulation Query

Authors: Haodong Jiang, Zhi Ma, Zhenfeng Zhang


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.

ePrint: https://eprint.iacr.org/2023/007

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .