ABOUT ELECTRONIC VOTING
---Warren D. Smith 2003---------

The advantages of electronic voting are so vast, and its potential
to increase voter turnout and improve democracy (and reduce wasted time)
are so vast, it is essential to investigate to see how it can be done 
and what its limits are.  The paper 
     Niemi & Renvall:
     Efficient voting with no selling of votes,
     Theoretical computer science 226, 1-2 (1999) 105-116
shows a lot of things one might naively have thought
impossible, in fact ARE possible.  I pointed out to N&R their stuff could be
made more feasible by use of elliptic curve discrete logs instead of
integer modular discrete logs.
The question is whether it can be made cheap enough and good enough 
that it is preferable to the low-tech voting systems currently in use.

N&R discussed how to implement electronic voting in such a way that
there is an audit trail and nevertheless voter anonymity is preserved.
(These would seem at first to be mutually incompatible objectives.)
N&R indeed have a fairly long list of voting systems desiderata, some 
of which seem naively to be incompatible, but which nevertheless they satisfy.
I found this paper pretty impressive.  However, in the real world
there are still some engineering problems (N&R requires a lot of 
computing, which is expensive), as well as some possible
abuse problems, with it... For example, elections could be compromised 
by use of widely circulated "spoofed" software where you think you've 
cast a vote, but actually it did something else.  Whatever the screen 
says to you, has nothing to do with what actually happened. Now of course,
if you ever accessed another computer having the official N&R software, you
could run the audit and thus would be able to realize you must have 
had spoofed software! Also, you could run widely available "checksum" 
programs (or better: cryptographic hash functions) to verify 
the software you had was the genuine article.
Still, if any such spoofs become widely enough distributed 
to enough stupid enough people, it would be a vast problem. 
Bill Gates could control the world.  I'm just saying that that 
(wide spoofing) would be impossible to do without people noticing immediately,
and creating a furor.

Another objection to N&R is that the candidates (or their parties) all have
to cooperate to run the verification and tabulation protocol. If
one suddenly claims "oh, bummer, my computer broke and I cannot cooperate" 
the entire system breaks. (Or he could use the threat of this for
blackmail.)  I pointed out to N&R how their system could probably
be improved so it would still work even if some minority of the candidates 
refused to cooperate or actively faked everything. Still, even then the N&R
system could be defeated if AT LEAST HALF the candidates refused to cooperate.

[Incidentally, the N&R stuff can be implemented with my "range voting" scheme
just as easily as with any other voting scheme.]

"Rebecca Mercuri's Statement on Electronic Voting"
http://www.notablesoftware.com/RMstatement.html
claims that electronic voting would be a disaster opening the
floodgates to vast manipulation and cheating.  However, most of Mercuri's
specific claims are in fact mathematically false as the N&R paper showed.  

Examples of Mercuri bogus statements:
1. "Fully electronic systems do not provide any way that the voter can
truly verify that the ballot cast corresponds to that being recorded, 
transmitted, or tabulated." False: N&R shows how.
2. "Electronic balloting systems without individual print-outs for 
examination by the voters, do not provide an independent audit trail."
False, N&R shows how.
3. "There are no required standards for voting displays, so 
computer ballots can be constructed to be confusing..."
True, but it would be easy to make such standards. This is hardly
an obstacle.
4. "Electronic balloting and tabulation... removes any opportunity
to perform bipartisan checks." Completely false, N&R show how.
5. "Encryption provides no assurance of privacy or accuracy of ballots cast.
Cryptographic systems, even strong ones, can be cracked or hacked..."
Mathematically speaking, this is almost certainly false.
6. "Off-site Internet voting creates unresolvable problems with 
authentication, leading to possible loss of voter privacy, vote-selling, 
and coercion."  False: N&R show how to protect privacy and abolish coercion
and vote-selling even then.  There is, however, an on-site pre-election
"registration" of voters which could be done arbitrarily far ahead of time
over an arbitrarily long period.

Nothing like the N&R system is commercially available now, of course, 
but it might be constructible.  Basically I think Mercuri has
the viewpoint of a commonsense person who knows a lot
about what systems are commercially available and how well they
work in practice. But at the same time, I think she has a low
level of understanding of cryptography algorithms like the N&R paper
and a kind of Luddite distrust in cryptography.  In fact, the
cryptosystems used in the N&R paper can be proven to be unbreakable 
unless certain mathematical tasks (such as factoring large integers)
are easy.  I think the likelihood these systems can be broken is so incredibly
tiny it should have no impact on Mercuri's arguments.  I think it more
likely, for example, that Mercuri is a robot manufactured by aliens
from another planet, than that some strong cryptosystem 
such as AES will be broken.

I had written a long email to N&R critiquing their paper, which they 
never replied to.  I had also pointed out to Mercuri that her claims 
were overstated, and she e-corresponded with me for a bit, but she 
appears to have forgotten what I said, if her "Statement" is any indication.

If people like Mercuri were to stop burying their heads in the sand
and instead work toward trying to incorporate N&R-like algorithms into a 
real-world electronic voting system, then progress would likely be made.

---