CPA-secure PKE ⇒ D-PKE (Encrypt-with-Hash, random oracle model)
Statement
Let be a CPA-secure PKE scheme whose message space contains for some (any CPA-secure PKE with two distinct messages of equal length gives one, by encrypting each bit of an -bit string componentwise as one of the two — standard), and a hash function, modelled as a random oracle, with outputs of the length of ‘s coins. The Encrypt-with-Hash scheme, with the same key generation and decryption and
is a PRIV-secure D-PKE for every min-entropy — BBO07.
Sketch
Unless the adversary queries at for an encrypted message , every ciphertext is a CPA encryption under fresh uniform coins, and the two worlds differ only in which independent vector is encrypted. The message finder does not see , so it queries at with negligible probability, since a correct CPA-secure scheme gives each public key negligible probability; the guesser, which sees only such ciphertexts, hits an encrypted message with probability at most its number of queries times , for the number of messages in the vector, plus a CPA advantage.