ADDENDA to "Three Voting Protocols: ThreeBallot, VAV, and Twin"

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,
July 2007

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.)

Range voting with "no opinion" scores allowed

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:

1. A C-candidate single-digit range voting election with "no opinion" votes allowed (11 possible scores for a candidate: 0-9 and "no opinion") can be mathematically transformed to be C plurality elections, each one with 11 candidates.
2. I.e. Jo versus Tom (range voting election) becomes these 2 plurality-voting elections: Jo₀ vs Jo₁ vs Jo₂ vs .. vs Jo₉ vs Jo_{No opinion} and Tom₀ vs Tom₁ vs Tom₂ vs .. vs Tom₉ vs Tom_{No opinion}.
3. This transformation was invented by Jan Kok for the purpose of running range voting elections on old-style plurality-voting dumb-totalizing machines.
4. However, it can also be used to run secure range voting elections via VAV. As Rivest & Smith's paper shows, VAV handles plurality elections securely. So therefore we can via Kok's transformation handle range voting (with "no opinion" allowed) elections securely. (The only flaw with this approach is that write-ins are no longer allowed. Plain range voting handled via ThreeBallot, not VAV, permits write-ins.)

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.

Cut apart ballots so we get fewer papers?

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:

1. The ballot printer could make secret relationships among all the ballot numbers (or steganography for same purpose) and thus be able to carry out a "reconstruction attack" (or anybody he told his secret relations to, could do such an attack) to violate vote privacy.
2. micro-examination of torn paper could also allow reconstruction.

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.)

A way to make Twin more practical (but weaken its security)

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.

Don't need copying machine

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.

Elegant "circular" trick for Twin

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.

Why are VAV "antivotes" different from just reverse-order ordinary (rank-order) votes?

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
A: 1
B: 2
C: 3
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.

Are Rivest/Smith voting protocols ready for prime time (as of early 2008)?

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

1. They indeed do these tasks.
2. Enough testing and experience has accumulated that we know they do them well enough.
3. It is visibly obvious to onlookers that they do them.
4. They are cheap and simple.

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.

History of Election Fraud

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.

Kenya's rigged 2007 election

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.