Trying to understand a solution from this paper:

enter image description here


  1. $E'_K=0||E_K(m)$ and $D'_K(0||c)=D_K(c)$ and $D'_K(1||c)=1$
  2. IND-CCA secure (how?) as $1||c$ and $0||c$ are are easily decryptable
  3. Not authenticated because $(1,c)$ is easy to decrypt because it will equal to 1. So, an adversary can append 1 to any ciphertext so that $1||c$ and say it was from him

Could someone explain what step 2, I can see why they are easily decryptable but cannot make the link between that and IND-CCA. My confusion is that the decryption looks like IND-CCA insecure because you can easily append 1 to c to get 1, so adv will always win.


Note that the goal of the adversary in the IND-CCA game is not to be able to output some valid ciphertext (i.e., a ciphertext that decrypts to something other than $\perp$), but rather to guess the secret bit $b$ on which the security game is parameterized (see the definitions here).

Since submitting a ciphertext of the form $1 || C$ to the decrypt oracle $D_K(\cdot)$ does not leak any information about the secret bit $b$, this informally shows that the security of $(G,E',D')$ essentially boils down to that of $(G,E,D)$.

Stated more formally as a reduction: if some adversary $A$ could break the scheme $(G, E', D')$ (in the IND-CCA sense), then we can come up with an adversary $B$ that breaks the underlying scheme $(G,E,D)$. Namely, $B$ runs $A$ and whenever $A$ makes a call to its left-right encryption oracle $LR'_K(M_0, M_1)$, then $B$ responds with $0 || LR_K(M_0, M_1)$, where $LR_K(\cdot, \cdot)$ is the left-right oracle in $B$'s own game. When $A$ asks $0 || C$ to its decryption oracle $D'_K(\cdot)$, then $B$ responds with $D_K(C)$, where $D_K(\cdot)$ is the decryption oracle in $B$'s own game. Finally, if $A$ asks to decrypt $1 || C$ and $C$ as never been used before, then $B$ simply responds with $1$, otherwise $B$ responds with $\perp$. In the end, $B$ outputs the same bit as $A$.

Created in this way, $B$ perfectly simulates the oracles $LR'_K(\cdot, \cdot)$ and $D'_K(\cdot)$ for $A$, and thus wins its IND-CCA game against the underlying scheme $(G,E,D)$ with at least the same probability as $A$.

Incidentally, what you have noticed is that the scheme $(G,E',D')$ is not INT-CTXT secure. This security notion does ask the adversary to come up with some ciphertext that decrypts to something other than $\perp$. A standard result (shown in the paper linked to above) is that IND-CPA + INT-CTXT $\implies$ IND-CCA. So what your example shows is that the converse of this is not true.


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.