Let $(\mathsf{Gen}, E, D)$ be a CCA-secure public key encryption system with a message space $\{0,1\}^{128}$. Is the following derived cipher $(\mathsf{Gen}, E', D')$ also CCA-secure? Justify your answer.

$$\begin{array}{l} E’(\operatorname{pk}, m)&=&E(\operatorname{pk}, m + 1^{128})&\text{and}\\ D’(\operatorname{sk}, c)&=&D(\operatorname{sk}, c) + 1^{128} \end{array}$$

I've come across this exercise and the answer was apparently yes, it is CCA-secure, although I don't understand why, Can't the active adversary clearly see the part of the encrypted message $1^{128}$ during decryption $D’(\operatorname{sk}, c)=D(\operatorname{sk}, c) \oplus1^{128}$ and therefore be able to exploit this vulnerability to manipulate the ciphertext and observe the effects on the decrypted message? For example send $m_0=m+1^{128}+1^{128}$ since he also has CPA security power? I'd appreciate help.

  • 3
    $\begingroup$ I'd bet a cup of coffee that it should be $m \oplus 1^{128}$. I.e. the operation is bitwise exclusive or, not concatenation as you seem to think. $\endgroup$
    – Maeher
    Dec 18, 2023 at 16:36
  • $\begingroup$ I guess I missed that $\endgroup$
    – xorya
    Dec 18, 2023 at 16:39
  • $\begingroup$ I second that the question's $+$ most certainly is bitwise exclusive-OR, often noted $\oplus$ (though the $+$ notation makes perfect sense too in a context where it's clear that arguments are bitstrings), rather than concatenation, typically noted $\mathbin\Vert$. Suggestion: first understand why the derived cipher is sound (that is, always decipher correctly) assuming the original is, and what property of $\oplus$ is used. That property is not possessed by $\mathbin\Vert$, ordinary addition, or addition modulo $2^{128}$, regardless of endianness and other conventions. $\endgroup$
    – fgrieu
    Dec 18, 2023 at 17:12

1 Answer 1


To do the actual proof, we can set a CCA game with two adversaries. Adversary A = (A1, A2) is the CCA adversary attacking PE = (Gen, E, D) and adversary B = (B1, B2) is the CCA adversary attacking PE' = (Gen, E', D') as defined above. Essentially, we want to prove that PE being CCA-secure implies PE' being CCA-secure. To help illustrate the game, here's the following sketch:

enter image description here

On the surface adversary B is playing against challenger PE' but will invoke adversary A at her whim. Challenger PE' starts by generating a new key pair and sends the public key pk to adversary B1. B1 passes pk to A1. In this phase of the game A1 produces two challenge plaintexts m0 and m1. Adversary B1 takes those two plaintexts and XOR's each one of them with 1^128. Adversary B1 then sends those modified challenge plaintexts along with the state s (x0, x1, s) to PE'. Challenger PE', upon receiving the two challenge plaintexts, flips a coin to get the bit b that determines which plaintext to encrypt. Now since this is a PE' challenger, when it's encrypting x0 or x1, it will XOR them with 1^128 which effectively makes it an encryption of mb (since two XOR's with 1^128 will cancel out). Hence the ciphertext challenge y is an encryption of mb. Now adversary B2 receives the challenge y and passes it to adversary A2 along with m0, m1, and s from phase 1. A2 takes all this input and produces a guess d. Here we have to realize that if A2 guesses right, then B2 guess will be right as well (an encryption of m0 implies an encryption of x0, likewise for m1 and x1). Likewise, if A2 guesses wrong, then B2's guess will be wrong as well. Hence, we see that the chances of B winning the game are identical to the chances of A winning the game. Since this is true for any adversary, we may conclude that if PE is CCA-secure against any adversary it must follow that PE' is CCA-secure against any adversary


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.