Existing works on pre-computing ElGamal ephermal keys

Question

I was playing around with a problem in e-voting schemes that use additive homomorphic encryption to tally votes, namely that at the end of the day somebody (or somebodies, if the secret material has been broken up somehow) has to be trusted to decrypt the final tally.

Looking at ElGamal's additive variant, reproduced here for reference:

• $M$ is a modulo field in which all computation happens
• $g$ is a generator for $M$
• private key = $k_2$ = random number < $M$
• public key = $k_1$ = $g^{k_2}$
• $m$ is a member of the modulo field $M$
• $x$ is the plaintext
• $r$ is a random number < $M$, different for each call to E
  • this is the ephemeral key, used in the second $D(...)$
• $E(k_1, x) = <g^r, m^x * k_1^r> = <c_1, c_2>$
• $D(k_2, c_1, c_2) = c_2 * ({c_1^{k_2}})^{-1}$
• $D(r, k_1, c_1, c_2) = c_2 * (k_1^r)^{-1}$

In e-voting schemes*, every vote is represented as a 1 or 0 plaintext and tallying is a simple matter of multiplying all the ciphertexts together and decrypting the result.

The following scheme eliminates the need to release the private key to decrypt the final tally:

Prior to the "election"

• precompute a large list of random numbers $R = [R_1, ... , R_n]$ where $n$ is the number of possible voters
• let $A = [A_1, ..., A_n] = [R_1, A_1+R_2, A_2+R3, ... , A_{n-1}+R_n]$
• publish the hashes of each member of A in order

When encrypting "ballots"

• when choosing an $r$ for a $E(k_1, x)$, choose the first unused member of R

After the election

• publish all the ciphertexts (the "ballots")
• publish $A_y$ where $y$ is the number of ballots cast

$A_y$ would be the ephemeral key for the tally, but wouldn't allow for the decryption of any other ballots (like the private key would). The correctness of $A_y$ is achieved by the polling authority committing to its value by publishing hashes before hand.

---

In a nutshell, it's just publishing a commitment (via hashing) for all possible ephemeral keys for the final tally; then releasing the singular relevant ephemeral key. Everyone can tally, and decrypt that tally but decrypting individual "ballot" values shouldn't be possible.

I built a little proof of concept program that actual does this (using some open source implementations of additive ElGamal), and it works.

Of course, simply working isn't sufficient; I'm curious about the security of the scheme.

My question, are there any publications or other work related to this approach?

This seems like a pretty simple extension to the well documented additive ElGamal e-voting schemes, but my Google-Fu is failing to find anything and I'm personally unfamiliar with any such material.

(This approach [the pre-computed ephemeral key part, specifically] being broken and why, also acceptable naturally)

_{*Simplified greatly from actual schemes, but this is the heart of the crypto bits.}

Answer 1

It seems you want to decrypt the final value without revealing the private key. First, if someone knows the private key, they can issue a very simple non-interactive zero knowledge proof that the plaintext is a decryption of the ciphertext (the ciphertext being the accumulation of all the ballots) without revealing the actual value of the key. This is the standard way of approaching the problem. (I can add the proof if you are interested).

Second, the approach of pre-committing to the random factors for Elgamal has been examined in the literature however for completely different reasons. There is a worry that if a voting machine chooses the randomness, they could try a few values until the ciphertext comes out with a certain pattern (e.g., the 5th bit is a 0 if the vote is for Alice and a 1 if it is for Bob). Your scheme incidentally avoids this. A more thorough approach is considered in On Subliminal Channels in Encrypt-on-Cast Voting Systems .

If you insist on your approach, note that you never need to use $c_1$ at all. $c_2$ alone is a simpler primitive called a Pedersen commitment. The approach of encoding votes with Pedersen commitments, adding them up (under commitment), and then revealing the sum of the random factors is considered in Improving Helios with Everlasting Privacy Towards the Public. The difference is that voters choose the random factor and submit an encryption of it rather than using factors chosen for them. (It also is being done for totally different reasons: Pedersen commitments have a property called everlasting privacy).

In terms of the security of your approach, it is not clear who knows R and how voters get their value of R. For example, if I give voter 5 the value ($R_5$ - 1) and give voter 6 the value ($R_6$ +1), they will still add up to the correct value of $R$. However voter 5's message will be $m^x/k_1$ and voter 6's will be $m^x*k_1$. These may be sensible values for a vote: for example say that $k_1=m^2$. If voter 5 votes for 0, then this can be counted as a -1 and if voter 6 votes for 1, it can be counted as a +3. In other words, you end up with 2 votes for candidate 1 instead of one vote for each.

It may be sufficient to choose $m$ in such a way that no one knows the discrete logarithm between $k_1$ and $m$ but I'd have to think about it some more before endorsing it.

Answer 2

A problem I see is that you're not actually achieving the goal you're trying to reach: Prove to the public that the authority is honest.

By making $A_y$ public, you're only proving that you used the (secondary) key that you said you would be using. What you're not proving though, is that it actually is the correct one, the sum of the ephemeral keys.

To prove that it is, you would have to do one of two things:

1. Publicize the $R_i$, so people can see that indeed $A_y = \sum R_i$. That would of course make the whole thing moot, since the votes wouldn't be secret anymore.
2. Let voter $V_i$ know the value of $A_{i-1}$, in which case each voter could verify that ${\cal H}(A_{i-1} + R_i)$ is indeed the published hash (and the voters would have to trust that everybody checks theirs). However, this would mean that $V_i$ can find out (by using $A_{i-1}$ to decrypt the ciphertext product $\prod_{j<i} <c_{1_j}, c_{2_j}>$) what the tally was up to the point where they themselves voted. In particular, $V_2$ would know how $V_1$ voted. This is obviously undesirable as well.

I don't know if there's a way for an evil authority to chose the $A_i$ such that they tweak the result in a "desired" way and not give implausible results (like 20 million votes for candidate 1, although there were just 30 voters), but unless this is proven to be impossible, your scheme doesn't seem to make the authority's decryption verifiable.

Answer 3

There has been extensive research literature on this subject. If you are considering using this for real, please read my answer to a similar question first.

As far as the specific question you asked, there is a general technique here. Rather than trusting a single electoral authority with the ability to decrypt all the votes (and thus the ability to learn how everyone voted, if they cared to act contrary to the public trust), a standard defense is to designate multiple electoral authorities and design a cryptographic protocol with the property that it would require collusion of all of the electoral authorities to improperly learn how people voted.

If you are using homomorphic encryption, a standard technical tool for achieving this property is to use threshold cryptography. Some additional stuff is needed (e.g., to allow the authorities to prove they did the decryption of the tally properly), but that is orthogonal and is described in the research literature.

(If you're not using homomorphic encryption, the other standard technical tool is mixnets, which allow a group of authorities to randomly permute and decrypt the encrypted votes, in a way that renders the cleartext votes unlinkable to the ciphertexts submitted by voters.)

If you'd like to learn more about this subject, I recommend that you start with Ben Adida's presentation, Voting Cryptography Tutorial for Non-Cryptographers (slides and audio recording of his talk). Then, once you understand everything in his talk, a good next place to start would be to read some of the research papers in the literature. For instance, the original Helios paper is excellent.