Scantegrity II at EVT08
July 31st, 2008 by Aleks Essex and Richard Carback in : UncategorizedWe presented Scantegrity II at this year’s 2008 USENIX/ACCURATE Electronic Voting Technology Workshop (EVT ‘08).
The paper can be read here [PDF].
| Event Photos |
 Photo: Me giving the talk at EVT08 |
 Photo: Taking questions |
 Photo: David and Jeremy going over the slides beforehand |
August 5th, 2008 at 6:14 pm
Regarding the dispute resolution protocol, it seems that a political party could effectively raise the fraud tolerance of the system by asking its members to file as many bogus disputes as possible. Perhaps this isn’t a huge problem, but conceivably hundreds of votes could be safely stolen.
I believe that there are also some procedural details to be worked out. For example, if your singular right to dispute is represented by possession of your receipt, then you must surrender your receipt when you file a dispute. But then the EA would have to give you an authenticated acknowledgment of the dispute in order to prevent it from denying that the dispute as filed was a plausible discrepancy.
August 5th, 2008 at 6:28 pm
>> Regarding the dispute resolution protocol, it seems that a political party could effectively raise the fraud tolerance of the system by asking its members to file as many bogus disputes as possible.
Bogus disputes can be handled by the system by basic statistics. Assuming the voter cannot see the other (valid) confirmation codes on the ballot, the best they can do is randomly guess a (another) valid code during a dispute. Then it is just a matter of how big the code space is to control your the false (aka bogus) positive rate. We would also presumably want a cap on the overall disputes that can be filed, for example, not more than one dispute per voter.
>> For example, if your singular right to dispute is represented by possession of your receipt, then you must surrender your receipt when you file a dispute.
The receipt is not a bearer bond, and in fact, it is not really a receipt at all… it’s a confirmation code, which can exist in any manifestation. Knowledge of the (valid) code is the only requirement.
August 5th, 2008 at 7:43 pm
Take, for example, C = 1296 = (36*36), D = 100,000, p = 4/1296 = 0.3%, mu=309, tau = 845. If we assume that 5% of voters verify, then we could steal about 10,000 votes without the probability triggering an investigation exceeding 50%. This argues for a C of at least 36^4 in order to ensure that it is never cost effective to cheat.
>> The receipt is not a bearer bond…
Sec 4.7: “…only one dispute may be filed per voter.”
Sec 7: “Disputes in the basic system require physical possession of a stamped receipt.”
I’m having some trouble reconciling these statements.
BTW, regarding the enhancement with the “authenticated ballot status” codes, I don’t see what prevents the EA from printing all of these codes in contradiction to the commitments.
August 5th, 2008 at 11:45 pm
It’s too late for me to respond to this one other than to say it’s on the TODO.
I think this an artifact of multiple authors. By “basic system” I think the author in that section is talking about Scantegrity I, not II. If not, then he/she means the same as the above statement, that you need to show you are a voter who voted to complain, but not that you’d lose your receipt.
The print audit? It’s a bit different (voter and poll worker need to write down codes and the poll worker needs to sign it).
August 7th, 2008 at 1:10 pm
>> By “basic system” I think the author in that section is talking about Scantegrity I, …
This seems unlikely to me. Since the section is entitled “Enhancements to the Basic System,” I would think that “basic system” means the “the basic Scantegrity II system described thus far” without the optional enhancements.
In any case, wouldn’t you agree that in order to claim that the system is ready for use in public sector elections, you have a duty to disclose your proposal in specific clear detail, including which enhancements should be included?
>> The print audit? …
I think I buy that now. If the voter produces a stamped audit ballot with a bogus authentication code still attached to it, then we can conclude that the EA erred. However, I would argue that this “authenticated ballot status” codes enhancement is susceptible to poll worker error, and therefore probably ought not to be included in the first public roll-out.
August 7th, 2008 at 9:06 pm
I don’t follow. The claim is that the basic system could be used. The enhancements are talking about ways to make it better, raising the bar even further than the basic system will. Due to page limitations, it is somewhat impossible to go into great detail for everything. To some extent that stuff is future work because we do not have prototypes built yet.
Regarding the specific detail (how ballot receipts are handled during complaints), it seems you’ve come to an unambiguous interpretation based on the context and possibly found a minor oversight. There are only two sane ways (of which i’m aware) you can guarantee the property that only one complaint per voter may be filed. Option 1 is as stated in the section you point out. Option 2 is to look at the voter sign-in from election day and have the voter prove their Identity. Elsewhere (unless it’s been dropped inadvertently due to size constraints), we said that we didn’t want voters to identify themselves during complaints. Thus, option 1 should be the only valid option, unless you do something crazy like stop accepting complaints when # of complaints >= # of voters.
I agree in the general sense with what you are saying, but I think that “specific clear detail” is a sliding bar that depends on the person, specific requirements, and the language in which the details are written (English is not very good for this purpose). I think the paper is sufficiently detailed to show that the system will be appropriate for polling site based public sector elections, but perhaps doesn’t (and cannot) dive into enough detail to cover all the details that might come up. I don’t think i’ve ever read a paper or requirements document that I would say is entirely clear and specific, no matter how long or explicit. I’ve always been able to point to an issue that isn’t covered, so in some sense this is impossible if you go in deep enough.
That said, what you’ve pointed out is definitely unclear and that makes your feedback on this point invaluable. We are working on a longer and more detailed paper for a journal publication, and we’ll definitely be cleaning this up. Thanks!
August 8th, 2008 at 1:54 pm
Anders,
Firstly I believe trigger tau, under your scenario, should be
mu + r = 309 + 845 = 1154.
Secondly, if I’m not mistaken, you’ve essentially outlined some sort of election Armageddon scenario in which 100% of 100,000 voters attempt to file an illegitimate dispute with the election authority who is simultaneously illegitimately modifying the bulletin board.
Would using 4 alpha-numeric characters really solve such a twisted election?
August 8th, 2008 at 2:10 pm
Sec 7: ?Disputes in the basic system require physical possession of a stamped receipt.?
The “basic system,” by which we mean Scantegrity II (invisible ink) WITH a tear-off chit, is a hang-over from Scantegrtiy I where you did require a chit for forensic matching purposes, and was offered because its a conceptually simple (though procedurally tedious) way to prevent certain class of attacks (such a voted ballot being fraudulently “exchanged” in status to an audited ballot).
However I think quite obviously, we want to minimize reliance on physical custody of documents, so we ultimately seek an informational mechanism:
“…the enhancement [over the basic system] allows for informational disputes, where a voter need only know her confirmation codes in order to prove that her ballot is misrepresented online.”
This is of course the incarnation that I was speaking of (earlier in this thread), and the one that we would be looking to use in practice.
August 8th, 2008 at 9:29 pm
>> Secondly, if I?m not mistaken, you?ve essentially outlined some sort of election Armageddon scenario in which 100% of 100,000 voters attempt to file an illegitimate dispute with the election authority who is simultaneously illegitimately modifying the bulletin board.
Or 10% of 1,000,000 votes, in conjunction with hacking the optical scanners, in order to get a 2% MOV shift. This is conceivably cost-effective for a political party. If it cannot be reliably detected, than it is really worth the effort to retool elections?
>> Would using 4 alpha-numeric characters really solve such a twisted election?
It would prevent such shenanigans from being cost-effective. If we assume that the cost of filing a bogus dispute is $0.10, then the cost of getting away with stealing each vote is about $20 with 2 characters, but about $20,000 with 4. Historically, the going rate for selling a vote has been about $10-$100 dollars.
August 9th, 2008 at 12:46 am
“If it cannot be reliably detected, than it is really worth the effort to retool elections?”
Well in the million voter election, the fraud represents a 1% shift in the outcome, and meanwhile all you needed is 100,000 dishonest voters working with a dishonest election authority to do it.
“It would prevent such shenanigans from being cost-effective.”
There’s a great saying: “privacy, integrity, usability, choose any two.” Personally, I think 4 characters is fantastic. Heck, make it at least 8–that’s what a self respecting airline e-ticket would do.
We tend to face a pretty tough usability crowd and the two code letter notion was offered with them in mind. But I get the feeling the jury is still out on the best code length.
Oh, did you know our actual version of C is < 36^2 ?
We had to cut down on the alphabet because some letters kind of look the same; 1, I, l for example! O, 0, etc. As we all know, with voting, there’s no room for ambiguity. I’m not even sure what our current C is, but it’s been pretty decimated for this purpose.
Also, keep in mind that the trigger presented in the paper was just one possibility. I know there were at least two considered. I’ll try to get those authors to chime in.
August 9th, 2008 at 4:48 pm
>> “privacy, integrity, usability, choose any two.”
Of course I agree that there are trade-offs to be made. However, a trade-off that is known to enable the additional integrity to be cost-effectively subverted is going to be a tough sell.
>> we ultimately seek an informational mechanism
I agree, but in my estimation, the informational mechanism proposed is virtually guaranteed to result in poll workers erroneously releasing large populations of audit ballots with both status authentication codes intact. I’m sure you can appreciate how problematic this could be.
August 11th, 2008 at 1:38 pm
Hi Anders,
Thought I’d chime in on this point:
>> I agree, but in my estimation, the informational mechanism proposed is virtually guaranteed to result in poll workers erroneously releasing large populations of audit ballots with both status authentication codes intact.
Choosing the informational model over the chit-stamping models is definitely a cost-benefit decision. The benefits are convenience for the voter filing the dispute and anonymity. The latter was our main motivation, since we want a model that can be used in hostile voting environments, where a voter may be persecuted for challenging the election authority. The costs of the model, as you point out, are increased complexity for poll workers.
The paper doesn’t conclusively advocate one model or the other for two reasons: (1) the decision is situational and (2) the factors will need to be empirically verified through the kind of extensive usability testing required for certification. I suspect you are thinking primarily of the US election market, where the costs could very well outweigh the benefits.
That said, I also want to challenge your pessimism as to the poll worker’s ability to conduct such a task. This model was designed to be very close to a mechanism that is already used in Canadian elections to prevent chain voting.
Canadian ballots contain two detachable serial numbers (the same number twice). One is detached by the poll worker prior to handing the ballot to the voter. When the voter returns from the booth, they hand the ballot back (folded to protect ballot secrecy) to the poll worker who detaches the second serial number and compares it to the first. If they are the same, the voter is permitted to submit their ballot to the collection.
Our scheme could be added to this mechanism with a small footprint. The codes would be on the back of the detachable serial numbers in invisible ink, for example. The poll worker would detach the serial number and hand the voter the ballot, thus audited ballots and ballots taken to the voting booth to be voted on would be issued identically, which is intuitive if the voter is issued two and gets to choose which one to vote on. When the ballot is returned, the same procedure is followed except the voter gets to take home both detached codes.
I wish I could point to some empirical study for how effective this mechanism is in Canadian elections, as its quite similar in its requirements from a usability perspective.
As I’m sure you will point out, an error in our mechanism has greater consequences than an error in the chain-vote preventing mechanism, and so the costs may still outweigh the benefits. However, I do stand behind the mechanism as being only a modest expectation of poll workers and not out-of-line with existing procedures.
August 11th, 2008 at 4:46 pm
>> I do stand behind the mechanism as being only a modest expectation of poll workers and not out-of-line with existing procedures.
Point taken.
BTW, Scantegrity II is apparently susceptible to unvoted issues (presumably on a multi-issue ballot, which is outside the scope of the paper) being fraudulently marked by a poll worker after the ballot is cast. Would this be addressed by having a required “no vote” bubble, or did you have something else in mind?
August 12th, 2008 at 6:08 pm
“Scantegrity II is apparently susceptible to unvoted issues”
Yes, this is the awful problem space we live in: people want a comprehensive solution with no change.
So we said, ok, most people use optical scanners, so we want to develop a solution to tie into that, without requiring new components, but in so doing, we inherit some of its limitations. What you describe is a limitation of optical scan.
What can we do about it? Well use Punchscan for one thing!!
But seriously though, at an administrative level it may be sufficient to say “if that’s not acceptable to you, you may need to be prepared to change some things.” We have some ideas, but they all require adding something:
-more cryptography
-more physical protection such as:
- -different forensically tagged pen inks
- -an clear adhesive overlay tape for voted ballots
- -over-printing of voter-made marks with digital signature barcodes
We’ll have to think about it some more, and get some feedback as to what people actually want, because as the Germans say, ‘kundin ist Koenig’ (customer is king).