• flickr
  • twitter
  • facebook
  • delicious
  • Google Buzz

25C3: eVoting after Nedap and Digital Pen

by Christian Scholz on December 29, 2008

or “Why cryptography does not fix the transparency issue”, held by Ulrich Wiesner.

25C3: eVoting after Nedap and Digital Pen

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.

Why eVoting?

They say:

  • 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

Better reasons:

  • 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.

Other issues:

  • 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

Cryptographic Solutions

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
  • more..

Problems:

Can verification that my vote is counted as cast replace verification of the whole election?

No, because

  • 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.

More issues:

  • 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.

Fundamental concepts

Mix Nets (D Chaum 1981). IN elections you have keys which permute your initial votes. Those individual keys can be controlled by individual people.

25C3: eVoting after Nedap and Digital Pen

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

Punchscan (2006)

25C3: eVoting after Nedap and Digital Pen

  • 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
Coercion attack:

  • 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!

25C3: eVoting after Nedap and Digital Pen

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…

Bingo Voting

too fast error… preparation phase you prepare something for every voter

Voting phase
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.

Issues:

  • 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

General issues

  • 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..

Reality problems:

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.

Scutiny

What happens in case of dispute? Who can evaluate the integrity of election
etc.

If this goes to court then this becomes a battel of experts.

Conclusions

  • 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.

Technorati Tags: , , , , ,

3 comments

Contrary to your statement, manual counting of single transferable vote ballot papers is not prohibitive. Manual counts have been used for STV-PR elections in Ireland since 1920 and in Northern Ireland since 1973.

In Scotland conventional paper ballot papers were counted electronically for the STV-PR local government elections in 2007 because we used a version of the STV counting rules that would be more tedious to count by hand although the calculations are trivial.

by Edinburgh Voter on 29.12.2008 at 19:15. #

Well, it's Ulrich' statement. And I think his point was that in some situations it's simply saving work to do it eletronically. It might depend on the situation. Still there are all the general issues around electronic voting and the question is whether it's worth to do more manual work and have a "better" election than doing it the automated but maybe more problematic way.

I think when it comes to the basis of democracy you really should keep things simple and understandable.

by Christian Scholz on 29.12.2008 at 19:59. #

[...] Wie man sich denken konnte, gab es dazu ein wenig Diskussion, denn schliesslich sind die Piraten ja gegen Wahlcomputer. Er wolle aber in seinem noch zu schreibendem Blogpost genauer auf die Unterscheidung Wahl und Abstimmung eingehen. Insgesamt kann man aber sagen, dass es nicht sofort total verrissen wurde. (bzgl. Wahlcomputer empfehle ich noch meine Mitschrift vom 25C3). [...]

by mrtopf.de » Blog Archive » Das PirateCamp on 9.2.2010 at 15:19. #