[EM] 3ballot - revolutionary new protocol for secure secret ballot elections

[Warren Smith]

>Ka-Ping Yee:
I'm talking about "marking the ballot" by filling in bubbles, not
by scribbling on it.  There may be enough down-ballot contests in
many elections (at least in the U. S.) that the vote-buyer could
instruct a voter to create a distinct pattern of filled bubbles in
down-ballot contests.

--Oh. Then: true.
Well, first of all, the whole idea of bundling several races onto one ballot,
is just stupid.  It allows an attacker to identify you by your
vote on the school board candidates (100 voters and 12 candidates
total in that race) and then use that identification to attack your
presidential vote.  The sole "reason" to have such bundling is a 
holdover from the pre-3ballot-era traditions.  It makes absolutely
no logical sense in terms of security, 
simplicity of procedures, standardization of ballots, or anything.
Rivest, to the extent he supports this bundling idea, was an idiot.  

OK, fine.  So suppose we've de-bundled so we have one ballot per race.
Then still, your (KPY's) attack idea is still applicable even in just one
race (if there are enough candidates, e.g. 135 in the CA governor Schwarzenegger race)
and Rivest includes discussion of this attack in his (latest! but not his original!) 
draft, calling it the "3-pattern attack" or "specified pattern attack"
where the attacker coerces the voter to vote in a specific pattern on his 3 ballots
and then sees if those patterns got published on the bulletin board.  If not,
punish the voter.  This attack appears to be quite devastating to me.
I personally regard Rivest's scheme as therefore dead or anyway on the critical list,
for purpose of applying it to plurality voting.  Rivest has a few lame attempts
to rescusitate it, but they do not impress me much.  However, for approval & range voting,
this attack (in the de-bundled world of course) is not an attack at all.  It
is nothing.  So Rivest's idea is strong and healthy for range & approval voting.

That's a point I have made to Rivest repeatedly, but he just does not want to accept that
because (I guess) he hates the thought of getting into voting methods, & he hates the
thought his 3ballot method might "only" be useful for some voting methods that are
(in comparison with plurality voting) not used.  Somebody needs to waterboard Rivest 
until he sees the light, which is that his method works synergistically with range and approval
voting.  (I don't even think the WORDS "approval voting" even OCCUR in Rivest's
paper, even the revised one, which shows you how far into the land of the loony Rivest is
drifting in his efforts to ignore the obvious.

>Jan Kok: This can be alleviated by putting different contests on different ballots.
There is still the possibility of mischief if there are many
candidates in a contest.
With Range Voting, each _candidate_ can be put on a separate ballot.

--All exactly right.

>A u-R Lomax:
Vote-buying may shift close elections; but, 
frankly, I think it is rare. very rare.

--Well, that is not clear.  May be rare here & now, but historically it has at the right
times and places been not rare, but "the norm."  Read LBJ biography & Gumbel book if you
want to learn about that.  Also in the right kind of country, it (or coercion) may be common or
an easy way to slide into non-democracy.

>>WDS: That's all totally wrong thinking.  If all voters did that, then a
>> Dem voter would on all
>> three ballots show (usually) a pro-Dem bias, and then his vote could
>> be reliably (in an averaged statistical sense) be bought by a Dem-Boss
>> vote buyer.
>KPY: I don't see how that would be possible.  How would a vote-buyer be
>able to buy votes in an "averaged statistical sense"?  Could you
>describe this vote-buying process in more detail?

--trivial.  I just say to you: "show me your ballot copy when you come out
of the polls.  If it votes for Clinton, I'll give you $1."
With your foolish randomization nonsense which totally breaks 3ballot,
if you vote Clinton, then 2/3 chance you get a dollar; if you vote not-Clinton,
then 1/3 chance.

STENCILS:
--One more thing.  Raphfrk on this forum suggested some
ideas about sliding widgets and 3ballot.   
I thought his stuff (assuming raphfrk is a "him") was rather kludgy and confused
and I wasn't even sure it would work, BUT, it had the germ of a very good idea.
Which I call "STENCILS."  Basically there are a set of stencils whose pre-drilled holes
correspond to a set of allowed 3ballot (+1 copy) patterns.   Make the rules be:
voter must use a stencil (he can pick from a supplied set of stencils).
In principle the stencil trick allows defeating both the devastating "3pattern attack"
and the reconstruction attack since you can't hide info in your vote-pattern if the vote
pattern is prescribed for you in a small numebr of possible ways.

I investigated this idea moderately deeply and found out that a certain kind of
set of stencils would work, in principle.   So good news: this in theory cures
the attacks and Rivest's 3ballot is once agains healthy even for plurality voting.
(I sent my stencil investigations to Rivest.)
BUT bad news: the set of stencils I constructed was rather large - about 144*N*N
stencils in an N-candidate race.  I think I can decrease the constant 144 to, like, 30,
but still, this is a huge number of stencils required.  So I think in PRACTICE
this does not fix things and Rivest & 3ballot remain in trouble for plurality
(but are fine for approval & range voting).  I also proved at least 3*N^(3/2)
stencils are necessary.  I sent all that to Rivest along with a credit to raphfrk.


I have some optimism Rivest will see the light and realize he"s come up with
a great reason to prefer range & approval voting, and he ought to at least
mention AV in his paper, for heaven's sake.
...

Warren D Smith
http://rangevoting.org