Paper 2017/1096

Post-quantum IND-CCA-secure KEM without Additional Hash

Haodong Jiang and Zhenfeng Zhang and Long Chen and Hong Wang and Zhi Ma

Abstract

With the gradual progress of NIST's post-quantum cryptography standardization, several practical post-quantum secure key encapsulation mechanism (KEM) schemes have been proposed. Generally, an IND-CCA-secure KEM is usually achieved by introducing an IND-CPA-secure (or OW-CPA-secure) public-key encryption (PKE) scheme, then applying some generic transformations to it. All these generic transformations are constructed in the random oracle model (ROM). To fully assess the post-quantum security, security analysis in the quantum random oracle model (QROM) is preferred. However, current works either lacked a QROM security proof or just followed Targhi and Unruh's proof technique (TCC-B 2016) and modified the original transformations by adding an additional hash to the ciphertext to achieve the QROM security. In this paper, by using a novel proof technique, we present QROM security reductions for two widely used generic transformations without suffering any ciphertext overhead. Meanwhile, the security bounds are much tighter than the ones derived by utilizing Targhi and Unruh's proof technique. Thus, our QROM security proofs not only provide a solid post-quantum security guarantee for previous KEM schemes, but also simplify the constructions and reduce the ciphertext sizes. We also provide QROM security reductions for Hofheinz-Hoevelmanns-Kiltz modular transformations (TCC 2017), which can help to obtain a variety of combined transformations with different requirements and properties.

Note: A new footnote is added.