The ‘Lawonomics’ of the Secret Ballot July 11, 2008
Posted by Aleks Essex in : Legislation, Privacy , add a commentThe great Freakonom, Steven Levitt, argues that the market price of vote selling is effectively zero because of its essentially insignificant weighting in the outcome.
Of course I agree entirely with Ben Adida’s take: the price is effectively zero because the transaction cannot be verified as having been fulfilled.
The design of E2E receipts completely revolves around this idea, and we spend a lot of time on it. It’s also why E2E voting via the internet is such a hard nut to crack.How can you possibly enforce ballot secrecy in that environment? How can you even enforce it in a polling place?
There is another dimension to it that I wanted to talk about.
If you already have a law against vote selling, do you really need the additional enforcement mechanism (booths, envelopes, etc) at the polling place?
Many other criminal laws do not lean on an additional physical protection measure to prevent the crime; being caught and punished is enough.
There’s no particular physical measure preventing someone from robbing someone of $10 (the minimum bid of the ebay vote selling incident), presumably just the risk of a jail term.
Consider a related situation. In Canada (obviously where there is no HAVA) you can assist someone in voting as long as you sign a statutory declaration that you won’t tell anyone how that person voted. The idea being, yes, you could do it, but you have the legal incentive not to, especially that you’re on record. The Crown probably couldn’t even prove the offense in most situations. And yet this measure seems to be effective enough that no cases come to mind.
You can also (again via a statutory declaration) vote at a polling place without being on the voter list. Presumably you just could go around from poll to poll casting ballots. But it’s ultimately the ‘lawonomics’ — the cost of going to jail weighed against the benefit of stuffing 3 or 4 ballots — that seems to prevent this.
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 II in EVT 2008
Posted by Richard Carback in : Concepts in E2E, Privacy, Security, Voting Events , add a commentWe will be presenting Scantegrity II at the 2008 USENIX/ACCURATE Electronic Voting Technology Workshop. Here’s the abstract of our paper:
Scantegrity II: End-to-End Verifiability for Optical Scan Election Systems using Invisible Ink Confirmation Codes
by David Chaum, Richard Carback, Jeremy Clark, Aleksander Essex, Stefan Popoveniuc, Ronald L. Rivest, Peter Y. A. Ryan, Emily Shen, and Alan T. Sherman
We introduce Scantegrity II, a practical enhancement for optical scan voting systems that achieves increased election integrity through the novel use of confirmation codes
printed on ballots in invisible ink. Voters mark ballots just as in conventional optical scan but using a special pen that develops the invisible ink. Verifiability of election integrity is end-to-end, allowing voters to check that their votes are correctly included (without revealing their votes) and allowing anyone to check that the tally is computed correctly from the included votes. Unlike in the original Scantegrity, dispute resolution neither relies on paper chits nor requires election officials to recover particular ballot forms. Scantegrity II works with either precinct-based or central scan systems. The basic system has been implemented in open-source Java with off-the-shelf printing equipment and has been tested in a small election.An enhancement to Scantegrity II keeps ballot identification and other unique information that is revealed to the voter in the booth from being learned by persons other than the voter. This modification achieves privacy that is essentially equivalent to that of ordinary paper ballot systems, allowing manual counting and recounting of ballots.
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 3 of 3: Surveillance July 10, 2008
Posted by Richard Carback and in : Privacy , 3 commentsBoth part 1 and 2 dealt with interface problems between the voter and a paper ballot, machine, or computer that records her vote. For this last segment, Surveillance, we discuss the ways the voter can be watched to determine her choices. Because the attacker or a device must be present to carry out these attacks, they are generally considered more expensive to carry out than what we have discussed so far.
Using the same strategy as seen in the previous segment, we will start with simple examples of this attack, move on to more elaborate examples, and end our discussion with how you could defend against these attacks. Again, as we’ve already seen, different flavors of these attacks may or may not require voter cooperation to work.
Simple Surveillance
The simplest paper ballot scenario is the following: the local union boss sits in the polling place. You flash your ballot to him as you take it from the booth to the ballot box or scanner. He checks your name off on his list.
Another, that works for DREs as well, is to take a cell phone picture or video of your ballot just before or as you are casting it. If the DRE has an audio interface, you may also be able to hook up an audio recorder and record your vote casting experience on tape.
Another class is the “over the shoulder” attack. The voter or poll workers may or may not have to cooperate for it to work. In some cases you may be able to succeed at a significant distance.
Hacking the Machine
The optical scanner or computer (or even lever machine), by definition, records voter choices. It could be modified to keep a serial record this input. The attacker can record the serialization to each voter by recording the order of who uses the machine, and retrieve the record after the election.
Because of the trail it would leave, this class of attacks is undesirable. However, our current testing practices and laws are such that this information might be public record, as seen in Ohio after the 2006 election.
Going High Tech
Mini wireless spy cameras sell for as low as $70, possibly lower. That is well within the range of affordability. In addition, the relative predictability of how polling places are set up means the cameras could be there days before the election begins. A bag or pen equipped with this technology would have no problem recording voter choices.
The camera does not have to be limited to the visible light spectrum. An infrared or other kind of camera might be much easier to hide. In some cases, your body might not be enough to block its vision.
It may not even need to be a camera. Sensors or microphones in the polling booth might be enough to correlate voter choices. You can recover typed text using audio, it’s not a huge jump to do it for voting.
TEMPEST Attacks
A TEMPEST attack is one which records electronic emanations that reveal information being processed by the computer. A dutch group created a great video showing how this works. Take a look:
My favorite TEMPEST hack, from what I have seen, is an MP3 player for CRT monitors. Just tune your AM radio and enjoy.
Defeating Surveillance
In general, it’s an arms race. As technology progresses and becomes ever more affordable, the situation gets worse. Unless you can strip each voter and scan for optical eye and other types of implants, election officials will eventually lose.
The strategy here should be to drive up costs and take precautions. Make machines that meet the TEMPEST standards. Go to each polling place and do a scan for wireless emissions. Look for cameras and sensors when you set up the polling place. Do not allow voters to take cell phone cameras or bags into the voting booth. As long as it is prohibitively expensive, the laws are harsh, and there is the threat of being caught, it is hopefully not worth 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.
How secret is your secret ballot? Part 2 of 3: Identifying Marks June 26, 2008
Posted by Richard Carback and in : Privacy , 2 commentsAs 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.
How secret is your secret ballot? Part 1 of 3: Pattern Voting June 16, 2008
Posted by Richard Carback and in : Privacy , 6 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.
Political Data Mining Destroying Voter Privacy? January 31, 2008
Posted by Richard Carback in : Privacy , 1 comment so farWired’s Threat level has an interesting post on a story by VanityFair on Aristotle, a political data mining company. The title is “Voter Privacy Is Gone — Get Over It”, but I think that is slightly misleading.
A campaign or other entity could certainly take advantage of (abuse) the information provided by Aristotle. However, the data only shows which way you are likely to vote, not necessarily that you will vote that way. Being allowed to vote (which is what this data is abused to determine) is only half the equation. You also need to be protected from being forced to vote differently than you otherwise would.
I see a problem, but I don’t see how Aristotle or any political data mining company is contributing to it per se. Any entity, private or political, with enough resources is going to be capable of gathering this data. Whether that should be regulated/illegal or not is another matter entirely. I will say that their false claims of buyer verification in the article do not inspire confidence…
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.
Cast as Intended: Feeling vs. Accuracy August 7, 2007
Posted by Aleks Essex in : Privacy, Security, VoComp , add a commentOur colleague Ben Adida offers an interesting recap in his blog of this week’s EVT conference in Boston.
VoComp judge and voting systems researcher Josh Beneloah presented a ballot casting protocol and touched on the issue of usability; the ability to cast a vote the way you intend to. Ben explains Josh “mentioned VoComp to point out that there seems to be a dilemma between verification and usability: can we make it look identical to a DRE?”
This brings up an excellent point, because a point we tried to make at VoComp was that usability includes two aspects;
- accuracy
- feel goodness
and more importantly that one does not necessarily imply the other. But I think people have got it in their heads that something that feels easy to use makes it more accurate. But it doesn’t require much conscious thought to push a button. So what if a DRE is less accurate even if people think it’s easy to use? Isn’t accuracy the more important attribute? Somehow I doubt people feel that way.
Kinda like the 80’s architectural trend of putting little shutters on windows - it doesn’t really do what it’s supposed to, but who cares if it looks cool?
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.
Random Memorandum
Posted by Aleks Essex in : Privacy, Security, VoComp , 1 comment so farI mentioned in a recent post that in talking to a Diebold rep at last month’s VoComp he stated to me that their voting machines store ballots in memory in random order. I had indicated my skepticism to him at the time.
Now I read that in fact the Diebold AccuVote-TSX actually does “record votes in the order in which they are cast, and (it) records the time that each vote is cast.”
I will give the gentleman the benefit of the doubt that he was misinformed.
Alternatively in a cryptographic voting system such as Punchscan, the thing that records your vote only ever sees an encrypted version. So it doesn’t matter if they get stored in order.
UPDATE: Looks like we weren’t the only ones they were telling that lie too.
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.
Identifying Marks Pt. II July 26, 2007
Posted by Aleks Essex, Richard Carback and in : Privacy , 1 comment so farRick’s post reminded me of some thoughts on the same topic. Roughly speaking, identity can be broken into three categories. Say you go to a party and no one knows each other, you could reveal identity like this:
- Veronymous - you’re wearing a name tag
- Pseudonymous - you’re wearing a name tag with some made up name (e.g. Richard Bachman)
- Anonymous - you’re not wearing a name tag
People have a tendency to confuse veronymous with pseudonymous. A serial number on a ballot could be either, depending on how identity is protected.
A Diebold rep says to me “you can’t be putting a serial number on a ballot; it identifies you.”
I counter by saying the order ballots get stored in a DRE memory card can identify you too.
He replies “but they’re stored in random order.” Whoa now, don’t be taking the cryptographer’s lord’s name in vein. “Random” is a holy word.
People like to throw this word around, but this is a special word for people in the world of information security. So special in fact, that experts argue it doesn’t even exist. People often (erroneously) use it in the stead of “pseudo-random.” I won’t get into why this is (save it for another post), but…
In the end, ye who controls the entropy source knows the order the ballots get stored in memory. At which point you have pseudonymous identification (the “first” voter, the “second…”). If the poll worker was kind enough to provide you with an order that people signed in, you now have veronymous identification.
Not as anonymous as the average person might think. Yet they seem comfortable using it.
And at the same time carry on about serial numbers on ballots.
Well… all’s fair is fair: you can’t have it both ways. I argue that a ballot serial number is, at worst, equivalent to a DRE in terms of identifiability.
But in the end, there really is no way to be truly anonymous on a ballot. There will always be some fingerprint; human or electronic.
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.
Identifying Marks
Posted by Richard Carback and in : Privacy , add a commentPrivacy on ballots is tricky…Digital systems suffer from tempest attacks, and a well hidden camera, fingerprint scanner, or a modified optical scanner could all identify a voter . A voter with a cell phone camera can very convincingly sell their vote, regardless of the system. I imagine if I spent some time writing them all down, I could easily come up with dozens of ways to spy on voters or have them spy on themselves to determine how they voted, and almost all of them would be system independent and hard to detect or prevent. This situation is only going to get worse as technology gets smaller and cheaper.
People, particularly the hand counting crowd, also worry about having identifying marks on ballots. A lot of people confuse identifying with unique and mistakenly believe this means there should not be ballot id’s or similar writings on ballots. In reality, it really depends on how that unique mark is used, and if there’s no relationship made between mark and voter then it would not be an identifying mark.
One thing people may not realize is that there are a lot of things that could be considered identifying marks that they would not have thought of at first look. My favorite example must be write-ins, which, in the world of handwriting recognition, would be identifying. Even if you assume the recognition wasn’t good enough to count, you still might have voter’s identifying themselves with unique write-in candidates (e.g. themselves, or something a coercer tells them to put). So, the way write-ins are handled are important, and I think Ben has come up with a good way to handle write-ins in Punchscan (PS).
Another good identifying mark example is marking your choices in a unique way, perhaps by adding a little tail on the optical scan circle, or (in DRE VVPAT) waiting for the confirm printout and canceling with a certain ballot choice and then changing choices to match what you want to show you voted. I think the most interesting one is the “Italian Attack”, and that is, if there are enough races on the ballot, you could identify yourself by using the races as bits, and choose the race you want to show how you voted on (9 races could conceivably give you 8 bits, more if you had IRV or other election rules in place). This one is important because the regular marks are identifying so long as there’s no process to disassociate the races from each other (by cutting them up, I guess?, we effectively do something similar to that to prevent it in Punchscan).
Not permitting weird marks on ballots presents problems, as it makes it really easy to spoil ballots. All you need to do is find a vote you don’t like and add an illegal mark. So I caution people to take a deeper look into the system before proposing identifying mark rules, as the cure might be worse than the disease, in this case. In PS, we avoid this problem by only showing a reproduction that shows what marks were interpreted, this might be the way to go for more traditional systems.
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.