Homomorphic cryptosystems in RSA

Question

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 perform 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?

Answer 1

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.

Answer 2

Unfortunately, homomorphic encryption probably isn't very useful for your purpose. Or, at least, it doesn't provide very strong protection.

Here's why homomorphic crypto doesn't help very much, in this setting. You will implement some function increment_score(). This function works using homomorphic crypto magic to increment the encrypted score, but forget about all those technical details; they don't matter. As you correctly state, a player can look through your code and execute any of the functions in your code. So, a mischievous player could keep calling increment_score() many times to increase their score to an arbitrarily high level before sending it back to the server.

Sure, the score is encrypted, but nothing prevents the player from increasing their score by as much as you need. So, you're not actually significantly better off than you were.

Sadly, crypto isn't magic. It can't solve the problem of players who reverse-engineer your client. The only robust defense is to avoid trusting the client, and perform the score computations on the server (however, that may or may not be an option in your case).