6.857 Computer and Network Security October 29, 2002Lecture Notes 15 : Voting, Homomorphic EncryptionLecturer: Ron Rivest Scribe: Ledlie/Ortiz/Paskalev/Zhao1 IntroductionThe big picture — and where we end up at the end of the lecture — is a voting scheme where (a)each voter casts exactly one ballot and (b) voting is anonymous. We delve into two areas on ourway to this goal: Blind Signatures, which allow for anonymous voting, and Paillier Cryptosystem,which gives us the ability to sum up votes even though they have been encrypted. From there, wetry out a voting scheme without privacy and show how privacy without cheating can be added tothis pretty simple scheme.2 Outline• Homomorphic Encryption• Blind Signatures• Paillier Cryptosystem• Electronic Voting with Paillier Cryptosystem and Blind SignaturesHistorical Note: Bush signed the ”Help America Vote Act of 2002”1today. This act will givestates $3.9 billion to replace outdated punch-card and lever voting machines, and to improve votereducation and poll-worker training.3 Homomorphic Encryption• Homomorphic EncryptionThe encryption algorithm E() is homomorphic if given E(x) and E(y), one can obtain E(x ⊥ y)without decrypting x, y for some operation ⊥.• RSA (Multiplicative Homomorphism)Given ci= E(mi) = meimod Nc1= me1modNc2= me2modNc1· c2= me1· me2modN = (m1· m2)emodN0May be freely reproduced for educational or personal use.1http://www.cnn.com/2002/ALLPOLITICS/10/29/elec02.bush.changes.ap/index.html12 4 BLIND SIGNATURESRSA demonstrates a multiplicative homomorphic property: E(m1) · E(m2) = E(m1· m2)4 Blind SignaturesBefore we cover Paillier Cryptosystem, let’s think about how a vote can be anonymized. To achievethis, we use Blind Signatures.UserSignerm//σ(m)=md(mod N )ooThe diagram above shows how ordinary RSA signatures work.In order to sign, the signer needs to know what the message m is.UserSignerm//σ(m·re)=σ(m)·r (mod N)ooWith blind signatures, the signer does not know what the message mis but is still able to sign the message.Calculation performed by Signer on last sending:σ(m · re) = (m · re)d= md· red= md· r = σ(m) · r (mod N)Note The symbols e and d refer to the encryption and decryption keys, respectively. Also note,when you divide the response by r, you get the signature of the message σ(m) :σ(m)·rr= σ(m).• Physical Example of Blind Signature SchemeMaterials: Envelope, White paper, Carbon paper1. Place the carbon paper on top of the white paper2. Place both items in the envelope and seal3. Sign on the envelopeIn the end, the signer does not know what he has signed.• ExamplesIn the top figure x represents a coin in the special form00Bank...r00, where r is a random number.σ(x) is a coin signed by the bank. Hence, the bank recognizes its signature but cannot trace the3Figure 1: Two examples of Blind Signatures.coin. The initial signing is information theoretically secure; however, problems arise when user triesto spend a coin multiple times.Similarly, in the bottom figure, the registrar signs the voter’s sealed vote, which the voter thenpasses on to the counter.5 Paillier Cryptosystem5.1 Key GenerationLike RSA, pick two primes p, q and let N = p · q — but here we are going to work mod N2. Notethat ϕ(N2) = N · ϕ(N) = N · ϕ(p) · ϕ(q) and that all elements have order dividing ϕ(N2). CreateP K = (N, g) where g has order a multiple of N and SK = (λ(n)) where λ(n) =lcm(p − 1, q − 1)(where “lcm” denotes lowest common multiple).4 6 VOTING WITH PAILLIER CRYPTOSYSTEM AND BLIND SIGNATURES5.2 EncryptionTo encrypt a message m ∈ ZN:• Choose x ∈RZ∗N.• Produce an encryption E(m) = gmxNmod N2.Doing some arithmetic, here we can show that Paillier has the following useful property:E(m1) = gm1xN1modN2E(m2) = gm2xN2modN2E(m1) · E(m2) = gm1+m2(x1x2)NmodN2= E(m1+ m2)Paillier demonstrates an additive homomorphic property.5.3 DecryptionUse L(u) =(u−1)Nfor u ≡ 1 (mod N). Note that the formula for L(u) is not modulo anything.If c = E(m), thenm =L(cλ(n)mod N2)L(cλ(n)mod N2)mod NProof is given in [1].5.4 Benefits of Paillier Cryptography• It gives the homomorphic property we want for voting.• It is semantically secure, assuming that it is hard to distinguish Nthresidues from non-Nthresidues mod N2(in addition to the DLP). Semantically secure means that you cannot distin-guish E(0) from E(1) better than 50% as N → ∞.6 Voting with Paillier Cryptosystem and Blind Signatures6.1 Motivation: Bulletin Board VotingWe are aiming to use E(m1) · E(m2) = E(m1+ m2) so that we can add up the votes.Imagine that we have a large public bulletin board with candidates X, Y, Z and voters V1, . . . , Vn.6.2 Correctness 5X Y ZV11 0 0V20 1 0V31 0 0Total 2 1 0With a regular bulletin board we have theballots in plaintext. X, Y, and Z denotecandidates. The Viare voters. The entry1 represents a vote for a candidate.X Y ZV1C1XC1YC1ZV2C2XC2YC2ZV3C3XC3YC3ZTotal CXCYCZC1X, etc., denote votes encrypted usingsome public key scheme, with the privatekeys owned by election officials.If we have the additive homomorphic property, we only need to decrypt the figures in the row oftotals, thereby providing voter privacy. We want to find E(Tj) =QiEij.Question : Does encryption have to be randomized?Answer : Yes. Encryptions of 0s must look different, so that an adversary will notbe able to tell whether two people made the same vote by simply checkingwhether the ciphertexts are the same. Similarly encryptions of 1s mustalso look different. Hence, simple RSA is therefore not suitable for thisapplication.6.2 CorrectnessNow that we have these two tools, Paillier Cryptosystem and Blind Signatures, we can return to ourpublic bulletin board of votes.• To stop a voter from submitting multiple votes for one candidate (or negative votes) we haveto make sure that mij∈ {0, 1} and that the row subtotal ∈ {0, 1}.• We also need to enforce non-malleability. For example if Alice’s vote were mij∈ {0, 1}, Bobcould negate Alice’s ballot in this fashion by computing:E(1)E(mij)= E(1) · E(−mij) = E(1 − mij)The solution is to use zero knowledge proofs.• To prove the vote is correct:VoterSystemucommitment/witness//challengeooe ∈R{0, 1, . . . , A − 1}response//check6 REFERENCESThis round is performed t times.Fiat-Shamir trick: replace e ∈R{0, 1, . . . , A − 1} with e = hash(commitment) to make ita non-interactive ZK proof. Hence, commitment/witness and response can be reduced to
View Full Document
Unlocking...