ElGamal, RSA, and Paillier cryptosystem have homomorphic property, and can be used fro re-encryption purposes. I want to use the encryption to re-encrypt ciphertext(as in proxy re-encryption but differently/different scenario / may be like universal re-encryption)


  • Encryption: Encryption: choose some random number r1 with other parameters like public key, private key, mod, message:m ,C1:ciphertext etc. The key pair (private key,public key). C1=Encrypt(m,public key,r1).

  • Decryption: m=Decrypt(C1,private key)

  • Re-encrypt: choose random r2 (used to re-encrypt/re-randomize cipher text)

    C2=Re-enc(C1,public key,r2)

  • Decryption: m=Dec(c2,private key) (may be 2 time decryption to retrieve m)

Note: I want to generate decryption key from receiver environmental variable(i,e from ip address etc), so that it can automatically decrypt when received by correct machine and the algorithm must have some random number in encryption used to re-encrypt (randomize) cipher text. I want re-encrypt cipher text without knowing the private key.

ElGamal: ElGamal meets all the above requirements exactly. (I want some other cryptosystem like ElGamal)

RSA: I try RSA but RSA haven't used random r for encryption, so re-encrypting cipher text will issue. Is there solution for RSA?

Paillier: Another public key cryptosystem, have used random r and hence can have possibility to re-encrypt cipher text but the issue is private key lambda, lambda =LCM(p-1,q-1). So it can not be environmental key(because it is dependent on p and q). How to resolve this.

Is there alternate solution? Any suggestion will be appreciated.

  • $\begingroup$ It almost sounds like you want an IBE scheme instead $\endgroup$
    – Natanael
    Sep 3, 2019 at 20:38

1 Answer 1


With Paillier, it's easy; generate a random encryption of 0 ($r^n \bmod n^2$ for random $r$ r.p to $n$), and then homomorphically add it to the encryption (that is, $C2 = C1 \cdot r^n \bmod n^2$), and you're done (and all you need is the public key).

I don't believe RSA allows this as a possibility...

  • $\begingroup$ But what is about other part. The paillier secret key is dependent on p and q but i want to decrypt the cipher text if terget environment (as a private key) matched $\endgroup$ Sep 3, 2019 at 20:56
  • $\begingroup$ @abbasi_ahsan: you can decrypt with the private key. Or, do you want the 'private key' to be an arbitrary value (which $p$ and $q$ are not) - if so, then one could define a deterministic procedure for mapping an arbitrary value into a $p, q$ pair... $\endgroup$
    – poncho
    Sep 3, 2019 at 21:15
  • $\begingroup$ Thanks but how it can be " deterministic procedure for mapping an arbitrary value into a 𝑝,𝑞 pair", can you have a little detail $\endgroup$ Sep 4, 2019 at 4:56
  • $\begingroup$ What i want is exactly " deterministic procedure for mapping an arbitrary value into a 𝑝,𝑞 pair" $\endgroup$ Sep 4, 2019 at 5:14
  • $\begingroup$ @abbasi_ahsan: seed a CSPRNG with your arbitrary value (and nothing else), and then run prime generation logic to find an $n$-bit value $p$ (using the output of the CSPRNG), and once that is done, run the prime generation logic to find an $n$-bit value $q$ (using more output from the CSPRNG). You could then verify that $p \ne q$; however if $n$ is reasonable size, the probability of that happening is neglectable. $\endgroup$
    – poncho
    Sep 4, 2019 at 12:22

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.