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

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.

• For example, there are some ciphertexts {C1, C2, C3, ...., Cn}. Alice wants to prove that the decryption of these ciphertexts all results in a. Jun 21, 2023 at 6:29
• 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? Jun 21, 2023 at 11:37
• Yes. These ciphertexts all use the same (pk,dk) pair. Jun 21, 2023 at 12:45

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.