[1] http://scholar.google.com/scholar?q=Information-theoreticall...
http://www.youtube.com/watch?v=sJfj9ySYg0Q
Massive voter fraud could be happening every election - it's pretty easy to vote fraudulently and there is almost no way to find out after the fact (I've done it unintentionally). For whatever reason, we are insanely afraid of hackers pushing an election over the edge, and yet we don't even ask for photo ID at the voting booth.
Seems to work very well, but I guess one advantage we have is that none of the parties here are worth cheating for.
Granted, oversight would likely thin a bit.
In regards to your comment regarding untrusted parties handling the hardware, here are a few counterpoints:
- We already trust polling place workers with paper ballots, the possibility for fraud already exists.
- The potential for fraud from any one polling place can be limited by implementing a system which makes it impossible (or very very difficult) to spoof the location from which a vote was cast, and ensuring that the number of votes cast per polling place is within an expected range.
- Such a system could also include a paper receipt with an ID number on it. A voter could plug this "tracking number" in on a trusted website (ie. vote.gov) and confirm that their name is associated with their preferred candidates, but not allow them to change these choices. This would go a long way towards identifying fraudulent activity when/if it occurs.
[1] Though figuring out how to quantify this is anybody's guess.
I don't know about the US, but here in Germany _anyone_ can watch the whole process including the counting of the votes.
So it is possible for me to check up on my polling place.
With the current paper ballot system you need a lot of people to cheat significantly. With voting computers you need only a really tiny number of people to steal an election.
Having representatives of each party overseeing the process should serve to keep any monkey business in check. Though when people are involved, there's always a chance for corruption.
They recently used a system called Scantegrity in Takoma Park, MD (Rivest also collaborated here). I've been meaning to look up the usability conclusions on this one, but I don't remember seeing much in the way of problems at the time.
(Speaking only of the US voting system)
The challenge is to allow for anonymous voting. I don't think it is necessarily a problem that is impossible to solve. Practical solutions are also a challenge.
The best way to ameliorate these discomforts is to ensure that a list of eligible voters is made available every year (already available under the current system), as well as a list and sum total of those eligible that voted. We would need to assign every voter a UUID every time he votes, and provide the voter a printed receipt of the UUID and selected choices (if desired) on security paper (controlled stock of security paper with its own unique identifier to be accounted for), and publish all election results with the selected choices matched to a UUID on a website every year in CSV and HTML formats.
I'm sure there will always be ways to tamper the system. The key is that if every one is able to watch the system (like open source code auditing), the risk of discrepancies or error is minimized. The UUID will allow the voter to confirm that his choices match the recorded results.
If this system were implemented, it would be better than the status quo. The current system may seem better, but it's prone to human error (Scantrons not being scanned by an optical reader; hanging chads; etc).
(We already saw a variant of the latter in 2000. Remember "I couldn't follow the arrow and accidentally voted buchanan"?).
Further, if a person's vote is verifiable, it also opens the door to paying people for their votes.
As far as the UUID/pair frauds, we could mail a confirmation letter to the voters stating that they voted. Since I don't think we could tie the UUID to the actual voter, we could tell them they participated in this year's election and to verify the results to the receipt. This part is compounded in difficulty partly due to federal voting regulations that don't allow us to tie a voter to his votes, so I think the only real way is to verify videotapes verifying that said voters appeared in person to vote.
Again there are flaws and it will take more people to resolve the issues with electronic voting.
It reduced the problem significantly by making it impossible (or at least significantly harder) to verify that you vote the way you promised.
The UUID suggestion is worse than the way it used to be, as in the past you generally required people at the polling place to oversee the voting to ensure your people voted the way they were told/paid to do, while with a receipt available, you can monitor more people with fewer people of your own.
Secondly, the OS on these devices should have been stored into ROM; not only is this a bastard way of ensuring people have to use the manufacturer to upgrade the systems, but it also makes tampering that much more of a pain in the ass.
Thirdly a proprietary data storage should have been used. Preferably one designed so that the voting machines only ever contain a write-only drive, in that it either cannot edit the data, or preferably doesn't even have the necessary hardware to read the data it writes (this would be complicated to get working right, but would be well worth it). This means only the manufacturer would have access to the edit/read connections.
I mean come on, compact flash, seriously. My phone can read flash drives, what were the designers thinking!
Otherewise, you start feeling secure based on your assumptions, like "only we can read these drives" - when maybe your assumption is wrong. Maybe somebody has hacked one machine somewhere and reverse-engineered the connector.
Now you've got an unknown danger out there. Whereas if you're constantly submitting your system to public scrutiny, you'll probably only have known dangers. Which you can fix.
Actually, this isn't true, given properly-implemented crypto. Or, I suppose I should say, it's true only with very low probability.
I wouldn't mind if election results weren't available for a day or two. The ancient Greeks had a completely tamper-proof voting method (and voting was theoretically obligatory). We should likewise be seeking a tamper-proof voting method, whatever that may be. I would also support obligatory voting (with "abstain" as a choice), and media outlets that cover elections like entertainment should be ridiculed.
I think it's because the people who most understand how computers work also understand that no data can be considered trustworthy if somebody else has been in possession of the hardware. Yet governments continue to trust the impossible promises of the people who make voting machines that their machines are secure, despite a continuous stream of demonstrations to the contrary, both intentional and accidental.