# Interesting malleability property of Goldwasser-Micali PKC

GM is a cryptosystem with a modulus $N = pq$ ($p$, $q$ prime) and quadratic nonresidue $r \in (\Bbb Z / N\Bbb Z)^*$ as the public key. You can see the details on Wikipedia.

Anyway, let's say that $N < 2^{1024}$. Then the ciphertext can be represented as a $1024$-bit string regardless of $N$. In which case, you can take a ciphertext $c$ (which is the encryption of a single bit), and then multiply $c$ by a random $z^2 \pmod{2^{1024}}$, and get an equivalent ciphertext. An adversary should, as far as I can tell, be unable to decide whether this decrypts to the same plainbit as $c$. And you don't need to know the public key $(N,r)$ to do this operation.

Is there any literature on this property?

• It sounds similar to universal re-encryption – cygnusv May 31 '15 at 15:10
• @cygnusv looks about right – ogogmad May 31 '15 at 15:13
• Re-encryption is pretty common. Any homomorphic scheme, which is IND-CPA has this property: You only need the public key to encrypt the neutral element, and then you use the homomorphic operation to apply it to the ciphertext. – tylo Jun 1 '15 at 10:12

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.