Voter verifiability and Public verifiability
2010-11-07 16 Comments
A few people have asked about how a voter can be sure that her vote has been counted correctly just because she verifies that her vote has made it correctly into the batch of counted votes when she has no insight into the various stages of decryption and she has not got the expertise to verify those later stages herself.
The key is the combination of Voter verifiability and something called Public verifiability. A system is voter verifiable if an individual voter can verify that her vote has made it correctly into the batch of votes that is subsequently counted. A system is publicly verifiable if the public (in some form that I discuss below) can verify that all the votes (verified by the voters) are decrypted (and thus anonymised) and counted correctly.
Voter verifiability + Public verifiability = End-to-end verifiability
If a voter can verify the correct inclusion of her vote in the batch of votes that the public can then verify is correctly decrypted and then counted, then the system is end-to-end verifiable.
So how does the public verify that votes are decrypted and counted correctly?
If we skip the detail about exactly how the votes are decrypted (and thus anonymised) then we can more easily describe in general terms how the public does this verification. To start with, all the encrypted votes cast by the voters are collected in a database. Then all of those votes are downloaded by the first trusted party who performs a decryption step and a mix. The decryption that this trusted party is only one of many such decryptions that must be done by many different trusted parties before the votes are completely decrypted and thus readable. When the first trusted party is done then the output is published online for all to see. The second trusted party downloads all the data and does the same thing as the first. After a while, all trusted parties have performed their duties and the votes are decrypted and can be counted.
The trusted parties have key shares that together make up a secret key. Because they all have key shares, there is no central point where this key is known and no single organisation which knows the secret key. Only if all of the trusted parties work together can they decrypt the votes and because this decryption is done serially in a distributed fashion, there is no single server where the election secret can be revealed.
The public key is, as its name signals, made public – that is to say, it is published. This means that if I want to verify the work done by the trusted parties, I can download all the data from the decryption and mixing rounds done by the trusted parties and then use the public key to verify it. The work that the trusted parties do is done using the private key shares, but I can verify their work with the public key, which I know. So in order to verify the election data, I do not need to know the private key.
Doing this verification is, as you can imagine, quite tricky. You need to know how to program and you need to understand the technical specifications that you have to follow. Therefore, we envisage that all the various political parties, the government, Non-Government Organisations (NGOs), the United Nations, the ODIHR, government of other countries in the region, newspapers and other media outlets and any interested organisation or individual will nominate one or more experts to perform the public verifiability. This means that if I don’t trust the expert nominated by my political party then perhaps I do trust the expert nominated by the newspaper I subscribe to or the workers’ union I belong to. If I really do not trust any one of the experts available then I can learn a programming language (if I don’t already know one) and read up on the technical specifications that are published and then I can, on my own computer, write a program that verifies the election data.
So to sum up.
Each voter is able to verify that her vote is included correctly in the tally and the public is able to verify that all the votes are counted correctly, thus making the system completely verifiable.
About David Bismark
David Bismark on Verifiable Electronic Voting 
Still too complicated for me to understand.
Can you make a video, comic, or something similar?
A picture is more than thousand words.
There exists a video of my talk at TEDxStockholm in 2009 you YouTube. On pretavoter.com there is also a video about the voting process.
You said, “no hacker can break in and change your vote because then it won’t match your receipt”.
Let us say that a hacker does break in, and changes the vote and makes it so that it won’t match. My question is, how to you contest such an occurance at law and still remain anonymous? Presumably you would have to say “I voted this way and here is the proof” and by having that paper receipt in your hand with the way you really voted visually puts you with your vote, thus removing your anonymity.
If this one problem were answered, I might be convinced. Otherwise I think we must return to paper ballots, and a verifiable counting process with counters that are chosen like we choose juries, complete with voi dur. And we should take a minimum of one week to count them just to piss off the media, and we should film it (with real film) and we should gaurd it. And they should be sequestered. And people who interfere or defraud should be deterred by uniformly applied stiff prison sentences. Counters should be paid quite well. And it should all be paid for by raising taxes on everyone.
Until we do these kinds of things we will not be taking voting seriously and we will continue to get what we have always gotten.
But I want to know what you think about the loss of anonymity when contesting.
It is indeed very important that you can challenge the election without revealing how you have voted. When you verify your vote in Prêt à Voter, you simply check that the marks that you made on your vote, that are shown on the encrypted receipt you hold in paper form, are the same (and in the same positions) on the online version of the encrypted vote. If someone tries to change your vote, the marks will be in different positions. Because the encrypted receipt that you get at the time of voting is digitally signed, you can use this receipt to challenge the election without revealing how you have voted.
David, loved your TED talk on fraud-free e-voting.
Question for you.
With a system that allows the individual to verify how they voted, how do you fight vote buying schemes?
The encrypted receipt does not reveal how you have voted and neither does verifying your vote.
I think your e-voting idea is marvelous, but you mentioned your system is unbreakable, no cracker can break in. I understand some Cryptography, I know only the One-time Pad encryption is unbreakable, if you use the One-time Pad encryption, it takes too much manpower to do it. So you choose the RSA encryptiony, am I right?
Which crypto system you use may vary – the current version of Prêt à Voter uses ElGamal. You are quite right that no crypto system is unbreakable – and there are two things I would like to say about this:
(a) For the election to be VERIFIABLE we only need to be certain that the key length of the crypto system we are using is not broken TODAY.
(b) For SECRECY the key length of the crypto systems must never be broken – and this has given rise to a property called Everlasting Privacy, which is something the research community is working hard at right now.
David why not do both. Leave the physically marked ballot with the election officials so that in the case of a recount they are there to be recounted? But give the voter the encrypted receipt so that they can go on line as you say and check that the vote stored is the same as how the voter voted.
No vote is verifiable if the physical ballots don’t exist and I’m uncomfortable with the ballots being taken out of the control of the election officials. Or to put it another way I am uncomfortable with anyone off the street being able to come in and present a piece of paper and claim that it is an official ballot.
One question: How does the voter go on line and verify their vote? Is it done by scanning the encrypted bar code somehow? Or is it done with a PIN number? How exactly? Thanks. Very interesting and definitely a step toward a better system than pure electronic voting.
The voter simply types in the serial nuber of her receipt into the web browser form and the encrypted vote comes up on screen. As all the information on the website is encrypted anyone can look at all the votes that are on there, they are not secret. The system fully supports paper being left in a ballot box – perhaps some constituencies would like to do it that way for a few elections until they are all happy with the system. The verification that the voters do makes paper in a ballot box superflous though.
I find this system interesting. Please don’t take my questions as saying it’s a bad idea, I’m just trying to understand how it handles different bad faith actors. A few scenarios:
1. Say I lose the election. I then cry voter fraud and present my receipt showing that the numbers are different – because I changed them on the receipt. Perhaps my supporters do the same thing.
2. Say I have concerns before the election and steal a batch of ballot papers. If the result doesn’t go in my favour I have enough ballots filled out to win and then say they weren’t in the count.
I think that probably public perception, and how it can be manipulated without the system being at fault (i.e. scaremongering), is one of the hardest, most vital things to get right. But from our view as researchers, we hope to make the system so transparent (and verifiable) that we can have many, many people looking into it and finding their own facts. This is completely different to how voting systems are sold today, with no way for people to have an insight into how the system works.
Liked your TED Talk. One thing that can to mind is recounts, and the assumption that ballots are marked correctly. At least here in Missouri (US), there are always a number of mis-marked ballots that are not counted by the machine (fill in the oval, “scantron”). Where there is a recount because of a close election, those ballots are looked at by a republican and democrat election judge. If those two judges decided that the voter intended to vote for candidate A, then that vote is now counted for candidate A and that vote is considered an a priori fact, that candidate B would have to disprove in order for it not be be counted. (An example of a miscount: instead of filling in the circle for the candidate they wanted, a voter crosses out all the names except for the person they want…turns out this was they way it was done in West Virginia for a long time and 3-4 older folks who have immigrated from WV to our county will vote that way each election).
Would this system assume that all ballots are marked correctly ? (Here in MO, you can’t prevent someone from submitting a mis-marked ballot. There is a machine that will tell you that it is mismarked (overvotes, undervotes) when you turn in your ballot, but you have the right to submit it anyway). How would mis-marked ballots be recounted?
Scott
J. Scott Christianson
Web: TheFreeRangeTechnologist.com
Email: jscottchristianson@mac.com
Cell: 573-424-4254
The great thing about scanning the encrypted votes, like we do in Prêt à Voter, is that you can do a “sanity check” on the vote in public. In fact, if the scanner doesn’t understand your marks, or if you have under or over voted, it will return it to you with a message. So spoiling your vote by accident should not be possible – but in places where it is a legal right to spoil your ballot form we propose actually adding a “SPOIL” candidate to the list.
I understand the system allows individual voters to verify that their vote was unchanged int the batch and verify that all the anonymous votes in the batch were counted correctly. The only possibility for fraud seems to be to introduce extra votes into the batch that do not actually come from real voters. Who and how can verify that this has not taken place?
There are a number of different approaches to verifying that the votes come from eligible voters. In many places around the world today the poll books (lists of eligible voters with marks to indicate whether or not they have voted in the election) are open for public scrutiny. Verifying that the votes come from eligible voters is very important, but it is not handled by the e-voting system.