0
$\begingroup$

In the answer for Is it possible to subtract/multiply numbers using homomorphic encryption? it says:

To add two encrypted numbers, one could use Benaloh, Damgård–Jurik, or several other known partially homomorphic cryptosystems. (Many of these "addition-only" cryptosystems can also be tweaked to support subtraction.

But I couldn't write down a way to sum two ciphered numbers with Benaloh's scheme neither find the mathematics for this on the forum.

So, how to sum numbers ciphered under benaloh's scheme without decrypting them?

$\endgroup$
1
$\begingroup$

From here, it says that encryption in Benaloh's scheme takes the form:

$$E_r(m) = y^mu^r\bmod n$$ I'll actually write it as: $$E_r(m;u) = y^mu^r\bmod n$$ Where $m$ is the message (in $\mathbb{Z}_r$) to be encrypted, and $u\in\mathbb{Z}_n^*$ should be uniformly random. The other parameters $y, r, n$ are of course important for the scheme, but will not be important to discuss the additive homomorphic properties of the scheme.

The trick here is to note that messages are "in the exponent". So if we want to add the messages, we'll have to multiply the ciphertexts. If we do this, we'll see that: $$E_r(m_0)E_r(m_1) = (y^{m_0}u_0^r)(y^{m_1}u_1^r) = y^{m_0+m_1}(u_0u_1)^r\bmod n = E_r(m_0+m_1;u_0u_1)$$ This will be a valid Benaloh ciphertext of $m_0+m_1$ (we technically should verify that $u_0u_1$ is distributed uniformly randomly over $\mathbb{Z}_n^*$, but this is not difficult).

Note that this homomorphic property is very similar to that of (unpadded) RSA, where ciphertexts take the form $E(m) = m^e\bmod N$. Of course there is the difference here that RSA must be padded to be secure, and this padding ususally removes the homomorphic property.

$\endgroup$
2
  • $\begingroup$ I was concerned if I could "extract" mod n out of equation when multiplying the ciphers. But you made it clear, thanks a lot! $\endgroup$ – Vieira Neto Sep 3 '20 at 1:54
  • $\begingroup$ No problem! For a self-contained answer to that question, you can do that because $(a\bmod n)(b\bmod n) = (ab)\bmod n$. While not relevant to this current discussion, $(a\bmod n) + (b\bmod n) = (a+b)\bmod n$ as well. These two properties mean that $\bmod n$ is what is known as a "ring homomorphism". $\endgroup$ – Mark Sep 3 '20 at 2:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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