User:Cacadril/Secret-ballot receipt

Secret-ballot receipt (SBR) is a voting system invented by David Chaum in 2004. It allows voters to take home an encrypted copy of the ballot, which the voter can use to verify that it has been included in the tally. The system was the first that offered end-to-end auditability while still ensuring voter anonymity. The system does not offer absolute guarantees against voter fraud, but offers strong probabilistic proofs of integrity.

Usability

While it is hard for ordinary voters to understand the cryptographic techniques behind the proofs, it is easy to cast a vote. Compared to an ordinary system that uses a touch-screen ballot recording machine (DRE) and generates a voter-verifiable paper ballot, SBR at first sight only differs in the following ways:

• The ballot that comes out of the printer has two layers.
• The voter must respond to a question about which layer, the top or the bottom layer, she wants to take home.
• The voter then separates the two layers before leaving the booth.
• The voter surrenders the layer not chosen to an officer.
• The voter takes home the chosen layer.

Some confusion may arise from the following:

• When the layers are separated, the text of the vote seems to disappear. The layers still contain some codes, including a marks indicating which layer to take home.
• Where the ballot box used to be, there is instead a shredder. The officer that receives the layer not chosen, will check that it is indeed not the chosen layer, and will drop it in the shredder while the voter looks on.

How it works

The two layers use [visual cryptography] to show the contents of the vote while the two layers are together. When the layers are separated, the text disappears leaving behind a gray area. However, on closer inspection the gray area consists of alternating black and white dots that encode an encryption of the vote. It is straightforward for any computer programmer to program a computer to extract the encrypted ballot data from an optical scan of the layer. In addition to the visual cryptography, there are some additional codes on the layers that do not disappear. The additional codes include a serial number that identifies the ballot.

The DRE machine keeps an electronic copy of the same layer that the user takes home. Alternatively, the DRE machine can be made memoryless, and the selected layer can be optically scanned while the other layer is shredded. In either case, complete contents of the selected layer is later posted on a web site where the general public can download all the encrypted ballots in order to participate in the verification of the election.

-- Trustees --

Before election day, a number of trustees have been appointed to participate in the decryption of the ballots. The trustees should be all manner of independent organizations with sufficient resources to handle the data volumes, and with sufficient credibility that they are unlikely to drop out before the tallying is completed. They should represent different interests in society, so that it becomes highly unlikely that they would all collude to falsify the results.

Each trustee separately and privately generates a pairs of encryption and decryption keys. The encryption keys are published to the world before the election starts, while the decryption keys are kept secret. Even the election authority should not have access to the decryption keys.

-- Tallying while securing voter anonymity --

The DRE machines use the trustees' published encryption keys to add layers of encryption to each ballot. For the tally, the ballots must be sent to all the trustees, one after the other, to have the layers of encryption removed. Each trustee receives batches of encrypted ballots in some order, decrypts them and passes them on in a different order. Only the first trustee knows the IDs of the ballots it receives, but this trustee cannot read the votes because even after removing one layer of encryption there are several layers left. The next trustee receives the ballots in a jumbled order, and can therefore not know which ballot belongs to which ID. This trustee again removes a layer of encryption, and permutes the order again before passing the resulting batch on to the next trustee. The final trustee will remove the last layers of encryption and post the results, the clear-text ballots to the Internet. Then the general public can download the complete set of ballots and count them on their own computers.

Verification of the tally

All trustees must publish to the Internet the batches they receive and the batches they produce. The correctness of the trustee operations are verified as follows.

When the ballot is encrypted by the DRE, an extra piece of data is included before encryption. When the trustees decrypt the ballot this extra piece is recovered. Without this extra piece, nobody else can repeat the encryption to verify the correspondence between the input and the output of each trustee.

