# Which public key encryption scheme is re-randomizable? How can I re-randomize an encryption scheme?

1. Which public key encryption scheme is re-randomizable?

2. Is there any library for re-randomizable encryption scheme?

3. If not, how can I re-randomize a given public key encryption scheme?

I cannot find any papers about re-randomizable encryption.

I will start with an example and then comment on a natural general way to achieve re-randomization:

1. ElGamal: Let’s say we have a multiplicative written group $G$ (suitable for ElGamal) with public key $h=g^x$ and $g$ generates $G$ (or some prime order subgroup of $G$).

2. Any library that implements ElGamal encryption can do the following, although there may be no explicit function to do this: Take some ciphertext $(g^r,mh^r)$ for some message $m$ under public key $h$ and (since ElGamal is multplicatively homomorphic) do a component-wise multiplication with an encryption of the identity $1$ in $G$, say $(g^k,h^k$), with $k$ chosen uniformly at random. This gives you $(g^rg^k,mh^rh^k)=(g^{r+k},mh^{r+k})$, which is a re-randomized ciphertext to the original message $m$ under the public key $h$.

Generically, any public key encryption scheme that is probabilistic and homomorphic will let you re-randomize a given ciphertext by using the homomorphic property with a ciphertext to the identity of the respective group.

To generate the ciphertext of the identity element you obviously need access to the respective public key, i.e., you have to know under which public key the respective ciphertext has been produced. This can be avoided by extending the regular ciphertext with an encryption of the identity, as e.g. done in universal re-encryption.

• Thanks! Can I re-randomise OAEP RSA? Does the openssl use OAEP to make its RSA probabilistic? – Jan Leo Sep 9 '14 at 14:14
• @Jian Liu Unfortunately not. RSA-OAEP is not homomorphic (its CCA2 secure). You cannot publicly re-randomize ciphertexts of this scheme. – DrLecter Sep 9 '14 at 14:56
• The question is that I cannot find a good C/C++ implementation of Paillier. – Jan Leo Sep 9 '14 at 15:57
• @Jian Liu here is a C library. But I do not know if it is good enough for productive use. – DrLecter Sep 9 '14 at 16:12
• Thanks! I want to use a well known library like OpenSSL. I've tried to re-randomise the ElGamal in Crypto++. But the code in Crypto++ is too complex to modify. Currently, I am playing with libgcrypt. – Jan Leo Sep 9 '14 at 16:28