I have been studying additive ElGamal and I think I have the hang of it except the part where the message $M$ must be retrieved by computing the discrete log of $g^M$.

From what I've read, the result of such computations is a function of $k$ e.g. for $g=3, M=4, \pmod{17}$ we have $3^4=13 \pmod{17}$ but computing the discrete log however gives $M=4 + 16k$. How do I know that $M=4$ and not $M=20$?

Note that for $g=3,M=20 \pmod{17}$ we also get $M=4+16k$.


The answer is simple if you know the answer to this question:

  • Can you use 20 instead of 4 for a plaintext?
  • If you can they will be the same encryption and no problem since 20 and 4 same for yo.
  • If you cannot, therefore, you cannot decide the plaintext after you decrypted.

To solve this issue you have to limit your message space into $\pmod{17}$ and divide your longer message block in an appropriate way. Now, you know, you have to take the smallest positive value where $k=0$.

The problem with adding homomorphically is a different issue. Before the computation, you have to consider the upper bound of your calculations and choose your modulus according to it. For example, if you are going to add 4 and 8 there is no problem, however, if you are going to add 10 and 9 you have to consider a bigger modulus.

| improve this answer | |
  • $\begingroup$ In my use case I know the maximum amount to sum can reach which means I have to find the next biggest prime after that correct? $\endgroup$ – Konstantine Oct 11 '19 at 10:07
  • $\begingroup$ That is what you need and that is commonly used in FHE implementations. Bigger than the necessary means more unnecessary computation. $\endgroup$ – kelalaka Oct 11 '19 at 10:09

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.