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$.

  • $\begingroup$ I hope I got the terminology right, if anything is wrong feel free to correct. $\endgroup$ – SEJPM Aug 1 '15 at 12:55
  • $\begingroup$ Is $\hspace{.04 in}f_K^{-1}$ assumed to not output an element of $\operatorname{Dom}(\hspace{.05 in}f_K)$ whenever $\hspace{.04 in}f_K^{-1}$'s $\hspace{1.93 in}$ input is not an element of $\operatorname{Range}(\hspace{.05 in}f_K)$? $\;$ $\endgroup$ – user991 Aug 1 '15 at 14:56
  • $\begingroup$ You mean something like $c \notin \mathcal C \rightarrow f_K(c)=\bot$? Yes I think it's reasonable to assume this, I'll add it. $\endgroup$ – SEJPM Aug 1 '15 at 16:26
  • 1
    $\begingroup$ Associated data authentication might work, but in general one should just use a(n efficiently-invertible) pairing function (that is efficiently computable), such as $\:$ prefixfree(x) || y $\:$ or if ​ length(y) < length(x) ​ then ​ 1 || prefixfree(y) || x ​ else ​ 0 || prefixfree(x) || y. $\hspace{.54 in}$ $\endgroup$ – user991 Aug 1 '15 at 20:30
  • 1
    $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – e-sushi Aug 1 '15 at 22:53

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.

  • $\begingroup$ The OP fixed that issue well before you posted this answer. $\;$ $\endgroup$ – user991 Aug 1 '15 at 19:18
  • $\begingroup$ @RickyDemer, ahhh, now I understand why you asked me for the explicit check if the supplied $c$ is actually in the range of the $f_K$! :) Just another sample on how subtle details and implicit assumptions not written out can break otherwise secure systems :) $\endgroup$ – SEJPM Aug 1 '15 at 19:42
  • $\begingroup$ @SEJPM Note that in my silly counterexample, the range is defined to include 1y. You can of course come up with a more natural counterexample, but it won't make a difference. A range check won't help here, and neither will using authenticated encryption for the symmetric part. As I wrote, however, a permutation may suffice. $\endgroup$ – Yehuda Lindell Aug 2 '15 at 9:13
  • $\begingroup$ @YehudaLindell, just to be sure (because the term range has two meanings): You're referring to range of a function $f$ as the set of all possible outcomes of the function? (not neccessarily the co-domain) For example 1y is indeed part of the co-domain (${0,1}\times \mathcal C$) but not part of the range (as was meant in the question, I couldn't find the proper notation for this :( ) as $\forall x\in \mathcal M:f'(x)\neq 1f(x)$. Either way +1 for the permutation suggestion and the answer for the unrevised question. $\endgroup$ – SEJPM Aug 2 '15 at 12:24
  • $\begingroup$ I just mean anything that the inversion algorithm will accept. Of course, it's possible to define the inversion function so that it won't accept $1f(x)$. However, that's not the point. $\endgroup$ – Yehuda Lindell Aug 2 '15 at 21:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.