Zhe Xia Steve A. Schneider James Heather
Department of Computing, University of Surrey, U.K.
{z.xia, s.schneider, j.heather}@surrey.ac.uk
Jacques Traoré
France Telecom, Orange Lab
jacques.traore@orange-ftgroup.com
Voter privacy: this aspect includes privacy and receipt-freeness. The privacy property keeps the voter's choice information private from others if the voter does not want to reveal it. Receipt-freeness, introduced by Benaloh and Tuinstra [9], has a much stricter requirement than privacy. It requires that voters are unable to generate receipts to prove to others how they have voted, or that they can use fake receipts to lie to adversaries, and adversaries cannot distinguish fake receipts from genuine ones. Therefore, receipt-freeness implies privacy. In this paper, voter privacy will have the same security requirement as receipt-freeness. The purpose is to ensure that the whole election system will not leak voters' choice information, even if voters are coerced to collude with adversaries. Therefore voters can cast their votes without coercion and intimidation. We say that the election system suffers from the information leakage problem if some threats against voter privacy can be introduced with non-negligible probability.
Verifiability: this aspect includes integrity, correctness, individual verifiability and public verifiability. Integrity means that all eligible voters will be allowed to vote, each eligible voter is allowed to vote once and only once, and all valid votes will be tallied. Correctness means that if all participants in the election behave honestly, the correct result will always be obtained. Individual verifiability ensures a correct mapping from voters' intent to the received votes, and public verifiability ensures a correct mapping from the received votes to the final result. The verifiability aspect is a combination of the above four properties, therefore it ensures a correct mapping from voters' intent to the final result, and furthermore, this procedure can be verified.
Reliability: includes robustness and fairness. Robustness requires that the election systems are able to tolerate some mistakes caused by ordinary voters, as well as some faulty behaviour caused by a minority of election authorities. The ability to recover from cheating is important as well. Fairness ensures that no partial result will be revealed before the final result is announced.
Versatility: the election system is able to handle different election methods, such as First-Past-The-Post elections, Borda Court elections, Condorcet elections and Single Transferable Voting.
Usability: the election system can be used by ordinary voters without special knowledge (e.g. click-and-go). Besides, the system should be easy for election authorities to set-up and control, no special or expensive equipment is needed. Furthermore, the system can be executed efficiently even if the number of candidates or number of voters scales up.
Among these aspects, the first three, which are called security aspects, are always crucial, that particularly of certain for cryptographic electronic voting. The other two aspects are called auxiliary aspects. And there are two major conflicts among these aspects:
Generally speaking, early cryptographic e-voting schemes were focused on the ballot tallying phase, aiming to solve the first conflict by achieving voter privacy and verifiability simultaneously. These schemes can be classified into two major approaches: based on mixnets, and based on homomorphic encryption.
In schemes based on mixnets, each voter first encrypts her choice under some public key. The corresponding secret key is distributed among a number of decryption parties in a threshold fashion [46,26]. The voter publishes this encrypted value on the bulletin board with some proof to show her knowledge of the plaintext. The proof aims to prevent the ballot duplication attack in [47]. When all voters have cast their votes, a number of mix servers will launch the shuffle phase. Each mix server receives a batch of encrypted votes, randomly re-encrypts and shuffles them, then outputs the result to the next mix server. Therefore, if all mix servers are honest, the outputs of the shuffle phase will be a permutation of the incoming votes, but their relationships have been mixed to ensure voter privacy. Finally, each of the encrypted values in the outcome will be decoded in a threshold fashion. Each decryption party publishes some auxiliary information [13] to prove the correctness of decoding. In order to audit the shuffle phase, each mix server needs to post some certificates1 onto the bulletin board which can be verified by the public afterwards. These certificates should not reveal how the mix server has shuffled the encrypted values. Note that the most expensive part in the mix networks is for mix servers to prove the shuffle. There have been some attempts to improve efficiency. Some repetitive robust mixnets are interesting, e.g. [31,32,27], but most of them have been broken [19,39,1,55]. We advocate choosing one from [25,41,28]2.
Schemes based on homomorphic encryption were first introduced by Benaloh [15,10,7]. To cast a vote, each voter generates an encrypted value of her desired vote and posts it onto the bulletin board. A proof that her encrypted value contains a valid vote is also required. The proof should not reveal the content of that vote, but it prevents dishonest voters from casting multiple votes. The received encrypted values are then aggregated in some public manner. Finally, the result can be tallied in a threshold fashion without opening each ballot for voter privacy. Similarly, some certificates to prove the correct decoding are published on the bulletin board. Schemes based on homomorphic encryption are efficient in obtaining the final result3, however intensive zero-knowledge proofs are needed to prove the validity of each encrypted vote, and voting is normally restricted to the 1-out-of- format. Major issues and important building blocks of e-voting schemes based on homomorphic encryption have been introduced in [17,6,18].
In these early schemes, the receipt-free property has attracted a lot of interest. Each encrypted vote is published, and the voter herself can prove the content of her vote by revealing the randomness she used for encryption. Thus some additional methods need to be applied in order to achieve receipt-freeness. We have to note that although a number of schemes have claimed achievement of the receipt-free property, some of them have been broken or shown to suffer drawbacks.
(1). Some schemes [9,37,38] suggest that after the voter encrypts her vote, some trusted party will re-encrypt each voter's vote and prove the re-encryption in an interactive way. However, if adversaries force voters to use some special randomness for their challenge, e.g. the outcome of some hash functions, then receipt-freeness fails. Therefore, the re-encryption proof has to be given in a non-interactive and designated-verifier way.
(2). There are two reasons why if an e-voting system uses designated verifier proof (DVP) [35] to prove some facts, the prover needs to be some trusted party, e.g. a tamper-resistant device, or some distributed parties [5]. First, when receiving some DVP proof, the verifier cannot make an accusation if she is not satisfied with the proof. Second, if adversaries coerce a voter to surrender her private key and then share the key with the prover, the prover can generate fake proofs which will be accepted by the voter. Furthermore, the verifier needs to prove knowledge of her private key [53]. Otherwise, the designated verifier proof will be meaningless to her.
(3). Hirt and Sako [30] claimed that a one-way untappable channel from the authorities to the voters to achieve receipt-freeness has the weakest physical assumption. However, this kind of structure (also in [52]) is not very elegant. Authorities prove the shuffle of encrypted votes using DVP, and receipt-freeness is achieved if voters are able to lie to adversaries about the shuffle. However, in the context of coercion, the possibility of a lying voter being caught is linear in the number of authorities colluding with the coercer.
The early cryptographic e-voting schemes introduced above require all voters to have an advanced knowledge of mathmatics. Obviously, this requirement is not realistic for ordinary voters. Some suggestions are for voters to indicate their intent to some voting device (e.g. DRE machine) or election authorities. These parties then help the voters to generate the encrypted votes and publish them onto the bulletin board. However, this might result in two problems:
Two approaches, SureVote [12] and MarkPledge [42], that aim to solve the first problem have been proposed by Chaum and Neff respectively. Both systems provide voters with a receipt, which does not allow voters to prove how they have voted, but enables them to verify that their votes have been recorded in the election system. To ensure that the voter's intent has been correctly contained in the receipt, Chaum and Neff have introduced different ideas.
In Chaum's scheme [12], the voter indicates her intent to the voting machine, which then prints the ballot into two layers that are encoded using visual cryptography. The voter can read her intent on the ballot when the two layers are laminated together. After the voter has approved the ballot, she separates the two layers, randomly chooses one layer to retain as a receipt and destroys the other part. Later, Ryan's Prêt à Voter system [14] simplified Chaum's method using cut-and-choose. In [14], each voter will be provided with two ballots, she can randomly choose one ballot to challenge and use the other to cast her vote. If the ballot is correctly generated, the receipt will contain voter's intent. Although a single voter only has 50% chance to detect the fraud ballot, any attempt to cheat in more than a very small number of ballots would be detected with overwhelming probability. Ryan's cut-and-choose method also appears in [51,4,8].
Neff's scheme [42] is based on a different approach. The voter first indicates her intent to the voting machine, the machine then constructs an encrypted electronic ballot representing this voter's intent and commits it. After that, the voter interacts with the voting machine to obtain a receipt. Note that the voter's task in this process can be simplified, therefore ordinary voters can cast their votes without special knowledge, and some helper organisations [2] can help to verify the receipt afterwards. Similar idea of voter intent verification can be found in [3,40].
The schemes introduced above have only solved our first problem. However, because voters need to indicate their intent to some voting device or election authorities, the voter privacy will be violated if the voting device or election authorities are faulty. Some work of e-voting threat analysis [36,50] have shown that because of this problem, voter's choice information can be leaked in a number of ways. Taking the Prêt à Voter scheme [14] as an example, because all ballot forms are generated by some election authorities in advance, these authorities have the ability to read the voter's choice directly from their receipts. Besides, these authorities can apply subliminal & Kleptographic channel attacks to enable their colluding parties to read voter's receipt as well. Furthermore, the Chain-of-custody issues require that the ballots generated in advance cannot be tampered with before use, e.g. during transmission. Otherwise, voter privacy will be violated because of information leakage.
To the best of our knowledge, the first e-voting scheme which solves both our problems is Ryan's Prêt à Voter with re-encryption mixes [51], in which all ballots are generated by a number of election authorities, called clerks, in a distributed fashion. Therefore, although some voting device is still proposed, the voters no longer need to indicate their intent to the voting device or some single clerk. In theory, voter privacy can be computationally preserved under the assumption that all clerks do not collude. However, in order to apply the homomorphic property to absorb voter's choice index into the onion, [51] has employed the exponential ElGamal encryption, which is not a trapdoor function. After decryption, we need to search some large field in order to retrieve the plaintext. To overcome this problem, Ryan has introduced Prêt à Voter with Paillier encryption (PAV-Paillier) [49,48].
In this paper, we analyse information leakage in PAV-Paillier. Our analysis shows that although PAV-Paillier seems to achieve a high level of voter privacy at first glance, it might still leak voter's choice information in some circumstances. Some threats are trivial and have appeared in the literature, but others are more complicated because colluding adversaries may apply combined attacks. Several strategies have been suggested to mitigate these threats, but we have not resolved all the threats. We leave those unsolved threats as open questions. In order to describe our analysis in a logical manner, we will introduce an information leakage model to aid our analysis. We suggest that this model can be applied to analyse information leakage in other complex mixnet based e-voting schemes as well.
Furthermore, we introduce a simplification of PAV-Paillier. In our proposal, without degrading security properties such as voter privacy, verifiability and reliability, we no longer need to apply the homomorphic property, thus we step back to employ the ElGamal encryption. This results in a simpler and more straightforward threshold cryptosystem. Some other attractive properties of our proposal scheme are: unlike traditional Prêt à Voter schemes, the candidate list in our scheme can be in alphabetical order. Our scheme handles both approval elections and ranked elections (e.g. Single Transferable Voting). Furthermore, our scheme mitigates the randomisation attack.
Proof. Since there is a relation from to , for a target element , with non-negligible probability, its image in can be found. Similarly, for the target element , with non-negligible probability, its image in can be found. Then for a target element , with non-negligible probability, its image in can be found. Therefore, there is a relation from to .
In the above scheme, there will be three sets with the same cardinality: the set of voters, the set of receipts, and the set of result. We denote them as , and respectively. Based on our definition, the scheme will suffer information leakage if there is a relation from to . Therefore, there might be two possible threats of information leakage in the scheme, as shown in Figure 1.
Threat 1:
Some attacks may be applied by adversaries to generate a relation from to :
(1). Hidden camera attack: if the voting booth is monitored by hidden cameras, adversaries can directly know the choice made by a target voter.
(2). Knowledge of the voting machine: since the voting machine learns the voter's intent, a cheating voting machine can leak the choice made by a target voter.
(3). Italian attack: this attack only happens in ranked elections with a large number of candidates. Adversaries can coerce a target voter to cast her vote in some particular manner. The voter will be caught with high possibility if she does not cooperate. This attack is possible when the number of possible votes are much more than the number of voters.
Threat 2:
Each voter will be provided with a receipt in the above scheme, and any voter may reveal her receipt to others. Therefore, there is always a relation from to . The remaining task for an adversary to violate voter privacy is to generate a relation from to . Several attacks can be applied to generate such a relation:
(1). Ballot duplication attack: the attack is possible if the vote is not encrypted using non-malleable encryption [20,31]: adversaries can cast a duplication of a target vote in order to find out the choice information of the target vote. For more information, see [47,23].
(2). Subliminal & Kleptographic channel attack: the voting machine which generates the encrypted votes can employ this attack to enable any party colluding with it to read a voter's receipt without the need to have it decrypted.
(3). Chain voting attack: the above election scheme does not suffer this attack, but some schemes which uses paper ballots generated in advance may suffer this attack, e.g. the Prêt à Voter scheme [14]. If adversaries successfully smuggle one blank ballot out of the voting booth, they can force a target voter to cast her vote using this ballot and bring back another blank ballot. Therefore, the receipt tells the adversaries how this voter has voted.
The above election scheme is simple. Its use here is to illustrate how the model can be applied to analyse information leakage in mixnets based e-voting schemes. Note that all the listed attacks have been introduced in the literature, e.g. [36,50]. But it is obvious that the information leakage model can help to summarise these attacks in some logical manner, and this is very important if the election scheme becomes complicated.
The ballot form contains two columns with a perforation down the middle. There are two encrypted values, called onions, printed at the bottom. The onion in the left hand column is called the booth onion, which can be decoded by the voting machine. If it is decrypted, the voting machine will derive the seed value and print the candidate list on the ballot form. At this moment, the ballot form will be shown in Figure 3. Note that the order of the candidate list is cyclically shifted and varies among different ballots, thus it is infeasible to predict the candidate order of a certain ballot form. The onion in the right hand column, which is printed on some scratch strips, is called the ready onion.
Paillier cipher [44] Let be an RSA modulus , where and are large primes. Let be an integer of order a multiple of modulo . The public key is , and the corresponding secret key
. To encrypt a message , we randomly choose and compute the ciphertext
. To decrypt , we compute
, where the -function takes in input values from the set
and computes
.
Construction of the receipt onions Suppose the public key is made public and the corresponding secret key is shared among a number of decryption parties, called tellers, in a threshold fashion [54], where a quorum of these tellers work together can decrypt a ciphertext which is encrypted under the public key , but fewer than tellers will learn nothing from the ciphertext.
The first step to construct the ballot forms is for a set of clerks to generate a receipt onion for each ballot form.
The first clerk randomly chooses some seed values and some blinding factors
. Then generates a batch of initial onions as:
After that, the remaining clerks perform as follows: the th clerk receives a batch of onions
from the clerk . chooses some seed values
and some blinding factors
, and then she calculates
Finally, the last clerk will output a batch of onions
where
We call the onions output by the last clerk receipt onions, in which each clerk has contributed to the entropy of the seed values from which the candidate list is derived. This process does not reveal the seed values. Therefore, the final seed values can be kept private unless all these clerks collude. For each ballot, a unique receipt onion will be printed on it, at the bottom in the right hand column.
Transforming receipt onions into booth onions When some of the above ballot forms are generated, a number of re-encryption parties (which can be the same clerks) will perform the following tasks:
When the above procedure is finished, we call the onions which are printed on top of the scratch surface ready onions. The major purpose of the above procedure is to break the links between the receipt onions and the ready onions. At this moment, we have a batch of ballot forms, each contains a unique receipt onion, but it is covered by multi-layer of scratch strip. The only visible value is the ready onion, which is the re-encryption of the receipt onion. Note that Ryan has suggested that in some cases, just one such re-encryption might be sufficient.
The ready onions are transformed into the booth onions, which can be directly decrypted by the voting machine. However, the transformation procedure introduced in PAV-Paillier is not very elegant. Ryan suggests that each ready onion is partially decrypted by a subset of the tellers, and the result is the booth onion. In the ballot forms, the booth onion is printed at the bottom in the left hand column. Therefore, if the voting machine is provided with another share of the secret key , it can decrypt the booth onion to obtain the seed value.
Auditing the ballot construction To audit the ballot construction phase, Ryan has introduced two methods in PAV-Paillier. The traditional cut-and-choose method, which is similar as in [14,51], requires some tellers to be online. The other method aims to resolve this drawback, but some auxiliary information needs to be published. However, this information might result the leakage of the secret key . Thus, the second method does not work. Because of space limitations, we will not describe this technical weakness in detail.
This voter marks her choice, followed by tearing the ballot form apart along the perforation and destroying the left hand column. The voter brings the right hand column to the election officials and removes the scratch surface in their presence. After that, the voter can keep the right hand column as the receipt once it has been scanned by the election officials. A receipt example is shown as in Figure 4. The receipt can be used to check that the voter's vote has been properly recorded by the election system. We note that the receipt only contains the voter's mark and the receipt onion.
Then these encrypted values (pure Paillier terms) will be inserted into some re-encryption mixnet, which will shuffle and re-encrypt these terms by changing the randomisations while leaving the seed values untouched. The mixnet can be audited using techniques in [34,43]. Finally, the outputs of the mixnet will be decoded by a quorum of tellers in a threshold fashion, and the results will be announced.
Threat 1:
We will examine some existing attacks to see whether the PAV-Paillier scheme suffers from this threat.
(1). Italian attack: PAV-Paillier does not suffer this attack because it cannot directly handle ranked elections.
(2). Knowledge of the voting machine: In PAV-Pailler, the voter does not indicate her intent to the voting machine. Therefore, the voting machine itself has no way to find out how this voter has voted.
(3). Hidden camera attack: PAV-Paillier suffers this attack, but all other election scheme will suffer this attack as well. To ensure voter privacy, the assumption is needed that the voting booth is not monitored by hidden cameras.
In the rest of this paper, we will not consider the hidden camera attack, and we suppose there is no direct relation from to in the PAV-Paillier scheme.
Threat 2:
Within this threat, we will first check whether there is a relation from to . Based on our definition, such a relation can be generated if for any particular target ballot form, with non-negligible probability, the adversaries can find out how this ballot has been used to cast a vote.
In the PAV-Paillier scheme, for a target ballot form, the voting machine can learn the seed value after the booth onion has been decrypted. In the ballot tallying phase, the receipt onion
will absorb the voter's choice index as
To violate voter privacy, the remaining task for adversaries is to find a relation from to . It is obvious that if some adversaries know which ballot form has been assigned to a particular voter, these authorities colluding with the voting machine can find out how this voter has voted. To overcome this problem, all ballot forms are required to be distributed in an anonymous way.
Furthermore, even if we suppose that all ballot forms are distributed in an anonymous way, and there does not exist a direct relation from to , does this mean that the PAV-Paillier can resist this threat? Unfortunately, the adversaries can generate the relation from to as shown in Figure 6.
Because any voter may reveal her receipt to others, there always exists a relation from to . Therefore, the task to generate a relation from to can be transferred to the task of generating a relation from to . In order words, if adversaries can generate a relation from to , their collusion with the voting machine can violate voter privacy. We will discuss whether there exists such a relation later.
Threat 3:
Because any voter may reveal her receipt to others, the relation from to always exists. The remaining task for adversaries to violate voter privacy is to generate a relation from to . We will examine some existing attacks against this relation and check whether they can be applied with the PAV-Paillier scheme:
(1). Chain voting attack: PAV-Paillier does not suffer the chain voting attack because even if some adversaries can smuggle a ballot form (with the candidate list) out of the voting booth, they cannot coerce a voter to cast her vote using this ballot form. In one aspect, if the adversaries remove the scratch surface, the election officials will reject this vote when a coerced voter submits it. In the other aspect, if the adversaries keep the scratch surface intact, they will not know whether the voter has voted using this ballot form, because the relationship between a ballot form and its receipt is kept private thanks to the scratch surface.
(2). Subliminal & Kleptographic channel attack: The PAV-Paillier scheme is designed to resist this attack by generating the ballot forms in a distributed fashion. However, some mechanisms are necessary to ensure this. Otherwise, once a receipt onion is generated, no one can tell whether it is generated by a set of clerks or just by a single clerk. Therefore, if some receipt onions are generated by a single clerk, this clerk has the ability to learn some voters' choice just by reading their receipts. Also, this clerk can apply the subliminal & kleptographic channel attack to enable her colluding parties to learn these voters' choice just from their receipts.
(3). Ballot duplication attack: Generally speaking, the ballot duplication attack can be frustrated if the party who generates the encrypted value has proven the knowledge of the plaintext. However, in the PAV-Paillier scheme, the receipt onions are generated in a distributed fashion where each clerk contributes to the entropy of the seed values from which the candidate list is derived. The seed values will be kept private unless all these clerk collude. Therefore, the non-malleable encryption solution is not suitable for PAV-Paillier since it is infeasible for these clerks to generate such a proof. Another solution to this attack is that every receipt onion is proved to be generated by a number of authorised clerks. Thus if there exists at least one honest clerk, although some receipt onions might collide to have the same seed value, no receipt onion will be the duplication of others. Similar to the previous attack, some mechanisms are necessary to ensure this point.
Therefore, to avoid a direct relation from to , all the receipt onions need to be proved that they have been generated by a number of clerks. One possible solution is that each clerk who has been involved in generating the receipt onion has to sign it. Thus, both the subliminal & Kleptographic channel attack and the ballot duplication attack can be frustrated. However, this still does not guarantee that the relation from to cannot be generated. As shown in Figure 7, if adversaries can find a relation from to and a relation from to , they can still generate a relation from to .
We have shown in Threat 2 that the voting machine can generate a relation from to . Therefore, if any adversaries can generate a relation from to , the collusion of these adversaries and the voting machine can find out how a particular voter has voted. We will discuss whether the adversaries can generate a relation from to later.
Threat 4:
This threat contains three parts. The first part is to find a relation from to . We have shown in Threat 2 that even if all ballot forms are distributed in an anonymous way, adversaries still can generate such a relation as shown in Figure 6. The second part is to find a relation from to . The third part of this threat is to find a relation from to . Similarly, even if we apply some mechanisms to ensure that all ballot forms are generated in a distributed fashion, adversaries can still find such a relation as shown in Figure 7. When we combine these three parts together, we know that if adversaries can find a relation between and , the colluding of these adversaries and the voting machine can cause information leakage. Note that the requirement within this threat is stricter than in Threats 2 & 3, instead of requiring one way relation, a two way relation is needed here. In other words, if the voter privacy in PAV-Paillier can be violated by Threat 4, it can also be violated by Threats 2 & 3.
Threat 5:
In Threat 2, we have shown that the relation from to can be independently generated by the voting machine. In this threat, because there always exists a relation from to , if an adversary can generate a relation from to , the collusion of this adversary and the voting machine can generate the relation from to in a more straightforward manner. For example, a voter has revealed her receipt. Then an adversary who has the ability to generate a relation from to can find out the ballot form which has been assigned to this voter. As follows, the voting machine decrypts this ballot form and obtains the candidate ordering. Therefore, the candidate ordering and the choice mark in the receipt will reveal how this ballot form has been used to cast a vote. Similarly, the key point of this threat is whether there exists a relation from to .
(1). Single re-encryption: The PAV-Paillier scheme has suggested that just one re-encryption of the receipt onion might be sufficient in some case. However, this will enable the re-encryption party to learn the relationship between the ballot form and its receipt. Furthermore, if this party colludes with the coercers, the PAV-Paillier scheme will suffer the chain voting attack.
(2). Ready onion leakage: In the PAV-Paillier scheme, in order to counter the chain voting attack and the chain-of-custody issues, to submit a vote, the voter is required to remove the scratch strip in the presence of the election officials. However, if some officials see the ready onion before it has been removed, they learn the relationship between the ballot form and its receipt.
(3). Fingerprinting attack: Adversaries can apply this attack to link a ballot form with its receipt. For every ballot form, the adversaries leave a unique fingerprinting on both columns. When the voting machine prints the candidate list on the left hand column, it will build a relation between the unique fingerprinting and the ballot form. And when a voter submits her vote, some cheating officials will build a relation between the unique fingerprinting and the receipt. Thus, if they work together, they can link a ballot form with its receipt. Similar problem will occur if voters leave their fingerprinting on the ballot forms.
(4). Particular power of the last re-encryption party: The last re-encryption party in PAV-Paillier will have some particular power. When she receives a batch of ballot forms from the previous party, she can remove all the scratch surface and read every receipt onion. After that, she generates multiple scratch layers for each ballot form and prints the ready onion (which might be just one re-encryption of the receipt onion) at the top of the scratch surface. In this way, she has generated the link between every ballot form and its receipt. And in most cases, this attack will go without being detected.
(1). All ballot forms need to be distributed in an anonymous way. Otherwise, if the party who distributes the ballot forms colludes with the voting machine, they might find out how a voter has voted. We suggest that after all ballot forms have been generated, each ballot will be put into an envelope with uniform layout, and all these envelopes are shuffled before use.
(2). All the receipt onions need to be proven that they have been generated by a number of clerks. Otherwise, if they are just generated by a single clerk, this clerk can violate voter privacy either by subliminal & kleptographic channel attack or by ballot duplication attack. It is required that each clerk who has been involved in generating the receipt onion has to sign it.
(3). The re-encryption of the receipt onion needs to be executed by a number of different parties. Just one such re-encryption is not sufficient. And we need to trust that there is at least one honest re-encryption party.
(4). When the voter submits her vote, the election officials should not read the ready onion before it is removed. We suggest that once the ready onion has been transformed into the booth onion, it will be covered by another layer of scratch surface. Therefore, the booth onion can be kept private in the ballot casting phase.
(5). Normally, we do not need to worry about the fingerprinting attack. But if it is an issue we have to consider, we need to apply some mechanisms to ensure the ballot forms are fingerprinting free. For example, some help organisations in the voting booth can help to check that the ballot forms are free of fingerprinting (or digital watermarking) when it is assigned to the voters. And each voter can be provided with some special gloves to avoid leaving the fingerprinting on the ballot form.
(6). The use of multiple layers of scratch strips has a drawback that the last re-encryption party has more power than the others. We are not clear how to resolve this drawback. It might be necessary to replace the use of multiple scratch strips by some other techniques.
(7). In the PAV-Paillier scheme, the voting machine will have very high likelihood of finding out how a ballot form has been used to cast a vote. This is because , where and are large primes, and the seed value is randomly chosen from . We suggest that all clerks randomly choose the seed values from a smaller set , where is the number of candidates8. This will give the voting machine less chance to find a unique value in the final result whose difference to is smaller than .
(1). The process of transforming the ready onion into the booth onion is not very elegant. The booth onion is the partial decryption of the ready onion by tellers. Although this enables the voting machine to decrypt the booth onion, anyone else who has another share of the secret key will have the same ability as the voting machine. Therefore, some of the information leakage attacks might be applied by other tellers as well.
(2). The candidate list in PAV-Paillier is a cyclic shift from the canonical order. This is an intelligent idea to generate secret ballot forms. But in some elections with large number of candidates, e.g. hundreds of candidates, voters might face difficulty in finding their preferred candidate on the ballot form. The situation will become much worse if the candidate order is randomly permuted instead of just cyclic shifted, e.g. [29,56]. Because of this problem, election rules in some districts require that the candidate order has to be in alphabetical order.
(3). The PAV-Paillier scheme only handles approval elections. However, ranked elections, e.g. Single Transferable Voting, are widely used in a number of areas. It is clear that any e-voting system aiming at a large potential market needs to be able to deal with ranked elections.
(4). The PAV-Paillier scheme, as well as some other schemes, suffers from the randomisation attack. Adversaries can coerce the voter to take out a receipt with the mark at the top. Although, adversaries are unable to learn the content of this vote, they coerce the voter to vote in a random manner.
In this section, we will introduce a variant of the PAV-Paillier scheme, aiming to resolve the above four issues. Furthermore, because of the replacement of the Paillier cipher by the ElGamal cipher, the threshold cryptosystem in our proposal scheme will be simpler and more straightforward. The security properties of our proposal scheme are similar to those in PAV-Paillier.
ElGamal cipher [21] Let and be two large primes such that . We denote as the subgroup of with order . Let be a generator of . The secret key is an element and the corresponding public key is
. In the following, we assume all arithmetic to be modulo where applicable, unless otherwise stated. To encrypt a plaintext , we choose a random blinding factor and compute the ciphertext
. Note that an ElGamal ciphertext is a pair of values of . To decrypt an ElGamal ciphertext , we compute . ElGamal is a probabilistic public-key encryption scheme, which is semantically secure if the decision Diffie-Hellman assumption holds in the group .
ElGamal re-encryption Given an ElGamal ciphertext
, a party can efficiently compute a new ciphertext that decrypts to the same plaintext as . We denote that the ciphertext is a re-encryption of . To re-encrypt a ciphertext, the mix server chooses a value uniformly at random and computes
. We note that this does not require the knowledge of the secret key .
Threshold ElGamal cipher Suppose the ElGamal secret key is generated using a distributed key generation protocol such as in [46] or [26]. We denote that is the secret key of decryption party and
is the corresponding public key share. A quorum decryption parties working together can jointly reconstruct the ElGamal secret key as
, where is the Lagrange coefficient for the th share. To decrypt an ElGamal ciphertext
, the decryption party first publishes , and then generates a Chaum-Pedersen proof [13] that
to prove that she has published the correct . Finally, the plaintext can be retrieved as
.
Proxy re-encryption A proxy re-encryption [33] is a function to transfer an ElGamal encryption from one encryption key to another encryption key. Let be an ElGamal encryption of a plaintext using public key , and let be the corresponding secret key, which is shared among a number of decryption parties using a threshold scheme. A quorum of these parties can transfer to an ElGamal encryption , which contains the same plaintext w.r.t. the public key , without revealing . Firstly, selects a random value uniformly at random from , and computes . Then can be computed as .
Stage 1. System setup
A number of tellers generate an ElGamal secret key using a distributed key generation protocol [46,26]. The corresponding public key is made public. The voting machine generates another ElGamal private key and publishes its public key . Furthermore, every clerk generates a private key for signing and reveals the corresponding public key.
Stage 2. Ballot construction
We first introduce how to generate a ballot slice, then it will be clear how to construct an entire ballot form.
Generating the receipt onions. The first step is for a set of clerks to generate a large number of receipt onions. For each receipt onion, the th clerk randomly chooses a value and a blinding factor , and computes an ElGamal ciphertext
Transforming receipt onions into ready onions When a large number of such ballot slices have been generated, several re-encryption parties will re-encrypt each of the receipt onions. This procedure is similar to PAV-Paillier. A re-encryption party receives a batch of ballot slices, she re-encrypts each onion in the right hand column, covers it by a scratch strip and overwrites it with its re-encrypted value. Then this party shuffles all the ballot slices and sends them to the next party. At this moment, there is a receipt onion in each ballot slice, but it is covered by multiple scratch strips. The only visible value is the ready onion on top of the scratch surface, which is the re-encryption of the receipt onion.
Transforming ready onions into booth onions For each ballot slice, a quorum of tellers apply the proxy re-encryption to transfer the ready onion which is encrypted under the public key into the booth onion which is encrypted under the public key . The booth onion is printed in the left hand column. When this procedure finishes, the quorum of tellers use another scratch layer to cover the ready onion.
Printing the candidate name For each ballot slice, the voting machine decrypts the booth onion and overwrites it with the corresponding candidate name. Note that since the voting machine has the knowledge of the private key , it can decrypt a booth onion
and retrieve its plaintext . Then the candidate name is derived as , where is a collision-resistant hash function and is the number of candidates.
Construction of the entire ballot forms When generating a ballot slice, all parties know that they are generating a ballot slice for some candidate, but not for which candidate. Once a large number of such ballot slices have been generated, there should be some ballot slices for every candidate. We now sort these ballot slices into piles according to the candidate names. Therefore, an entire ballot form can be constructed by selecting a ballot slice from each pile and stick them together with the candidate in the alphabetical order. Therefore, a ballot form will be shown as in Figure 8.
Step 3. Check the ballot construction
In the voting booth, each voter will be provided with two ballot forms. The voter can randomly choose one ballot form to challenge and casts her vote use the other one. To check whether a ballot form is correctly constructed, the voter removes the scratch surface in the right hand column. Then the voter requires the threshold tellers to decrypt one or several of the receipt onions, and checks whether the feedback of each receipt onion is the same as the candidate name printed in the left hand column.
Step 4. Ballot casting and tabulation
Our proposal scheme handles both approval elections and ranked elections. We will introduce how to cast a vote and how the received votes will be tallied in each case respectively.
Approval elections In the voting booth, each voter can randomly select a ballot form as shown in Figure 8. If a voter wishes to vote for Bob, she tears off the right hand column against Bob, as shown in Figure 9, destroys the remaining ballot form and submits the small piece to the election officials. The scratch surface is now checked, and only a vote with an intact scratch surface will be accepted. Then the voter removes the scratch surface in the presence of the election officials, revealing the receipt onion and its signature. The election officials check the signature, and return the small piece to the voter as the receipt after it has been scanned and signed. In the ballot tallying phase, all these received receipt onions will be tabulated by some mixnets, e.g. Neff's mix [41]. Finally, the shuffled votes will be decrypted by a quorum of tellers in a threshold fashion and the result will be announced.
Ranked elections We will introduce how to implement the proposal scheme in STV elections. Furthermore, it would be possible to implement it in some other ranked elections, such as Borda Court elections and Condorcet elections, if the ballot tallying phase has been modified according to the election requirement.
In STV elections, besides the ballot form, each voter will be provided with a voting card. A voter casts her vote as shown in Figure 10. She first tears off the right hand column against her most favourite candidate and sticks it to the first choice position in the voting card. Then she tears off the right hand column against her second preferred candidate and sticks it to the second choice position, and so on. The procedure of ballot submitting is similar: the voter removes the scratch surface in the presence of the election officials. Then the signatures are checked and the voting card will be returned to the voter as the receipt after it has been scanned and signed.
To tally STV votes, we apply the techniques which have been introduced in [29]. For simplicity, the notation will be used to denote the receipt onions. For example, a receipt onion for Bob will be denoted as . At first, each received vote will be sorted in a public manner. E.g. the example vote will be sorted as:
In this paper, we have introduced an information leakage model to analyse information leakage in mixnet based e-voting schemes. The model might be found useful because of the following two properties:
(1). In some complex e-voting schemes, just by experience, it might be difficult to work out all possible threats against voter privacy. The information leakage model can help to list all these threats in a systematic manner9. Furthermore, different threats can be assigned to different experts, therefore it is possible to implement the threat analysis in parallel.
(2). In some circumstances, although it might be impossible to prevent all threats against voter privacy, the information leakage model can help to identify which parties could collude to obtain informaiton leakage. Therefore, we can select these parties from different groups with different interests. For example, in the PAV-Paillier scheme, because of the use of multiple layer of scratch surface, the last re-encryption party colluding with the voting machine might find out how a certain voter has cast her vote. Therefore, they should be carefully chosen so that they should not collude.
We have applied the information leakage model with the PAV-Paillier scheme, and our result shows that the scheme still suffers some threats which might leak voters' choice information. However, the majority of the threats can be mitigated as long as the scheme is carefully implemented. And among all existing e-voting schemes, we still consider PAV-Paillier to be one of the best e-voting schemes to provide voter privacy.
We also have introduced a variant of the PAV-Paillier scheme. We inherit similar ideas to construct the ballot forms, but Paillier encryption has been replaced by ElGamal encryption. This directly yields a more simple and straightforward threshold cryptosystem. Furthermore, it provides some other interesting properties such as the candidate list can be given in alphabetical order, the scheme can handle not only approval elections but also ranked elections, and it mitigates the randomisation attack.
Peter Ryan has suggested that our proposal would be very convenient for French elections, in which there is a separate ballot for each candidate. The voters will find all the different ballots in the polling station. Each voter has to pick several ballots before entering the voting booth and then puts the ballot for the preferred candidate in an envelope. Therefore, it would be not necessary to stick the ballot slices together.
This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.70)
Copyright © 1993, 1994, 1995, 1996,
Nikos Drakos,
Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999,
Ross Moore,
Mathematics Department, Macquarie University, Sydney.
The command line arguments were:
latex2html -split 0 -show_section_numbers -local_icons -no_navigation PAV-Paillier.tex
The translation was initiated by Zhe Xia on 2008-06-26