Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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 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.
In short, we can ask for a modified message decryption and get useful info. This is not allowed to happen in a IND-CCA-2 secure system.
