I want to find a secure and efficient way to tally votes.
Say we have N ~ 10000 voters. Each one can vote for candidate 1, candidate 0, or both. But no one can vote more than once. The groups who voted for 1 or 0 want to tally their votes.
Is there a way to tally votes that is fast and cryptographically secure? Perhaps a zero knowledge proof or a ring signature? Thanks!
Yes it is possible, check out the CGS voting protocol: A Secure and Optimally Efficient Multi-Authority Election Scheme. In this voting scheme, each voter encrypts their vote $v \in \{0,1\}$ with Elgamal encryption: ${\it ctxt} = (g^vg^{xy}, g^y)$ under public key $(g, g^x)$. At this point anyone can compute the aggregate of all votes as the componentwise product of all ballots: $(g^{\sum v_i}, g^{x\sum y_i}, g^{\sum y_i})$ and the authorities (who jointly hold the secret key $x$ matching the public key) decrypt this ciphertext.
In order to make this protocol secure against malicious voters, the voters are required to provide a zero-knowledge proof the their encryption is an encryption of 1 or 0 but of nothing else. This is accomplished using the CDS '94 technique, which allows you to compose simple zero-knowledge proofs using (among other access structures) "and" and "or" type predicates. Specifically, the zero-knowledge proof says "this ciphertext is an encryption of 1 OR this ciphertext is an encryption of 0".
In your case, a voter's ballot should consist of two ciphertexts so that they can be tallied independently across voters leading to a tally for each candidate. Accordingly, there should be two "this ciphertext encrypts 0 or 1" proofs.
You do need a way to collect all these encrypted ballots. Voting schemes usually assume the existence of a public append-only bulletin board available to everybody. If access to the bulletin board logs your identity, then you can use those logs to identify double voters and count only their most recent ballot. An alternative is to assume that each voter has a public / private key pair associated to a digital signature scheme. They then sign their votes, and the talliers make sure not to count votes twice that are signed by the same public key.
