[clug] e-Voting: What would you want in a smartphone App?

[Kevin Pulo]

On Sat, Mar 20, 2010 at 12:10:27PM +0100, Martijn van Oosterhout wrote:

> On Sat, Mar 20, 2010 at 05:11:52PM +1100, Hal wrote:
> > The point is enhanced by the fact that even if you have a technical  
> > solution for /all/ of the security issues, the voting public still won't  
> > believe it and it will cast extra suspicion over a result. Especially so  
> > for the passionate supporters of the losing side. We hear dark  
> > mutterings of nefarious election conduct enough as it is, mercifully, no  
> > matter how disappointed we are with a result, such things have zero  
> > credibility.

...

> That said, such a solution completely misses the social factor: the
> "proof" would be mathmatical which most people won't understand and
> probably complicated enough that people wont trust it.

To these two points, I can only say "not necessarily".

> I was actually explained by someone once that it was theoretically
> possible to build a voting system such that you could after the fact
> prove that your vote was correctly counted in the end result, but in
> such a way they you could not prove to anyone else how you voted.
> Unfortunatly they didn't have any references...

I was pondering this over the weekend, since it's the sort of thing
that crypto systems should be able to eat up.  This is what I came up
with, and although I expect substantially similar systems have already
been proposed, I also can't be bothered trying to look them up.  Maybe
I should have rather than write all this out... oh well.  :)

This is pie-in-the-sky stuff; there are several points that aren't
possible with current technology or are insanely expensive, but it
should be at least vaguely conceivable that technology might one day
be able to do this sort of thing.

To give a taste of the idea without delving into public/private
keypairs etc (yet), the summarised paper ballot analogy goes something
like this:

Every ballot paper has a unique number on it, and when you vote you
are given and take home a gadget that knows your ballot number (but
won't tell it to you).  After the election, the electoral commission
gives anyone who wants a photocopy of the complete set of ballot
papers.  Now anyone can figure out who won the election (if they can
be bothered doing the tallying themselves, but that's much easier with
electronic votes than paper ones).  But also, anyone can feed the
stack of ballot photocopies to their gadget, which will confirm that
their vote is in there somewhere and hasn't been altered.

Now for the details (and of course I may have missed some; I'm no
cryptanalyst).

When the election is formally declared, the GG also generates a
private/public keypair, publishes the public one and stashes away the
private one.  This key will be used to encrypt every vote, and the GG
will publish the private key (yes) after the electoral commission is
satisfied with the actual running of the election.

The electoral commission manufactures 15 million (or however many, one
for each voter + some spares) smartcards.  Each card contains three
things: the GG's public election key, the electoral commission public
key that they will use to sign the collected votes, and a randomly
generated ("unique") private key.  The card does only two things:
given voting preferences of a user (ie. a "vote"), encrypt the vote
with the GG's public election key and then sign that with the private
key on the card, and give back the ciphertext.  The second thing comes
later.

When you turn up at the polling place, you get your eligibility
verified as usual (which is a separate problem that crypto and
electronic systems could help with), but instead of being given a
ballot sheet, the official grabs a random smartcard from the bucket
and gives it to you.

You go into the booth, shove the card into the machine, and then
choose your preferences.  The card takes your vote, encrypts and signs
it as above, and then gives it back to the machine which whisks it off
to the central server.  Random seeds, padding etc can be added to make
sure identical votes don't have identical ciphertext, etc.  You're
done now, go home - but keep the smartcard.

After polling closes, the electoral commission collects all of these
encrypted+signed votes.  They are encrypted and only the GG has the
key, so the commission can't tally them.  That's fine, they don't need
to, and it means they can't tamper with them either.  They just
assemble them all into a big database, sign that with their private
key (whose matching public key is on everyone's smartcard), and then
publish that on their website, bittorrent, whatever.

Simultaneously, the GG publishes the private election key (yes
really).  Now two very important things can be done.

First, any voter can use the second feature of their smartcard to
check their vote.  The complete set of encrypted votes (validly signed
by the electoral commission) is fed to the smartcard, which trawls
through the lot and will say one of: there is no vote signed by the
private key on the card (uh-oh, vote suppression), there is a vote
signed by the private key, but the signature is invalid (uh-oh, vote
tampering), or your vote is in there and is as you cast it (yay).  In
the first two cases you keep the card as evidence and complain (and
possibly revote, if the result is close enough), and in the third case
you can shred the card.

Second, anyone can use the private key published by the GG to compute
the election result.  Assuming ~15 million vote(r)s and say 100 bytes
each for the preferences, seat(s) and some padding (and ignoring
crypto overheads), that's around a 1.5Gb dataset.  This is feasible
now, but with 100Mbit/s broadband would be around a 2.5 minute
download instead of 16 minutes at 1.5Mbit/s.  The actual computation
shouldn't be too onerous, most of the CPU time would be decrypting,
rather than actual tallying.  Full preferences results could easily be
included.

This is a massive win for transparency (as well as traditional
e-voting wins of speed and accuracy).  At the same time, votes remain
anonymous because the smartcard won't give up the private key (not
easily, anyway), making large-scale coersion difficult.  (If you can't
check how the person you've threatened has voted, then what's the
point in trying?)

It also makes systemic rigging extremely difficult - the only person
who has the key to unlock the votes (GG) does not have the encrypted
votes until they are published, and those who do have the votes
(electoral commission) can't read them.  Changes to votes and
omissions can be detected.

The weakest points would probably be around keeping the private keys
private (as with all such systems), stopping extra votes (signed with
private keys not from smartcards) from being injected into the system
somewhere, the physical security of the smartcards before the event
(same as with ballot papers now), the security of the cards to crypto
attacks (as with all such systems) and eligibility problems (eg.
enrolling dead people, voting at multiple polling places, etc, same as
now).

And perhaps people wouldn't bother checking their vote afterwards, but
public interest groups could collect unwanted cards outside polling
places and provide this service.  But I think it's similar enough to
existing voting practices, and that the majority of people would be
happy enough to trust their smartcard, and how they've been told it
will operate.

Hopefully this gives an idea of the sort of thing that's at least
plausible using electronic voting systems, without necessarily having
to compromise standards.  I also like that such a system would be a
great justification/use of national broadband infrastructure (compared
to say, youtube, etc), and that really does require high capacity
internet connections.

I'm also reminded of when I looked in on some course notes on voting
in a Public Economics course.  Any sort of group consensus with more
than 3 people is a vastly non-trivial exercise, no matter how you try
to go about it.  It was a real eye opener just how poor many common
voting schemes are (eg. simple majority), and how well the Hare-Clark
system performs by comparison - and how little it is used (basically
only here, Ireland and Malta).

Kev.

-- 
.----------------------------------------------------------------------.
| Kevin Pulo                Quidquid latine dictum sit, altum viditur. |
| kev at pulo.com.au               _ll l_ng__g_e_ _r_ hi__ly p__d_ct__le. |
| http://www.kev.pulo.com.au/         God casts the die, not the dice. |
`--------------- Linux: The choice of a GNU generation. ---------------'
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
URL: <http://lists.samba.org/pipermail/linux/attachments/20100322/f7f108cd/attachment.pgp>