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?

  • $\begingroup$ The argument is mentioned (briefly) under the point Security and Efficiency on that same page. $\endgroup$ Commented Feb 19, 2013 at 18:36

1 Answer 1


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.

  • $\begingroup$ Is Blum-Goldwasser also obviously not RCCA secure? $\:$ (eprint.iacr.org/2003/174.pdf) $\hspace{1.1 in}$ $\endgroup$
    – user991
    Commented Feb 19, 2013 at 19:31
  • $\begingroup$ 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? $\endgroup$
    – Johannes
    Commented Feb 19, 2013 at 19:45
  • 2
    $\begingroup$ @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! $\endgroup$ Commented Feb 19, 2013 at 21:31
  • $\begingroup$ 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! $\endgroup$
    – Johannes
    Commented Feb 20, 2013 at 9:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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