On the KDM-CCA Security from Partial Trapdoor One-Way Family in the Random Oracle Model.

In PKC 2000, Pointcheval presented a generic technique to make a highly secure cryptosystem from any partially trapdoor one-way function in the random oracle model. More precisely, any suitable problem providing a one-way cryptosystem can be efficiently derived into a chosen-ciphertext attack (CCA) secure public key encryption (PKE) scheme. In fact, the overhead only consists of two hashing and a XOR. In this paper, we consider the key-dependent message (KDM) security of the Pointcheval's transformation. Unfortunately, we do not know how to directly prove its KDM-CCA security because there are some details in the proof that we can not bypass. However, a slight modification of the original transformation (we call twisted Pointcheval's scheme) makes it possible to obtain the KDM-CCA security. As a result, we prove that the twisted Pointcheval's scheme achieves the KDM-CCA security without introducing any new assumption. That is, we can construct a KDM-CCA secure PKE scheme from partial trapdoor one-way injective family in the random oracle model. [ABSTRACT FROM AUTHOR]