Interesting malleability property of Goldwasser-Micali PKC
This property is a consequence of the homeomorphic property of GM (plus the fact you don't need to know $r$ to encrypt a 0).

In GM, given $Encrypt(A)$ and $Encrypt(B)$, you can compute $Encrypt(A \oplus B)$.  This is what the above observation is doing; generating a random encryption of 0, and then computing $Encrypt( A \oplus 0 )$ (which, of course, stands for the same plaintext as did the original $Encrypt(A)$.  Because someone without the private key couldn't tell that your random $Encrypt(0)$ held a 0 or not, they also can't tell whether your new ciphertext has the same plaintext as same as the old.

You can do the same with Pallier; you can encrypt a 0, and then compute $Encrypt(A + 0)$; again, no one without the private key can tell whether the new ciphertext conceals the same value as the old.