From CryptoDox, The Online Encyclopedia on Cryptography and Information Security
A vote is an expression of the preference of a voter. Votes are used in voting systems to choose between a number of options.
A voting system describes how voters cast their votes, and how the votes are counted to discover which option is the preferred option. "Voting theory" is the study of voting systems. Voting theory is a multidisciplinary field overlapping political science, economics, and mathematics.
People are often surprised when they first hear about the variety of voting systems.
Voting theory and cryptology have many things in common.
voting when there are 2 options
The voting theory when there are 2 exclusive options is fairly simple: Whichever option gets more votes is the winner.
The tricky bit is preventing vote fraud: How do we know the totals reported in the paper are accurate? (How do we know there was no ballot stuffing, or systematically ignored votes, or illegally modified votes?) And even if the totals are accurate, how do we keep people from being coerced into voting for an option they didn't really want?
Too often people try to maliciously break the system:
The U.N. "Universal Declaration of Human Rights" calls for "The will of the people shall be the basis of the authority of government; this will shall be expressed in periodic and genuine elections which shall be by universal and equal suffrage and shall be held by secret vote or by equivalent free voting procedures.".
The U.N. "International Covenant on Civil and Political Rights" requires that "Every citizen shall have the right and the opportunity, ... To vote and to be elected at genuine periodic elections which shall be by universal and equal suffrage and shall be held by secret ballot, guaranteeing the free expression of the will of the electors;".
Because of the above requirements, some voting systems encrypt votes and use other cryptographic protocols for secrecy and authentication.
"I am adamantly opposed to the use of fully electronic or Internet-based systems for use in anonymous balloting and vote tabulation applications. ... At the present time, it is my strong recommendation that all election officials REFRAIN from procuring ANY system that does not provide an indisputable, voter verified paper ballot. ... I have also recommended (and continue to recommend) that municipalities ONLY purchase the opscan + ballot-marking systems." ( http://notablesoftware.com/evote.html ) -- Rebecca Mercuri, Ph.D., who created the "Voter Verified Balloting" concept.
Cryptographer Bruce Schneier wrote several essays about electronic voting machines:
and one brief note about a highly secure paper-based election process:
In addition to people maliciously breaking the system, there are also user-interface issues. Some voting machines are unnecessarily difficult or impossible to operate when a voter is in a wheelchair or has poor vision. Some ballots are unnecessarily confusing. Some polling places silently discard the entire ballot when the voter has made some innocent mistake ("overvoting" or "undervoting") on any part of it. Some polling places have policies that make it unnecessarily difficult for a person to change his vote when he realizes he has made an innocent mistake. Some polling places have unnecessarily complicated and confusing policies, or inadequately train the poll workers, that make it too easy for a poll worker to make an innocent mistake. There are other things about a polling place that may discourage a voter from voting at all, or rush the voter through and increase the chance of making innocent mistakes.
Are these user-interface mistakes biased towards a particular candidate? Yes, when both (a) counties expected to vote against that candidate have lots of user-interface problems, reducing the number of votes against that candidate, and also (b) counties expected to vote for that candidate have fewer user-interface problems.
And even when none of these problems actually occur, the loser often suspects that one or more of these problems occurred. How can we accurately detect that a problem occurred, with enough detail to fix the problem or at least make sure it doesn't happen again? How do we convince everyone, even the loser, when a fair and honest vote was conducted?
voting when there are more than 2 options
In addition to all the issues with the 2-option case, there are some other subtle issues when there are more than 2 options. There is widespread disagreement on the correct way to pick the winner, or even if there should be only one winner.
In situations where one candidate is preferred by more than half the voters, that candidate will win no matter which of these voting systems is in use. However, these systems may give very different results in more typical situations where the vote is more evenly split among the top few candidates.
There are a variety of voting systems for picking a single winner:
Others suggest there should be no single winner:
In addition to "voting theory" issues, user interface issues become more critical when many options are available, because it is now much easier for a voter to get off-by-one and mark a candidate other than the intended candidate.
testing voting machines
How do you know a voting machine really does work?
With any other kind of machine, the way I avoid buying machines that don't work is testing to make sure it does work. Sometimes I test it out myself. Other times I rely on some independent, unbiased person to do the testing. Or I rely on several independent people, biased in a variety of ways, to do their own tests.
For a simple machine like a faucet, it's pretty easy to inspect from the outside -- when I move the knob, water comes out only when it's supposed to.
But when you get software involved, it's almost impossible to inspect from the outside. It function perfectly when you operate the controls in a normal manner, but how do you know the Konami Code doesn't trigger a hidden subroutine?
How do you test the system ?
end-to-end auditable voting systems
Until recently, it was believed to be impossible for a voting protocol to satisfy 2 seemingly contradictory requirements:
Until recently, all voting protocols either satisfied only the first requirement (such as "everyone in favor, hold up your hands"), or only the second requirement ("take this ballot, secretly mark it, and put it in this locked ballot box.").
Recently, voting protocols have been invented that satisfy both requirements. Such protocols are called "end-to-end auditable voting systems" or "end-to-end voting protocols" or "cryptographic voting protocol".
end-to-end auditable voting systems myth #1: They are too complicated to use.
Fact: Like most systems, end-to-end auditable voting systems are fairly easy to use, but more complicated to explain exactly how they work. Do you know how a optical-scan machine works? Do you know how the Reed-Solomon codes in a compact disk player work?
This page is oriented towards the sort of detail-oriented people who want to know how it works, in detail. Please don't mis-use this detailed explanation -- or my poor explaining skills -- for confirmation of the myth that end-to-end auditable voting systems are complicated to use or hard to understand.
FIXME: fill in details of the end-to-end auditable voting systems
end-to-end voting protocols include:
FIXME: add the year each one was invented
voting system hardware
Testing voting system hardware: