How to prove the correct decryption of several (ElGamal) ciphertexts in a batch？

user109993

6/21/24, 6:26 AM

I know how to prove the correct decryption of a (ElGamal) ciphertext.

The above protocol is from the paper: Bootle J, Cerulli A, Chaidos P, et al. Short accountable ring signatures based on DDH[C]//European Symposium on Research in Computer Security. Cham: Springer International Publishing, 2015: 243-265.

But,how to prove the correct decryption of several (ElGamal) ciphertexts in a batch? Performing the above protocol for each ciphertext seems inefficient.

104

1 + 3

elgamal-encryption

zero-knowledge-proofs

user109993

6/21/24, 6:29 AM

For example, there are some ciphertexts {C1, C2, C3, ...., Cn}. Alice wants to prove that the decryption of these ciphertexts all results in a.

Daniel S

6/21/24, 11:37 AM

Do these multiple texts a) all use the same $(pk, dk)$ pair with multiple $(u_i,v_i,vk_i)$ triples or b) use multiple $(pk_i,dk_i,u_i,v_i,vk_i)$ 5-tuples?

user109993

6/21/24, 12:45 PM

Yes. These ciphertexts all use the same (pk,dk) pair.

Score:3

Crypto

Daniel S

6/21/24, 1:23 PM

Batch verification is straightforward in this case. Given $n$ signatures $(u_i,v_i,vk_i)$ for $1\le i\le n$, the same $x$ and $z$ value can be used to verify all $n$ signatures, by multiplying together the left and right hand sides of the verification equations thus: $$pk^xA\stackrel ?= g^z$$ $$\left(\prod_i u_i\right)^x\prod_i B_i\stackrel ?=\left(\prod_i\left(\frac{v_i}{vk_i}\right)\right)^z.$$ This requires only 4 modular exponentiations and $3(n-1)$ multiplications rather than $2(n+1)$ modular exponentiations and $n$ multiplications. Clearly if the individual checks hold, then the composite check must also hold.

+ 2

user109993

6/22/24, 8:51 AM

thx！May I know which paper contains the security analysis of this algorithm? It would be very helpful for me.

Daniel S

6/22/24, 1:22 PM

I think the paper [Can DSA be improved?](https://link.springer.com/chapter/10.1007/BFb0053426) from Eurocrypt 1994 is the ur-source for this observation.

Elon Musk

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

EN: How to prove the correct decryption of several (ElGamal) ciphertexts in a batch？

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.