Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
The argument is mentioned (briefly) under the point Security and Efficiency on that same page. – Henno Brandsma Feb 19 '13 at 18:36
up vote 2 down vote accepted

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.

share|improve this answer
Is Blum-Goldwasser also obviously not RCCA secure? $\:$ ( $\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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.