by Christian Scholz on December 29, 2008
or “Why cryptography does not fix the transparency issue”, held by Ulrich Wiesner.
Voting seemed to be so easy before computers came in but then the Nedap chess computer showed that it wasn’t that easy. Ulrich talks about the solutions and their problems.
Goal: Implement secure and auditable voting computers by using cryptography.
Why is eVoting an issue?
There is a strong community believing that all the issues with those computers are fixable. There even was some media hype around the German IT Security 2008 award for Bingo voting. So everybody now thinks it’s fixed.
He thinks though that it’s not that easy.
Why do we have to deal with eVoting at all?
Voting computers are frequently used in polling stations, e.g. Netherlands had nearly 100% coverage but it has been stopped thanks to Rob. Ireland had 100% but never used, Belgium 40%, discontinued, France 5%, growing, Germany 5% but federal constitutional court decision pending about usage.
Internet voting is also used in some countries, e.g. Estonia since 2006, now even looking into mobile phone voting.
Some countries are discussing or trying it.
What not is it an issue?
Election principle: verifiable, transparency and secrecy
Secrecy: protects free elections, choice has no personal consequences, Vote can not be sold
Auditability: Measure of QA: identify and correct errors, typeically conducted by authorities but can never replace Transparency
Transparency: Ensures that election is conducted according to regulations and principles and that everybody can verify this. It creates trust, prevents denunciation of the results and cannot be delegated to authorities because this would take the right away from everybody
Implementation of Transparency
Transparency of elections is mandatory for all OSCE member states.
Different approaches in different country:
- Germany: anybody can, no passport required, no country residency required
- Austria: Participating parties can nominate two election witnesses per polling station
- UK: similar to Austria but individuals and organisations can register for observation
What is the problem with eVoting?
Paper based election: white box, the input is the output, it’s a passive device. If nobody tampers with the box then you can trust the result.
eVoting device: Black box (from voters view). You have a secret input, it’s an active device, output might be input but processing is not observable. So input and processing is not available, how can you check the output? So in order to do that you need to lift the secrecy a bit and look at the input to check if the output is generated properly.
- because it’s cheaper (but questionable and even then no reason to tamper with it)
- Because we’ve already spent the money on the equipment
- Because it saves 1 hours of counting
- Multi-vote elections (cumulative voting) could be implemented. E.g. one vote per council member, migth be 50+ votes per election
- Preferential system would be possible, a single transferable vote
- Manual counting can be prohibitive in such situations
But what does it help if you cannot check if the results are correct.
Keep Physical Copies?
Sounds like an easy solution, like having a paper trail or scan them.
Paper Trail, Digital Pen was introduced in Hamburg. Allows validation of result independant of voting device.
But: What triggers the recount? When and where is the count conducted? Who stores the paper trail until the recount happens?
Paper Trail can fix the auditability issue but will typically not fix transparency
Defeats the business case
And if recount is restricted to a sample? Like in Hamburg it was 1.5% of polling stations to proof correctness once and forever.
But: Sample needs to be truly random, Sample size needs to be dependent on outcome and which sample size ensures a high probability tp detect fraud? Easy for 2 candidates but difficult in multi-party/multi coalition scenario. Esp. with e.g. a 5% threshold to get elected a few votes can decide.
- What if the electronic and audit result do not match? Hamburg decided that the electronic results should then be binding? Defeats purpose!
- TEMPEST proof printers? Difficulty to protect secrecy of vote
- Printers fail or create paper jam. Mainly concern of vendors
Wouldn’t this be easier?
Idea: Use enryptography to ensure election integrity. Provide the voter with an encrypted receipt. Allow voter to verify that his vote is cast as intended etc.
There have been lots of proposals over the year.
What all have in common:
- Ballots have unique id (random/serial)
- Voters receives a receipt
Can verification that my vote is counted as cast replace verification of the whole election?
- does not protect against ballot stuffing
- does not allow external observers
- How many voters need to cooperate to unveil fraud?
- Who protects the encrypted votes from decryption? Is my vote really secret? Who controls/protects the encryption keys?
- Who ensures that the receipt is just issued to a single voter? Give same serial number to multiple voters?
ThreeBallot (Ronald Rivest, 2005)
Ballot paper has three columns (‘ballots’). Choosen candidate is marked twice, other candidates are marked once
Step 1: Mark every row randomly
Step 2: Mark your choice twice
Step 3: a “trusted” checker machine ensures that the voter has submitted a valid ballot
Step 4: then you select one row to take home, the other rows are put in the box.
Step 7: Votes are counted as usual
Step 8: Compare receipt with published ballots
Receipt alows to verify that the ballot has been counted as cast, but does not unveil the choice of the voter.
It’s not a cryptographic solution, it’s not coercion free.
- Requires serial numbers being secret and truly random (puts secrecy of election at risk)
- Requires trust in checker/carbon copy algo
- Extremely user un-friendly approach
- Might enhance auditability. If nobody complains, voting organisation can be confident that everything went ok.
- Does not enhance transparency.
Mix Nets (D Chaum 1981). IN elections you have keys which permute your initial votes. Those individual keys can be controlled by individual people.
Randomized Partial Checking (2002). You check the bits in a middle row and check if either the left side is ok or the right side. You only need one key for this because you cannot check both sides.
Now some math which I will skip here… :) (but he does sort of as well but then not really.). ai mod p. This creates a pseudo random permutation, to google: Petersen Commitments
- Two superimposed sheets
- Voters receive individual sheets with codes next to each candidate
- Candidate codes on bottom sheets are isible through holes on top sheet
- Voters mark selected candidate in the lower fields
- Then you take one home.
- Receipt is scanned, other half is destroyed
- All receipts are published on a bulletin board
- Permutations are validated through Mix Net / Randomized Partial checking
First version was not protected against coercion dependant on sequence of events.
Voter needs to select top or bottom sheet as receipt before the ballot is presented
Had been overlooked by authors in earlier versions
- Bring top layer with “1″ assigned to Candidate A and left hole marked, or
- Bring bottom layer where “1″ appears left and is marked
- Prefers Candiate B at 2:1
This is solved but shows a general issue of all the approaches: Sequence is important!
Scantegrety is a successor.
- Similar concept but on one sheet, random codes next to candidate names, ballot paper is scanned, codes relate dto chosen candidates are published.
- version 2 of it: Only uncover random codes of chosen candidates, easier complaint validation.
So the thing was was presented as a sufficient solution in the first place wasn’t good enough later…
too fast error… preparation phase you prepare something for every voter
voter selects candidate, fresh random number is generated (“Bingo”) and presneted to voter
Machine will print receipt with fresh random number next to chosen candidate, dummy votes next to opther candidates.
too fast error…
With his vote for Candidate A, rthe voter reduces the number of remaining dummy votes for all other voters by 1
too fast error…
Post voting phase
too fast error…
Real World implementation used for student council elections at Karlsruhe university.
Java Code has no docs though and does not compile.
- If the random number is not random, then votes can be stolen
- Transformation of problem: Trust in random number generation rather than trust in voting computer
Real World hassle
Commitments are only binding if shared
Publish commitments separately for every polling station
- Secure Concept does not ensure secure implemenation (e.g. randomness, can never be verified by observer. Good example: Debian OpenSSH implementation)
- What if we find out later that concept or implementation was not secure? You cannot unpublish a bulletin board.
- Even if concept and implementation is “secure” there can be user vs. admin problems, like if the system in the polling station also runs the right version of the software.
- Are there evil implementations of the secure concept which behave the same as the honest one?
- Can I fool inexperienced users?
- Denounciation attack: If you are the authority and you don’t like the result you publish a different bulletin board. too fast..
Lots to mark. e.g. in Werder with ThreeBallot you would have to mark 324 rows once, mark 3 rows twice.
With Punchscan you have 327 holes in random orders
BingoVoting: 327 random numbers
With Frankfurt: 1836 rows, 93 rows marking twice. Punchscan, 1929 holes, random order. Bingovoting: 1929 random numbers to check. check 93 out of 1929 numbers for correctness.
So this is definitely not usable.
What happens in case of dispute? Who can evaluate the integrity of election
If this goes to court then this becomes a battel of experts.
- Core issue is combination of secret input (votes) and black box process
- every attempt to fix auditability and transparency will put secrecy at risk.
- Can cryptography fix it? It’s an academic problem and this is where it should stay!
- Usability decribed is a blocker
- Even if cryptography fixed auditability: Transparency remains issue vecause methods are too complex
- Alice and Bob cannot understand this at all.