Each trustee executes two rounds of decryption and order-jumbling. The intermediate batch is also published along with the trustee's input and output batches. After all batches are published, the election authority selects randomly one half of all input ballots, using a method similar to a national lottery. The method must ensure that the selection is not predictable and has not been secretly agreed on beforehand. Now the trustee must reveal and publish the complete outcome of the decryption of the selected ballots together with their new positions in the intermediate batch. This allows the general public to repeat the encryption, since the encryption keys are public. In this way the general public can verify that the selected ballots are present in the intermediate batch, correctly decrypted. If the decryption was incorrectly executed, then, when the public repeats the encryption, the results do not match the selected ballots in the input batch.

In the intermediate batch, half the ballots have been checked against the corresponding input ballots. The other half of the intermediate batch is then checked against the output batch in the same way. The trustee must reveal and publish the exact results of the decryption and their positions in the output batch.

In spite of these revelations, other than the trustee, nobody else can know which ballot in the output batch corresponds to which ballot in the input batch. For example, if ballot number three in the input became ballot number twelve in the intermediate batch, and then became number seven in the output batch, only one of the connections three to twelve or twelve to seven is revealed. If three is among the ballots selected for checking in the input batch, then the link three to twelve is revealed, but then ballot twelve in the intermediate batch is not selected for verification in the second round.

Since no ballot can be traced back from the output batch to the input batch, the anonymity of the voters has been preserved. In order to break this anonymity, a collusion would be needed with participation of all the trustees. If only one trustee refuses to collude, voter anonymity is ensured.

Possible attacks and its defenses

It is a property of the visual cryptography that for any given single ballot layer, it is easy to construct a second layer that, when placed over the first layer, shows any desired image. In the present scheme, both layers must contain an encryption of the ballot, and additionally possess the visual cryptographic property of showing the clear-text ballot image when the two layers are combined.

Suppose the voter voted for Mickey Mouse. Then the two layers of the printed ballot must show the name "Mickey Mouse" when combined. But a malicious DRE can create a layer that contains an encrypted ballot with a vote for Donald Duck, and construct a second layer such that combines with the first to show the name "Mickey Mouse". But the second layer can not at the same time contain any valid encrypted ballot. If the voter choses to keep the layer with the encrypted ballot, the DRE will have successfully changed a vote for Mickey Mouse into one for Donald Duck. However, if the voter choses the second layer, the fraud will be detected as soon as the layer is examined.

If the DRE can know which layer the voter will chose, the DRE can cheat. For this reason, it is important that the voter does not reveal to the DRE which layer she prefers until after the ballot image has been printed on both layers.

The voters should be educated to report it if the DRE asks about which layer the voter wants to take home before both layers have been committed to printer. On the other hand it is not necessary that all voters actually are vigilant. If an election is to be subverted, most of the time several thousands of votes must be stolen. If only a few percent of the voters do report such irregularities when they happen it will become plainly evident that the DRE has been improperly programmed. If the DRE only plays this game against a subset of the voters, it is still very unlikely that it can chose thousands of voters and not chose any of those who are vigilant.

The receipts also contains a digital signature made with a secret signing key contained in the DRE. It is the responsibility of the election authority to preserve the security of this key. If a receipt shows up in the wild after the election day with a valid signature and a bogus contents, there are only two possible explanations: Either the DRE does produce bogus receipts or somebody else does, who has access to the signing key. In either case the election authority has failed and is to blame.

The trustees can replace valid ballots with ballots containing votes for a particular outcome. But the election authority selects half the ballots for control in each round. If a bogus ballot is selected, there is no way it can be re-encrypted to match the input ballot. Both the input, intermediate, and output batches are published before it is decided which ballots to check. The output batch of one trustee is the input batch of the next trustee. No trustee can publish an input batch that differs from the published output batch of the previous trustee. This means that the probability of detection is 50% for each stolen vote. Since thousands of votes must usually be stolen to affect the outcome of the election, the likelihood of this not being detected is less than 2^-1000, indistinguishable from zero in practical terms.

Cryptographic details

Different data are used for the top and bottom layer of the printed ballot. In the following we use the superscript t or b to indicate which layer an entity will be used for.

