0
$\begingroup$

By running some tests I observed that if I perform a homomorphic division (multiplication with the multiplicative inverse) between two values using the ElGamal scheme, I get the correct result when the division produces a whole number.

For example, D(E(10) / E(2)) = 5 which is the expected result (here "/" denotes division applied homomorphically).

But if I try D(E(10) / E(3)) the result is a very large positive or negative number.

This might be expected since, I think, ElGamal supports homomorphic division only when the dividend is divisible by the divisor. My question is given only the decrypted result of such operation, is there a way to know whether the division "succeeded" in the sense that it is the result of a division where the dividend is divisible by the divisor?

$\endgroup$
1
2
$\begingroup$

I've included some discussion in general, but "El Gamal" here is a red herring. Your confusion is with the difference between "division" in $\mathbb{R}$, and "division" in $\mathbb{F}_p$. I discuss this more in detail at the end.


El Gamal's ciphertexts are of the form:

$$\mathsf{Enc}_{g, h}(m) = (g^y, mh^y)$$ Note that $h = g^x$, where $x$ is the secret key. This admits a (multiplicative) homomorphism, as you mention: $$\mathsf{Enc}_{g, h}(m_1)\ast \mathsf{Enc}_{g, h}(m_2) = (g^{y_1+y_2}, m_1m_2 h^{y_1+y_2})$$ I believe your confusion stems from confusion over what $m_1m_2h^{y_1+y_2}$ means. Like many cryptosystems, El Gamal is defined over what is known as a "finite field" (in particular $\mathbb{Z}/p\mathbb{Z}\cong\mathbb{F}_p$). This is a number system that allows you to add, subtract, multiply, and divide (just like with $\mathbb{R}$), but the operations are somehwat different than you are used to. Fix $p = 5$ (although any prime number works). Then addition is defined "mod 5", so: $$3 + 3\bmod 5 \equiv 6\bmod 5\equiv 1\bmod 5$$ So in this number system, $3 + 3 = 1$. Multiplication is similarly defined "mod 5". So: $$3 \times 3\bmod 5 \equiv 9\bmod 5 \equiv 4\bmod 5$$ So $3\times 3 = 4$ in this number system.

What does "division" mean in this number system? Well, one can show that for any (non-zero) $x\in\mathbb{Z}/p\mathbb{Z}$, there is a unique $y$ such that $xy \equiv 1\bmod p$. Over $\mathbb{R}$ this is true as well (instead with the equation $xy = 1$) --- if $x = 2$, then $y = 1/2$. But in $\mathbb{Z}/5\mathbb{Z}$, if we have that $x = 2$, then $y = 3$ means that $xy\bmod 5\equiv 6\bmod 5\equiv 1\bmod 5$. So, in $\mathbb{Z}/5\mathbb{Z}$, we have that $2^{-1} = 1/2\equiv 3\bmod p$.

This is now when we get to your point --- if we have $x,y\in\mathbb{Z}/p\mathbb{Z}$, then $xy/y\equiv xyy^{-1}\equiv x\bmod p$, so "when $y$ divides $xy$, division is like you would expect over $\mathbb{R}$". But the situation can be more complicated in general.

$\endgroup$

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.