Vote Selling: Harder Than You Would Think July 4, 2008
Posted by Richard Carback in : Voting Policy , 1 comment so farAccording to one Minnesota voter’s story:
A college student claimed it was all a joke when he put his vote in this fall’s presidential election up for sale on the Web auction site eBay. But prosecutors didn’t see the humor.
Back in 2000 there was a website specifically for selling votes, but that was taken down fairly quickly, too. Surely, a widespread black market off-shore shop might be possible, but succeeding with this sort of thing usually requires a confidential and limited approach.
The vote selling issue has always been interesting to me. Obviously, it should not possible to make a proof of sale, because that opens the system up to other forms of coercion. However, if you can’t confirm compliance, is there anything to worry about?
My opinion is that these laws should still exist, for two reasons. First, privacy is really hard to guarantee with a voting system, and you can still get lesser forms of “proof” (e.g. cellphone picture of ballot–can be faked but still might be enough). Second, I (weakly) disagree with the major argument that I have heard for vote selling, which is that candidates are buying votes with their positions and promises anyway. Otherwise non-voting voters affect the process for more interested voters. I think that anything that makes a voter change his vote other than the opinion of the candidate is probably wrong.
I am still writing part 3 of the secret ballot series, and I should be finished soon. Have a happy 4th of July!
The content of posts to the Punchscan blog belong to the author and do not necessarily reflect the thoughts, feelings, or opinions of the Punchscan voting project.
Semiprime Time
Posted by Aleks Essex in : Voting Goals, Voting Policy , add a commentComputer scientist and election technology analyst Avi Rubin touched on some familiar themes in an interview yesterday:
There are cryptographic techniques that can be used to achieve software independence so that even if there’s a bug in the software, you’ll detect if there’s a problem. But those are not ready for prime time in my opinion.
Though I’m generally more optimistic about this, it’s a fair statement, especially since there hasn’t yet been any definitive event to have changed many minds. The question I put to you, fair reader, is how do we recognize when the time has come? It would seem, as in Rubin’s case, a conservative assessment of the situation would best allow one to avoid taking a premature position on the matter.
I suppose there are only two factors to take into account. One is a stable convergence of the technology with a consistent, set of security ideals. However this by itself may be too abstract to be appreciated by the general public.
Naturally for me as an engineer, the defining characteristic of a technology entering “prime time” is its first successful deployment in the field.
But perhaps we can never say for certain the time has come, only that now is as good a time as any.
The content of posts to the Punchscan blog belong to the author and do not necessarily reflect the thoughts, feelings, or opinions of the Punchscan voting project.
How secret is your secret ballot? Part 2 of 3: Identifying Marks June 26, 2008
Posted by Richard Carback in : Privacy , 1 comment so farAs explained in part 1, there are numerous ways for a voter to violate the principle of a secret ballot. In this post we discuss identifying marks (IMs). Such marks occupy a middle ground because the voter may or may not knowingly be giving away his identity.
Many states make IMs on ballots illegal but they rarely give a clear definition. In some cases it means serial numbers. In others it means writing outside of acceptable spaces. For our purposes, the definition of an IM is anything on the ballot that could potentially identify a voter after her ballot has been cast. As far as I know, only a small subset of such IMs could be considered illegal under most laws.
Simple Identifying Marks
Simple IMs are obvious and generally require voter complicity. These include marks that would generally be considered illegal under an IM law, such as arbitrarily signing your name or writing your address on the ballot.
Because they are legal, write-in candidate slots are the worst kind of simple IM. Voter’s can easily identify their ballots by voting for an agreed upon candidate. It might also be possible to identify voters through a handwriting recognition program (unlikely at this point, but possible in the future).
Serial numbers can also be an IM. If the voter knows the serial number, she can write it down and tell people what it is. This is easy to fix, however, by making the serial number unreadable to the voter, or adding said serial numbers after the voter casts her vote. Some places have serial numbers on ballots that are removed when casting a ballot.
Covert Identifying Marks With Voter Cooperation
There are endless possibilities for IMs when the voter cooperates. A voter could mark her ballot in a specific way. In an optical scan system the voter could make little flags on the circled choices. Since some people will do this accidentally (but not in a specific pattern), it is hard to detect. Some optical scan systems make voters draw an arrow, and a voter could do the same thing by drawing predictably crooked arrows.
Marking patterns are not the only way to make identifying marks. Voters could make creases in the paper. The coercer could give the voter a particular marking device (and it could be invisible except under blacklight). The other end of the pen used for marking could make a barely visible indentation in the paper. A particular colored grease could be put on the voter’s hands as they are using the ballot. The voter could write something on the other side of the ballot that is not checked by the scanner.
IMs without Voter Cooperation
As in the write-ins example, it is possible to identify voter’s choices without their knowledge. The attack I am most familiar with can be done with lever machines and grease. Levers for the candidates are marked with various colors of grease or ink. Voter’s who vote for those candidates must pull on the levers, and they will unwittingly get the grease on their hands. As the voter leaves the polling place, the attacker shakes her hand, and he can check the transfer to see how the voter voted.
The opposite of the grease attack is also possible. A voter could shake hands with the attacker before she votes, and the attacker could identify the ballot after the election by checking for grease. There’s also genetic material and finger prints on the ballot. A sophisticated attacker could scan all the ballots and identify voters if he knew their DNA or fingerprints (again, this is something that is probably not possible now, but might be in the future).
On absentee ballots, voters are required to sign the envelope that contains the ballot. Pressure on the envelope could transfer the signature to the ballot. Of course, if an attacker controls the receipt of the absentee ballots, he can get the identity anyway. Likewise, if an attacker has a poll worker on his side, the poll worker could put identifying marks on the ballot during casting time by helping the voter put the ballot into the ballot box.
Defeating IM Attacks
Unfortunately, there are no easy answers here for traditional paper systems, and as technology gets more powerful the situation gets worse. You can’t detect all IMs before casting without violating voter privacy, but you might be able to get a machine to do it in a limited way.
One way to prevent IM would be to create a machine that makes a pristine copy of the ballot and destroys the other copy. Only the valid marks would be transferred to the new copy, and any identifying marks would not. The problem here, though, is that voters might not always check the copy very carefully before casting their ballots.
As with PV, DREs mostly avoid this problem, because the voter doesn’t have the opportunity to make IMs. However, the logging might still make it possible, particularly if it records interaction with the machine (e.g. how the voter moves through the ballot, or when the voter marks and unmarks candidates). Even simply storing the choices in order could identify voter choices if you correlated it with poll book data, and I remember a story of this being done successfully in Ohio. You might also be able to do the grease attack, if you could make the grease undetectable. As we’ll see in part 3, surveillance is much easier on DREs, too.
E2E systems, again, do a great job solving these problems. That’s because the ballot you submit, the receipt, is public knowledge. That you put identifying information on it matters a lot less, because a copy is made without those marks and posted online then you walk out with what you used to vote.
Stay tuned for part 3, surveillance, next week.
Special thanks to Taral for proofing this week.
The content of posts to the Punchscan blog belong to the author and do not necessarily reflect the thoughts, feelings, or opinions of the Punchscan voting project.
Scantegrity in IEEE S&P June 20, 2008
Posted by Richard Carback in : Misc , add a commentAn article about the first version of Scantegrity was published in the May/June issue of IEEE Security and Privacy Magazine.
Scantegrity II will appear at EVT at the end of next month.
The content of posts to the Punchscan blog belong to the author and do not necessarily reflect the thoughts, feelings, or opinions of the Punchscan voting project.
How secret is your secret ballot? Part 1 of 3: Pattern Voting June 16, 2008
Posted by Richard Carback in : Privacy , 4 commentsWe rely on the secret ballot to prevent vote selling and voter intimidation, but the “secret” ballot isn’t always very secret. In this post I will discuss a problem that very few people know about or understand—one that allows us to give ourselves away using the very choices we make!
The problem is called pattern voting (PV), and it occurs when there are enough choices on a ballot to allow voters to identify themselves using a predetermined voting pattern. Whether or not this is possible is a function of the the number of unique choices on the ballot, the number of voters, and how ballots are counted.
The simplest PV example is an election with one voter. That voter identifies her choices simply by voting, but more realistic scenarios are simple to construct. Consider an election with 10 voters and 3 races with 2 candidates each. Assuming a two-party system, let us say the choices for each race are the democrat (D), republican(R), or no vote (N). If voters follow the rules, this situation leads to the following 27 possible voting patterns:
DDD, DDR, DDN, DRD, DRR, DRN, DND, DNR, DNN, RDD, RDR, RDN, RRD, RRR, RRN, RND, RNR, RNN, NDD, NDR, NDN, NRD, NRR, NRN, NND, NNR, NNN
This is simply a permutation with repetition (3^3). To identify a voter, all that is necessary is to agree before the election on an unlikely voting combination. Up to 9 voters could vote for the same candidate in a select race using unique patterns between them.
As a coercer or vote buyer, all I need to do is give the voter a unique combination (e.g. DNR), and look for that pattern in the ballots during counting or whenever they become publicly available. The voter can either vote the way I told her, guaranteeing that unique pattern in the output, or vote the way she wants hoping the pattern will appear anyway.
The chance of the latter happening is pretty low given the number of voters. Assuming each voter votes randomly, there is less than a 30% ((1-(26/27)^9), see the birthday paradox) chance that a random voter will share the same vote as the coerced voter.
The worst part about this situation is that what I gave above is a best case scenario. Chances decrease if the other voters do not vote randomly, are also being coerced, or do not follow the rules. Unless there’s a particularly bad or good candidate, the likely patterns are straight party (DDD or RRR).
Pattern Voting on a Real Ballot
To make this seem more real, I decided to take Maryland’s 2006 sample ballot I got and calculate the number of unique patterns you could make on it. Note that Maryland used DREs w/out VVPAT, so this is not directly applicable, but it does point out a potential problem when we switch back to optical scan.
There are 30 contests on this ballot. 16 of them have 2 options or 3 choices (yes/no/none), yielding 3^16 patterns. 3 of the races are “choose x” elections, for which the logic is explained in the next section. The rest of the races are detailed below (assuming voters follow the rules):
- Governor: 6 patterns
- Comptroller: 4
- AG: 4
- US Senator: 5
- District 3 Congressional Rep: 5
- State Senator: 4
- House of Delegates (vote for 2 of 6): C(6, 2)+C(6,1)+C(6,0) = 15+6+1 = 22
- County Executive: 4
- County Council District 1: 4
- Circuit Court Judge (vote for 4 of 8): C(8, 4)+C(8,3)+C(8,2)+C(8,1)+C(8,0) = 70 + 56 + 28 + 8 + 1 = 163
- States Attorney: 4
- Circuit Court Clerk: 4
- Judge of the Orphans Court (vote for 3 of 9): C(9,3)+C(9,2)+C(9,1)+C(9,0) = 84 + 36 + 9 + 1 = 130
- Sheriff: 4
To get the total number of patterns, we multiply it all together:
3^16*6*4*4*5*5*4*22*4*4*163*4*4*130*4 = 1.97271752×10^20 = 197,271,752,498,675,712,000
There are only 5,615,727 people in Maryland, and fewer in the county. Not all of these people are registered to vote. If you counted at each polling place, the numbers would be noticeably worse. Also remember that this is a conservative number. You could easily sell over half the ballot and have plenty of patterns left over!
Calculating Your Ballot’s Secrecy
It’s not too hard. Each race has a certain number of choices, and all you have to do is calculate these numbers and multiply them together. If you want to see the number of unique choices after targeting a specific race, for 1 choice election methods you remove that race from the multiplication. For rank choices, n out of m, or range/approval voting you simply remove the candidate you want to win from the calculation.
Below is a guide to help you figure out how many unique patterns appear on your ballot. n is the number of candidates in the election, r is the range or number of choices you can make.
- Choose 1: n+1
- Choose r: sum(C(n,r), 0, r) — this can express choose 1, too.
- Approval: 2^n
- Range: (r+1)^n — this can also express approval
- Ranked Choice: P(n,r) ==> n!/(n-r)!
Of course, this is assuming the voters follow the rules. Otherwise, the answer is 2^(number of dots) (because each dot can either be chosen or not). You can see wikipedia’s combinatorics page for more.
Fighting the Pattern Vote
The bad news is that few people pay attention to this problem, but the good news is that it can be mitigated. To defeat pattern voting, you have to reduce the number of choices that are associated with each other. Except for Ranked Choice, which is special, the key is treating each race separately, and in some election methods you need to treat each candidate separately. This is (sometimes) easier said than done.
In paper ballot systems you have a few choices. You could keep the ballots secret, and use only trusted counters (machines or people). You could have one ballot per race. You could also have a machine that cuts ballots after they are used. DREs w/ VVPAT would need a different mechanism than a paper rolltape to work. Because DREs w/out VVPAT can report results in aggregate, they avoid the PV problem.
As far as I know, every E2E system can handle PV, and some can handle PV with ranked choice. My colleague Stefan Popoveniuc wrote a paper about how this is accomplished in Punchscan and Scantegrity.
The problem with ranked choice is that you can’t hide the relationship between rankings. You need to know it to do the counting. In this scenario, the only choice for traditional systems is secret counting. Digital systems have the possibility of zero knowledge proofs to prove that the counting was correct, however.
That’s it for part 1 of this series. Part 2 will be on the effect of identifying marks (including write-ins and serial numbers), Part 3 will be on surveillance.
Special thanks to my proof readers: Taral, Emily, Jeremy, Scott, and Ben.
The content of posts to the Punchscan blog belong to the author and do not necessarily reflect the thoughts, feelings, or opinions of the Punchscan voting project.
Scantegrity: Choice in audit trails June 7, 2008
Posted by Aleks Essex in : Concepts in E2E, Voting Goals , add a commentWith respect to Scantegrity and our design objectives, Flaherty has it wrong:
A system that started as an attempt at secure voting without paper ballots has, ironically, evolved into a system designed for compatibility with existing paper ballot voting systems.
If he were to live in the shoes of a voting system designer for one day he would learn an interesting lesson: the barrier to entry for new paradigms is so vast, and onus on voters to learn anything new is so low, the only way to present truly new ideas, regrettably, seems to be to allow some people to believe they’re not new ideas at all.
We didn’t integrate a paper trail into Scantegrity because we necessarily think it adds security. But the pride of the 1850’s still gives folks comfort, and we’re not out to take that away from them.
What we’ve done, I think quite reasonably, gives people who want to verify an election a choice: paper trail verification if it floats your boat, and for those who want something more compelling, a new approach to proof of election integrity called E2E.
The fact is, Scantegrity incorporates both “old” and “new” into one system, which we felt was a vital direction, and I’m not bashful about telling you a lot of work went into it.
The content of posts to the Punchscan blog belong to the author and do not necessarily reflect the thoughts, feelings, or opinions of the Punchscan voting project.
Response to an Ill-Informed Post at VoteTrustUSA June 5, 2008
Posted by Richard Carback in : Misc , add a commentA recent post at VoteTrustUSA, entitled Electronic Verification for E-voting: A Dead End for Voter Confidence, contains misleading and false information. While such pieces are commonplace in the blogosphere, this particular piece is notable because it has enough references to seem plausible. The author also references our work, which makes a response inevitable.
In an effort to be brief, I will address the systemic errors in roughly the order they appear and avoid getting into unnecessary analysis and discussion. This is by no means a comprehensive refutation of everything wrong with the post, just the higher level ideas.
Invalid comparison. From the title, we are lead to believe that the post will discuss the topic of “electronic verification.” That term means E2E based on the link to our work and discussion of cryptographic voting protocols. However, the topic is inconsistent with the very first sentence of the post:
Paperless electronic voting is in retreat, its popularity done in by disturbing security reviews of current e-voting systems and significant voter concern about the integrity of elections.
This sentence is equating the existing paperless DRE voting systems with E2E, but clearly they cannot be the same. E2E, or electronic verification, is a set of methods that guarantee certain properties. In other words, E2E is technology neutral and not specific to paperless DREs.
The idea to compare and contrast E2E with specific technology is flawed. Systems based on E2E methods derive their properties from the underlying protocols and not the specific hardware. Since they do not correspond, it is not possible to usefully compare them unless you are comparing a specific implementation using such technology, which the article fails to do.
My guess is that the author mistakenly believes that an E2E based system is simply a piece of software put on a DRE. The word “paperless” supports this conclusion, because every proposed E2E based system for poll site voting that I have seen uses paper (or transparency sheets) in some way.
Confusion between use of a cryptographic protocol designed for voting and one for secure key exchange. The “bullet proof system” story referenced is about the use of quantum cryptography. This is not an E2E based system, so the comparison does not apply here either outside of the notion that it could have security problems. This is about as useful as saying “elections can have fraud.”
The effect of security problems are in the details, and E2E based systems show pretty graceful failure in the face of unforeseen flaws. What we have found is that the concepts in E2E are somewhat independent of the cryptographic algorithms used, and some newer E2E systems do not use cryptography.
E-commerce misconception. The post states that “it is necessary to compare electronic voting to electronic commerce.” Unfortunately, the post provides a rather narrow view of e-commerce, equating it only with non-anonymous transactions and glossing over many topics like anonymous digital cash. It is also not very clear why such a comparison is necessary or what it proves outside of the problem being difficult.
Improper assertion of the motivation behind Scantegrity. The 6th paragraph cites our work on Scantegrity, which adds E2E security properties to optical scan systems. Unfortunately, it is depicted as a descendant of a paperless system, but this is false as Punchscan uses a paper ballot. Apparently the author’s definition of paper ballot is not “a piece of paper the voter uses to vote” but “a hand readable piece of paper available after the voter votes.”
Regardless of the definition of paper ballot, the implication is that the paper ballot is necessary for some sort of security property. The reality of the situation is that we really, really care about having secure elections as soon as possible. An add-on is, in my view, the best way to meet that goal because it will work with existing election equipment without modification and allows us to add security properties to systems that are already in use. Certification becomes clear and simple, and a voting system does not have to be created around it. The path to adoption is substantially cleaner and cheaper.
An unintended consequence of this choice is that the people who think paper provides certain security features find it less objectionable. The irony is that Scantegrity is a great example of what E2E can do better than paper, and in that sense it is particularly damning to someone saying that paper must be used, especially if his argument is against the use of E2E. Paper certainly can be useful, but it is more a matter of convenience than security.
Confusion between properties of a method and certification of an implementation. The post asks “Is the certification process for voting equipment up to the challenge of ensuring that electronic verification can secure an election?” Again, E2E is a method, and not a piece of equipment. E2E based systems are created to be secure assuming the public has full knowledge of their inner workings. They can be reviewed by any interested party, and not simply through a closed certification process. E2E methods are also designed to resist equipment failure. Whether a particular E2E method works is something you could verify once. After that you simply verify that the implementation adheres to the prescribed method and addresses the other certification requirements.
Ignorance of E2E requirements on voters. The post states:
Cryptographic verification requires that voters use a code to avoid compromising the secrecy of the ballot, and understanding the mathematics of the coding system would require substantial training on the part of voters.
This is simply false. While the privacy preserving receipt that the voter receives might have a code on it, this is not always the case and there is no requirement for the voter to understand it. In some cases the E2E parts can be ignored by many of the voters if they are uninterested in using it. There is no training involved outside of pointing out what it is and maybe how to check if there are no clear directions on the receipt. Anything more than a poster and maybe a handout would probably be overkill.
The post also seems to ignore the feature that the privacy preserving receipts let each voter check that his or her ballot was actually counted and represented in the final tally. Even if voters understood only how to use this receipt, this is much more feedback than what they currently receive.
The author also fails to understand that it is possible for anyone to take the receipt data and verify that the receipts were correctly counted. This capability is in stark contrast to what we have now, where you have to stay the whole day and watch the counting afterward. Instead, you are only limited by your knowledge. If you couldn’t do it on your own, you could get someone you trust to do it for you. You, by yourself—sitting in your jammies the next morning—could do it for the whole state, or even the whole country, in no time at all. This is a lot different than taking several days off work and having a limited ability to check the goings on of one polling place.
The end of the article is a quote from Bruce Schneier that doesn’t make a whole lot of sense in the context the author uses it:
Building a secure cryptographic system is easy to do badly, and very difficult to do well. Unfortunately, most people can’t tell the difference.
The use of the quote seems to imply that since it is hard to make cryptographic systems, we should not try. I find the implication absurd—think of all the other things we shouldn’t be doing since they’re hard…What ever happened to that “can-do” american attitude? JFK once said:
We choose to go to the moon in this decade and do the other things, not because they are easy, but because they are hard, because that goal will serve to organize and measure the best of our energies and skills, because that challenge is one that we are willing to accept, one we are unwilling to postpone, and one which we intend to win, and the others, too.
Voting is a far cry from going to the moon, but it is an important and difficult problem.
The content of posts to the Punchscan blog belong to the author and do not necessarily reflect the thoughts, feelings, or opinions of the Punchscan voting project.
Scantegrity Poster May 4, 2008
Posted by Richard Carback in : Misc , add a commentI recently created a poster about Scantegrity that may be of interest to those wishing to learn more about it.
The poster won first place at a competition at the annual UMBC CSEE department research day.
The content of posts to the Punchscan blog belong to the author and do not necessarily reflect the thoughts, feelings, or opinions of the Punchscan voting project.
Wordpress Update Glitch May 2, 2008
Posted by Richard Carback in : Misc , add a commentI upgraded the blog recently, and the feed URL went from:
http://punchscan.org/blog/?feed=rss2
To
http://punchscan.org/blog/feed/
This caused an RSS feed error on the front page. It is fixed now. This will probably break everyone’s RSS feed reader (although google reader is still working for me). I apologize for the inconvenience.
The content of posts to the Punchscan blog belong to the author and do not necessarily reflect the thoughts, feelings, or opinions of the Punchscan voting project.
Rivest announces Scantegrity collaboration in RSA08 keynote
Posted by Aleks Essex in : Voting Events, Voting Policy , add a commentIn the cryptographer’s panel discussion last month at RSA 2008, Ron Rivest took the opportunity to relate his recent work in voting and announced his collaboration with David Chaum and the Punchscan team in an upcoming paper presenting Scantegrity II (invisible ink). Rivest goes on to discuss the ongoing EAC VVSG comment period as well as the notion of ’software independence’ in voting machines.
Watch the video of his discussion of voting HERE beginning at 17′:00″. This video also contains excellent discussion from crypto all-stars Diffie, Hellman and Shamir.
In related news you’ll be able to read about Scantegrity (aka “Scantegrity I”) in the upcoming May/June edition of IEEE Security and Privacy Magazine
The content of posts to the Punchscan blog belong to the author and do not necessarily reflect the thoughts, feelings, or opinions of the Punchscan voting project.