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?

  • $\begingroup$ It sounds similar to universal re-encryption $\endgroup$
    – cygnusv
    Commented May 31, 2015 at 15:10
  • $\begingroup$ @cygnusv looks about right $\endgroup$
    – wlad
    Commented May 31, 2015 at 15:13
  • 1
    $\begingroup$ 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. $\endgroup$
    – tylo
    Commented Jun 1, 2015 at 10:12

1 Answer 1


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.


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.