Privacy of vote from tallying authority in El Gamal Voting Schemes

Question

I've been reading this paper about ElGamal encryptions and its application in electronic voting:

http://www.win.tue.nl/~berry/papers/euro97.pdf

Section 2.3 talks about using Shamir secret sharing so that t-out-of-n authorities need to combine to decrypt an ElGamal ciphertext. This makes sense so that after multiplying the voters' individual commitments, authorities can combine to reveal the sum of the votes.

My question is, if this is the case, can the authorities not take advantage of this to decrypt individual voters' commitments since the commitments still use the same $g$ and $h$ values after all? Where does the security of the vote from the authority come from.

Section 3 talks about creating commitments using random values $b \in \{-1, 1\}$ and then posting another value $e \in \{-1, 1\}$ such that vote $= b \cdot e$, which I think might be where the security comes from, but does not expand further on this.

Any help is appreciated!

Answer 1

The random $b,e$ values would seem to allow the uniform randomisation of the message between $G$ and $G^{-1}$.

Also, while reading a technical article at this level, one can note the citing of sources [SK94,CFSY96] where the technique seems to have been first used and follow up those.

Answer 2

For Shamir sharing scheme, an individual authority can only decrypt his share of anything is has, including individual voter ballot. With this scheme, such a share would give no information about the vote. The whole point of introducing Shamir scheme is to achieve agreement on reconstructing (and then decrypting) only the final result.

Answer 3

For a very detailed answer, you might want to see Cryptographic Voting: A gentle Introduction that was written for a summer school on the topic.

Thw way threshold decryption of ElGamal usually works is that each authority produces a decryption factor $d$ for each ciphertext that they are willing to decrypt. The decryption factors for one ciphertext are no help in decrypting an unrelated ciphertext; the authorities do not share their secret keys with each other to perform the decryption. To decrypt an individual voter's ballot, you'd need at least $k$ authorities (if that's your threshold) agree to act maliciously and make an effort to decrypt this particular ciphertext.

For an ElGamal ciphertext $e = (a, b) = (g^r, m \cdot pk^r)$ with $pk = \prod_{i=1}^t pk_i$, that is there are $t$ authorities each with a key share $(pk_i, sk_i)_{i=1}^t$ the $i$-th authority's decryption factor for this ciphertext is $d_i = a^{sk_i}$. In a voting scheme, the obvious thing for the authorities to do is post their decryption factors for the encrypted tallies back to the bulletin board (along wit PoKs that they decrypted correctly, which gets you universal verifiability). Anyone can then decrypt this particular ciphertext by computing $m = b/\prod_{i=1}^t d_i$. (This is $n$-out-of-$n$ sharing, the idea generalises to $k$-out-of-$n$ polynomial secret sharing.)

If you have $t$ voters, in a straightforward homomorphic scheme you end up with ciphertexts $e_1, \ldots, e_t$ on the board and the procedure for one authority is to compute $e = \prod_{j=1}^t e_j$, then to produce a decryption factor for $e$ and only for $e$. This factor is no use in decrypting (say) $e_1$.