2
$\begingroup$

I know how to prove the correct decryption of a (ElGamal) ciphertext. enter image description here

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.

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

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ thx!May I know which paper contains the security analysis of this algorithm? It would be very helpful for me. $\endgroup$
    – user109993
    Jun 22, 2023 at 8:51
  • $\begingroup$ I think the paper Can DSA be improved? from Eurocrypt 1994 is the ur-source for this observation. $\endgroup$
    – Daniel S
    Jun 22, 2023 at 13:22

Your Answer

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

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