Proving correctness of a decryption of a homomorphically summed ciphertext?

Question

I would like to take some additively homomorphic cryptosystem - don't care much which one for now - and encrypt a series of numbers with it. I would then like to (in public) take these numbers, add them together, decrypt the sum and convince everyone that I did it correctly.

This may seem pointless because I myself encrypted those numbers to begin with, but I'm thinking about voting applications where in reality the party who encrypted the numbers is not the same as the party decrypting the sum, and the numbers being summed/decrypted are all on a public bulletin board.

I know voting is a well studied problem in the literature, but so far none of the papers I've read have been doing it in quite the same way I'm interested in, so I see this as a good opportunity to go exploring.

So far I understand that with a regular Paillier encryption, to prove a correct decryption you can just reveal the randomness, however this does not work if you have added together ciphertexts. Exponential ElGamal would probably work for my use case, but I'm not sure if it lets me do what I need either ... plus I'm uncertain how fast a normal computer can actually brute force discrete log in a message space of say a few hundred million possibilities. I know it's perfectly possible but there's a gap between "possible" and "fast enough to be usable" and I'm unclear how to calculate this out short of just implementing it myself and trying it empirically.

Answer 1

For exponential ElGamal this is quite easy if all singe ciphertexts are public (you mentioned they are on a public bulletin board). Lets call $(c_1,c_2)=(g^my^r,g^r)$ the ciphertext corresponding to the sum $m$ of all single encrypted messages after your homomorphic summing (with $y=g^x$ being the public key). The decrypting party simply provides a non-interactive proof of knowledge (signature of knowledge - $SoK$) of the private key $x$ (denoted $\alpha$ below), i.e.,: $$\pi \gets SoK\{(\alpha): c_1=g^mc_2^\alpha ~~\land~~y=c_2^\alpha \}$$ along with $m$ (this $SoK$ can be efficiently realised by converting the respective sigma-protocol to a non-interactive proof using Fiat-Shamir). Everybody can now check if homomorphically adding all ciphertexts yields $(c_1,c_2)$ and taking $(c_1,c_2)$ as well as $m$ and $y$ the proof $\pi$ verifies. If all this works out, then everybody will be convinced that the decrypting party behaves honest.

If you have a few million possibilities you can either use a pre-computed lookup table, brute force or by using some suitable, more sophisticated method to compute discrete logarithms, like Pollards lambda method (since you know where to search). Whats more suitable for you depends on your setting, i.e., how resource constrained are your entities, group setting, etc.

You may use a similar approach for any other additively homomorphic encryption scheme (such as Paillier).