Re: [Demexp-dev] Thoughts on voting machines

[Brian Hurt]

On Sun, 19 Sep 2004, David MENTRE wrote:

> The scope of this project is to make an electronic voting system
> suitable to the requirements of the democratic experience project.

One thing you don't make clear: who is our target audience?  Are we 
talking about online preference polling, online community organization 
(eg Debian), "non-political" votes (eg American Idol), or official 
political votes?

This is a non-trivial question.  How much security do we need?  That 1 
carat diamond ring at the local mall jewelry store needs a lot less 
security than the Hope Diamond does, despite the fact that they're both 
diamonds.  The amount of security (and paranoia) needed to protect, for 
example, the United States Presidential election (to pick an example out 
of the hat) is a very different level of security than we need to protect 
the Debian board elections, or the selection of MTV's movie of the year.

I was thinking solely of official political voting systems- effectively, 
US Presidential ballots.  Events of the last few years have highlighted 
the problems in this area to me.

Note that a system secure enough and paranoid enough that I'd trust it to 
elect the US President (or any official political position) would be way 
too paranoid and cumbersome to elect the Debian board, for example.  I 
don't think scaling is possible.

> 
> In short: - votes can be modified at any time;
>           - you can delegate your vote to another person;
>           - use Condorcet voting algorithm.

Arrow's theorem says that no one voting system is perfect.

Here's an example case- the voters have three choices, A, B, and C.  
1/3rd of the population (group 1) prefers A over B, and B over C.  
Another 1/3rd (group 2)  prefers B over C, and C over A.  The last 1/3rd 
(group 3) prefers C over A, and A over B.  Now, 2/3rds of the population 
prefers A over B (groups 1 and 3), B over C (groups 1 and 2), and C over A 
(groups 2 and 3).  Who wins?

Similiar voting problems exist for all voting systems.  It's been proven 
mathematically.

Also, if the target market is official political campaigns, you're going 
to have to be able to fit the local voting requirements.

As such, I don't think I'd lock into Condorcet.


> Another solution would be to display the paper ballot behind a glass. If
> the voter likes the ballot, it goes into the voting box, oterwise in the
> cancel box (for recount of canceld ballots). 

Why would you ever need to recount canceled ballots?  I'd say the 
alternative- canceled ballots should be destroyed.  I'd be tempted to 
shred them.

> 
> I think a firm as even made and commercialized such a system.

Most of the one's I've seen don't come with paper.  Or paper comes at such 
a markup that most places don't bother.  See:
http://www.blackboxvoting.org/

for the appropriate horror stories.

> Beside that, I don't know if a systematic statistical recount sampling
> is necessary or not.

I'd do a statistical recount just to sanity check the system.  Note that 
you can get a very good sample counting only a few thousand votes in an 
election with millions of votes.

Actually, thinking about it, I'd do half and half.  Each party with 
officials on the ballot gets to pick a machine to be recounted.  Then an 
equal number are picked randomly to be recounted in addition.  This way, 
if a party even suspects the other side was tampering, they can pick the 
worst example for a recount.

> > The goal of the computer is to make creating the ballot as easy, 
> > foolproof, and quick as possible.
> 
> Or you can recount manually, without OCR. After all, if you don't trust
> a computer to count votes, you won't trust a computer to recognized
> characters, which is a much more complicated task. 

True.  As I mentioned.

> 
> > There is a known tendency for voters, when picking at random, to pick the 
> > first name on the list.  So we want to randomize the order of candidates 
> > for every voter, to negate any statistical advantage of position.
> 
> Interesting point. I've never seen it elsewhere.

This came up in the California recall.  The problem with pre-printed 
ballots is the cost of doing multiple ballots.  If you're showing names on 
a screen, this is no-cost.

> Well, the strong point of democracy is not the vote itself but the the
> vote *and* the debate before the vote. So the information should be made
> before the vote and not at vote time.

I agree.  Often it isn't, however- and I'm willing to go on at length as 
to why this is bad for democracy.  It's especially true for "minor" races- 
most people in the US go into the voting booth with a pretty fair idea of 
which Presidential candidate they're going to vote for, and a much less 
clear idea of which judges and county commissioners they are going to vote 
for.

