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.

  • $\begingroup$ From the same page. where we may safely assume that $l < q/2$ for any reasonable security parameter $k$. $\endgroup$ – kelalaka Jan 14 '20 at 19:33
  • $\begingroup$ @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. $\endgroup$ – PentaKon Jan 14 '20 at 20:57
  • $\begingroup$ @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. $\endgroup$ – PentaKon Jan 15 '20 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.

  • $\begingroup$ @kelalaka please edit or post a better if needed $\endgroup$ – PentaKon Jan 15 '20 at 10:49
  • $\begingroup$ @kelalaka I can't upvote my own answer :( $\endgroup$ – PentaKon Jan 15 '20 at 22:04
  • $\begingroup$ That was not the point. You don't upvote, It can be seen your profile. You ask questions, accept them but no upvote. Actually you upvoted 0 times in here. :) $\endgroup$ – kelalaka Jan 15 '20 at 22:07

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.