Workshop on Electronic voting

Fall 2010

Contents:

General Information. 1

Schedule. 1

Projects. 2

References. 2

What should be in your Design Document?. 2

FAQ from previous semesters. 3

General Information

Lecturer: Amnon Ta-Shma.

T.A.: Ben Riva.

Lecture Hours: Wednesdays, 10:10-12:00. Location: Kaplun 324.

Schedule

Date
22.10.10	Background – Electronic Voting, Crypto. Detailed description: DLOG, ElGamal encryption, Zero-knowledge proofs. High-level description of other important crypto primitives: digital signatures, symmetric encryption, Mix-nets. Introduction of the Wombat E-Voting system. Projects description. Assigning projects.
28.10.10
01.12.10	Design Presentations
15.12.10	Deadline for submitting interfaces + running time estimation (measured in basic group operations)
20.1.11	Final submission

Projects

Wombat- Smartcards (3-4 students)	A system for smartcards that generates randomness and verifies the booth’s computations.
Wombat- Ballot Verification using Mobile Phones (3-4 students)	Given an audit ballot, scan it and verify its correctness using a regular mobile phone.
Qilin modules (for single students)	Contribute to the open-source project http://qilin.seas.harvard.edu/ one or more of the next modules: · broadcast channels o one implementation using (the existing) p2p channels o second implementation using a semi-trusted bulletin board · generic implementation of the zk proof that the plaintext of some elgamal encryption is from n possible messages (1-out-of-L) · generic implementation of threshold elgamal encryption

References

· Niko’s lecture notes.

· Great summary of the main primitives we use (written by Tomer Levinboim).

· General background

o Links to some US newspaper articles and other sources of information.

· Technical background

o Number theory background: http://shoup.net/ntb/

o Amos Fiat and Adi Shamir: How to prove yourself: practical solutions to identification and signatures problems.

o Ben Riva's thesis.

What should be in your Design Document?

· High-level description

o Description of the problem (the goal)

o Description of the module/system/protocol

§ What it solves and how?

§ External dependencies

· Detailed description

o Design overview

o Main modules

§ What they do?

§ How?

§ Interfaces to other modules

o User interface

§ Main properties

§ Main screens

o Testing

§ Unit tests for main modules

§ Stress tests for modules with complex computations (e.g., a mix server)

§ Human interface tests

FAQ from previous semesters

(answers by Oded Schwartz and Ben Riva):

Q1	Should we describe the ZKP needed in our project?
	Yes.
Q2	What is the coverage of the design (e.g. how many pages are expected?)
	The design should be such that it is clear to us (and to you) what you are going to do. It should be only a few pages long, but it should contain, for each part of your project: - A description of the interface (UI and/or software interface, whichever is relevant). - A short explanation of which algorithm(s) you use. If you choose from a few options explain your choice. - What are the algorithm's main building blocks, functions and data-structures and how they interact.
Q3	How do we know for sure on which elements one may trust (e.g, maybe the public board show a copy of your vote, then later changes it to something else)?
	Actually you don't. You should write in your design a short section describing the trust issue (i.e, what one has to trust so that we know the system works properly).
Q4	How do we do a non-interactive ZKP?
	The method we use is called Fiat-Shamir heuristic (or method) because it is not proven (see link above). In their paper they presented a signature protocol which uses it, and on the way, they present the novel idea of using hash function instead of a challenge. That is why this paper is cited in every paper which use this method (even though it doesn't generally talk about Non-Interactive-ZKP).
Q5	Which hash should we use in practice for the non-interactive ZK signature?
	I don't think it really matters which hash you use. I basically like MD5 (Pseudocode and nice info at http://en.wikipedia.org/wiki/MD5). Also, you can google "md5 implementation" and find it implemented in any language. SHA-1 is also good (again, wiki is a good start http://en.wikipedia.org/wiki/SHA-1). Moreover, There are many implementations of other methods like in http://www.partow.net/programming/hashfunctions/ You just need to choose and google a little.
Q6	How can we generate a large prime with the respective generator?
	Finding general large primes and generators is not an easy task, but, finding a specific kind is an easier problem. Usually we use p = 2q + 1 as our primes (where p,q are primes), and then we can find a generator by: while 1 choose a random number x if x^2 != 1 (mod p) and x^q != 1 (mod p) return x See, for example, slides 5-6 at: http://www.pinkas.net/teaching/itc/2005/lectures/lecture6.pdf
Q8	We have problems finding libraries which support large numbers on the one hand, and UI on the other hand, and can be easily compiled together.
	A few suggestions: For Java: IIRC Java has its own, built-in BigNumber library. For C/C++ programs, you may want to use the GMP library. Unfortunately, it doesn't compile all that well with MSVC (it is possible, but really it's a lot easier to use on linux/unix systems). To make the UI programming easier, You may use a web-based solution: the UI is programmed in PHP. PHP has modules for GMP and MySQL databases, and it's very easy to learn (especially if you already know C or Java). The only glaring omission is secure random number generation. If you run the webserver on linux, you can bypass that by reading from /dev/random or /dev/urandom.  You can see an example server at http://www.wisdom.weizmann.ac.il/~talm/voting/ where there is also a link to the source code. Other suggestions are Crypto++ and MIRACL. You may also search for “big integers” on google.