Is constructing IND-CCA2 public key encryption schemes particularly easy with the KEM/DEM approach?

Question

After the introduction of McBits, I was interested what security notions are neccessary for IND-CCA2 security of integrated encryption schemes (IES, following the key encapsulation mechanism / data encapsulation mechanism KEM/DEM approach). Now I've recently answered a different question and stated that the DEM and the KEM both need to be CCA secure in order for the whole scheme to be CCA secure.

As a consequence of this I asked myself how to generically construct an IND-CCA2 public key encryption scheme. My question now is:

Is the below ("simple") KEM/DEM public key encryption scheme IND-CCA2 under the assumption that $KDF(x)$ behaves like a random oracle and that $f_K(m):\mathcal K\times \mathcal M \rightarrow \mathcal C$ is an invertible one-way trapdoor function?

---

The scheme (formalized as per "Introduction to modern Cryptgraphy", second edition, by Katz and Lindell):

The KEM:
$Gen:$ the same as for $f_K(m)$
$Encaps:$ choose a random $k\in \mathcal M$, apply $c\gets f_K(k)$, convert both to a (suitable) binary representation and output $(c,KDF(k))$ with KDF being a secure arbitrary length hash function
$Decaps:$ convert $c$ from a binary string to an element of $\mathcal C$, apply $k\gets f^{-1}_K(c)$ and output $KDF(k)$ or $\bot$ in case $k=\bot$ which is always the case whenever $c \notin \text{Range}(f_K)$ holds.

The encryption scheme is then constructed as in construction 11.10, meaning the returned $c$ is prepended to the ciphertext, the $KDF(k)$ is used to key an authenticated encryption with associated data (AEAD) scheme which does the bulk encryption. To prevent unclearities while parsing the inputs and outputs a special encoding (pairing functions) must be used, any additional data introduced here will be fed into the AEAD scheme, see this comment (by Ricky Demer) for the details. Decryption is then obviously applying Decaps to the prepended $c$ and decrypting and verifying using the AEAD scheme, decryption fails (and thereby returns $\bot$) if either $Decaps$ or the AEAD scheme return $\bot$.

Answer 1

If I understand the question correctly, you are asking whether it's really needed to have the KEM be CCA secure, and maybe in the random oracle model it would suffice for it to just be an invertible one-way function.

This would not be CCA2-secure. Specifically, let $f$ be any invertible one-way function, and construct $f'$ so that $f'(x)=0f(x)$ for every $x$. In addition, the inversion function works by ignoring the first bit of $y$ and then inverting the rest using $f^{-1}$. Note that $f'^{-1}(0y) = f^{-1}(1y)$ for every $y$. Thus, it is possible to change a single bit in the ciphertext, and the encrypted value remains untouched. Since the CCA2 experiment allows the adversary to query a decryption oracle on anything but the challenge ciphertext, this would allow it to obtain a decryption (by changing the appropriate bit of the ciphertext). I know that this is a stupid counterexample, but this is exactly the point of these counterexample: it demonstrates that additional properties are needed.

If we ask the same question for a trapdoor permutation then this seems more promising. The same KEM proof when using RSA (see Section 11.5.5) may go through in this case. I'm not guaranteeing it, since sometimes proofs fall on strange things, but it's my intuition. I suggest writing out a proof to make sure.