Dave Ketchum wrote:
You claim that many fragments can be done by specialized machines.
AGREED, though I do not agree that they can do it any better than a
normal computer - which has equivalent capability.
In a technical capacity, of course not. Since a computer is
Turing-complete, it can do anything the specialized machines can.
However, and this is the point I've been trying to make, the specialized
machines are simple enough that it's possible to formally prove that
they do only what they're intended to do, and perhaps also to convince
the voters that this is the case.
It's kind of like the difference between physics and mathematics. Doing
tests is analogous to the hypothesis testing of physics: you can say
that this particular machine does not exhibit any flaws that would
compromise security, within some margin of error. However, if the
machines are sufficiently simple, then one can use formal proving to
show, mathematically, that there are no bugs; that the Condorcet counter
will turn ballot records into Condorcet matrices and no more - that the
machine with buttons on it will register votes, register them to the
candidate shown on the display, and no more, and so on.
Now, the analogy is not total. Even a correct hardware system could be
compromised by vendors adding backdoors to their fabrication (going
outside of the spec) and so on, but those errors are much harder to
conceal than simple software tinkering. Even if the software is open
source (as you've stated that you want), knowing the full limits of the
hardware keeps hackers out. The more complex the OS, the greater the
chance that there's a bug: even Linux has had privilege escalation bugs,
although they appear much less frequently than in closed-source
software. What I'm saying here is that if you have to have machines,
have a way of saying to, first, the experts that there is no way there
can be an error, and second (if possible), the same to the ordinary
voters as well.
However, the whole task involves connecting the fragments:
One way is via computer capability.
You seem to be doing without such, so What do you have other than
humans HOPEFULLY correctly following a HOPEFULLY correct and complete
script?
That's right - the links are the weak spots. The script can be devised
just as any programming can be, and it would be quite simple, and
ideally reminiscent of what one does when having a manual count regime.
The PROMs or CDs are the ballot boxes, and they're transported from one
location to another as one would ballot boxes.
That leaves the humans. The humans may do weird things, and the ensured
limits that the specialized hardware would have would obviously not
apply to them. But since the script is simple, various parties can
monitor each other. In the worst case, the transportation and
aggregation parts of the process are as insecure as they would be for
manual ballots.
If that is still too risky, the "ballot boxes" could be numbered and
digitally signed prior to being distributed to the machines for writing,
so that if any are lost or replaced, it would immediately show up as an
error. Such a process would add steps to the script, but I think it'd be
managable.
Consider a general computer. Even for general computers, it makes
little sense to have the district joining software - that counts the
results from various districts and sum them up in the case of a
summable method - on the individual units. As such, the
general-purpose computers are already specialized, only in software
instead of hardware.
???
That was simply intended to show that you don't need the full powers of
a computer. It's convenient, but that convenience can tilt in the favor
of manipulators or hackers as well.
That's true. Maybe a compromise could be using cheap computer hardware
with read-only software, standardized components, and have the
software not be a full OS, but instead just enough to get the job done
and be provable. You'd have to rely on that there are no hardware
backdoors, but the existence of such would be very unlikely, and the
entire thing would have to be put inside some sort of tamper-resistant
enclosure so hackers can't attach keyloggers or do similar things.
Hardware backdoors can be hard to find. Still, if and when one is
found, can there not be an appropriate punishment to discourage such
crimes in the future?
Agreed defense against such as keyloggers is essential.
I still say OPEN SOURCE!
I was thinking more of hardware keyloggers, such as those that look like
keyboard extension cords. Thus the computer should be tamper resistant
so you can't just do these things. Ideally, for the cheap computer
compromise, you'd use a cryptoprocessor (like banks use to keep their
keys, but more general purpose) to run the actual software - perhaps an
IBM 4758, though since I'm not a hardware expert I don't know if that
one is sufficiently powerful to do what you want. Searching the web says
that the 4758 has a 486 inside.
A chip with just enough transistors to do this task. I'm not a
hardware expert, but I think it could be done by the use of a HDL like
Verilog.
The chip needs to be able to find its data.
Yes. For the sake of simplicity, I'll assume a PROM format - a CD
interface would need an IDE translator.
Then the PROM could be set up like this:
header:
uint32 number_of_candidates
then, for each ballot
uint32 rank_number[number_of_candidates].
which means that if rank_number[0] < rank_number[1], then candidate 0 is
ranked ahead of (better than) candidate 1.
Then assume that addresses contain 32-bit values. That is, you have
something like
0 1 < address
12345678901234567890123456789012 123456... < bit
First read off address 0. This gives you the number of candidates. Then
for addresses 1 to number_of_candidates, inclusive, do the Condorcet
counting algorithm. After you're done, go to address 1 + (number of
candidates) to count the next ballot. Repeat until all ballots have been
counted.
No matter what you do, errors can happen. Proper target is to minimize
them, which I claim can best be via using computers for what computers
can do well.
I think you can minimize further by removing the slack that could be
used for trickery, as you can't twist something that isn't there. Hence
my idea.
I'll grant the point, though, regarding malicious machines. If the
entire standard is public, and the machines can be rigorously tested
to be sure no tricks are being done by the manufacturers, then
deliberately malicious holes should not exist. I still hold that one
should engineer defensively and as simple as possible, so that the
system is transparent to as many people as possible, and so that bugs
either are fixed very quickly or (preferrably) don't have the room to
exist at all.
Looks like what I am trying for.
Simple is a good word, as is defensively.
See above.
I want:
Display completed ballot, for voters to review and redo any
problems.
Record ballot on CD-R.
Open source, so the programs SHOULD be 100% correct.
(Just a note: if the programs are simple enough, one can *know* they
are correct. With provisions for unexpected OS bugs unless the OS
itself is equally simple, and so on.)
When you mention OS, remember my insistence on open source.
Yes, but try proving Linux (which is what I mean by *know*). At multiple
million lines of code, that's going to be quite a task.
The compromise option could have an open source software system that is
simple enough, and thus would get around the problem. It wouldn't be a
traditional OS, though (but perhaps it would lead to a formally secure
microkernel, something that would be very interesting in "ordinary" OS
development as well).
Granted, if the machine isn't hacked due to an unexpected bug.
Printout-based machines could be useful even if we have provably
correct machines (strongest sense of security) if the voters are very
distrustful. Counting only based on the printout ensures the voter
that nothing fishy is going on - because nothing fishy *can* be going on.
Our sorry history justifies distrust.
I DO NOT like printout-based machines. To start some thinking, how about:
All machines have identical valid code,
Some have video cameras recording the ballot as the voter submits it.
Voters choose which machines to vote on.
Audit that tapes prove 100% correctness of those machines taped -
BETTER be.
If you use this in real elections, be prepared for voters with privacy
complaints. If you let the voters decide which machine to use, the great
majority would use the untaped ones. Also, the cameras would add to the
cost of the machine. If the videotape is publically available or it's
possible to identify voters, that could leak information to vote-sellers.
If you use it for verification purposes only, you have to be sure that
the voters don't act differently than in the real election (so the test
is representative). I suppose you don't need exact correspondence since
"probabilistic flipping" algorithms would easily be detected, but it
would fail to catch things like election-day hacking.
In any case, instead of using a literal tape, I think you'd have to
record the video on a write-once storage medium so that it can't be
tampered with afterwards. You would have to compress the video stream
very heavily to fit.
What, in your opinion, is the problem with printout-based machines?
Use a LED with a photoresistor on the other (logging machine) end. No
data can move from the voting machine to the logging machine, and so
would reduce complexity significantly. Or have two in different
colors, one of which is always on to detect broken cables.
There'd still be some code to verify, though: make sure that the
voting machine don't leak ballot data to the logging machine, for
instance.
Oops, that should have been "No data can move from the logging machine
to the voting machine". Of course data would have to move from the
voting machine to the logging machine, or there would be nothing to log.
----
Election-Methods mailing list - see http://electorama.com/em for list info
