[E-voting] FW: Fraudproof voting protocols from scientists

Kieran Tully kieran.tully at gmail.com
Sat Aug 4 14:45:47 IST 2007

Interesting reading from yesterday's RISKS Digest on some new receipt
based protocols, all of which claim to preserve the secrecy of the
ballot. Haven't had a chance to look into the details, but I suspect
at least one is still vulnerable to "vote signing" in a PR system.
Kieran Tully, Software Developer and Tenor, http://ktully.net

---------- Forwarded message ----------
From: RISKS List Owner <risko at csl.sri.com>
Date: Aug 3, 2007 8:14 PM
Subject: [RISKS] Risks Digest 24.77


Date: Thu, 2 Aug 2007 09:44:42 -0400
From: "Warren Smith" <warren.wds at gmail.com>
Subject: Fraudproof voting protocols from scientists

Simple New Voting Protocols provide Ballot Secrecy AND Fraud Resistance

Conventional wisdom says elections with "secret ballots" are protected
against vote-buying and coercion, while elections publicizing the list of
all voters with their votes are immune to fraud -- but you can't have it
both ways.  In a paper at EVT 07 (Boston, 6 August) mathematicians Ronald
L. Rivest and Warren D. Smith refute that conventional wisdom, potentially
enabling a new level of voting integrity.

"You can have your cake and eat it too with some very simple new voting
protocols," said Professor Daniel Sleator of Carnegie-Mellon's computer
science department.  "These are explainable to children.  It's surprising
this wasn't thought of 50 years ago."

Previous attempts to create such protocols have "succeeded" in mathematical
senses, but only by employing very complicated cryptographic algorithms,
challenging even for math PhDs.  Humans can't vote in those systems without
computer aid, which means that each voter would have to own a small computer
"helper" they trusted to be running correct, unhacked, voting software.

Rivest & Smith's new protocols, called "VAV," "Twin," and "ThreeBallot,"
don't require computers or cryptography, and need only low-tech mechanical
voting devices.  In each, voters get take-home "receipts" they can use later
to check their vote was correctly counted -- or prove fraud -- but which
nevertheless bear absolutely no relation to that voter's vote, hence aren't
helpful for vote-selling.

How can that be?  Your take-home receipt in Twin is a copy of a random
_other_ person's vote.  In VAV, each voter casts two votes and one matching
"antivote" and gets a copy of one of these three (she chooses which) as her
receipt.  Either way, the receipt has no logical relation to that voter's

All three Rivest-Smith protocols allow "mixing in" old-style unsafe ballots
with the new safe ones.  That not only permits happy coexistence with voters
who don't want to use the new system, but also "contagiously protects" even
the unsafe ballots against fraud.  "I really love this 'easy upgrade'
feature," said Doug Jones, former chair of Iowa voting systems examiners and
computer science professor at University of Iowa.

The Rivest-Smith protocols work with a wide variety of vote-totaling
systems, not just the "plurality" system most familiar in the USA.
"Plurality is a very poor voting system," said Guy Ottewell, an astronomer
and author regarded as the inventor of Approval Voting in 1968.  "We've
known better ones for 200 years."  "In plurality voting, it's 'name one
candidate then shut up'," said Ottewell.  "With Approval, you name _all_ the
candidates you 'approve.'  It's actually simpler because there is no special
rule outlawing 'overvoting,' and it both delivers more information in each
vote and allows voters to approve their true favorite without being
strategically foolish, so it's also more honest information."

But why would voters want dishonestly to vote for someone other than their
true favorite?  "Two words," said Ottewell. "Ralph Nader."  "With approval
voting, Nader voters aren't a problem, they're beneficial."

But Ottewell and Smith now instead advocate "Range voting," essentially the
system used in the Olympics: as their vote, voters score all the candidates
they want to within some fixed score-range (say 0 to 9); highest average
wins.  (Range becomes the same as Approval if the range is 0 and 1.)
"Honeybees have been using range voting for millions of years, and my
computer simulations indicate it outperforms every other common
vote-totaling proposal," said Smith.  ###

Fuller Story (including how VAV & Twin actually work):
Rivest-Smith actual paper:   http://www.math.temple.edu/~wds/homepage/tb8.pdf
   also in html:            http://rangevoting.org/RivSmiTB.html
Addenda to the paper:        http://rangevoting.org/RivSmiTBadd.html
Follow-up stories:           http://rangevoting.org/RivSmiPRfollow.html
EVT 07 Conference:           http://www.usenix.org/events/evt07/cfp/
Center for Range Voting:     http://RangeVoting.org

 Dr. Warren D. Smith   631-675-6128    warren.wds AT gmail.com  (prefer email)
*Approval & Range voting (AV & RV):
 Guy Ottewell  +1297-442247   guy AT universalworkshop.com
*(AV, RV, and also most other vote-totaling systems too)
 Prof. Steven Brams,  NYU politics dept. 212-998-8510  steven.brams AT nyu.edu
 (co-author of book "Approval Voting")    FAX: 212-995-4184
*Computer Science:
 Prof. Daniel Sleator, CMU CS dept. Office ph 412-268-7563, fax: 412-268-5576,
    home ph: 412-HACKERS


 The ACM RISKS Forum is a MODERATED digest, with Usenet equivalent comp.risks.
=> SUBSCRIPTIONS: PLEASE read RISKS as a newsgroup (comp.risks or equivalent)
 if possible and convenient for you.   The mailman web interface can
 be used directly to subscribe and unsubscribe:

More information about the E-voting mailing list