Suppose that in order to avoid loss in transmission, a secret key encryption scheme $(Gen, Enc, Dec)$ is modified to be $(Gen, Enc', Dec')$, such that the message m is encrypted independently three times as $Enc'(m)=(c_1,c_2,c_3)$, each $c_i=Enc(m)$.

For decryption, the 3 transmitted ciphertexts are decrypted using $Dec$. If at least 2 recover to the same message, that message is output as the decryption. Otherwise, an error message will be output.

So, I am wondering if $(Gen, Enc, Dec)$ is indistinguishable under a chosen-ciphertext-attack (IND-CCA), why isn't $(Gen, Enc', Dec')$ IND-CCA, too? Is that because there is the possibility that we may receive the error message? I mean $(Gen, Enc', Dec')$ uses the same $Enc$ and $Dec$, why doesn't it inherit the IND-CCA property?

  • $\begingroup$ What makes you sure that $(Gen,Enc',Dec')$ is not IND-CCA? $\endgroup$
    – mikeazo
    Commented Sep 27, 2011 at 12:51
  • $\begingroup$ Are you actually using a public-key scheme (e.g. using a key-pair), or are you using a secret key scheme (where both parties have the same shared key)? "private key" is normally used to refer to the former, but sometimes also the latter, this is why "public key scheme" is preferred. $\endgroup$ Commented Sep 27, 2011 at 18:20
  • $\begingroup$ I think this is a secret key scheme. $\endgroup$
    – huyichen
    Commented Sep 27, 2011 at 18:40

1 Answer 1


[EDIT: I am assuming a public key system here]

IND-CCA2 summary:

  1. get encryption key.
  2. make decryption queries on chosen ciphertexts.
  3. obtain challenge ciphertext on $m_L$, $m_R$, two equal-length messages chosen by you, the attacker. The challenger is suppsed to randomply pick one, encrypt it and return the ciphertext.
  4. make decryption queries as in 2. except that queries on challenge ciphertext are disallowed.
  5. guess if the challenger encrypted $m_L$ or $m_R$

In IND-CCA2 decryption oracle, Step 4 logic is "decrypt only if the ciphertext is not the same as the challenge ciphertext".

How would you define "same" in the modified case? (Does the decryption oracle require all three pieces to match? If so the new scheme is clearly not IND-CCA2 - the attacker can ask for decryption of a ciphertext where one piece is random). Once "being same" is properly defined, it will be simple to check if the new scheme is IND-CCA2 or not .

By the way, you probably need IND-CCA2 instead of IND-CCA.

Also, you should check out the R-CCA security notion, where Step 4. is replaced by:

  • make decryption queries as in 2. except that if ciphertext decrypts to one of the challenge messages, the oracle returns "INVALID".

I recall seeing this definition of R-CCA but don't recall where. If you want, I can dig thru the references and post a link.

[EDIT:] One reference for R-CCA is this IACR eprint article, Section 1.3.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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