0368.3500
Workshop on Electronic voting
Fall 2009.
Lecturer: Amnon TaShma
T.A.: Tomer Levinboim, levinboim dot tomer at gmail dot com
When and where: Wednesdays, 10:1012:00. Location: Kaplun 324.
Background: Links to some US newspaper articles and other sources of information.
Very recent: SequoiaVotingSystemshacksselfinfoot (thanks to Oded Regev for the reference)
Schedule:
Date 

21.10.09 
Background. 
28.10.09 
DLOG. ElGamal. Zeroknowledge proofs. Assigning projects. 
02/12/09 
Design Presentations 
16/12/09 
Deadline for submitting interfaces + running time estimation (measured in basic group operations). 
13/01/10 
Final submission 
Projects:
Prêt à Vote 
כלב אלפרנס ודים סטוטלנד סרברו אסנת 

Threshold encryption 
אור איגלקה אלי זיגל 
Torben Pedersen: A threshold cryptosystem without a trusted party 
ZK module 
ארז טלגם רוני שטרן 

Mix Nets 
אלכס קרצמן רן סלע יעל כרוב תומר היימן 
K Sako, J Kilian  EUROCRYPT'95Receiptfree mixtype voting scheme 



The version of Prêt à Vote we use: Ballots are created on the spot by the booth. Ballots have two columns as usual. The first column is randomly shifted. The second column lower entry contains the encrypted value of each entry + ZKP. The encryption is done with the public threshold key (the secret key is not known to the booth). The booth is randomly checked and then has to prove validity of the ballot and the ballot is discarded. Tallying is immediate. If ElGamal is used, the homomorphism is multiplicative, so additive values are raised to the exponent, and after threshold decryption one does brute force search on the result.
Technical references:
Ben Riva's thesis.
A nice online book with very good number theory background: http://shoup.net/ntb/
Amos Fiat and Adi Shamir: How to prove yourself: practical solutions to identification and signatures problems.
FAQ from past year (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). 
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 noninteractive ZKP? 

The method we use is called FiatShamir 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 NonInteractiveZKP). 
Q5 
Which hash should we use in practice for the noninteractive 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. SHA1 is also good (again, wiki is a good start http://en.wikipedia.org/wiki/SHA1). 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 
Is there an example of a practical use of the FiatShamir paper? 

There are few follow up papers which mention some theoretic problems in this method (like  http://www.mit.edu/~tauman/fiatshamirshort.pdf), but for specific uses (mainly signatures or voting protocols) it is common to use it (like CGF97). 
Q7 
How can we generate a large prime with the respective generator? 

Corrected answer: Finding general large primes and generators is not an easy task, but, finding a specific kinds 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 56 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 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 webbased 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
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. 
Q 


