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

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.

-
Not a crypto-question. In fact, this belongs on Stack Overflow as OP asks for nothing more than "how to implement a counter for votes". To OP: Encrypted or not... nothing is stopping you from counting how many votes your system receives. A simple "if(NumberOfReceivedVotes > TheThreshold) { MakeVotesPublic=TRUE }" will do the rest. –  e-sushi Aug 16 '13 at 16:33
@e-sushi: You might be mistaken. The OP asks for an authority free scheme, and your solution would require an authority to count the votes and keep them secret until the threshold has been reached. –  Henrick Hellström Aug 16 '13 at 16:41
@e-sushi: I think the key phrase in the question is "authority free", which rules out a central server that has to be explicitly trusted by the participants. Electronic voting is a topic in cryptography crypto.stanford.edu/pbc/notes/crypto/voting.xhtml. However, I do agree that the question should be edited by the OP to include more details about the exact requirements. –  Henrick Hellström Aug 16 '13 at 17:09
Once the threshold is satisfied, what are the security requirements? For example, if the threshold is satisfied and the tally revealed, then someone comes along and casts another vote. If the new tally is immediately revealed, we now know the value of that vote. –  mikeazo Aug 16 '13 at 18:14
@mikeazo: Most e-voting schemes are based on the premise that the individual votes should be kept secret even after counting has ended, but this is not how this question has been put: The votes are supposed to become public once the threshold has been reached. This is of course an unusual requirement for public elections, but not for e.g. board meetings. –  Henrick Hellström Aug 17 '13 at 0:03

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)$

-

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...

-
What do you mean, as key chunks come in? The key chunks themselves are not send, are they? Where do they come in? And you now suddenly require a trusted third party? Have you studied this particular field of cryptography? –  owlstead Aug 18 '13 at 23:41
All it requires is some way of splitting a key into chunks such that after n chunks are revealed the key is revealed. You could do this by just generating n random messages of key length such that, XOR'd together, they reveal the key. One less is insufficient. Distribute these randomly among the other voters. (Some voters will have duplicates.) As voters vote, they publish the key chunks they've received from others. If they publish a duplicate, they solicit a new public key chunk from the original voter or from the crowd of nonvoters. No third party required. –  Brownbat Aug 20 '13 at 1:18