Before the election, the election authority decides on signature functions S^t, S^b, O^t, and O^b. The inverses of these functions are published so that everybody can compute e.g. q when s^t(q) is given.

The election authority selects four hash functions h^t, h^b, H^t, and H^b. The latter two produce matrices of m by n/2 bits (see below).

The election authority appoints k trustees who each publishes its encryption function e_l, l = 1, ..., k.

Each voter or each ballot receives a serial number q. The DRE computes two digital signatures from this number, s^t = s^t(q) and s^b = s^b(q). These signatures are used as seeds to produce "one-time pads" for the encryption of the ballot image. There are four one-time pads for each trustee l, one for each layer (t or b) and mix round (1 or 2),
P^t_l,1 = H( d^t_l,1 ), where d^t_l,1 = h( s^t, 2l-1 ),
P^b_l,1 = H( d^b_l,1 ), where d^b_l,1 = h( s^b, 2l-1 ),
P^t_l,2 = H( d^t_l,2 ), where d^t_l,2 = h( s^t, 2l ),
P^b_l,2 = H( d^b_l,2 ), where d^b_l,2 = h( s^b, 2l ).

The one-time pads for one layer are combined to form the "white" bits, W^t = P^t_l,1 + P^t_l,2 + ... + P^t_k,2 and W^b = P^b_l,1 + P^b_l,2 + ... + P^b_k,2 where the addition is bitwise modulo 2, so that 1+1=0. In other words, the addition is a "xor" operation.

The arguments to the H function are encrypted in messages to the trustee, using the trustees encryption key. In the message to trustee number l is included the the encrypted message for trustee l-1, which contains the encrypted message for trustee l-2, etc. The messages for trustee one contain just the arguments to the H function. These messages will allow the trustees to decrypt the ballots by recomputing the one-time pads.

The messages, called "dolls", are
D^t₁ = e₁(d^t_1,1),
D^t₂ = e₁(d^t_1,2, D^t₁),

D^t_2l-1 = e_l(d^t_l,1, D^t_2l-2),
D^t_2l = e_l(d^t_l,2, D^t_2l-1), for l=2, ..., k, and

D^b₁ = e₁(d^b_1,1),
D^b₂ = e₁(d^b_1,2, D^t₁),

D^b_2l-1 = e_l(d^b_l,1, D^t_2l-2),
D^b_2l = e_l(d^b_l,2, D^t_2l-1), for l=2, ..., k.

At the DRE, the voter first prepares a ballot. The DRE then prepares a ballot image as a grid of m by n pixels. We shall denote this image by B. The image must have sufficient resolution so that if one of every two columns of pixels is deleted, the remaining pixels still represent the voter's choices unambiguously.

From this image the DRE produces two reduced images B^t and B^b, by deleting pixels whose coordinates add to an odd or even sum respectively. That is, if the image's pixels are

EOEOEOEO
OEOEOEOE
EOEOEOEO
OEOEOEOE

then the two reduced images are

EEEE              OOOO
EEEE              OOOO
EEEE     and      OOOO
EEEE              OOOO

respectively. Then B^t and B^b each have m by n/2 pixels. I shall write B^t = even(B) and B^b = odd(B), and conversely B = interleave(B^t, B^b).

The value of a single pixel is 0 or 1.

The DRE then computes
L^t = interleave(B^t + W^b, W^t), and
L^b = interleave(W^b, B^b + W^t)

Now observe that B^t + W^b + W^b = B^t, B^b + W^t + W^t = B^b, and therefore L^t + L^b = B.

The DRE prints bar-code representations of the numbers q, D^t_2k, and D^b_2k on both layers. Then it prints the images of L^t and L^b on the top and bottom layer respectively, using pixel representations described in the article about visual cryptography. Then the DRE asks the voter which layer she wants to keep, and prints. Finally the DRE prints on the chosen layer the bar-code representation of the numbers s^c and o^c(L^b, q, D^t_2k, D^b_2k, s^c).