The Perfect Voting Machine

Ballots must be physical. The ballot should exist as a physical medium, allowing for recount by multiple independent parties.

Ballots must be machine-readable. The ballot must be marked in such a way that it can be counted by machine, for speed, efficiency, and repeatability.

Ballots must be human-readable. The ballot should be marked in such a way that an average human can read it, in case the counting machines are called into question or unavailable.

Ballots should be marked by machine. This prevents human error in ballot-marking in such a way that the ballot becomes invalid.

Ballots should be confirmed by the voter before final casting. Before the ballot is counted and stored, it must be read by the same machines that would count the votes in a recount. This ensures that the ballot is readable, and reduces the possibility of both mechanical and human error marking the ballot.

Each ballot should have the choices printed in a random order. It's been shown that earlier placement on the ballot conveys an advantage in winning the election. This means that whoever writes the laws defining ballot order can give themselves an electoral advantage, which is a clear conflict of interest. Each ballot should randomize the order of the candidates.

No machine, document, or person besides the voter should possess both the voter's identifying information and ballot contents. The ballot must not be marked with any potentially identifying information such as the user's name or a timestamp with precision finer than one hour. No person should see the marked ballot after it is marked besides the voter. Neither the printing nor reading machines should have any knowledge of the voter.

Ballots must be impossible to counterfeit. Exactly as many valid countable ballots should exist as votes are cast. Voters must be prevented from walking in with a pocket full of blank ballots; similarly, false ballots should be impossible to insert after the election ends. Practically, this means all ballots must be marked on-site with unique information that can be confirmed valid, but which is different on every ballot. As a first-guess suggestion, perform a one-way encryption on a timestamp. Then perform a two-way encryption on that, plus GPS coordinates, using an encryption key that is known only to a few high-level election officials. This ensures every valid ballot is unique, and allows each ballot to be tracked to the polling location it was marked, while maintaining timestamp (and thus voter) anonymity.

Ballots should only be issued to registered voters. It should be impossible to issue a ballot without also marking the name of a single registered voter off the roll. Similarly, it should be impossible to mark a name off a roll without issuing a ballot. Each registered voter should be issued a voting card before arriving at the polling location, containing cryptographically unique information to that voter. Only with the presence of that card will a ballot be issued.

Only one ballot should be issued to each voter. After a voter is issued a ballot, their name is marked on the roll. If that voter determines that their ballot was mismarked, they must turn it back in to receive a replacement. No replacement ballots can be issued without the original being returned.

The design and firmware of all machines involved must be open and inspectable. Maintaining voter trust in the system is paramount. Open-source and open-hardware systems ensure that no back doors or remote access is possible, and allow review for flaws by many thousands of coders and engineers.

It should be impossible to lose ballots. The to-the-minute vote count shall be constantly shared via network with the central election office. This creates a check against large numbers of ballots suddenly "disappearing" before being counted.

So here's the process.

1) I receive my voter card in the mail. The card is marked with a crypto-hash of my personal information, making it effectively impossible to fake.

2) I arrive at the polling location and present my card. My card is scanned, marking me from the roll as having voted. (Optionally, some biometric identification may be performed here, to prevent people from voting with others' voting cards.) A ballot is printed with spaces for all races in my district, plus a unique code identifying the ballot as legitimate and from this polling location.

3) I take that ballot to the marking machine. I insert my ballot, manipulate a touchscreen, and the machine marks my ballot for each race as I indicate

4) I take my marked ballot to the reading machine. I insert my ballot, and it tells me who it thinks I voted for. This machine also confirms that my ballot is properly marked with a valid crypto-stamp indicating a legitimate ballot.
4a) I confirm that my ballot is printed correctly, both visually and by machine. The machine keeps my ballot and counts my vote. I get a sticker and leave.
4b) I find an error in my ballot marking. I return to the poll worker, who inserts my ballot into the ballot-printing machine. The machine confirms that my ballot was valid, marks it with information which renders it invalid (including a human-readable timestamp), and issues a new one with new markings. Return to step 3.

What attacks are possible against this architecture? Obviously we have a problem with running out of ink. Perhaps we mark everything with high-power lasers?