Ronald L. Rivest rivest AT mit.edu
Computer Science and Artificial Intelligence Laboratory
Massachusetts Institute of Technology, Cambridge, MA 02139
Warren D. Smith warren.wds AT gmail.com
Center for Range Voting,
Here is a collection of extra tidbits about ThreeBallot, VAV, and Twin, which due to space limits, oversights, or whatever other reason (e.g. somebody else suggested it) were not included in the paper. (Sometimes several reasons all apply.)
An important and common modification of range voting is also to permit voters to express "no opinion" on candidates they'd rather have judged by more-knowledgeable voters. (Highest average score wins.)
We can handle this kind of range voting securely via VAV as follows:
This kind of (single-digit plus "no opinion") range voting can also be handled via Twin, of course. That has the advantage that it consumes fewer pieces of paper. An N-candidate range election with VAV or ThreeBallot requires 3N pieces of paper cast per voter (assuming debundling down to single candidates); with Twin that is only N.
Jeiel Schalkwijk was disturbed by that paper-count:
E.g. with 20 candidates TWIN requires 20 ballots, while VAV requires 60 ballots. I think it would be hard to require every voter handle 20 ballots, especially the elderly and uneducated voters...
Unless it is one paper, which is visibly separated mechanically and automatically deposited in the bin afterwards. This does making the voting process more complex (mechanically), but it is doable.
Our response: The problem with Schalkwijk's "cut-apart" suggestion is:
But... it might work in combination with the "Shamos checker" (which prints random ballot numbers, instead of pre-printed ballot IDs), if we trust the Shamos-checker, if we are confident there is no steganography, and if make two cuts not one to separate paper so that no matching of micro-patterns is possible. (Or if we just trust the printer or somehow enforce the printer's integrity.)
We could make the voter fill out white ballots with K red carbonless copies produced automatically as she does so. (The reason we keep saying "carbonless" is so that there is no sheet of "carbon paper" for an adversary to inspect.) Here K is a small constant for example K=2. She then tosses the white ballot in the white bin and the K red ballot copies into the red bin. Twin's random sampling (with replacement) of a previous ballot and copying it to make a receipt, is replaced by simply extracting (without replacement) one random red ballot-copy from the red bin and handing it to the voter as her take-home receipt.
This weakened version of Twin is a lot simpler. However, it does not satisfy our security criteria because somebody who collected all K ballot copies, could then confidently fraud the corresponding original ballot. (In our genuine Twin scheme, you essentially never can be confident you've collected all the copies of anything.) It might, however, be reckoned that the security nevertheless is good enough, plus digital signature schemes could permit crude copies of receipts (since they are as good as actual receipts) to exist, re-endangering fraudsters.
Jeiel Schalkwijk points out that with digital signatures, any copy is legitimate. Therefore, in (e.g.) Twin, there is no need for a "copy machine" and also no need for red/white carbonless copying etc; we can simply extract a random ballot from the bin, ask the voter (who sees it through glass) to copy it as her take-home receipt, and then replace it in the bin.
An elegant "circular" twist suggested by Stefan Popoveniuc is that the first 10 voters be required to be election workers, and at the end of the day, after the last voter, they each get a take-home receipt too – again a copy of a ballot randomly selected from the box. The point is that, this way, everybody gets exactly one receipt, and nobody has to wait around until the end of the day who wouldn't have done so anyhow, and there is a less-severe security failure for voting machines with few voters.
However... unfortunately in practice there are not this many election workers per voting machine.Jeiel Schalkwijk suggested another version: initially some constant K number of fake receipts (K=10? 100?) are placed in the bin. A "cryptographic hash" of the fake receipts is published before election day and after election day the list of all fake receipts is published. This too allows every voter to take home a receipt.
C wins this IRV election. But if the 4 C>B>A ballots were regarded as anti-votes of 4 of the 6 A>B>C ballots and these 8 votes were eliminated before counting, then B would win.
The moral of this little example is that with instant runoff voting, reverse-order ordinary votes do not cancel the original votes. With genuine antivotes, they do cancel. That's one difference. The second difference is that antivote ballots are labeled as such (with a big "A", maybe a different color paper too).
Ivan Ryan comments (somewhat edited): The Rivest-Smith "antivote" concept is you match up the votes and anti-votes and cancel them out before counting. However, with instant runoff voting, there is another, perhaps easier, method of handling antivotes that appears to be equivalent:
An anti-vote with
will count as minus-one votes towards A until he is eliminated and then will pass to be a minus-one vote towards B, etc.
No. We've been asked stuff like "why don't you go do it in some test town/county/state and see what happens?" In my (Smith's) opinion (and it sounded to me like Rivest was probably thinking the same way), the prime problems with all three Rivest/Smith protocols are not the math or theory behind them. It is engineering and (secondarily) politics.
Rivest/Smith needs (if you want to do it right) certain machines to be located in each in polling place that perform certain specified tasks. All the tasks are known to be simple enough that they can be done (and have been done) purely mechanically without need for electronics or a computer. It is possible to make simulated Rivest/Smith elections without the machines, just by having human supervisors playing the roles of the machines for simulation purposes. But simulations, while useful, are not the real thing. The machines optimally should have the properties that
The second problem is politicians. Politicians have to do something to make this happen. The two interact in a vicious circle. (I.e. who is going to design, build, and test the machines, without any country demanding them? And what politician is going to enact Rivest/Smith in the absence of commercially-available machines?) Also complicating the situation is the possibility that perhaps the Rivest/Smith protocols are not the best possible protocols. Perhaps some version of Chaum's "scantegrity," or something else not invented yet, might be better. It seems like the only way out of this conundrum is grant money – enough to fund machine R&D.
Those devising anti-fraud voting protocols ought to have a clinician's understanding of what election fraud really is like. Smith wrote a description for this purpose.
I used this election to do a numerical cost-benefit calculation for the adoption of Rivest-Smith. The costs to Kenya of the fraud (or mere appearance of fraud) kept growing day after day, making the estimate a bit tough to write (moving target!)... but eventually those costs grew so staggeringly large that, in my view, there can now be no doubt that the benefits of Rivest-Smith are indeed worth it, at least in some countries.
See also: Pakistan election rigging/assassination rumors.