2
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Hi, thanks for the response and sorry for the delay on my side. I looked over the formulae provided and they seem to work given (x′,y′)=(M+r′A,r′G). In my case though, (x′,y′)=(MA^r', G^r'). Would you know how to adjust the proof to fit this? $\endgroup$
    – Andrei Florian
    Dec 19, 2021 at 22:57
  • 1
    $\begingroup$ Yes, this is multiplicative notation as in the second paragraph. I’ve edited to make this clearer. $\endgroup$
    – Daniel S
    Dec 20, 2021 at 9:46
  • $\begingroup$ 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? $\endgroup$
    – Andrei Florian
    Dec 21, 2021 at 14:00
  • 1
    $\begingroup$ 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. $\endgroup$
    – Daniel S
    Dec 21, 2021 at 20:49
  • 1
    $\begingroup$ Yes. Instead use (r'-r'')%(p-1) $\endgroup$
    – Daniel S
    Dec 22, 2021 at 6:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.