0
$\begingroup$

Is there a way to modify the RSA so that it's homomorphically additive?

I did some research and came across a paper which describes MREA (Modified RSA Encryption Algorithm), an RSA modification that, supposedly, is homomorphically additive.

The authors define the encryption algorithm as follows: $$ E(message) = g^{message^e \bmod {n}} \cdot r^{m} \bmod m^{2}$$

$e$ and $n$ have the same meaning like in RSA.
$m = r \cdot s$.
$r$ and $s$ are randomly generated large prime numbers.
$g = m + 1$.

I tried proving that $E(message_{1} + message_{2}) \equiv E(message_{1}) \cdot E(message_{2})$.

Here's my attempt: $$E(message_{1}) \cdot E(message_{2}) = g^{(message_{1} + message_{2})^e \bmod {n}} \cdot r^{\textbf{2}m} \bmod m^{2}$$ $$\neq $$ $$g^{(message_{1} + message_{2})^e \bmod {n}} \cdot r^{m} \bmod m^{2} = E(message_{1} + message_{2})$$

I do believe that I made a mistake somewhere but I fail to spot it.

Does anyone see where I messed up?

Thanks in advance!

$\endgroup$
2
  • 1
    $\begingroup$ Whoever may suggest one reads this paper as part of instruction on cryptography (rather than on the pitfalls of the academic publishing system) is incompetent or/and ill-intentioned. Read this instead. $\endgroup$
    – fgrieu
    Apr 30, 2022 at 17:51
  • 1
    $\begingroup$ No one suggested I read that paper. I was just researching a way to modify RSA to obtain the mentioned property. Thanks for the suggested paper, but it's not quite what I'm looking for. $\endgroup$
    – Arya513
    May 2, 2022 at 16:34

1 Answer 1

1
$\begingroup$

I tried proving that $E(message_{1} + message_{2}) \equiv E(message_{1}) \cdot E(message_{2})$.

Does anyone see where I messed up?

It is appeared you messed up when you tried to take this paper seriously.

This system glues together the Paillier cryptosystem with textbook RSA; Paillier and textbook RSA both have homomorphic properties, however they don't combine properly. For Paillier, multiplying two ciphertexts effectively adds the plaintexts; however adding two textbook RSA ciphertexts doesn't do anything (you need to multiple the RSA ciphertexts to homomorphically multiply the plaintexts).

If you need an additively homomorphic system, just use straight Paillier.

Other complaints about this paper:

  • From the security analysis section, they claim "If RSA which is based on single modulus, is broken in time $x$ and additive homomorphic based on dual modulus, is broken in time $y$ then the time required to break MREA algorithm is $x \cdot y$". It should be obvious that, because the public key contains both the RSA and the Paillier public key, it would suffice to break both individually, and so the security is no better than $x + y$. If both problems are about the same amount of difficulty, you end up doubling the amount of work the attacker needs to do, at the cost of increasing the encryptor/decryptor by a factor of 6 - not a great trade-off.

  • They use Paillier (and use the same notation that Paillier did), but do not cite him - that's plagiarism

$\endgroup$
3
  • $\begingroup$ I was suspicious of the paper, that's why I asked. Thanks for the detailed explanation! I can't use Paillier, I really need it to be a modification of RSA. $\endgroup$
    – Arya513
    May 2, 2022 at 16:30
  • $\begingroup$ @Arya513: why can't you use Paillier? RSA doesn't have any usable homomorphic properties (the ones it has are more useful to the attackers, hence we add padding to break up those properties) $\endgroup$
    – poncho
    May 2, 2022 at 16:36
  • $\begingroup$ Long story, but I wanted to see if there's a usable (or any at all) RSA modification with the stated property. $\endgroup$
    – Arya513
    May 2, 2022 at 17:58

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.