Chaum's "Scantegrity" secure-voting concept

In 2007, David Chaum introduced an interesting new way to achieve secure voting. We are going to explain his core concept but omit the precise details. That is partly because we are not sure (and maybe even Chaum himself is not sure – we doubt his concept has reached its final form) what is the best way to handle those details and what the ultimate limits of this concept are.

We suppose there are N voters. Chaum's idea is that the government needs, essentially, to create (and publish for all to see) a "zero knowledge proof" that it did the vote-counting correctly. Here is that proof. Make two columns each containing N sealed envelopes. There will actually be four N-entry columns:

1. the N voters (names & addresses & "ID numbers" publicly posted).
2. lefthand column of envelopes.
3. righthand column of envelopes.
4. The N votes (publicly posted; anybody can total).

Initially, all envelopes are sealed shut and their contents are invisible. (The "envelopes" could be physical containers, or also could be implemented with crypto techniques.) All four columns are laid out publicly visible:

The kth envelope in the left column, is associated with voter k.

The two columns of envelopes (and the votes) all are randomly ordered (and nobody knows the order) with respect to each other, preserving vote privacy.

Suspicious voter #i can check that her vote seems ok in envelope #i in the left column, by demanding the envelope be opened. The contents of envelope #i do not reveal her vote but do reveal her ID number (which the voter has a receipt of and/or which could be publicly posted in column 1 under her name). If there had been fraud, this number probably would have been wrong. Also, opening envelope reveals a pointer to j, the number of the corresponding envelope in the right column. This envelope does contain voter's vote.

We could even allow a protesting voter to insist on opening the second envelope too, which verifies her vote was correctly counted but breaks her privacy. (Chaum also has additional tricks to try to preserve voter privacy even then, but we won't discuss.) The second envelope contains the vote and a pointer to k, the number of the corresponding vote in the rightmost column, but does not contain the voter's name or ID number.

After protest rounds ended and protests resolved, we verify the election: Scrutineers randomly flip coins to choose half of the lefthand column of envelopes and open them in public view.

Then, all the envelopes in the righthand column which are not pointed to by the opened lefthand envelopes, are opened in public view.

We then verify all the left-envelopes that were opened, genuinely correspond to the exact voter in column 1 by checking ID numbers match. (Or scream fraud.)

We then verify all the right-envelopes that were opened, genuinely correspond to the exact vote they point to in column 4. (Or scream fraud.)

Finally, we note that every opened left-envelope genuinely corresponds (via pointer) to exactly one right-envelope and vice-versa. (Or scream fraud.)

Now if there were more than a constant number of votes worth of cheating (i.e. vote-altering or bogus pointers) then with overwhelming probability, at least one of these checks would have failed. (The probability you can fraud 10 votes without detection, is 1/1024.)

Also note that since no 2-envelope chain is opened, we never break voter privacy and hence votes cannot be sold.

The key question in Chaum's scheme is: how does the government create those magic secret envelope correspondences in the first place? In such a way we all can be confident no cheating happened? There are many approaches to try to do that. I'm not sure which is best and I'm not going to discuss them here. (Chaum himself has a scheme based on ballots with tear-off parts and preprinting creates the correspondences... but I see no reason that is the only way to do it, and in fact it has some disadvantages such as worries about corrupt printers.)

Advantages of Chaum scheme:

• Works with any voting system (provided votes not "uniquifiable")
• Easy for voters. Just vote normally.
• No particularly magic trusted machines seem needed like with Rivest-Smith schemes.
• Can be done either with crypto or without crypto.
• Pretty simple and easy to explain core idea (not as simple as Rivest-Smith, but pretty simple).
• Like Rivest-Smith, you can estimate the magnitude of fraud, not just lamely say "it existed" or "not".

Disadvantages(?):

• Rivest-Smith had "mix in" easy-upgrade property allowing gradual transition from insecure to secure voting with "contagious protection" of the old-style votes. I do not see a comparably nice property for Chaum - which may kill its viability in USA practice since it'll never get adopted.
• With Chaum, the government maybe can break voter privacy en masse by opening all envelopes. Can we stop that? What is the status? Not totally clear to me yet...
• With Rivest-Smith, there are ways (although it does not work as well as we'd like) to try to track down fraudsters. It isn't just "there was fraud, we have to die now." It is "we can actually try to track down whodunit and punish them." That is important. Chaum does not seem to have that ability at all(?).

However, it is early days. It may be these Chaum "disadvantages" can be overcome. Maybe you can be the one to do that. It's definitely an interesting and promising approach.