Score:0

Additively homomorphic (modified) RSA?

us flag

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!

fgrieu avatar
ng flag
Whoever may suggest one reads [this paper](https://doi.org/10.1109/ACCT.2012.74) as part of instruction on cryptography (rather than on the pitfalls of the academic publishing system) is incompetent or/and ill-intentioned. Read [this](https://doi.org/10.1007/3-540-48910-X_16) instead.
Arya513 avatar
us flag
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.
Score:1
my flag

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

Arya513 avatar
us flag
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.
poncho avatar
my flag
@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)
Arya513 avatar
us flag
Long story, but I wanted to see if there's a usable (or any at all) RSA modification with the stated property.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.