# Retrieving ElGamal message with negative exponent value

Although the ElGamal scheme states that the message $$M$$ must be $$1 \le M \le p-1$$ in this paper: A Secure and Optimally Efficient Multi-Authority Election Scheme they propose a method where the message can be $$-l \le M \le l$$ where $$|\ l\ | \lt p/2$$. This is stated in page 9.

The idea behind the paper is that for 2-way voting system the available options are encoded as $$m_0=1,\ m_1=-1$$ and when doing additive ElGamal the result could possibly be $$g^{-4}$$ or any negative exponent.

I know that for computing the message in the final stage of ElGamal we execute a loop for each possible value of $$M$$ but in this case, although this is what the paper proposes as well, I don't see how it is done.

• From the same page. where we may safely assume that $l < q/2$ for any reasonable security parameter $k$. – kelalaka Jan 14 at 19:33
• @kelalaka That was an embarassing misread. I did some tests and it works if $l \lt q/2$ rounded down, am I correct? Because for example, for $p=7,\ g=3$ we get the same result for $l=3\ and\ l=-3$ since $g^3 mod7 = 6$ but $g^{-3} = 1/27$ and taking the modular inverse of $27 mod7 = 6$ as well. – Konstantine Jan 14 at 20:57
• @kelalaka Thank you for the $\text{LaTeX}$ tips. Thinking about it carefully I also understand why $l \lt \text{Math.floor}(q/2)$. I will be posting an answer in order to not leave this question unanswered. – Konstantine Jan 15 at 10:29

In order to retrieve the message $$M$$ from the Discrete Log provided by the final step of ElGamal, knowing that $$-l \le M \le l \text{ where } |\ l\ | \lt \lfloor p/2\rfloor$$ works the same way as if $$1 \le M \le p - 1$$ that is, testing for all exponents. For negative values of $$l$$ we use modular division, e.g. $$5^{-3} \equiv 125^{-1} \equiv 6^{-1} \equiv 6\bmod7$$ and we find the inverse with Ext-GCD algorithm
It is important to note that $$|\ l\ | \lt p/2$$ where $$p/2$$ is rounded down e.g. for $$l=5$$ then $$p \ge 13$$. The reason for this is that the number of encoded values for $$-l \le M \le l$$ is $$2\ l + 1$$ due to the existence of the value $$0$$ and the defined cyclic group must have order greater than that.