Verifiable election (P36)

Ballot is an election where the server never sees a vote. Each ballot is encrypted in the voter's browser, the server adds the encrypted ballots together, and the trustees decrypt only the total. Anyone can check the whole election afterwards from its public board without learning a vote.

The curve

The cryptography is written for this prototype in plain JavaScript with BigInt, with no dependencies. The curve is NIST P-256, the curve WebCrypto offers and most TLS connections use.

Ballot has its own arithmetic modulo the curve's prime, points in Jacobian coordinates, addition and doubling, and scalar multiplication with a 4-bit window. The window does the same doublings and additions for every scalar. A precomputed table makes multiplying the generator fast. Points are written in SEC1's compressed and uncompressed forms, and a point that is not on the curve is refused when it is read.

A second generator h is made by hashing to the curve. SHA-256 of a fixed label and a counter gives x, and Ballot takes the first counter whose x is on the curve. Since x comes out of a hash, nobody knows how h relates to the generator.

A ballot

A ballot holds one encrypted number per candidate: 1 for the voter's pick and 0 for the others. Each number is encrypted with exponential ElGamal under the election key. Adding two ciphertexts adds the numbers inside them, so the server can total the ballots without opening one.

The browser adds zero-knowledge proofs to each ballot, made non-interactive with Fiat-Shamir over SHA-256:

• a disjunctive Chaum-Pedersen proof that each number is 0 or 1,
• a proof that the numbers add up to exactly one,
• a Schnorr signature by the voter's code.

Every proof is bound to the election and to the voter's code, so it cannot be copied into another ballot or another election.

Voter codes

A voter code never leaves the browser. It gives a key whose public half is on the election's list. The server checks that the code is listed and has not voted. It cannot change a ballot or make one for a code, because it cannot sign for that code.

The voter's receipt is the SHA-256 of their ballot, worked out in the browser before the ballot is sent. The voter can find it on the public board.

The trustees

Three trustees hold the election key between them, and any two can open the total. The key is made without a dealer:

• A trustee picks a random line and publishes commitments to it, with a proof of its secret.
• It sends the two other trustees a point on its line each, sealed to the receiver's transport key.
• The receivers check those points against the sender's commitments and name a sender whose point does not match.

The election key is the sum of the trustees' first commitments. The secret behind it is the sum of three secrets that stay with three trustees, so the server and each trustee hold one part or none.

To open the totals, two trustees each decrypt their part with a proof that they used their real share. The server joins the two parts by Lagrange interpolation, and the counts come out by searching the small range of possible totals. Every message a trustee sends is signed with its transport key.

The board and the verifier

The board is a log of every event: the setup, the ceremony, each ballot, the close, the partial decryptions and the result. Each entry holds the SHA-256 of the entry before it, so removing or changing an entry changes every hash after it.

The verifier reads only the board and runs eight checks: the chain, the setup and the ceremony; every ballot's proofs and signature; that each code voted once; the total added up again from the ballots; every partial decryption; and the result. Each check reports how many items it checked. The first failure gives its entry and its reason.

Four flawed servers show what the verifier catches. They drop a ballot, change a ballot, add a ballot for a code that is not on the list, or report a wrong total. Each makes every hash after its change anew, so the chain still holds and the deeper checks find it.

How it is judged

The unit tests compare Ballot's scalar multiplication and point encoding with node's P-256 for 313 scalars. They compare the shared x coordinate with node's ECDH for 200 pairs, and the refusal of 80 points that are not on the curve. The verifier page compares Ballot with the browser's WebCrypto.

A property test plays 24 random elections, with different numbers of voters and candidates and different pairs of trustees, and every one verifies. Each flawed server and a trustee who decrypts with a wrong share are caught at every seed.

The limits

Ballot is a demo. No authority has certified it for elections. The vote is in the clear on the voter's device until the browser encrypts it, so malware on that device could read or change it. The person who hands out the codes knows which code went to whom: they can see that a person voted, and the encryption hides the choice from them. Two trustees who work together could decrypt one ballot instead of the total. The prototype has no defense against a voter who is watched or paid while voting. BigInt arithmetic is not constant time.

Previous: Git in the page (P35). Next: Map of Aarhus (P37).