# Homomorphic cryptosystems in RSA

Hopefully Crypto can help me understand homomorphic cryptosystems.

I'm designing a high score server for a game I made, and because of facets in the language i'm using, the player would be able to look through the code and execute functions in my game, so I'm trying to encrypt the score when it is sent to the server. The suggestion was made on Stack Overflow that I try and use a Homomorphic cryptosystem, which would allow the client's game to add or change the value given by the server, then the server retrieves that value and decrypts it as a highscore. Anyway, what I'm having trouble with is the "homomorphic property", or as Wikipedia describes it:

If the RSA public key is modulus $m$ and exponent $e$, then the encryption of a message $x$ is given by $\epsilon(x)={x}^{e} \bmod m$. The homomorphic property is then $$\epsilon(x_1)\cdot\epsilon(x_2) = x_1^ex_2^e \bmod m=(x_1x_2)^e \bmod m=\epsilon(x_1\cdot x_2)$$

Now I understand the arithmetic fine, but don't understand this. Is the homomorphic property showing that the encryption is malleable?

That you can preform operations on two unknown (encrypted) ciphertexts, $\epsilon(x_1)$ and $\epsilon(x_2)$, and recieve the result, $\epsilon(x_1\cdot x_2)$ by preforming $x_1^ex_2^e\bmod m$? Or is it just showing that $\epsilon(x_1)\cdot \epsilon(x_2)$ is the same as $x_1^ex_2^e\bmod m$?

And subsequently, to decrypt it, you use the RSA private key?

-

Yes, homomorphic encryption operations are malleable by definition. The definition of "malleable" is something along the lines of "can be intelligently modified", which is what homomorphic encryption allows you to do.

That you can preform operations on two unknown (encrypted) ciphertexts, $\epsilon(x_1)$ and $\epsilon(x_2)$, and recieve the result, $\epsilon(x_1\cdot x_2)$ by preforming $x_1^ex_2^e\bmod m$? Or is it just showing that $\epsilon(x_1)\cdot \epsilon(x_2)$ is the same as $x_1^ex_2^e\bmod m$?

Those are the same thing by definition. The encryption operation will allow for the multiplication of two ciphertexts to equal the encryption of the multiplication of the two plaintexts (mod $m$, in your case).

And yes, you would use the RSA private key for decryption. The public key would contain the exponent e in your equation.

Edit, for completeness:

Note that textbook RSA usage (aka, simply taking the plaintext to an exponent) is not secure for several reasons. When security is necessary, we apply a padding scheme to the plaintext before encrypting it (aka, $m$ becomes $p(m)$ for some padding function $p$). But doing so causes the homomorphic usage to multiply the formatted plaintexts instead of the actual original plaintexts (aka, you wind up encrypting $p(m_1) * p(m_2)$ instead of $m_1 * m_2$), which won't yield the desired results. The padding schemes will completely mess up the ability to use homomorphic properties, since multiplying formatted texts yields garbage.

You mention this is for a game, so security may not be of utmost importance (it depends on what the stakes are and what data is involved), but take care before using RSA without any padding; if you do use it, investigate ways to mitigate at least some of the weaknesses of textbook RSA.

-
awesome! thanks for clearing that up. –  SomekidwithHTML Aug 14 '12 at 17:28
It wasn't directly asked in the question, but I felt obliged to edit my reply and add a quick caveat about security. –  B-Con Aug 14 '12 at 17:57