rsa public-key elgamal-encryption paillier proxy-re-encryption
Updated Mon, 11 Jul 2022 16:42:50 GMT

Can Paillier ,RSA or any other schemes be used for universal re-encryption like elGamal?

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.


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...

Comments (5)

  • +0 – 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 — Sep 03, 2019 at 20:56  
  • +0 – @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... — Sep 03, 2019 at 21:15  
  • +0 – Thanks but how it can be " deterministic procedure for mapping an arbitrary value into a , pair", can you have a little detail — Sep 04, 2019 at 04:56  
  • +0 – What i want is exactly " deterministic procedure for mapping an arbitrary value into a , pair" — Sep 04, 2019 at 05:14  
  • +0 – @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. — Sep 04, 2019 at 12:22