Build a scheme that is CCA secure but not authenticated Trying to understand a solution from this paper:



Summary:


$E'_K=0||E_K(m)$ and $D'_K(0||c)=D_K(c)$ and $D'_K(1||c)=1$
IND-CCA secure (how?) as $1||c$ and $0||c$ are are easily decryptable
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.