We have a $PRP : \{0,1\}^{3n} \rightarrow \{0,1\}^{3n}$ and encryption scheme constructed from this $PRP$.

$E_k(x\|r\|0^n)$, where $r$ is randomly chosen from $\{0,1\}^n$ and $0^n$ is a block of zeros with length equal to $n$.

To decrypt $y \in \{0,1\}^{3n}$, we compute $x\|r\|w = E_k^{-1}(y)$.

If $w \neq 0^n$ then output error. Otherwise, output $x$

I want to prove that this is CCA-secure (it's definitely secure, since it's a common CCA-secure scheme constructed from secure PRP). I understand the notion of CPA,CCA security and their respective game definitions. I know that for example if I manage to prove that it's IND-CPA and INT-CTXT secure, then it's also IND-CCA secure. However, is it INT-CTXT secure? My intuition is that it's not INT-CTXT, because we cannot check the authenticity (compare if the last block is all zeros) without decrypting.

I would say it's CPA-secure, because the encryption is not deterministic. However, there are schemes that are CPA-secure, but are not CCA-secure, like $E_k(r, f_k(x) \oplus r)$, where $r$ is random, and $f_k$ are PRFs. My other questions is whether a CPA-secure scheme is also IND-CPA secure.

I am struggling to find a formal proof of CCA-security, anyone willing to give me some hints or examples of other CCA-security proofs?

  • $\begingroup$ I don't understand your notation. $\endgroup$ – fkraiem May 9 '16 at 1:11

Your Answer

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

Browse other questions tagged or ask your own question.