Score:2

Crypto

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

Andrei Florian

4/18/23, 1:09 PM

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.

115

0 + 0

elgamal-encryption

zero-knowledge-proofs

Score:2

Crypto

Daniel S

4/18/23, 1:24 PM

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.

0 + 0

Andrei Florian

4/19/23, 10:57 PM

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?

Daniel S

4/20/23, 9:46 AM

Yes, this is multiplicative notation as in the second paragraph. I’ve edited to make this clearer.

Andrei Florian

4/21/23, 2:00 PM

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?

Daniel S

4/21/23, 8:49 PM

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.

Andrei Florian

4/22/23, 3:15 AM

That was the issue! Thank you. I am facing one problem with it though. I am generating (r' - r'') as r' - r'' % p. The proof works provided r'>r'', but doesn't otherwise unless I change left=(y1*modInverse(y2, p))%p to left=(y2*modInverse(y1, p))%p. Would there be a way to resolve that mathematically so that I can get r'-r'' to work regardless of the inequality?

Daniel S

4/22/23, 6:27 AM

Yes. Instead use `(r'-r'')%(p-1)`

Andrei Florian

4/22/23, 2:48 PM

Yes that's it. Thanks so much for all the help.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

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

TH: พิสูจน์ว่าการเข้ารหัสซ้ำสองครั้งของคู่ ElGamal เดียวกันมีการถอดรหัสเหมือนกัน

RO: Demonstrați că două re-criptări ale aceleiași perechi ElGamal au aceleași decriptări

RU: Докажите, что два перешифрования одной и той же пары Эль-Гамаля имеют одинаковые расшифровки.

VI: Chứng minh rằng hai lần mã hóa lại của cùng một cặp ElGamal có cùng cách giải mã

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.