In this paper, we consider the problem of combining a public key encryption (PKE) scheme and a public key encryption with keyword search (PEKS) scheme proposed by Boneh, Di Crescenzo, Ostrovsky and Persiano (BDOP) in Eurocrypt 2004. We argue that the two schemes need to be treated as a single scheme to securely provide the PEKS service that BDOP envisioned. We formally define such a scheme, which we call “PKE/PEKS” and its security against chosen ciphertext attack, which we call “IND-PKE/PEKS-CCA”. We then construct a highly efficient PKE/PEKS scheme using the PEKS scheme presented by BDOP and a variation of ElGamal encryption scheme and show that it is IND-PKE/PEKS-CCA secure in the random oracle model assuming that the Computational Diffie-Hellman (CDH) problem is intractable. We also propose a generic construction of PKE/PEKS, which is slightly less efficient than the first one. Finally, we present two extensions of a PKE/PEKS scheme to the multi-receiver setting and multi-keyword setting.