Electronic Voting

(Jointly with the Cryptographic Protocols Group)

Seminar, Summer 2010

• 2010-04-20: the topics and some literature are now online
• 2010-04-19: registration is closed

Electronic voting is receiving increasing attention from governments, mass media, and the scientific community. The deployment of electronic voting systems, however, is limited in practice since many open questions still remain.

• How do we ensure that the votes are counted correctly?
• How do we protect the voters from coercion?
• What are the security properties required for a voting scheme?
• And how do we define and prove security?

In this seminar, we will conduct research to provide answers to these and other questions. We will work, in particular, on formal security definitions, analysis techniques, and actual cryptographic voting systems.

Topic I. Symbolic verification of coercion resistance

Different approaches of defining coercion-resistance can be found in the following papers:

• Universally Composable Incoercibility. Dominique Unruh and Jörn Müller-Quade. Preprint on IACR ePrint Archive, Report 2009/520
• A Game-Based Definition of Coercion-Resistance and its Applications. Ralf Küsters, Tomasz Truderung, and Andreas Vogt. Preprint on IACR ePrint Archive, Report 2009/582
• Automated Verification of Electronic Voting Protocols in the Applied Pi-calculus. Michael Backes, Cătălin Hriţcu, and Matteo Maffei. In Proceedings of 21st IEEE Symposium on Computer Security Foundations (CSF 2008), IEEE, pages 195-209

(The latter already performs a symbolic analysis, it might be interesting for comparison with the other definitions.)

If you wish to do an analysis based on the paper by Unruh and Müller-Quade, you might find the following paper helpful, which transfers the so-called Universal Composability framework to the symbolic setting:

• Simulation based security in the applied pi calculus. Stéphanie Delaune, Steve Kremer, and Olivier Pereira. In Proceedings of IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2009)

Examples for voting schemes that could be analyzed are Bingo voting and the other protocols referenced in the following paper:

• Bingo Voting: Secure and Coercion-Free Voting Using a Trusted Random Number Generator. Jens-Matthias Bohli, Jörn Müller-Quade, and Stefan Röhrich. In Lecture Notes in Computer Science, Volume 4896/2007, E-Voting and Identity, pages 111-124, 2007.

Topic II. Randomized voting

Well-known remote voting schemes that you might wish to build upon are Civitas and Helios:

• Civitas: Toward a Secure Voting System. Michael R. Clarkson, Stephen Chong, Andrew C. Myers. In Proc. IEEE Symposium on Security and Privacy, pages 354-368, May 2008.
• Helios (blog, up to version 3), Helios: Web-based Open-Audit Voting (original paper). Ben Adida.

We also found the following on the net, it might be related to the topic:

• Randomized voting and Randomized voting with observers. Gregory S. Warrington.

Topic III. Robust elections

Well-known remote voting schemes that you might wish to build upon are Civitas and Helios:

• Civitas: Toward a Secure Voting System. Michael R. Clarkson, Stephen Chong, Andrew C. Myers. In Proc. IEEE Symposium on Security and Privacy, pages 354-368, May 2008.
• Helios (blog, up to version 3), Helios: Web-based Open-Audit Voting (original paper). Ben Adida.

One building block that might be useful for sharing data in a robust way is Shamir's secret sharing scheme:

• How to share a secret. Adi Shamir. In Communications of the ACM archive, Volume 22 , Issue 11 (November 1979), pages 612-613

Students will work in small groups. Each group will be assigned a research topic. Work on this topic will consist of reading relevant literature, performing original research, and writing a final report.

Each student will additionally give one talk, presenting a particular aspect of the group's research results.

Each group will be directly supervised by Dr. Matteo Maffei and Dr. Dominique Unruh and given the opportunity to regularly discuss their research with the supervisors.

You should enjoy math and theoretical computer science!

In addition, having passed at least one lecture on security or cryptography is a prerequisite of this course.

Since the topics are challenging and require original research, we especially recommend this course to students that obtained very good grades in these lectures.

The registration deadline is Sunday, April 18.

Since the number of available places is limited, we might have to perform a selection based on the students' background. Thus, for registering, please send an e-mail to <fabienne's surname> at cs dot uni-saarland dot de, indicating your name and matriculation number and listing any security-related courses you have taken.