What if the voting machine is the adversary (Distributed Knowledge/Trust)

Question

I read some e-voting questions here, but most deal with simple things like securing the connection from external attackers. But they usually put implicit trust on the central voting authority to be honest.

So assume you have 1000 Voters, and a single person (the Tallier) who tallies (i.e. counts) the votes. Each Voter knows what his own vote is (incomplete information), but only the Tallier knows how everyone voted (the complete picture). The Tallier wants to lie about the results, however.

Because the Voters don't trust the Tallier to be honest, they require him to provide them with some sort of a log. Each Voter then examines that log.

Can we make the system in such a way that it is impossible for the Tallier to provide a fraudulent log without a large percentage of Voters becoming aware that something is wrong?

I imagine something similar to SHA1 checksums, where a server cannot provide a file such that the SHA1 checksum will. Only in this case each voter has incomplete information (he only knows about his own vote).

Also, voters would need to detect if the Taller has invented non-existent voters.

Is there any research on the subject?

Answer 1

For paper ballots you have the tallier being audited or watched constantly by 3 people from your 1000 voters (scrutineers).

It could be something similar with e-voting, I don't know what exactly would work. Maybe you have one way data entry for the vote to go into secure government buildings, with giant display screens where any voter can see a list of anonymous vote receipts to gain confidence that their vote was counted, and a ceremony for ensuring the counting machines inside are working correctly and isn't tampered with during the vote.

Answer 2

I recently posted an answer to a question about the security of a voting system.

The external constraints for a vote are:

• secure identification of all voters
• impossibility to change the value of each vote
• anonymity of each vote : nobody including the (human) tallier can know who voted what

If you cannot trust the tallier system, you cannot trust the results. If you relax the anonymity, you can build a system where you publish all the votes so that each voter can control that his own one has correctly been processed. But you still need a third party authority to process the possible problems when a voter declares that his vote has been faked. If that part is manual, there is a risk of requiring as much human ressources as for a manual ballot.

The only way I can imagine is to setup a comitee of different persons each controled by the others able to:

• develop or analyze a voting system
• build and install it or control the build process and the installation on a production system.
• control the system all the time of the election

Answer 3

I think you're asking about the field of research known as

End-to-end auditable or end-to-end voter verifiable (E2E) systems are voting systems with stringent integrity properties and strong tamper resistance. E2E systems often employ cryptographic methods to craft receipts that allow voters to verify that their votes were counted as cast, without revealing which candidates were voted for. As such, these systems are sometimes referred to as receipt-based systems.

As MS Research set of slides is a bit more clear/concise than Wikipedia's article... the problem is defined (going from blurb to more precise statements) as:

Technology exists that enables any inaccuracies and tampering of election tallies to be detected …

… not just by election officials, but also by any candidate, media outlet, voter, or other observer …

… and not just external tampering, but corruption by election officials, equipment vendors, and others.

This is known as End-to-End (E2E) Verifiability.

An election is end-to-end verifiable if

1. Voters can verify that their own selections have been correctly recorded.
2. Anyone can verify that the recorded votes have been correctly tallied.

The real issue/challenge is that when you also want to enforce vote privacy/secrecy i.e.:

Voters must be unable to disclose their votes to others.

This is what you called "incomplete information". Without this last requirement (typical of democracies in the past 100 years or so, but not so much before), you can have an open ballot where everyone sees how everyone else votes (i.e. "complete information" to use your terms) as a fairly simple, low tech solution to just the first two constraints.

A relatively simple solution/idea when the 3rd constraint (vote secrecy aka "incomplete information" is added) is (thus) homomorphic tallying. Basically

a form of encryption allowing one to perform calculations on encrypted data without decrypting it first. The result of the computation is in an encrypted form, when decrypted the output is the same as if the operations had been performed on the unencrypted data

The MSR slides have an example.

If you're willing to make the voter do some extra work at voting time, then non-cryptographic solutions are possible e.g. Rivest's ThreeBallot.

Wikipedia mentions a couple of small scale tests/elections when such (cryptographic) E2E-V techniques were used. For a recent paper on a UK experiment, see Hao et al. "End-to-end Verifiable E-voting Trial for Polling Station Voting". For the earlier, more technical/theoretical paper from the same authors see "Every Vote Counts: Ensuring Integrity in Large-Scale Electronic Voting". In particular, research from this group attempted to eliminate any use of key-issuing Tallying Authorities.

we combine [a cancellation formula first introduced in 2006 in the design of an anonymous veto protocol [Hao and Zielinski 2006] with the conventional homomorphic encryption to build a self-enforcing e-voting protocol. Compared with the existing mix-net or homomorphic aggregation based tallying methods, the new method has the distinctive feature of not requiring any secret keys (hence no TAs).

Wikipedia also has a brief article on AV-nets, which underlies "the other half" of this technique.