Voting scheme where the votes become public when a threshold is reached

Question

Does there exist a voting scheme where voters cast private encrypted votes that automatically become public only after the threshold number of votes is cast?

It needs to be done without a central authority that is trusted to hold keys. I don't need it to be receipt-free, I just want it to be authority free and automatic.

The reason why I need this is, that seeing other people's votes before the threshold is reached could bias the final outcome.

Answer 1

I am making the following assumptions regarding your requirements:

1. The number of participants is low enough, for it to be feasible for each participant to open a reliable, authenticated and confidential communication channel to each other participant.
2. The vote of each individual participant is only meant to be kept secret until the threshold of votes has been reached, at which point it becomes public how each participant voted.
3. System parameters $p, q, g$ are selected in advance, such that the discrete logarithm problem in a sub group of prime order $q$ of might be assumed to be hard.
4. The participants should not be allowed to change their votes once their votes have been cast, and collusion between participants must be prevented.
5. The risk of individual participants invalidating the election by opting out, is relatively low, and when it happens, it can be dealt with by starting over.

Given the above requirements, a simple approach would be to combine a binding and computationally hiding discrete logarithm based scheme with Shamir Secret Sharing.

Steps:

1. Each participant $P_i$ selects a value $x_i$ uniformly at random from $\mathbb Z_q$, calculates $h_i = g^{x_i} \bmod p$, and broadcasts $h_i$ to all other participants.
2. Each participant computes $h = (\Sigma_1^nh_i)^{(p-1)/q} \bmod p$. If $h$ equals zero, step 1 is repeated. (Extension: Each participants broadcasts $h$ and some protocol is in place to disqualify users who broadcast a value the majority of the other users find to be incorrect. For simplicity, this has been left out at this stage and the rest of the stages of the protocol.)
3. Each participant $P_i$ selects a degree $t$ polynomial $p_i(x)$ with coefficients $a_{i,1},..,a_{i,t}$ selected uniformly at random from $\mathbb Z_q$ and $a_{i,0}$ representing the vote of the participant.
4. In order to vote, each participant $P_i$ selects $n$ values $r_{i,j}$ uniformly at random from $\mathbb Z_q$, keeps them secret, broadcasts a commitment sequence $C_{i,j} = g^{p_i(j)}h^{r_{i,j}}$, sends $p_i(j)$ with confidentiality and authenticity to each participant $P_j$ who has already voted and gets $p_j(i)$ back from $P_j$.
5. Once at least $t+2$ votes have been cast, each participant broadcasts its $r_{i,j}$ values and all of the $p_j(i)$ values it has received from other participants.
6. Each participant verifies that each value $C_{j,k}$ it received when user $P_j$ voted, meets $C_{j,k} = g^{p_j(k)}h^{r_{j,k}} \bmod p$. (If not, some protocol has to be in place to disqualify users.)
7. Each participant solves the shared secret of each other participant and broadcasts the result.
8. Some protocol is in place to confirm that a majority of the participants have broadcasted the same result.

Q: Does this protocol really prevent collusion?

A: Strictly speaking, no. Nothing prevents the participants from conducting informal out-of-band exit polls during the voting in step 4. No protocol has any influence over what the participants do out-of-band, so this is something that has to be dealt with out-of-band as well.

Q: Is the Shamir Secret Sharing component really necessary? Since all participants who vote have to be online during the entire protocol, wouldn't a commitment scheme and a counter be sufficient?

A: If the possible votes are "Yea" (1) or "Nay" (0), using Shamir Secret Sharing allows a minor modification to the protocol, by which the total number of votes are counted before each individual vote is revealed. Each participant $P_j$ reveals the sum of the $p_i(j)$ values. Together with the corresponding sum of $r_{i,j}$ values, this sum can be verified using the commitments. Reconstructing a polynomial from those summed up shares, will equal the number of "Yea" votes.

Now, if some participant (e.g. the last one to reveal its sum) chooses to opt out, this user might be disqualified and the rest of the participants might wait for the next vote to be cast. No individual vote will have been revealed (through the protocol), but it is possible that the disqualified participant already knows the result (and is the only one who knows it).

Q: Isn't constructing the $h$ generator as a sum, rather than a product, susceptible to doctoring by the last participant to submit its $h_i$ value?

A: Not if we assume that $q^3 \lt p$ and every participant verifies that each $h_i$ belongs to the $q$ order subgroup. Also, constructing it as a sum allows for each participant to open their $x_i$ value, to prove that they know the discrete logarithm of $h_i$, without making it possible to calculate $log_g(h)$

Answer 2

Just a toy proof of concept, lacking some key features the ultimate answer would probably want:

1. Choose some sufficiently long key.
2. Each voter is assigned some chunk of a key (and an index so we know where that chunk goes).
3. The assignments are encrypted by this same key.
4. The encrypted assignments shared publicly.
5. As votes come in, they are signed by a key chunk.

As key chunks come in, knowledge of the key increases, approaching the point where the mapping of keys to people could be brute forced.

You could only calibrate the moment when the keylist would become public by some very generous assumptions, and large elections might make the key size impractical.

Unless... you could declare that the key is the XOR of r known rows, and each row is divided into c chunks. Voters get a chunk with an index (you don't even need to give them a row index). Then no one would have any information about the key until at least one column was complete, so at least r votes would have to be in. But you couldn't guarantee you had any information until at least (r * c) - (c - 1) votes were in... a lot of unpredictability.

Maybe this can be tuned, though, by assigning chunks as the votes are cast. You assign the chunks to an ordinal, 1st voter gets (index = 0, chunk = "a9 68 c7 ... "), second voter gets (index = 0, chunk = "66 93 b9 ... "), third voter gets (index = 0, ... ). They leave with a slip that includes their key chunk, they sign a sheet saying they were they Xth voter.

So if you want votes to be revealed at 60 percent, and you have 100 voters, then your 55th voter gets (index = 1, chunk = "de ..."), 56th gets (index = 2, chunk = "be ...")

You move laterally only once you get near your target. (In fact, you don't need a bunch of full rows, you just need a bunch of redundant chunks for the first column, before you start moving laterally.)

Ok, so this involves a trusted administrator so far, but maybe it could be patched for distributed administration...

UPDATE

Wasn't a finished answer (didn't even address the distributed requirement!) I should have held off, apologies. But for anyone interested in a toy proof of concept, here's a better version.

Each party can encrypt their vote (providing signatures, commitments) and then distribute portions of key information among the other potential voters. As the voters lodge a vote, they publish the key information they have, such that once a certain number of voters have lodged a vote, all prior votes can be decrypted.

This relies on a primitive where some message is divided into a number of pieces such that it can be recovered after (and only after) some percentage of the pieces have been revealed, but remains cryptologically secure before that threshold.

I provided an ugly way to do that in the comments, just generate a number of suitably random unique masks equal to the number of voters required for revelation. The voter distributes these randomly among all other voters (some redundancy will be required). Have the pool of voters reveal this information during the voting process.

If a voter reveals previously revealed key information, here's the especially ugly bit, a call goes out to the other voters to supply a new piece of key information, or as voters see the key information they received published when they haven't yet voted, they can check their piece of key information back in with the voter who owns that key and request a random piece of key information from that voter that has not yet been revealed.

Would appreciate a better version of the primitive though. Not sure if error correcting codes might provide something here or not...