Retrieving ElGamal message with negative exponent value

Question

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.

Answer 1

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.