# Why is Blum-Goldwasser not IND-CCA-2 secure?

Consider the Blum-Goldwasser encryption scheme as described on Wikipedia. I was told that it was not IND-CCA-2 secure.

I heard there was malleabilty, probably it has to do with XOR-ing. But I do not see the point. As stated in the Wikipedia article, in step 2 of the encryption, we choose a random element. So what we xor to the message looks totally different every time. How can we have malleability here?

-
The argument is mentioned (briefly) under the point Security and Efficiency on that same page. – Henno Brandsma Feb 19 '13 at 18:36

The randomness is not enough for IND-CCA-2. If we get a message (so $L$ bits of data plus the $y$ to reconstruct the random seed), we can modify it, say flip the first bit, and ask the decryption oracle for a decryption of the modified message (which will have the same $y$!), which we will get. Then the original message can easily be obtained: we get the same key stream for the message (because we have the same $y$ in the modified message), we xor the plain text of the modified message with the modified message and we get the key stream for both the original challenge and (by construction) the modified message. So now we can decrypt the original message too.
Or in a more usual game: we choose a message $p$ to be encrypted and we get back either random or the actual encryption. We do out procedure from above and see if what we got back decrypts to our $p$, and if not, we "expose" the player as having "played" random.
Is Blum-Goldwasser also obviously not RCCA secure? $\:$ (eprint.iacr.org/2003/174.pdf) $\hspace{1.1 in}$ – Ricky Demer Feb 19 '13 at 19:31
Thanks! But I really don't see why we have the same $y$? Also, what do you mean by "ask the decryption oracle for a decryption of the modified message" - I think you can only encript a message? – Johannes Feb 19 '13 at 19:45
@Johannes We choose the same $y$. Read up on what the Ind-CCA2 game is: the adversary is allowed to ask for decryptions of all messages, except the ones that are totally identical to challenge messages. So we choose the message to be the same except the first bit, and this is allowed. You can see it is quite a strong notion of security! – Henno Brandsma Feb 19 '13 at 21:31
Oh, indeed, $y$ is part of the cipher text that we pass to the Decryption oracle... So we can choose it. Yes, now I see it. Thanks! – Johannes Feb 20 '13 at 9:34