> 
> Interestingly, in demexp, for each response to a question there will be
> a link to an external forum, web site, etc. to feed further debate.

Again, what's our market?  If it's electing the debian board of directors, 
this is a good idea.  If it's electing the President of the US, it's a bad 
idea.  

The polling place I go to has thousands of voters go through it on
election day- it's a zoo.  I actually want to limit the amount of
information they have to read in the booth, to maximize throughput of
voters.  This is actually an argument against having any candidate 
information available at all.  Plus, you have problems with laws requiring 
that all campaign material be kept away from the voting booth (in MN, the 
law is 100 yards- and election judges are issued the official, legal, 100 
yard long string).

> 
> > I also like the idea of allowing sample ballots to be programmed in.  Note 
> > that the voter would still be able to go back and override the choices, 
> > it'd just be a bunch of default choices.  So the voter could go "I want to 
> > vote the straight Trotskyist ticket, except I hate who they have running 
> > for Dog Catcher, do I want to vote for the other guy."
> 
> I don't like this idea. It's too complicated. What is your semantics of
> "Trotskyist" ticket. Our French socialists might look communists for
> Americans while they are more like American Republicans for us. :)

I picked the name "Trotskyist" just to have a political party no one would 
think I was endorsing (maybe not).  Around here, a lot of organizations 
issue "sample ballots"- these are just lists of what candidates the 
organization supports and wants you to vote for.  All the political 
parties have them, but also unions and other groups.

We need some way to go back and change your mind, before casting the 
official ballot.  One of the ideas I was playing with was a "running 
total" on the left hand side of the screen.  When you select a candidate 
or choice, it goes into a dock (probably shrunk).  You can then select any 
vote you've made from the dock to "go back" and choose again.  The sample 
ballots would be pre-programmed into the system, and by choosing a sample 
ballot, it would "pre-select" various choices for you.  You could then, 
using the standard method, go back and change the choices.

> 
> > Another idea I had: in addition to the ballot, the voter gets an identical 
> > "receipt" to take home.  The receipt and the vote is given a 256-bit, 
> > cryptographically secure random number as an ID.  After the vote is done, 
> > all the votes are published on a website somewhere- no names, just receipt 
> > ID and what the vote was.  The advantage here is that I, the voter, can 
> > then verify that a) my vote exists and was counted correctly, and b) the 
> > tabulation of votes as put up on the web site matches the tabulation of 
> > the votes announced as the result.

Note that the anonymity requires faith that the ID is, in fact, 
cryptographically secure, and no one can backtrace from the ID to who 
voted, or even where/when the vote happened.  This scheme places less 
faith in the voting officials, but more faith in the voting machines.

> 
> Yes, interesting point. The debian voting system is using a similar
> scheme. 
> 
> In a previous attempt to design a secure voting algorithm for demexp, I
> used a similar scheme. However, I'm not sure at all I've used it
> properly.
> 
>   http://lists.gnu.org/archive/html/demexp-dev/2004-03/msg00015.html
> 
> And the initial design was lacking important features for us. 
> 
>   http://lists.gnu.org/archive/html/demexp-dev/2004-03/msg00031.html

I'll take a look at it.  I'm not up to cryptographically analyzing a 
protocol at the moment.

> You also need to physically put those parts into a proper design. For
> example, you need to add physical devices to ensure that your voting
> machine is not tempered during the vote (or at least you can detect a
> tempering). You also need to make the machine work even in case of lack
> of electric power. Etc.

Physical security falls under the bent tin.  Electrical power I hadn't 
thought of- you'd need enough UPS to run the machine for 12 hours.  Low 
power may be as important as low-cost in this case.

> 
> > We need someway to know when the user has voted, and some way to make sure 
> > the voter only votes once.  Those I'm still working on.
> 
> I'm a strong proponent of formal verification of the machine code.

Open source software and off the shelf hardware components are sufficient, 
even for presidential elections.  If the software was available, it would 
be downloaded by "neutral third parties" and rigorously inspected.  The 
problem is that there are enough components to the system- the software we 
write, the Ocaml compiler, the operating systems, etc.- that formal 
verification of one part doesn't imply formal verification of all parts.

-- 
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 
Brian