Will prove the same as Gjøsteen [5] did in the original protocol, that is:
7.4 Auditor 61
• The submitted ballots remain confidential.
Game 1 In this game we want to do as we always have done so far, namely sim-ulate all the players by one machineM. M knows all decryption keys, especially M knows{a1i}and{a3i}.
Game 2 We see thatFpok never uses the witnesses received from the players, since it knows the players are honest, hence we do not need to provide the real witnesses. So in this game we provideFpok with random witnesses. This game is clearly indistinguishable from the previous one.
Game 3 SinceM knows the cleartext of each encrypted ballot, we no longer decrypt in the decryption service or the receipt generator. Instead we use the remembered cleartext ballots. These changes are not observable for the auditor since the end result is the same, hence the game is indistinguishable from the previous one. Note that we no longer use the contents of the encrypted ballots.
Game 4 Now we encrypt random group elements instead of the cleartext bal-lots when creating x, the wi’s and the ˆwi’s. Note that ˆwi and wi is created with the same random group element. Since the auditor never sees the ˆwi’s, only commitments to them, it cannot distinguish between generating them with encryptions of real ballots or random group elements. We also randomize wi with the same random group element as ˆwi. A straight-forward reduction will show that if we can distinguish between generatingwiwith a real ballot or a ran-dom group element, we get an advantage on the problem H0kmax+1 ←→? Gkmax+1, with H0kmax+1 =h(g, y11, . . . , y1kmax)i. So this game is indistinguishable to the previous one.
Game 5 In this last game we generate new random encryption in each round of the shuffle proof instead of rerandomization. As in the previous game, a straight-forward reduction to the problemH0kmax+1 ←→? Gkmax+1, withH0kmax+1= h(g, y11, . . . , y1kmax)iwill show that this game is indistinguishable to the previous one.
Analysis We are now in the same position as in the original protocol, and hence the analysis done there will hold in our case also.
62 7 Analysis of the New Protocol
CHAPTER 8 CONCLUSION
We have now proposed two changes in the protocol, and proved that it will not reduce the security. We had, though, a perfectly good protocol, and it is no point in changing it if we do not make any improvements to it. We have claimed that our first change would improve the performance of the protocol, and it is now time to find out exactly how much performance is improved because of this first change.
We will also look at what the second improvement has done to the number of expected exponentiations, even though the most important goal of that change was to remove{a2i}. Throughout we assume that computing the exponentiation of a element g with a number r takes one time unit, computation of the sum of two elements, product of two elements and computation of a hash function is assumed to use negligible time.
First we analyse the cost of the different functionalities in the old system (without the changes) and sum up, then we analyse the cost of the functionalities in the new system (with the first change). At last we analyse the cost of the functionalities with the second change implemented, before we comment on the differences between them.
64 8 Conclusion
Cost, old system
Player Cost
Key generation 2N+ 3
The voter’s computer 3kmax Ballot box and receipt generator N(23kmax)
Counting N(kmax+ 15)
Cost, after first change
Player Cost
Key generation 2N+ 3kmax
The voter’s computer kmax+ 2 Ballot box and receipt generator N(12kmax+ 9)
Counting 17N
Cost, after second change
Player Cost
Key generation 2N+ 2kmax
The voter’s computer 7kmax+ 3 Ballot box and receipt generator N(23kmax+ 10)
Counting N(4kmax+ 17)
Note thatN is the number of voters andkmaxis the maximum number of choices a voter can make. Further note that the number of exponentiations we have said the ballot box and the receipt generator uses is the number they use in total on receiving ballots (not including counting).
Firstly we see that even though we have counted them, we are not worried about that fact that the number of exponentiations the key generation function-ality must do has increased. These computations are done before the election and are therefore not noticed by the voters. One could argue in the same way that the counting is done after the election, but as people want to know the election result as fast as possible, it is meaningful to look at the number of exponentiations one must do during counting.
One sees that the number of exponentiations we must do to count has changed.
After the first improvement we see that the number of exponentiations done to count the ballots has gone down heavily. The reason for this is that the proof of knowledge to proveP has computed correctly done after the first improvement is much simpler than in the original protocol. After the second improvement we see that the number of exponentiations has increased, the number of exponentiations needed is almost 4 times as many as in the original protocol. This comes from the
8.0 65
fact that it after the second change is more complicated to check if a ciphertext is correctly computed. Since bothB andRchecks the proofs of knowledge, one could consider if the auditor needs to check the proofs. Both B and R must be corrupt if a proof of knowledge is invalid, and if both B and R are corrupt nothing can be guaranteed.
Now we look at the number of exponentiations needed to submit a ballot.
We see that with the first change (but not the second change) implemented the voter’s computer must do about one third as many exponentiations as in the original protocol. Also the ballot box and the receipt generator uses about half as many exponentiations when processing a ballot with the first change implemented compared to the original protocol.
So we see that we have achieved a pretty good speed up when it comes to submitting votes. Especially the improvement in the number of exponentiations the ballot box and the receipt generator must do is worth noticing. In practice it will be defined a limit for the amount of time it should take from the voter’s computer sends the encrypted ballot to the ballot box, until we should receive a receipt telling the voter’s computer that the ballot is accepted or not accepted.
Therefore if we use half as many exponentiations when submitting a ballot, we use about half as much computing power and hence we will need to purchase half as much hardware.
When we look at how the last improvement effects the number of exponenti-ations, we see that the number of exponentiations the ballot box and the receipt generator must do when receiving a ballot is about as many as in the original protocol. Further, we see that the number of exponentiations the voter’s com-puter must do when submitting a ballot is in fact more than twice as many as in the original protocol and 7 times as many as after the first improvement. The reason for this is that we had to introduce commitments to make the protocol secure. But the goal of this improvement was not to improve the performance, but rather to increase security by removing the connection between the different decryption keys. And this we have managed.
Still it is interesting to look at how to overcome this increased number of exponentiations. There are many possible commitment schemes, so one thing one could look at is if one could find a commitment scheme that uses fewer ex-ponentiations without losing any security measures. We have not had the time to look into this, but it is something that could be interesting to look at, at a later stage. If one could find such a scheme one might be able to reduce the number of exponentiations significantly as now the voter’s computer uses 4kmax
exponentiations per voter, the ballot box 2kmax exponentiations per voter and the receipt generator 4kmax exponentiations per voter on just generating com-mitments with this second change implemented. It would though be important that this commitment scheme is as secure as the one used now.
66 8 Conclusion
BIBLIOGRAPHY
[1] Dan Boneh. The decision diffie-hellman problem. Algorithmic Number The-ory, pages 48–63, 1998.
[2] Ronald Cramer and Victor Shoup. Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption. Cryptology ePrint Archive, Report 2001/085, 2001. http://eprint.iacr.org/.
[3] Ivan Damgard. Onσ-protocols.Lecture on Cryptologic Protocol Theory, 2010.
[4] Ivan Damgard and Jesper Buus Nielsen. Commitment schemes and zero-knowledge protocols (2008). 2008.
[5] Kristian Gjøsteen. Analysis of an internet voting protocol. Cryptology ePrint Archive, Report 2010/380, 2010.
[6] Statistisk Sentralbyr˚a. Folkemengd, etter alder og fylke. absolutte tal. 1. jan-uar 2011. http://www.ssb.no/folkemengde/arkiv/tab-2011-02-24-01.
html, 2011.