# Prove that Two Re-encryptions of the Same ElGamal Pair have the Same Decryptions

I'm working on an internet election system that requires the shuffling of ballots accompanied by an interactive proof of the legitimacy of the shuffle. I am working on this paper and I am stuck at the part outlined below:

By releasing the single value $$(r'-r'')\mod(p-1)$$, the two ElGamal pairs $$(x',y')$$ and $$(x'',y'')$$ can be shown to have the same decryptions without any linkage or association to the original ElGamal pair $$(x,y)$$.

I managed to get the value $$(r'-r'')\mod(p-1)$$ outlined above but I am not sure how to use this value to prove that both re-encryptions have the same decryption.

Thank you for the time 😊,

Andrei.

Writing in additive notation, suppose that we have a generator $$G$$ and public key $$A$$. Our two pairs are $$(x’,y’)=(M+r’A,r’G)$$ and $$(x’’,y’’)=(M+r’’A,r’’G)$$. Given $$r’-r’’$$, we can check that $$y’-y’’=(r’-r’’)G$$ and $$x’-x’’=(r’-r’’)A$$
In multiplicative notation we have $$(x’,y’)=(MA^{r’},G^{r’})$$ etc., we check that $$y’/y’’=G^{r’-r’’}$$ and $$x’/x”=A^{r’-r’’}$$.
Had the messages been different but with the same ephemeral $$r$$ values, the first check would pass, but not the second.
• Thanks for that, sorry to keep bothering, I tried implementing it through code (javascript, using jsbn library to do math on big integers) but I just can't seem to get it to work. I am trying to work out the left and right side of the equation and then equating them as below: const left = y1.divide(y2); const right = g.pow(proof); console.log(left.equals(right)); y1 is y', y2 is y'', and proof is (r'-r''). Whenever I raise g to the power of (r'-r''), I get 1 and when I divide y' by y'', I get a 0 is y1<y2 or a 1 if y1>y2. Would you know what I am doing wrong? Dec 21, 2021 at 14:00
• It sounds like you are doing naive arithmetic rather than arithmetic modulo $p$. You should have left=(y1*modInverse(y2,p))%p for a suitable modInverse function (I don't know what javascript has built in) and right=modPower(g,proof,p) for a suitable modPower function. Dec 21, 2021 at 20:49
• Yes. Instead use (r'-r'')%(p-1) Dec 22, 2021 at 6:27