1、10/25/2006,1,Threshold Paillier Encryption Web Service,A Masters Project Proposal by Brett Wilson,2,10/25/2006,Motivation,Secure Electronic Voting Research Interest in improving current voting process is high 2000 Presidential election snafu Improved access/availability (voter turnout) Cryptographic
2、 research has led to new solutions to problems with electronic voting Basic requirements for electronic voting Privacy All votes should be kept secret Completeness All valid votes should be counted correctly Soundness Any invalid vote should not be counted Unreusability No voter can vote twice Eligi
3、bility Only authorized voters can cast a vote Fairness Nothing can affect the voting Extended Requirements for electronic voting Robustness faulty behavior of any reasonably sized coalition of participants can be tolerated Universal Verifiability any party can verify the result of the voting Recipt-
4、freeness Voters are unable to prove the content of his/her vote Incoercibility Voter cannot be coerced into casting a particular vote by a coercer,3,10/25/2006,Motivation,Many of the proposed electronic voting protocols utilize threshold homomorhpic encryption schemes as part of the protocol Protect
5、s voter privacy Individual vote can not be decrypted without cooperation of t of l “authorities” Efficient, universally verifiable vote tallying Only sum of votes is decrypted Individuals can compute encrypted sum, verify proof of correct decryption of sum Implementations of threshold homomorphic en
6、cryption algorithms are not freely available,4,10/25/2006,Threshold Encryption,Public key encryption as usual Distribute secret key “shares” among l participants Decryption can only be accomplished if a threshold number t of the l participants cooperate No information about m can be obtained with le
7、ss than t participants cooperating Proof of valid decryption is provided,5,10/25/2006,Paillier Encryption,Trapdoor Discrete Logarithm Scheme c = gMrn mod n2n is an RSA modulusg is an integer of order n mod n2r is a random number in Zn* M = L(c(n) mod n2)/L(g(n) mod n2) mod n L(u) = (u-1)/n, (n)=lcm(
8、p-1)(q-1) Important Properties HomomorphicE(M1 + M2) = E(M1) x E(M2), E(k x M) = E(M)k Self-blinding Re-encryption with a different r doesnt change M,6,10/25/2006,Threshold Paillier Encryption,Different public key and secret key generation algorithm Distribute key shares using RSA public key encrypt
9、ion Distribute secret key shares using Shamir Secret Sharing scheme Web Service will be an implementation of scheme proposed in “Sharing Decryption in the Context of Voting or Lotteries” Fouque, Poupard, and Stern 2000,7,10/25/2006,Use of Threshold Paillier Encryption in Secure Voting,Ballot format:
10、 pick 1 out of c candidates Let N be number of voters, k such that N2k Vote = 2ck where c is the desired candidate number (0c) All Paillier-encrypted votes could be publicly posted Votes include proof of validity (v lies in a given set of valid votes) At end of election, all invalid votes are remove
11、d, all encrypted votes are then multiplied together to get encrypted sum (publicly verifiable) With cooperation of the required threshold number of “authorities”, the final product could be decrypted to reveal the vote total (sum of individual votes). A threshold number of authorities would not agre
12、e to decrypt a single particular vote, and thus the individual votes would remain private All computations are publicly verifiable given the validity proofs that prove the decryption was done correctly,8,10/25/2006,Web Service Design Goals,Platform Independent Use of web service XML input/output Ext
13、ensible Additional encryption algorithms could be added Additional services could be offered Threshold signatures Verifiable Mix Net,9,10/25/2006,Implementation Tools,Visual Studio 2005 VB.NET Gnu Multiprecision Library (Gmp) Open source arbitrary precision numeric library Compiled under Visual Stud
14、io 2005 NGmp Open source VB.NET binding of gmp.dll Enables calling of gmp library functions through VB.NET Compiled under Visual Studio 2005,10,10/25/2006,Threshold Paillier Encryption Web Service,Key generation algorithm Inputk size of keyl number of shares to generate One RSA public key (of the de
15、signated participant) for each sharet threshold parameter OutputPublic Key PKList SK1, , SKl of private key shares Encrypted with supplied RSA keys so only designated participant can recover the key shareList of Verifier Keys VK, VK1, ,VKl Used for proving validity of decryption,11,10/25/2006,Thresh
16、old Paillier Encryption Web Service,Encryption Algorithm InputPublic Key PKRandom string rCleartext M OutputCiphertext c,12,10/25/2006,Share Decryption Algorithm InputCiphertext cPrivate Key Share Ski Encrypted with public key of webservice OutputDecryption share ciValidity proof pi,Threshold Pailli
17、er Encryption Web Service,13,10/25/2006,Threshold Paillier Encryption Web Service,Combining Algorithm InputCiphertext cList of decryption shares c1,clList of verification keys VK, VK1VKlList of validity proofs P1,Pl OutputM,14,10/25/2006,Project Deliverables,A working prototype of Paillier Threshold
18、 Encryption Web Service (PTEWS) A simple demo of applying PTEWS in online voting A master project report documenting the research findings and lessons learned,15,10/25/2006,Tasks and Milestones,Week 1: Proposal Briefing/Approval Week 2: WebService “skeleton” complete WebMethod stubs created, classes
19、 for passing parameters and return results complete Week 3: Encryption algorithms implemented WebMethod stubs completely implemented with encryption and utility algorithms Week 4: Testing Interface complete Windows application for testing of Web Service Simple test of voting application Week 5: Fina
20、l Report complete Week 1 ends Oct 30, Week 5 ends Nov 27,16,10/25/2006,References,“Sharing Decryption in the Context of Voting or Lotteries” P. Fouque, G. Poupard, and J. Stern, 2000 “Public Key Cryptosystems Based on Composite Degree Residuosity Classes” P. Paillier, 1999 “How to Share a Secret” A.
21、 Shamir, 1979 Big Number Libraries Gnu Multiprecision Library Opensource C language library http:/ J# BigInteger J# library available from Microsoft http:/ C# BigInteger Opensource implementation of Java BigInteger http:/ NGmp .NET Mono Multiprecision Library (gmp binding to .NET) http:/ Building Gmp with Visual Studio 2005 http:/
