0
$\begingroup$

Both RSA and Elgamal have homomorphic properties. So both can re-encrypt the ciphertext. Re-encryption with Elgamal works as seen here.

How does re-encryption work using RSA?

What modification / addition is needed to transform simple RSA to RSA with re-encryption?

The keys for RSA:

Public key: $e$ & $n$

Private key: $d$

Encryption: $C=M^e \bmod n$

Decryption: $M=C^d \bmod n$

I read this answer and it's very similar to what I am looking for. But I have practically a few limitations (as it is textbook RSA, and I have security flaws). I have an arbitrary length (large) plaintext. I want to encrypt it with RSA. I want to re-encrypt the ciphertext (independently and multiple times). Also I don't understand this formatted plaintexts in this question.

Is there a practical scheme / implementation available?

What changes are there needed in RSA to re-encrypt a ciphertext without compromising security?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Both RSA and elGamal have homomorphic property. So both can re-encrypt the cipher text

That doesn't follow.

Re-encryption means being able to take $E_{a}(m)$ and $F(a, b)$ (that is, a function of both private keys), and being able to generate $E_{b}(m)$ (that is, the encryption of the same message under a different private key), but (and this is the critical part) it not being able to recover $m$ from those two. That is, $F(a, b)$ is a key that allows you to "switch keys", but is not sufficient (without the private keys $a$ or $b$) to allow you to decrypt.

What the homomorphic property of RSA is allow you to take $E_{a}(m)$ (and the public key), and allow you to generate $E_{a}(G(m))$ (for certain functions $G$).

That doesn't allow you to switch RSA keys (which would imply changing modulii), and there is no obvious way to do so...

Improve this answer
$\endgroup$
7
  • $\begingroup$ Proxy re-encryption is a thing, I believe possible to implement in RSA. Each keypair holder can create unidirectional re-encryption keys from their own keypair to other keypairs (one per target keypair). $\endgroup$
    – Natanael
    Aug 23, 2019 at 15:50
  • $\begingroup$ It's not possible. You can't map group structures, if the numbers of elements don't match. For ElGamal, that also only works if they use the same group. But in RSA, different keys can't have the same group - or it actually would imply both parties can calculate both private keys. $\endgroup$
    – tylo
    Aug 23, 2019 at 16:35
  • $\begingroup$ @tylo: I don't know of a proof that you can't translate elements from one group to another. I certainly don't know of a way, but that doesn't imply that it can't be done... $\endgroup$
    – poncho
    Aug 23, 2019 at 16:52
  • $\begingroup$ I believe the correct plural is modulopodes. $\endgroup$
    – Squeamish Ossifrage
    Aug 23, 2019 at 17:55
  • $\begingroup$ @poncho I think the problem is not just having any mapping, but a meaningful one. Something that can preserve the relevant group structures, ideally it should also be bijective and e.g. map subgroups to subgroups. A simple reason why cardinalities matter: Assume one group is much smaller (the one applied secondly), then you can't even encrypt and then decrypt and get your message with almost certain probability $\endgroup$
    – tylo
    Aug 23, 2019 at 19:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.