ArendPeter commented 2 years ago

We've had several discussion on how to setup our databases in a way that maintains user privacy, and I thought looking into STAR-Vote (Secure, Transparent, Auditable, Reliable) could be relevant as a case study

What is STAR-Vote (Secure, Transparent, Auditable, Reliable)?

The STAR-Vote project (same name, completely different organization), focuses on how to manage ballots in a hybrid physical/electronic election instead of the voting method https://www.youtube.com/watch?v=Cl8q_356zZs (description starts at 34:23)

Their method has come up a few times in Slack conversations, and it could be a good opportunity to collaborate and take advantage of the naming overlap https://starvoting.slack.com/archives/C9U6425CM/p1635474100035800 https://starvoting.slack.com/archives/C01EBAT283H/p1616783581154400?thread_ts=1616684618.142400&cid=C01EBAT283H

Here's a case study of how their STAR-Vote system works, and which pieces can apply to our online system

How does it work?

TLDR: The votes end up getting stored as a physical ballot, and an encrypted version on the voting terminals. These versions can be compared later for auditing

Registration

When the voter goes to the physical voting location they start at the registration system. Here their voting status is validated, and their name is crossed off from the online database

This is the ONLY ONLINE step, the rest of the steps are done on an offline network. The user gets a receipt (with a precinct id and a bar code) to be used in the following steps which validates that they were registered. The receipt only encodes the precinct, no other voter specific information is included

Voting Id: At this point they also checked the voter's id, but this is specific to the Travis county election rules rather than the STAR system it's self

Why precinct id?: Travis County allows voters to choose any voting station rather than being limited to their precinct, so this information is important for the later steps

Auth

At the controller machine the voter delivers their receipt and a volunteer scans it, gives them a one-time use printed auth code

Voting Terminal

At the voting terminal, the voter will input the auth code, and begin voting. Once they've finished, an encrypted version of the vote is stored on the machine, and a printed copy is made for the voter

Ballot box

The voter submits the printed ballot to the ballot box, and the vote is not officially counted until it's been stored in the ballot box

The ballot box scans the bar code on the ballot, it communicates with the voting terminals. If a duplicate ballot is given the ballot box will reject it

Ballot Receipt

Once the ballot is accepted the ballot box will provide a receipt to the voter. The voter can then use this to verify that their vote was counted in the final election. Specifically they could use it to look up their encrypted version of the vote, and verify all the properties covered in the cryptographic section

Cryptographic properties

The encryption process of the voting terminals allow for several different operations

No ballot stuffing: In theory an evil machine could store a ballot as having 100 votes for a candidate. A NIZK (non interactive zero knowledge) proof is used to show that every ballot is valid (0 or 1 for each candidate, with the sum of the candidates equal to 1).
Encrypted Totals: The encrypted ballots can be public (I think), and the encrypted totals can be publicly computed. However the total can only be decrypted by election officials (trustees) with the decryption keys. At that point they also provide a NIZK proof to show that the total was actually computed from the encrypted total
Multiple trustees: A group of n people are considered trustees (chair of republican party, democratic party, league of women voters etc). The encrypted votes can only be decrypted if k of the n trustees cooperate (more details)
Hashing chains: Ballots are encrypted with a hash of the previous encrypted ballot. This makes it really clear when people have tampered with the ballots because it breaks the history
Voting Terminal Verification: Cast ballots can't be viewed (because privacy), but spoiled/challenged ballots can. A voter and get a printed ballot from the voting terminal, and then challenge the ballot to view the encrypted version and verify that the plaintext matches
Risk limiting audits: After the election, the results can be audited using a process called SOBA. Here election officials can decrypt individual ballots and validate that they match the paper ballot. Statistically they would only need to sample a small percentage of all the ballots

Would NIZK work for a STAR ballot?: Yes I think so. A Star ballot would relax sum constraint (we don't care about the sum of all candidates on the ballot), and then checking that each candidate only got 0 or 1, it would use a zero knowledge range proof to verify that each candidate was rated 0-5

How does this apply to our system

Here's some correlations with our system

Registration: This represents keycloak for authentication + the voter roll table for determining which elections they're eligible for
Separation: We're keeping the ballot data themselves separate from the voter roll table (similar to how there's a physical separation between the online registration section that connected to the internet, and the offline voting area)
Ballot storage: We're only storing the ballots electronically, we don't have paper ballots

Action Items

If we wanted to make our system more like STAR-Vote (Secure, Transparent, Auditable, Reliable), then we could try the following

Encrypt Ballots: At the moment we're storing the anonymized ballots as plaintext, but we could instead encrypt. This would make it harder for a rouge web admin to tamper with an election
Trustees: If we use their encryption system then we could provide the option to delegate election trustees with keys for decrypting the ballots
Receipts: Offer the voter a receipt so they can access their encrypted ballot and verify the cryptographic properties
Challenge Ballots: Allow users to challenge ballots and verify the results instead of casting them

Would voters still be able to see how they voted?: All of the above would be optional features, and many of them come with a usability trade off. More casual elections would probably want voters to view or even change their vote, so we'd want to keep that option open for those who want it

mikefranze commented 2 years ago

Excellent writeup!

Something I'd thought of earlier was using hashing chains which could be used with or without encrypted ballots. You'd store the ballot data, previous ballot's hash, and a hash of ballot data+previous ballot's hash. The hash can be provided to the voter as a receipt. To verify the results you just need to check that the hashes are valid and the history is unbroken and voters can look up their ballot with the receipt.

Also a relevant xkcd =D