[EM] Verifiable secure voting using dual half pixel receipts

[Ken Johnson]

election-methods-electorama.com-request at electorama.com wrote:

>Message: 1
>From: Niemzinski at ecybermind.net
>Date: Tue, 25 Nov 2003 19:42:14 -0600
>To: election-methods at electorama.com
>Subject: [EM] Verifiable secure voting using dual half pixel receipts
>
>The cryptographer David Chaum, through discussion with top cryptographers such
>as Ron Rivest, has designed a secure and verifiable voting system. One of the
>goals of his design is that anyone can verify that votes were tabulated
>correctly.
>
>The article can found in the "white paper" hyperlink at the bottom of the press
>release http://www.vreceipt.com/
>  
>
This is a very clever and interesting idea, but I have some questions 
and doubts about its practicality.

As I understand it, a ballot receipt contains no information about the 
voter's identity, which only becomes potentially knowable when the voter 
presents the receipt for validation/verification. But how would the 
process verify that only legally registered voters have voted, and that 
no one voted twice? I don't quite understand the basis of the claim that 
"...it can lift the requirement that voters must vote from their home 
precinct ... inter-jurisdiction voting becomes workable ...".

I question whether a method with this level of technical sophistication 
and complexity would be practical or whether voters would trust the 
"mathematical magic" behind the secure encryption scheme - especially in 
emerging democracies where most voters may be barely literate, much less 
computer literate or technologically literate. One particular weakness 
is the reliance on a small number of "trustees" - holders of the private 
encryption keys - to ensure voter secrecy. The trustees might have the 
highest level of professionalism and integrity, but probably not much 
technical sophistication or understanding of cryptography, so you might 
find someday that a hacker has gotten hold of the private keys and 
posted them on the Internet, along with all of the decrypted ballots.

Following is an outline of a comparatively "low-tech" voting process 
that I think probably accomplishes the same objectives as Chaum's 
method, while overcoming its weaknesses. (Whether it actually does, I 
pose as an open question.)  This process has the following properties: 
(1) The vote tally for each separate ballot issue is generated 
automatically from a single cumulative database (one database per issue) 
- there are no no manual counts or precinct-level subtotals. (2) The 
vote tally can be independently and provably verified, beyond reasonable 
doubt, to be correct based on the original printed ballots, and the 
verification process is simple enough that it can be easily understood 
and implemented by election officials or independent auditors and can be 
applied as part of routine election certification processes. (3) The 
verification process relies on information and processes that are widely 
distributed among multiple precincts, so the integrity of the system 
could only be compromized through unlikely collusion and fraud on a very 
large scale. (4) Voter secrecy is absolutely guaranteed (i.e., ballots 
are not traceable to individual voters), provided that not everyone in a 
particular precinct votes the same way. (Precincts should be 
sufficiently large and diversified to practically eliminate the latter 
possibility.)  (5) Voter subgroup secrecy is not absolutely guaranteed 
(i.e., the voting profile of a particular precinct, or correlations 
between different voting issues, could be determined from the stored 
ballot  records), although subgroup secrecy could only be compromized if 
precinct-level ballots are recounted or inspected to trace voting errors 
or fraud.

The steps of the process are, briefly, as follows:

(1) Upon entering the voting center, I take a ballot - at random, if I 
choose - from any of several stacks of blank ballots. (At this stage my 
identification has not yet been checked, although a voting official may 
have requested that I display my mailed voting pamphlet to confirm that 
I am registered.)

(2) I take the ballot into a voting booth and fill it out. If a voting 
machine is used, it serves no purpose other than to translate my input 
into a valid printed ballot - it does not count, store, or transmit any 
voting information.

(3) I inspect the ballot for correctness and seal it to mask my voting 
selections. (If the ballot is botched, I have the option of shredding it 
an getting a new ballot.) The ballot contains no information about my 
personal identification, which I have not yet revealed to either 
precinct workers or the voting machine. (If fingerprints are a serious 
concern, voters can wear gloves.)

(4) A precinct worker cross-checks my identification with a voting log, 
has me sign the log, and places a generic, machine-readable stamp on my 
sealed ballot to mark it valid. I am then instructed to put my ballot in 
the ballot box, and after I do so, the worker puts a machine-readable 
stamp in the log as evidence (along with my signature) that I voted.

(5) At the end of the day, the voting log is automatically scanned to 
count the number of logged signatures. (The log can later be inspected 
manually, if necessary, to validate the count and the signatures.) The 
ballots are shuffled and passed through a vote-counting machine, which 
reports the total number of ballots and relays the vote data 
electronically, via secure encryption, to a remote tabulation center. 
(The encryption functions mainly to preserve precinct-level secrecy. 
Individual voter secrecy, and the correctness of the the vote tally, do 
not rely on the encryption.) The counting process does not necessarily 
require that the ballots be unsealed. Mechanisms such as 
infrared-transmitting paper or magnetic ink could make the ballot 
machine-readable through the seal. (The seal basically functions to 
shield the ballot from prying eyes, and would only be broken if visual 
inspection is necessary.) As each ballot is scanned, the vote-counting 
machine assigns a unique, randomly-generated ID number to each voting 
issue on the ballot. The ID's are both printed on the ballots and 
relayed to the tabulation center along with the vote results so that 
each vote on each ballot can be correlated to a corresponding database 
record. The tabulation center constructs separate, uncorrelated, 
databases for the different voting issues. (This is in order to preserve 
voter subgroup secrecy, e.g., you couldn't tell from the databases how 
Schwartznegger supporters voted on the illegal-immigrant issue.)

(6) The tabulation center's computer tallies the votes, and the results 
are submitted for certification.

(7) The tally is verified. The total ballot count is correlated between 
the precinct-level voting logs, the ballots, and the cumulative vote 
databases from which the tally was generated. The correctness of each 
vote database (one for each issue) is verified by first making sure that 
the ID's assinged to the vote records are unique, and then having 
election officials unseal and inspect a random sampling of paper ballots 
to confirm that they are correctly recorded in the database. (The ID's 
are used to correlate ballots to corresponding database records.) The 
required sample size would be quite small - for example, with 10,000,000 
ballots less than 1000 would typically need to be sampled to verify the 
correctness of the database with 99.99% certainty. Independent parties 
such as the press, public-interest groups, and invited international 
observers may participate in the process to provide independent 
verification of the  result.

(8) Assuming the verification tests succeed, the election result is 
certified and published. If not, a more thorough investigation would be 
conducted to trace the source of the discrepancy and, if necessary, 
order a recount or revote.

This kind of process lacks the technological "sex appeal" of Chaum's 
proposed bit-mask method, but I think most voters would perceive this 
type of process to be simpler and more transparent and trustworthy than 
one relying on high-tech "hocus-pocus" mechanisms.

Ken Johnson