# An Improved Coercion-Resistant E-Voting Scheme

Authors: Yuanjing Hao; Zhixin Zeng; Liang Chang
Journal: Security and Communication Networks
 (2021)

---

## Abstract

E-voting has gradually replaced the traditional voting methods to make it easier for people to conduct an election. Recently, Liu et al. propose an unconditional secure e-voting scheme using secret sharing and k-anonymity. Their scheme achieves correct tallying results without revealing raw voting information. However, in this paper, we observe that Liu et al.’s scheme cannot achieve coercion resistance in e-voting since the voter can prove the content of his ballot to the colluded candidates. Then, we propose an improved e-voting scheme to cover up the ballot of the voter with masked values. In this way, even if the voter colludes with corresponding candidates, he cannot prove which candidate he has voted for. Moreover, comparing with Liu et al.’s scheme, the security analysis shows that our proposed e-voting scheme achieves these security requirements like the coercion resistance, integrity of ballots, privacy of ballots, multiple-voting detection, and fairness. Through performance analysis, the experimental results show that our proposed e-voting scheme has higher time efficiency. Compared with other schemes, our scheme achieves a complete voting process and obtains the correct tallying result without complex computation and intricate communication process.


---

## Body

## 1. Introduction

At present, election is regarded as an indispensable democratic activity in real life. Over time, it has been divided into two categories: traditional election and electronic election. The traditional election consumes a lot of time and resources and has low tallying efficiency. Thus, Chaum [1] first proposed the electronic voting scheme in 1981, which eliminates these disadvantages. Subsequently, various e-voting schemes continue to spring up. Recently, cloud technology and blockchain technology are widely used in e-voting to achieve secure electronic election. For the cloud technology, Shankar et al. [2] proposed a secure e-voting protocol, which realizes secure data transfer with cloud effectively. Anjima and Hari [3] proposed a secure cloud e-voting system using fully homomorphic elliptical curve cryptography, which greatly ensures the privacy of ballots and minimizes the risk of the vote being tampered or leaked. Although the cloud technology presents advantages in the application of e-voting, it is less used than blockchain technology. Currently, some e-voting researches related to blockchain have a tendency to increase gradually, such as reducing voter fraud [4], preventing ballot content attacks [5], and achieving the universal verification of ballot [6]. However, the previously mentioned description mainly illustrates the recent development of e-voting, rather than the scope of our study.In a real election, due to multiparty participation, the voter may sell the content of his ballot to others to obtain profit. Out of curiosity, candidates may collude with other participants to infer the content of the original ballot. Therefore, in practical application, the secure e-voting scheme needs to satisfy some necessary security requirements to protect the privacy of ballot, such as freedom (no one can be forced to cast a certain vote); fairness (no one can use more than his own votes to influence the tallying result); confidentiality (no one can know other voter’s content except himself); coercion resistance [7–10] (the voter proves nothing about the content of his ballot to others); verifiability [11, 12] (every voter can verify if his ballot is correctly tallied, and any participant can verify the correctness of tallying result).For meeting the previously mentioned security requirements, some encryption techniques have been popularly applied to e-voting to achieve secure election, such as mix-net [13–16], blind signature [17–23], homomorphic encryption [24–28], and secret sharing [29–31]. Meanwhile, due to the high overhead, mix-net is hard to be applied for the actual election. Although blind signature has better practicality in e-voting, it does not satisfy the security requirement of receipt-freeness and verifiability to some extent. At present, in order to achieve secure and feasible e-voting, homomorphic encryption is popular in conjunction with other encryption techniques, such as zero-knowledge proof [32] and partial knowledge proof [33]. However, the computation burden becomes a problem that needs to be solved. Thus, avoiding these disadvantages of above encryption techniques, secret sharing is applied to e-voting because of its better completeness and feasibility and also achieves running time in linear [34]. Based on such advantages, Liu and Zhao [35] recently proposed an e-voting scheme using secret sharing and k-anonymity, which achieves the correct tallying result and satisfies the necessary security requirements. Concretely, the content of one ballot is used to sever as the coefficients of the shared polynomial. The calculated shares are regarded as the encrypted form of one ballot, respectively held by voter, voting system, and all candidates. Then, according to the additive homomorphism of secret sharing, the total number of ballots can be correctly obtained for each candidate. Liu and Zhao [35] declare their e-voting scheme achieves the security requirement of coercion resistance, which means the voter cannot prove the content of his ballot to others.However, in this paper, we observe that Liu et al.’s scheme cannot achieve the security requirement of coercion resistance. The voter can collude with candidates to prove the content of his ballot. Thus, we propose an improved coercion-resistant e-voting scheme to cover up the content of ballot with masked values, which achieves the security requirement of coercion resistance. Meantime, we also solve the abstention from voting. Additionally, through theoretical analysis and data simulation, we indicate that our proposed e-voting scheme can solve the shortcoming in [35] and has higher time efficiency compared with [32, 33]. Our contributions are shown in details as follows:(1)
In Liu et al.’s scheme [35], all voters and candidates hold shares. The shared polynomial constructed from the original ballot information can be recovered if the voter colludes with corresponding candidates. The voter can prove which candidate he has voted for. Liu et al.’s scheme does not satisfy the coercion-resistant security requirement. Thus, we propose an improved e-voting scheme, which replaces the content of the original ballot with masked values to achieve the construction of the share polynomial. In this way, even if the voter colludes with corresponding candidates to recover the shared polynomial, he cannot prove the content of his ballot to others. The improved e-voting scheme achieves coercion-resistant security requirement.(2)
The improved e-voting scheme considers abstention which Liu et al.’s scheme [35] does not accomplish. In the improved e-voting scheme, voting system constructs the shared polynomial of abstainer only using masked values, and then performs subsequent voting process. Finally, all participants can obtain the correct tallying result.(3)
The security analysis shows that the improved e-voting scheme not only inherits some security requirements in Liu et al.’s scheme [35] but also achieves coercion-resistant security requirement which Liu et al.’s scheme does not satisfy. Moreover, the scheme also achieves additional security properties which consist of the integrity of ballots, the privacy of ballots, multiple-voting detection, and fairness. The performance analysis shows that the proposed e-voting scheme has higher time efficiency when candidates and voters are, respectively, specific number.The rest of this paper is organized as follows. In Section2, the steps of Liu et al.’s e-voting scheme are reviewed. The system model and threat model are presented in Section 3. Section 4 proposes our improved e-voting scheme in detail. In Section 5, we state the differences between Liu et al.’s scheme and the improved e-voting scheme. Finally, the system analysis and conclusion are, respectively, presented in Section 6 and Section 7.


## 2. Review

In this section, Liu et al.’s scheme [35] is reviewed. It mainly consists of three phases: prevoting phase, voting phase, and postvoting phase. And the process of communication is shown in Figure 1.Figure 1
The process of communication.


### 2.1. Prevoting Phase

Assume that there aren voters and m candidates, respectively. The voters are divided into several sets, and each set containsk voters.


### 2.2. Voting Phase

Step 1. Each voter Vii=1,…,n registers to a trusted authority centre (AC). Then, the voting system (VS) issues a temporary identity IDi for each voter, and no one knows the relationship between voter and his temporary identity IDi.Step 2. If the candidate Cjj=1,…,m is selected by the voter Vi, ai,j=1; otherwise, ai,j=0. Then, VS generates the shared polynomial fix=ai,0+ai,1x+ai,2x2+⋯+ai,mxmmodp and computes m+2 shares xj,yi,j,j=1,2,…,m+2 by using the IDs of voter Vi, candidate Cjj=1,…,m and VS.Step 3. VS stores the share xm+1,yi,m+1, and then sends shares xj,yi,j,j=1,2,…,m to corresponding candidate Cj and credential CRi=ai,0,xm+2,yi,m+2 to the voter Vi.


### 2.3. Postvoting Phase

In this phase, first, voters are randomly divided into some sets, and each set containsk voters. The process can be briefly described in the following steps:Step 1. The voters who are located in a set publish their ai,0,i=1,…,k on the bulletin board.Step 2. VS and Cj compute yj=∑i=1kyi,j and publish the points xj,yj,j=1,2,…,m+1 on the bulletin board. According to these points, each participant can recover the polynomial Fx=a0+a1x+a2x2+⋯+amxmmodp, where aj=∑i=1kai,j,j=0,1,…,m.Step 3. VS publishes the aggregated ballots a0,a1,a2,…,am of k voters on the bulletin board.Step 4. The participant verifies the correctness of the aggregated ballots by the equation a0=∑i=1kai,0. If the verification is true, everyone can compute the result of Cj, votej=∑aj,j=1,2,…,m. Otherwise, all candidates and VS are asked to check their publishing information and reconstruct the polynomial again.


## 2.1. Prevoting Phase

Assume that there aren voters and m candidates, respectively. The voters are divided into several sets, and each set containsk voters.


## 2.2. Voting Phase

Step 1. Each voter Vii=1,…,n registers to a trusted authority centre (AC). Then, the voting system (VS) issues a temporary identity IDi for each voter, and no one knows the relationship between voter and his temporary identity IDi.Step 2. If the candidate Cjj=1,…,m is selected by the voter Vi, ai,j=1; otherwise, ai,j=0. Then, VS generates the shared polynomial fix=ai,0+ai,1x+ai,2x2+⋯+ai,mxmmodp and computes m+2 shares xj,yi,j,j=1,2,…,m+2 by using the IDs of voter Vi, candidate Cjj=1,…,m and VS.Step 3. VS stores the share xm+1,yi,m+1, and then sends shares xj,yi,j,j=1,2,…,m to corresponding candidate Cj and credential CRi=ai,0,xm+2,yi,m+2 to the voter Vi.


## 2.3. Postvoting Phase

In this phase, first, voters are randomly divided into some sets, and each set containsk voters. The process can be briefly described in the following steps:Step 1. The voters who are located in a set publish their ai,0,i=1,…,k on the bulletin board.Step 2. VS and Cj compute yj=∑i=1kyi,j and publish the points xj,yj,j=1,2,…,m+1 on the bulletin board. According to these points, each participant can recover the polynomial Fx=a0+a1x+a2x2+⋯+amxmmodp, where aj=∑i=1kai,j,j=0,1,…,m.Step 3. VS publishes the aggregated ballots a0,a1,a2,…,am of k voters on the bulletin board.Step 4. The participant verifies the correctness of the aggregated ballots by the equation a0=∑i=1kai,0. If the verification is true, everyone can compute the result of Cj, votej=∑aj,j=1,2,…,m. Otherwise, all candidates and VS are asked to check their publishing information and reconstruct the polynomial again.


## 3. The System Model and Threat Model

In this section, the system model, threat model, and design goals are introduced, respectively.


### 3.1. The System Model

In e-voting system, the participants involved are, respectively, a voter (V), candidate (C), trusted authority centre (AC), voting system (VS), and bulletin board, which is used to publish information in voting process. These participants mainly achieve the following functions:V: the voter votes for his favourite candidate and obtains the credential from VSC: the candidate and VS collaborate to get the tallying result togetherAC: AC authorizes the legal voter to cast the ballot and takes charge of arbitrating the disputes and granting the digital certificate for each participantVS: VS generates shares for candidate and credential for voter, respectively; moreover, VS leaks nothing about the intention of the voterIn this paper, the communication model is the same as Liu et al.’s scheme and presented in Figure1. In the communication model, a legal voter casts his favourite candidate using VS. VS generates corresponding credential for this voter and divides the masked voting intention of this voter into m shares. Then, VS sends credential to this voter and m shares to each candidate Cjj=1,…,m.


### 3.2. The Threat Model

In this section, the threat model is described, mainly embodied in the security issue of Liu et al.’s scheme. Many secure e-voting schemes can ensure the correctness of the tallying result. Meanwhile, Liu et al.’s scheme uses the homomorphic additivity of polynomial to get the correct tallying result. However, in this scheme, the voter can prove the content of his ballot to others. Their scheme cannot resist coercive attack from the internal voter, which cannot achieve coercion-resistant security requirement in e-voting. For the shortcoming in Liu et al.’s scheme, we give a brief example to describe the attack model. Assume that there are four candidates, and their IDs are separately 2, 3, 4, and 5.


#### 3.2.1. Adversary

Assume thatV1 is an internal attacker who launches the coercive attack to prove the content of his ballot to others. Meantime, assume that Vi’s ID is 1 and he casts candidates C1,C3,C4, a1,1=1,a1,2=0,a1,3=1,a1,4=1.


#### 3.2.2. Attack Process

(1)
First, for simplifying computation, we choosep=29. In voting phase, according to the selection of the voter V1, VS generates the shared polynomial f1x=3+x+x3+x4modp. Then, VS computes four shares (2,0), (3,27), (4,8), and (5,4), which are separately sent to C1,C2,C3,C4 and one credential 3,1,6, which is sent to V1.(2)
After receiving the credential,V1 colludes with the candidates C1,C3,C4 since he casts the supporting ballot for them. In this way, V1 can recover the shared polynomial f1x by owned random number 3 and known three shares of candidates C1,C3,C4.(3)
In order to prove the correctness of the recovered polynomialf1x, V1 verifies the recovered polynomial f1x using his share (1,6) and published random number a1,0=3. If the verification is true, the candidates C1,C3,C4 believe that the recovered polynomial f1x is true. In fact, the verification is usually true as long as the calculation is correct.


#### 3.2.3. Attack Result

Through construction of the shared polynomial in Liu et al.’s scheme, we know that the coefficient of the shared polynomial can show whether corresponding candidate obtains the ballot or not. If the coefficient is 1, it shows that the voter casts the candidate whose identity is the same as power of the shared polynomial. Thus, according to the description in attack process, the candidatesC1,C3,C4 believe the correctness of the recovered polynomial f1x. Naturally, V1 can prove he cast the supporting ballot for the candidates C1,C3,C4. Liu et al.’s scheme cannot achieve the security requirement of coercion resistance in e-voting.Therefore, to solve the shortcoming of Liu et al.’s scheme, we propose the improved coercion-resistant e-voting scheme. The scheme not only satisfies the coercion-resistant security requirement but also solves the issue of abstainers. The specific process is presented in section4.


### 3.3. Design Goals

For the design goals, we mainly introduce some necessary security requirements, which needs to be satisfied in next proposed e-voting scheme. These security requirements include coercion resistance, which Liu et al.’s scheme does not achieve and other additional security requirements, which are integrity of ballots, privacy of ballots, multiple-voting detection, and fairness.(i)
Coercion resistance: no one voter can prove to others which candidate he has voted for.(ii)
Integrity of ballots: in order to obtain correct tallying result, the ballots of all voters involved in the voting process should be counted validly.(iii)
Privacy of ballots: no one participant can leak any voting information.(iv)
Multiple-voting detection: a legal voter only can cast ballot once. If a voter votes for more than once, the superfluous ballots should be detected.(v)
Fairness: no one candidate can know his own ballot in advance.


## 3.1. The System Model

In e-voting system, the participants involved are, respectively, a voter (V), candidate (C), trusted authority centre (AC), voting system (VS), and bulletin board, which is used to publish information in voting process. These participants mainly achieve the following functions:V: the voter votes for his favourite candidate and obtains the credential from VSC: the candidate and VS collaborate to get the tallying result togetherAC: AC authorizes the legal voter to cast the ballot and takes charge of arbitrating the disputes and granting the digital certificate for each participantVS: VS generates shares for candidate and credential for voter, respectively; moreover, VS leaks nothing about the intention of the voterIn this paper, the communication model is the same as Liu et al.’s scheme and presented in Figure1. In the communication model, a legal voter casts his favourite candidate using VS. VS generates corresponding credential for this voter and divides the masked voting intention of this voter into m shares. Then, VS sends credential to this voter and m shares to each candidate Cjj=1,…,m.


## 3.2. The Threat Model

In this section, the threat model is described, mainly embodied in the security issue of Liu et al.’s scheme. Many secure e-voting schemes can ensure the correctness of the tallying result. Meanwhile, Liu et al.’s scheme uses the homomorphic additivity of polynomial to get the correct tallying result. However, in this scheme, the voter can prove the content of his ballot to others. Their scheme cannot resist coercive attack from the internal voter, which cannot achieve coercion-resistant security requirement in e-voting. For the shortcoming in Liu et al.’s scheme, we give a brief example to describe the attack model. Assume that there are four candidates, and their IDs are separately 2, 3, 4, and 5.


### 3.2.1. Adversary

Assume thatV1 is an internal attacker who launches the coercive attack to prove the content of his ballot to others. Meantime, assume that Vi’s ID is 1 and he casts candidates C1,C3,C4, a1,1=1,a1,2=0,a1,3=1,a1,4=1.


### 3.2.2. Attack Process

(1)
First, for simplifying computation, we choosep=29. In voting phase, according to the selection of the voter V1, VS generates the shared polynomial f1x=3+x+x3+x4modp. Then, VS computes four shares (2,0), (3,27), (4,8), and (5,4), which are separately sent to C1,C2,C3,C4 and one credential 3,1,6, which is sent to V1.(2)
After receiving the credential,V1 colludes with the candidates C1,C3,C4 since he casts the supporting ballot for them. In this way, V1 can recover the shared polynomial f1x by owned random number 3 and known three shares of candidates C1,C3,C4.(3)
In order to prove the correctness of the recovered polynomialf1x, V1 verifies the recovered polynomial f1x using his share (1,6) and published random number a1,0=3. If the verification is true, the candidates C1,C3,C4 believe that the recovered polynomial f1x is true. In fact, the verification is usually true as long as the calculation is correct.


### 3.2.3. Attack Result

Through construction of the shared polynomial in Liu et al.’s scheme, we know that the coefficient of the shared polynomial can show whether corresponding candidate obtains the ballot or not. If the coefficient is 1, it shows that the voter casts the candidate whose identity is the same as power of the shared polynomial. Thus, according to the description in attack process, the candidatesC1,C3,C4 believe the correctness of the recovered polynomial f1x. Naturally, V1 can prove he cast the supporting ballot for the candidates C1,C3,C4. Liu et al.’s scheme cannot achieve the security requirement of coercion resistance in e-voting.Therefore, to solve the shortcoming of Liu et al.’s scheme, we propose the improved coercion-resistant e-voting scheme. The scheme not only satisfies the coercion-resistant security requirement but also solves the issue of abstainers. The specific process is presented in section4.


## 3.2.1. Adversary

Assume thatV1 is an internal attacker who launches the coercive attack to prove the content of his ballot to others. Meantime, assume that Vi’s ID is 1 and he casts candidates C1,C3,C4, a1,1=1,a1,2=0,a1,3=1,a1,4=1.


## 3.2.2. Attack Process

(1)
First, for simplifying computation, we choosep=29. In voting phase, according to the selection of the voter V1, VS generates the shared polynomial f1x=3+x+x3+x4modp. Then, VS computes four shares (2,0), (3,27), (4,8), and (5,4), which are separately sent to C1,C2,C3,C4 and one credential 3,1,6, which is sent to V1.(2)
After receiving the credential,V1 colludes with the candidates C1,C3,C4 since he casts the supporting ballot for them. In this way, V1 can recover the shared polynomial f1x by owned random number 3 and known three shares of candidates C1,C3,C4.(3)
In order to prove the correctness of the recovered polynomialf1x, V1 verifies the recovered polynomial f1x using his share (1,6) and published random number a1,0=3. If the verification is true, the candidates C1,C3,C4 believe that the recovered polynomial f1x is true. In fact, the verification is usually true as long as the calculation is correct.


## 3.2.3. Attack Result

Through construction of the shared polynomial in Liu et al.’s scheme, we know that the coefficient of the shared polynomial can show whether corresponding candidate obtains the ballot or not. If the coefficient is 1, it shows that the voter casts the candidate whose identity is the same as power of the shared polynomial. Thus, according to the description in attack process, the candidatesC1,C3,C4 believe the correctness of the recovered polynomial f1x. Naturally, V1 can prove he cast the supporting ballot for the candidates C1,C3,C4. Liu et al.’s scheme cannot achieve the security requirement of coercion resistance in e-voting.Therefore, to solve the shortcoming of Liu et al.’s scheme, we propose the improved coercion-resistant e-voting scheme. The scheme not only satisfies the coercion-resistant security requirement but also solves the issue of abstainers. The specific process is presented in section4.


## 3.3. Design Goals

For the design goals, we mainly introduce some necessary security requirements, which needs to be satisfied in next proposed e-voting scheme. These security requirements include coercion resistance, which Liu et al.’s scheme does not achieve and other additional security requirements, which are integrity of ballots, privacy of ballots, multiple-voting detection, and fairness.(i)
Coercion resistance: no one voter can prove to others which candidate he has voted for.(ii)
Integrity of ballots: in order to obtain correct tallying result, the ballots of all voters involved in the voting process should be counted validly.(iii)
Privacy of ballots: no one participant can leak any voting information.(iv)
Multiple-voting detection: a legal voter only can cast ballot once. If a voter votes for more than once, the superfluous ballots should be detected.(v)
Fairness: no one candidate can know his own ballot in advance.


## 4. The Improved Voting Scheme

In this section, we present the improved e-voting scheme in detail. We first suppose that the trust assumptions are the same as [35]. The improved e-voting scheme consists of four phases: prevoting phase, voting phase, postvoting phase, and abstention from voting. Meanwhile, all computations are over a finite field Fp, where p is a secure prime, which is published by AC before the prevoting phase. The list of symbols used in the improved e-voting scheme is shown in Table 1, and Figure 2 shows the specific voting process in voting phase, postvoting phase, and abstention from voting.Table 1
List of notations.
SymbolSignificancenThe number of votersmThe number of candidatesVii-th voterCjj-th candidateIDiTemporary identification ofVi,i∈1,2,…,nkijSession key ofVi,i∈1,2,…,nβiThe number of session keys negotiated withVi,i∈1,2,…,nλi,lA value can be used to compute masked valuesBj,ij-th masked value of the i-th shared polynomialai,jA ballot fromVi,i∈1,2,…,n for Cj,j∈1,2,…,mxj,yi,jThe shares computed by thei-th shared polynomialCRiThe credential ofVi,i∈1,2,…,nyjThe sum of shares computed byCj,j∈1,2,…,majThe total number of ballots forCj,j∈1,2,…,mFigure 2
The voting phase, postvoting phase, and abstention from voting of two voters and two candidates in the improved e-voting system. Assume theVoter2 abstains from voting.


### 4.1. Prevoting Phase

Assume that there aren voters V1,…,Vn and m candidates C1,…,Cm.


### 4.2. Voting Phase

In this phase, the session keys are negotiated freely among voters, and VS computes the masked values. Then, each voter casts his favourite candidates and gets the credential in a face-to-face way. The process is described as follows:Step 1. Every voter Vi,i=1,2,…,n registers to AC. VS generates a temporary identity IDi,i=1,2,…,n for Vi, and no one knows the relationship between Vi and IDi.Step 2.Vi negotiates session key kij,i,j∈i=1,2,…,n,i≠j with other βi∈i=1,2,…,n−1 voters in a set and then obtains his session key list ki1,ki2,…,kiβi. For example, there are three voters V1,V2,V3 in a set, V1 and V2 share the session key k12, and V1 and V3 share the session key k13. Then, V1, V2, and V3 can, respectively, obtain their session key lists k12,k13, k21, and k31, where k12=k21,k13=k31.Step 3.Vi sends his session key list to VS via a secure channel. VS computes λi,l=∑j=1,j≠iβiIDi−IDjHkij|l,i∈i=1,2,…,n,l∈i=1,2,…,m and then divides λi,l=∑j=1nbl,j, where H:Zp∗⟶Zp∗ is a secure cryptographic hash function, which is published and bl,1,bl,2,…,bl,n are n random numbers. Afterwards, VS computes masked values ∑j=1nb1,i=B1,i,∑j=1nb2,i=B2,i,…,∑j=1nbm,i=Bm,i,i=1,2,…,n. Meanwhile, the masked values of the voter Vi can be represented as the list B1,i,B2,i,…,Bm,i.Step 4.Vi casts his favourite candidates. If the candidate Cjj=1,…,m is selected, ai,j=1; otherwise, ai,j=0. According to the computation of masked values for the voter Vi, VS constructs the shared polynomial fix=ai,0+B1,i+ai,1x+B2,i+ai,2x2+⋯+Bm,i+ai,mxmmodp, where ai,0≠0 is a random number.Step 5. Assume that the IDs of candidates Cjj=1,…,m, the voter Vi, and VS are, respectively, xj, xm+1 and xm+2. VS computes m+2 shares xj,yi,j,j=1,2,…,m+2 by the polynomial in Step 4. Then, VS stores the share xm+1,yi,m+1 and sends shares xj,yi,j,j=1,2,…,m to corresponding candidates Cjj=1,…,m and credential CRi=ai,0,xm+2,yi,m+2 to the voter Vi.


### 4.3. Postvoting Phase

In this phase, VS and all candidates reconstruct polynomial together by the sum of shares, and each participant can obtain the correct tallying result by verifying the constant coefficient of the reconstructed polynomial. The steps are given as follows:Step 1. All voters are published, and each voter Vi,i=1,2,…,n publishes their ai,0,i=1,2,…,n on the bulletin board.Step 2. VS and Cj compute yj=∑i=1nyi,jand publish the points xj,yj,j=1,2,…,m+1. Then, each participant can recover the polynomial Fx=a0+a1x+a2x2+⋯+amxmmodp, where aj=∑i=1nai,j,j=0,1,…,m. Finally, VS publishes the aggregated ballots a1,a2,…,am of n voters on the bulletin board.Step 3. Each participant verifies the correctness of the aggregated ballots by the equation a0=∑i=1nai,0. If the verification is not true, VS and all candidates are asked to check their publishing information and reconstruct the polynomial again.


### 4.4. Abstention from Voting

In the real-life case, abstention from voting is widespread. For obtaining the correct tallying result, when there are abstainers in voting phase, VS sets their ballots as 0 and then constructs the shared polynomials only using the masked values. In proposed e-voting scheme, if the candidateCj,j∈1,…,m obtains the supporting ballot of the voter Vi,i∈1,2,…,n, ai,j=1. For one abstainer, it can consider that all candidates do not get the supporting ballot from the abstainer. VS sets ai,j=0,i∈1,2,…,n,j=1,…,m. In this way, the voting system not only ensures the normal voting process but also does not make a difference for the voting result. Therefore, the improved e-voting scheme solves the issue of abstainers and guarantees the correctness of the tallying result.


## 4.1. Prevoting Phase

Assume that there aren voters V1,…,Vn and m candidates C1,…,Cm.


## 4.2. Voting Phase

In this phase, the session keys are negotiated freely among voters, and VS computes the masked values. Then, each voter casts his favourite candidates and gets the credential in a face-to-face way. The process is described as follows:Step 1. Every voter Vi,i=1,2,…,n registers to AC. VS generates a temporary identity IDi,i=1,2,…,n for Vi, and no one knows the relationship between Vi and IDi.Step 2.Vi negotiates session key kij,i,j∈i=1,2,…,n,i≠j with other βi∈i=1,2,…,n−1 voters in a set and then obtains his session key list ki1,ki2,…,kiβi. For example, there are three voters V1,V2,V3 in a set, V1 and V2 share the session key k12, and V1 and V3 share the session key k13. Then, V1, V2, and V3 can, respectively, obtain their session key lists k12,k13, k21, and k31, where k12=k21,k13=k31.Step 3.Vi sends his session key list to VS via a secure channel. VS computes λi,l=∑j=1,j≠iβiIDi−IDjHkij|l,i∈i=1,2,…,n,l∈i=1,2,…,m and then divides λi,l=∑j=1nbl,j, where H:Zp∗⟶Zp∗ is a secure cryptographic hash function, which is published and bl,1,bl,2,…,bl,n are n random numbers. Afterwards, VS computes masked values ∑j=1nb1,i=B1,i,∑j=1nb2,i=B2,i,…,∑j=1nbm,i=Bm,i,i=1,2,…,n. Meanwhile, the masked values of the voter Vi can be represented as the list B1,i,B2,i,…,Bm,i.Step 4.Vi casts his favourite candidates. If the candidate Cjj=1,…,m is selected, ai,j=1; otherwise, ai,j=0. According to the computation of masked values for the voter Vi, VS constructs the shared polynomial fix=ai,0+B1,i+ai,1x+B2,i+ai,2x2+⋯+Bm,i+ai,mxmmodp, where ai,0≠0 is a random number.Step 5. Assume that the IDs of candidates Cjj=1,…,m, the voter Vi, and VS are, respectively, xj, xm+1 and xm+2. VS computes m+2 shares xj,yi,j,j=1,2,…,m+2 by the polynomial in Step 4. Then, VS stores the share xm+1,yi,m+1 and sends shares xj,yi,j,j=1,2,…,m to corresponding candidates Cjj=1,…,m and credential CRi=ai,0,xm+2,yi,m+2 to the voter Vi.


## 4.3. Postvoting Phase

In this phase, VS and all candidates reconstruct polynomial together by the sum of shares, and each participant can obtain the correct tallying result by verifying the constant coefficient of the reconstructed polynomial. The steps are given as follows:Step 1. All voters are published, and each voter Vi,i=1,2,…,n publishes their ai,0,i=1,2,…,n on the bulletin board.Step 2. VS and Cj compute yj=∑i=1nyi,jand publish the points xj,yj,j=1,2,…,m+1. Then, each participant can recover the polynomial Fx=a0+a1x+a2x2+⋯+amxmmodp, where aj=∑i=1nai,j,j=0,1,…,m. Finally, VS publishes the aggregated ballots a1,a2,…,am of n voters on the bulletin board.Step 3. Each participant verifies the correctness of the aggregated ballots by the equation a0=∑i=1nai,0. If the verification is not true, VS and all candidates are asked to check their publishing information and reconstruct the polynomial again.


## 4.4. Abstention from Voting

In the real-life case, abstention from voting is widespread. For obtaining the correct tallying result, when there are abstainers in voting phase, VS sets their ballots as 0 and then constructs the shared polynomials only using the masked values. In proposed e-voting scheme, if the candidateCj,j∈1,…,m obtains the supporting ballot of the voter Vi,i∈1,2,…,n, ai,j=1. For one abstainer, it can consider that all candidates do not get the supporting ballot from the abstainer. VS sets ai,j=0,i∈1,2,…,n,j=1,…,m. In this way, the voting system not only ensures the normal voting process but also does not make a difference for the voting result. Therefore, the improved e-voting scheme solves the issue of abstainers and guarantees the correctness of the tallying result.


## 5. Differences of Two Schemes

In this section, the differences are expounded between Liu et al.’s scheme [35] and the improved e-voting scheme. We describe these differences in terms of the following five security requirements:Coercion resistance: coercion resistance means that no one voter can prove the content of his ballot to others. The requirement is described from the aspect of the voter. When the voter acts as an internal attacker, he cannot disclose the content of the original ballot. In Liu et al.’s scheme, VS constructs the shared polynomial with the ballot of one voter. However, if this voter colludes with at mostm candidates, he can recover the shared polynomial to disclose the content of the original ballot and prove which candidate he has voted for. Therefore, Liu et al.’s scheme cannot resist the coercive attack from the internal voter. In the improved e-voting scheme, the masked values are computed and added to the coefficients of the original shared polynomial. In this way, even if the voter recovers the shared polynomial, he also cannot prove the content of his ballot to others. The improved e-voting scheme achieves the security requirement of coercion resistance.Abstention from voting: in a real election, there are voters who may abstain from voting. In Liu et al.’s scheme, all voters take part in the election. Liu et al.’s scheme does not consider the issue of the abstainer. However, in the improved e-voting scheme, for an abstainer, we set his ballot as 0. In this way, all candidates cannot obtain the supporting ballot from the abstainer, which ensures the correctness of tallying result. Therefore, comparing Liu et al.’s scheme, the improved e-voting scheme considers the issue of abstainer and can obtain the correct tallying result.Privacy: in Liu et al.’s scheme, the voter can reveal the content of his ballot by colluding with some candidates. The scheme does not meet the privacy requirement in e-voting. However, in the improved e-voting scheme, the computation of the masked values prevents the voter from revealing the content of his ballot. Moreover, the participant can only obtain the tallying result by recovering the polynomial in postvoting phase. Thus, the improved e-voting scheme satisfies the privacy requirement of ballot.Security: security means that the voting scheme does not rely on the hard problem, such as discrete logarithm and integer factorization, and still can achieve the confidentiality of the voting process. This requirement is described from the aspect of the voting scheme. Without additionally complex conditions, the voting scheme can resist attacks from external and internal adversaries, respectively, and achieve the confidentiality of the original ballot. In Liu et al.’s scheme, it shows that the malicious adversary cannot obtain any voting information from some shares. In fact, according to the executive process of secret sharing, Liu et al.’s scheme does not achieve the confidentiality of the original ballot. First, as described in the security requirement of the coercion resistance, Liu et al.’s scheme cannot resist the coercive attack from an internal adversary. Second, since the number of shareholders exceeds the thresholdmof secret sharing in Liu et al.’s scheme. Likewise, Liu et al.’s scheme is also hard to prevent external adversary from obtaining the content of the original ballot. Thus, Liu et al.’s scheme cannot guarantee the requirement of security. However, in the improved e-voting scheme, the shares cannot be served as an advantage for adversary to reveal the content of the original ballot. The improved e-voting scheme guarantees the confidentiality of original ballot forever, which achieves the requirement of security.Fairness: fairness means that no one can know the ballot information in advance. In Liu et al.’s scheme, the voter can prove the content of his ballot to corresponding some candidates. In this way, these candidates can know partial ballots in advance. Liu et al.’s scheme does not satisfy the fairness requirement in e-voting. However, in the improved e-voting scheme, no one can know any ballot information in advance, and the correct tallying result can be obtained simultaneously by each participant. The improved e-voting scheme achieves the fairness requirement.


## 6. System Analysis

The system analysis includes the security analysis and the performance analysis.


### 6.1. Security Analysis

The improved e-voting scheme inherits these security requirements, which are correctness, anonymity, confidentiality, efficiency, noncheating, and universal verifiability in Liu et al.’s scheme [35]. Moreover, the improved e-voting scheme also achieves coercion-resistant security requirement, which Liu et al.’s scheme does not accomplish by adding masked values to the coefficients of the original shared polynomial. In this way, the content of one ballot can be protected, and corresponding privacy requirement can also be satisfied. Meantime, the improved e-voting scheme considers the abstention from voting, which not only ensures the correct tallying result but also achieves integrity of ballots.In the following part of this section, we give theoretical analysis and proof of the integrity of ballots, privacy of ballots, multiple-voting detection, fairness, and coercion resistance of the improved e-voting scheme.


#### 6.1.1. Integrity of Ballots

Theorem 1.
For voters who submit the session key list, VS should hold their voting information to ensure the integrity of ballots and then achieve the correct tallying result.Proof.
In a real election, the registered voter may give up casting his ballot. In the proposed e-voting system, assume that a voterVt,t∈1,2,…,n gives up voting for a ballot after submitting the session key list to VS.
For simplifying analysis, assume that separately negotiates the session key with the remaining voters in voting phase. First, VS computes and dividesλ as follows:(1)λ1,1=−Hk12|1+⋯+1−tHk1t|1+⋯+1−nHk1n|1=b1,1+⋯+b1,t+⋯+b1,n,⋯,λ1,m=−Hk12|m+⋯+1−tHk1t|m+⋯+1−nHk1n|m=bm,1+⋯+bm,t+⋯+bm,n,⋮,⋮,λn,1=n−1Hkn1|1=b1,1+⋯+b1,t+⋯+b1,n,⋯,λn,m=n−1Hkn1|1=bm,1+⋯+bm,t+⋯+bm,n.
Equation (1) shows ∑i=1nλi,l=0,l∈1,2,…,m. Then, VS computes the masked values B1,i=∑j=1nb1,i,…,Bm,i=∑j=1nbm,i,i=1,2,…,n.
For the abstainerVt,t∈1,2,…,n, if VS does not construct his shared polynomial, and the sum of shares can be computed as(2)∑i=1,i≠tnfix=∑i=1,i≠tna0,i+∑i=1nλi,1−∑j=1nb1,t+∑j=1nai,1x+⋯+∑i=1nλi,m−∑i=1nbm,t+∑i=1,i≠tnai,mxmmodp=∑i=1,i≠tna0,i+∑j=1nb1,t+∑i=1,i≠tnai,1x+⋯+−∑j=1nbm,t+∑i=1,i≠tnai,mxmmodp.
According to secret sharing homomorphism, the tallying result is−∑j=1nb1,t+∑i=1,i≠tnai,1,…,−∑j=1nbm,t+∑i=1,i≠tnai,m, instead of ∑i=1,i≠tnai,1,…,∑i=1,i≠tnai,m,.
Thus, in order to obtain the correct tallying result, VS should ensure the integrity of ballots. In our voting system, VS sets the ballot of abstainerVt as 0 and constructs the shared polynomial ftx=at,0+∑j=1nb1,tx+⋯+∑j=1nbm,txmmodp. In this way, the sum of shares is ∑i=1nfix=∑i=1na0,i+∑i=1nai,1x+⋯+∑i=1nai,mxmmodp. The ballot of Vt is 0. Therefore, the tallying result is ∑i=1nai,1=∑i=1,i≠tnai,1,…,∑i=1nai,m=∑i=1,i≠tnai,m.
To sum up, in a real election, abstention from voting needs to be considered to ensure the integrity of ballots and obtain the correct tallying result.


#### 6.1.2. Privacy of Ballots

Theorem 2.
No one voter or candidate can reveal any voting information.Proof.
In proposed voting scheme, assume the voterVk,k∈1,2,…,n colludes with m candidates after receiving credential and then recovers the shared polynomial fkx=ak,0+∑j=1nb1,k+ak,1x+⋯+∑j=1nbm,k+ak,mxmmodp. However, the voting information ak,1,…,ak,m cannot be revealed because of the masked values ∑j=1nb1,k,…,∑j=1nbm,k. Therefore, in the proposed e-voting scheme, even if a voter or candidate has enough computing power, he also cannot reveal any voting information. The scheme achieves the privacy requirement of ballots.


#### 6.1.3. Multiple-Voting Detection

Theorem 3.
A legal voter only can submit ballot to VS once.Proof.
In the proposed e-voting system, assume the legal voterVh,h∈1,2,…,n submits ballot to VS twice. In this way, VS can construct two shared polynomials fh1x and fh2x for Vh according to twice different submissions. Then, the voter Vh can receive two credentials, and each candidate can receive n+1 shares. However, according to the computation of the sum of shares in postvoting phase, each candidate only can hold n shares. Moreover, when all voters are published, each candidate can discover that the number of received shares is not equal to n. Thus, the multiple-voting is detected for the voter Vh. The improved e-voting scheme satisfies the requirement that a legal voter casts a ballot once.


#### 6.1.4. Fairness

Theorem 4.
No one candidate can know his own ballot in advance.Proof.
For knowing the voting information about himself, the candidate is willing to collude with one voter to reveal the content of one ballot after receiving shares. However, in the proof of Theorem2, it shows that no one voter can leak any privacy of ballots. Thus, it is impossible for one candidate to know the content of the single ballot in advance. Moreover, in postvoting phase, the sums of shares are published on the bulletin board, and any participant can obtain the tallying result. Therefore, the improved e-voting scheme achieves the requirement of fairness in e-voting.


#### 6.1.5. Coercion Resistance

Theorem 5.
No one voter can prove the content of his ballot to others.Proof.
In voting phase, assume that VS constructs the shared polynomialfex=ae,0+B1,e+ae,1x+B2,e+ae,2x2+⋯+Bm,e+ae,mxmmodp for the voter Ve,e∈1,2,…,n, and computes shares IDC1,feIDC1,…,IDCm,feIDCm,IDVS,feIDVS and credential ae,0,IDe,feIDe. The shares IDC1,feIDC1,…,IDCm,feIDCm are sent to corresponding candidates C1,…,Cm, and the credential ae,0,IDe,feIDe is sent to the voter Ve. For proving the content of the ballot, it is most likely for Ve to recover the shared polynomial fex by colluding with m candidates. However, different from the Liu et al.’s scheme [35], the improved e-voting scheme masks the relationship between coefficient of shared polynomial and voting information. Even if the voter Ve recovers the shared polynomial fex, he cannot prove his voting intention ae,1,…,ae,m to others. Thus, the scheme achieves the security requirement of coercion resistance.


### 6.2. Performance Analysis

In this section, the performance of our proposed e-voting system is analysed. The prevoting phase has no computation, which only distributes the numbers of the voters and candidates. Thus, we mainly analyse the computation cost of the voting phase and postvoting phase. In addition, we compare our scheme with [32, 33, 35] for partial security requirement and computation complexity, which is shown in Table 2. Moreover, we also, respectively, test the total time cost for the different numbers of voters and candidates by using the 1024-bit session key and the 512-bit shared secret on a laptop with Intel i5 3.1 GHz CPU and 8.00 GB memory, and the result is shown in Figures 3 and 4.Table 2
Comparison of partial security requirement and computation complexity.
Performance[35][32][33]Our schemePrivacyNoYesYesYesCoercion resistanceNoNoNoYesVerifiabilityYesYesYesYesComputation complexityOnmOnlognOnmOnmFigure 3
The total time cost comparison for four schemes in the case of five candidates: the number of voters is, respectively, 1000, 3000, 6000, 10000, 15000, and 21000.Figure 4
The total time cost comparison for four schemes in the case of 10000 voters: the number of candidates is, respectively, 2, 3, 5, 6, 7, and 8.


#### 6.2.1. Performance Analysis of the Voting Phase

In the voting phase, the five steps are as follows: registering identification for voters, negotiating session keys among voters, generating masked values, constructing shared polynomials, and computing shares. Meanwhile, the computation cost mainly concentrates upon generating masked values and computing shares. Assume that the computation costs of one masked value and one share are separately expressed ascostmask and costshare. The total computation cost in this phase can be expressed as costvoting_phase=n⋅m⋅costmask+n⋅m+2⋅costshare.


#### 6.2.2. Performance Analysis of the Postvoting Phase

In postvoting phase, VS and candidates are responsible for computing the sum of shares and then publish. Each participant reconstructs a polynomial to obtain the tallying result and then verifies it. Meanwhile, computing the sum of shares, recovering polynomial, and verifying the tallying result are the main computation cost in this phase. Assume that they are separately expressed ascostshare_sum, costrecover, and costverify. The total computation cost in this phase is costpost_voting=m+1⋅costshare_sum+costrecover+costverify.From the previously mentioned analysis of two phases, the total computation cost iscosttotal=costvoting_phase+costpost_voting in the improved e-voting scheme and increases with the numbers of voters and candidates. Thus, the computation complexity is Onm in the improved e-voting scheme. In Table 2, it shows that our e-voting scheme simultaneously achieves privacy, verifiability, and coercion resistance, and the computation complexity is less than that mentioned in [32] due to m≪n.In Figure3, we select m=5 candidates to test the total time cost with different numbers of voters. As shown in Figure 3, the total time cost of the improved e-voting scheme is slightly higher than the scheme [35]. Liu et al.’s scheme [35] is unaffected by the numbers of voters. Therefore, it has an advantage in total time cost. However, it cannot achieve the security requirement of coercion resistance in e-voting. Although the improved e-voting scheme increases the total time cost, it achieves the coercion-resistant security requirement. Moreover, comparing [32, 33], the improved e-voting scheme takes less time overall.In Figure4, we select n=10000 voters to test the total time cost with different numbers of candidates. As shown in Figure 4, both the improved e-voting scheme and the scheme [35] increase with the numbers of candidates in the total time cost. Similarly, the total time cost of the improved e-voting scheme is slightly higher than the scheme [35]. In order to achieve the security requirement of coercion resistance, the improved e-voting scheme adds masked values on the basis of the scheme [35]. Thus, the computation cost is higher than Liu et al.’s scheme [35]. However, the total time consumption is still smaller than those in [32, 33].


## 6.1. Security Analysis

The improved e-voting scheme inherits these security requirements, which are correctness, anonymity, confidentiality, efficiency, noncheating, and universal verifiability in Liu et al.’s scheme [35]. Moreover, the improved e-voting scheme also achieves coercion-resistant security requirement, which Liu et al.’s scheme does not accomplish by adding masked values to the coefficients of the original shared polynomial. In this way, the content of one ballot can be protected, and corresponding privacy requirement can also be satisfied. Meantime, the improved e-voting scheme considers the abstention from voting, which not only ensures the correct tallying result but also achieves integrity of ballots.In the following part of this section, we give theoretical analysis and proof of the integrity of ballots, privacy of ballots, multiple-voting detection, fairness, and coercion resistance of the improved e-voting scheme.


### 6.1.1. Integrity of Ballots

Theorem 1.
For voters who submit the session key list, VS should hold their voting information to ensure the integrity of ballots and then achieve the correct tallying result.Proof.
In a real election, the registered voter may give up casting his ballot. In the proposed e-voting system, assume that a voterVt,t∈1,2,…,n gives up voting for a ballot after submitting the session key list to VS.
For simplifying analysis, assume that separately negotiates the session key with the remaining voters in voting phase. First, VS computes and dividesλ as follows:(1)λ1,1=−Hk12|1+⋯+1−tHk1t|1+⋯+1−nHk1n|1=b1,1+⋯+b1,t+⋯+b1,n,⋯,λ1,m=−Hk12|m+⋯+1−tHk1t|m+⋯+1−nHk1n|m=bm,1+⋯+bm,t+⋯+bm,n,⋮,⋮,λn,1=n−1Hkn1|1=b1,1+⋯+b1,t+⋯+b1,n,⋯,λn,m=n−1Hkn1|1=bm,1+⋯+bm,t+⋯+bm,n.
Equation (1) shows ∑i=1nλi,l=0,l∈1,2,…,m. Then, VS computes the masked values B1,i=∑j=1nb1,i,…,Bm,i=∑j=1nbm,i,i=1,2,…,n.
For the abstainerVt,t∈1,2,…,n, if VS does not construct his shared polynomial, and the sum of shares can be computed as(2)∑i=1,i≠tnfix=∑i=1,i≠tna0,i+∑i=1nλi,1−∑j=1nb1,t+∑j=1nai,1x+⋯+∑i=1nλi,m−∑i=1nbm,t+∑i=1,i≠tnai,mxmmodp=∑i=1,i≠tna0,i+∑j=1nb1,t+∑i=1,i≠tnai,1x+⋯+−∑j=1nbm,t+∑i=1,i≠tnai,mxmmodp.
According to secret sharing homomorphism, the tallying result is−∑j=1nb1,t+∑i=1,i≠tnai,1,…,−∑j=1nbm,t+∑i=1,i≠tnai,m, instead of ∑i=1,i≠tnai,1,…,∑i=1,i≠tnai,m,.
Thus, in order to obtain the correct tallying result, VS should ensure the integrity of ballots. In our voting system, VS sets the ballot of abstainerVt as 0 and constructs the shared polynomial ftx=at,0+∑j=1nb1,tx+⋯+∑j=1nbm,txmmodp. In this way, the sum of shares is ∑i=1nfix=∑i=1na0,i+∑i=1nai,1x+⋯+∑i=1nai,mxmmodp. The ballot of Vt is 0. Therefore, the tallying result is ∑i=1nai,1=∑i=1,i≠tnai,1,…,∑i=1nai,m=∑i=1,i≠tnai,m.
To sum up, in a real election, abstention from voting needs to be considered to ensure the integrity of ballots and obtain the correct tallying result.


### 6.1.2. Privacy of Ballots

Theorem 2.
No one voter or candidate can reveal any voting information.Proof.
In proposed voting scheme, assume the voterVk,k∈1,2,…,n colludes with m candidates after receiving credential and then recovers the shared polynomial fkx=ak,0+∑j=1nb1,k+ak,1x+⋯+∑j=1nbm,k+ak,mxmmodp. However, the voting information ak,1,…,ak,m cannot be revealed because of the masked values ∑j=1nb1,k,…,∑j=1nbm,k. Therefore, in the proposed e-voting scheme, even if a voter or candidate has enough computing power, he also cannot reveal any voting information. The scheme achieves the privacy requirement of ballots.


### 6.1.3. Multiple-Voting Detection

Theorem 3.
A legal voter only can submit ballot to VS once.Proof.
In the proposed e-voting system, assume the legal voterVh,h∈1,2,…,n submits ballot to VS twice. In this way, VS can construct two shared polynomials fh1x and fh2x for Vh according to twice different submissions. Then, the voter Vh can receive two credentials, and each candidate can receive n+1 shares. However, according to the computation of the sum of shares in postvoting phase, each candidate only can hold n shares. Moreover, when all voters are published, each candidate can discover that the number of received shares is not equal to n. Thus, the multiple-voting is detected for the voter Vh. The improved e-voting scheme satisfies the requirement that a legal voter casts a ballot once.


### 6.1.4. Fairness

Theorem 4.
No one candidate can know his own ballot in advance.Proof.
For knowing the voting information about himself, the candidate is willing to collude with one voter to reveal the content of one ballot after receiving shares. However, in the proof of Theorem2, it shows that no one voter can leak any privacy of ballots. Thus, it is impossible for one candidate to know the content of the single ballot in advance. Moreover, in postvoting phase, the sums of shares are published on the bulletin board, and any participant can obtain the tallying result. Therefore, the improved e-voting scheme achieves the requirement of fairness in e-voting.


### 6.1.5. Coercion Resistance

Theorem 5.
No one voter can prove the content of his ballot to others.Proof.
In voting phase, assume that VS constructs the shared polynomialfex=ae,0+B1,e+ae,1x+B2,e+ae,2x2+⋯+Bm,e+ae,mxmmodp for the voter Ve,e∈1,2,…,n, and computes shares IDC1,feIDC1,…,IDCm,feIDCm,IDVS,feIDVS and credential ae,0,IDe,feIDe. The shares IDC1,feIDC1,…,IDCm,feIDCm are sent to corresponding candidates C1,…,Cm, and the credential ae,0,IDe,feIDe is sent to the voter Ve. For proving the content of the ballot, it is most likely for Ve to recover the shared polynomial fex by colluding with m candidates. However, different from the Liu et al.’s scheme [35], the improved e-voting scheme masks the relationship between coefficient of shared polynomial and voting information. Even if the voter Ve recovers the shared polynomial fex, he cannot prove his voting intention ae,1,…,ae,m to others. Thus, the scheme achieves the security requirement of coercion resistance.


## 6.1.1. Integrity of Ballots

Theorem 1.
For voters who submit the session key list, VS should hold their voting information to ensure the integrity of ballots and then achieve the correct tallying result.Proof.
In a real election, the registered voter may give up casting his ballot. In the proposed e-voting system, assume that a voterVt,t∈1,2,…,n gives up voting for a ballot after submitting the session key list to VS.
For simplifying analysis, assume that separately negotiates the session key with the remaining voters in voting phase. First, VS computes and dividesλ as follows:(1)λ1,1=−Hk12|1+⋯+1−tHk1t|1+⋯+1−nHk1n|1=b1,1+⋯+b1,t+⋯+b1,n,⋯,λ1,m=−Hk12|m+⋯+1−tHk1t|m+⋯+1−nHk1n|m=bm,1+⋯+bm,t+⋯+bm,n,⋮,⋮,λn,1=n−1Hkn1|1=b1,1+⋯+b1,t+⋯+b1,n,⋯,λn,m=n−1Hkn1|1=bm,1+⋯+bm,t+⋯+bm,n.
Equation (1) shows ∑i=1nλi,l=0,l∈1,2,…,m. Then, VS computes the masked values B1,i=∑j=1nb1,i,…,Bm,i=∑j=1nbm,i,i=1,2,…,n.
For the abstainerVt,t∈1,2,…,n, if VS does not construct his shared polynomial, and the sum of shares can be computed as(2)∑i=1,i≠tnfix=∑i=1,i≠tna0,i+∑i=1nλi,1−∑j=1nb1,t+∑j=1nai,1x+⋯+∑i=1nλi,m−∑i=1nbm,t+∑i=1,i≠tnai,mxmmodp=∑i=1,i≠tna0,i+∑j=1nb1,t+∑i=1,i≠tnai,1x+⋯+−∑j=1nbm,t+∑i=1,i≠tnai,mxmmodp.
According to secret sharing homomorphism, the tallying result is−∑j=1nb1,t+∑i=1,i≠tnai,1,…,−∑j=1nbm,t+∑i=1,i≠tnai,m, instead of ∑i=1,i≠tnai,1,…,∑i=1,i≠tnai,m,.
Thus, in order to obtain the correct tallying result, VS should ensure the integrity of ballots. In our voting system, VS sets the ballot of abstainerVt as 0 and constructs the shared polynomial ftx=at,0+∑j=1nb1,tx+⋯+∑j=1nbm,txmmodp. In this way, the sum of shares is ∑i=1nfix=∑i=1na0,i+∑i=1nai,1x+⋯+∑i=1nai,mxmmodp. The ballot of Vt is 0. Therefore, the tallying result is ∑i=1nai,1=∑i=1,i≠tnai,1,…,∑i=1nai,m=∑i=1,i≠tnai,m.
To sum up, in a real election, abstention from voting needs to be considered to ensure the integrity of ballots and obtain the correct tallying result.


## 6.1.2. Privacy of Ballots

Theorem 2.
No one voter or candidate can reveal any voting information.Proof.
In proposed voting scheme, assume the voterVk,k∈1,2,…,n colludes with m candidates after receiving credential and then recovers the shared polynomial fkx=ak,0+∑j=1nb1,k+ak,1x+⋯+∑j=1nbm,k+ak,mxmmodp. However, the voting information ak,1,…,ak,m cannot be revealed because of the masked values ∑j=1nb1,k,…,∑j=1nbm,k. Therefore, in the proposed e-voting scheme, even if a voter or candidate has enough computing power, he also cannot reveal any voting information. The scheme achieves the privacy requirement of ballots.


## 6.1.3. Multiple-Voting Detection

Theorem 3.
A legal voter only can submit ballot to VS once.Proof.
In the proposed e-voting system, assume the legal voterVh,h∈1,2,…,n submits ballot to VS twice. In this way, VS can construct two shared polynomials fh1x and fh2x for Vh according to twice different submissions. Then, the voter Vh can receive two credentials, and each candidate can receive n+1 shares. However, according to the computation of the sum of shares in postvoting phase, each candidate only can hold n shares. Moreover, when all voters are published, each candidate can discover that the number of received shares is not equal to n. Thus, the multiple-voting is detected for the voter Vh. The improved e-voting scheme satisfies the requirement that a legal voter casts a ballot once.


## 6.1.4. Fairness

Theorem 4.
No one candidate can know his own ballot in advance.Proof.
For knowing the voting information about himself, the candidate is willing to collude with one voter to reveal the content of one ballot after receiving shares. However, in the proof of Theorem2, it shows that no one voter can leak any privacy of ballots. Thus, it is impossible for one candidate to know the content of the single ballot in advance. Moreover, in postvoting phase, the sums of shares are published on the bulletin board, and any participant can obtain the tallying result. Therefore, the improved e-voting scheme achieves the requirement of fairness in e-voting.


## 6.1.5. Coercion Resistance

Theorem 5.
No one voter can prove the content of his ballot to others.Proof.
In voting phase, assume that VS constructs the shared polynomialfex=ae,0+B1,e+ae,1x+B2,e+ae,2x2+⋯+Bm,e+ae,mxmmodp for the voter Ve,e∈1,2,…,n, and computes shares IDC1,feIDC1,…,IDCm,feIDCm,IDVS,feIDVS and credential ae,0,IDe,feIDe. The shares IDC1,feIDC1,…,IDCm,feIDCm are sent to corresponding candidates C1,…,Cm, and the credential ae,0,IDe,feIDe is sent to the voter Ve. For proving the content of the ballot, it is most likely for Ve to recover the shared polynomial fex by colluding with m candidates. However, different from the Liu et al.’s scheme [35], the improved e-voting scheme masks the relationship between coefficient of shared polynomial and voting information. Even if the voter Ve recovers the shared polynomial fex, he cannot prove his voting intention ae,1,…,ae,m to others. Thus, the scheme achieves the security requirement of coercion resistance.


## 6.2. Performance Analysis

In this section, the performance of our proposed e-voting system is analysed. The prevoting phase has no computation, which only distributes the numbers of the voters and candidates. Thus, we mainly analyse the computation cost of the voting phase and postvoting phase. In addition, we compare our scheme with [32, 33, 35] for partial security requirement and computation complexity, which is shown in Table 2. Moreover, we also, respectively, test the total time cost for the different numbers of voters and candidates by using the 1024-bit session key and the 512-bit shared secret on a laptop with Intel i5 3.1 GHz CPU and 8.00 GB memory, and the result is shown in Figures 3 and 4.Table 2
Comparison of partial security requirement and computation complexity.
Performance[35][32][33]Our schemePrivacyNoYesYesYesCoercion resistanceNoNoNoYesVerifiabilityYesYesYesYesComputation complexityOnmOnlognOnmOnmFigure 3
The total time cost comparison for four schemes in the case of five candidates: the number of voters is, respectively, 1000, 3000, 6000, 10000, 15000, and 21000.Figure 4
The total time cost comparison for four schemes in the case of 10000 voters: the number of candidates is, respectively, 2, 3, 5, 6, 7, and 8.


### 6.2.1. Performance Analysis of the Voting Phase

In the voting phase, the five steps are as follows: registering identification for voters, negotiating session keys among voters, generating masked values, constructing shared polynomials, and computing shares. Meanwhile, the computation cost mainly concentrates upon generating masked values and computing shares. Assume that the computation costs of one masked value and one share are separately expressed ascostmask and costshare. The total computation cost in this phase can be expressed as costvoting_phase=n⋅m⋅costmask+n⋅m+2⋅costshare.


### 6.2.2. Performance Analysis of the Postvoting Phase

In postvoting phase, VS and candidates are responsible for computing the sum of shares and then publish. Each participant reconstructs a polynomial to obtain the tallying result and then verifies it. Meanwhile, computing the sum of shares, recovering polynomial, and verifying the tallying result are the main computation cost in this phase. Assume that they are separately expressed ascostshare_sum, costrecover, and costverify. The total computation cost in this phase is costpost_voting=m+1⋅costshare_sum+costrecover+costverify.From the previously mentioned analysis of two phases, the total computation cost iscosttotal=costvoting_phase+costpost_voting in the improved e-voting scheme and increases with the numbers of voters and candidates. Thus, the computation complexity is Onm in the improved e-voting scheme. In Table 2, it shows that our e-voting scheme simultaneously achieves privacy, verifiability, and coercion resistance, and the computation complexity is less than that mentioned in [32] due to m≪n.In Figure3, we select m=5 candidates to test the total time cost with different numbers of voters. As shown in Figure 3, the total time cost of the improved e-voting scheme is slightly higher than the scheme [35]. Liu et al.’s scheme [35] is unaffected by the numbers of voters. Therefore, it has an advantage in total time cost. However, it cannot achieve the security requirement of coercion resistance in e-voting. Although the improved e-voting scheme increases the total time cost, it achieves the coercion-resistant security requirement. Moreover, comparing [32, 33], the improved e-voting scheme takes less time overall.In Figure4, we select n=10000 voters to test the total time cost with different numbers of candidates. As shown in Figure 4, both the improved e-voting scheme and the scheme [35] increase with the numbers of candidates in the total time cost. Similarly, the total time cost of the improved e-voting scheme is slightly higher than the scheme [35]. In order to achieve the security requirement of coercion resistance, the improved e-voting scheme adds masked values on the basis of the scheme [35]. Thus, the computation cost is higher than Liu et al.’s scheme [35]. However, the total time consumption is still smaller than those in [32, 33].


## 6.2.1. Performance Analysis of the Voting Phase

In the voting phase, the five steps are as follows: registering identification for voters, negotiating session keys among voters, generating masked values, constructing shared polynomials, and computing shares. Meanwhile, the computation cost mainly concentrates upon generating masked values and computing shares. Assume that the computation costs of one masked value and one share are separately expressed ascostmask and costshare. The total computation cost in this phase can be expressed as costvoting_phase=n⋅m⋅costmask+n⋅m+2⋅costshare.


## 6.2.2. Performance Analysis of the Postvoting Phase

In postvoting phase, VS and candidates are responsible for computing the sum of shares and then publish. Each participant reconstructs a polynomial to obtain the tallying result and then verifies it. Meanwhile, computing the sum of shares, recovering polynomial, and verifying the tallying result are the main computation cost in this phase. Assume that they are separately expressed ascostshare_sum, costrecover, and costverify. The total computation cost in this phase is costpost_voting=m+1⋅costshare_sum+costrecover+costverify.From the previously mentioned analysis of two phases, the total computation cost iscosttotal=costvoting_phase+costpost_voting in the improved e-voting scheme and increases with the numbers of voters and candidates. Thus, the computation complexity is Onm in the improved e-voting scheme. In Table 2, it shows that our e-voting scheme simultaneously achieves privacy, verifiability, and coercion resistance, and the computation complexity is less than that mentioned in [32] due to m≪n.In Figure3, we select m=5 candidates to test the total time cost with different numbers of voters. As shown in Figure 3, the total time cost of the improved e-voting scheme is slightly higher than the scheme [35]. Liu et al.’s scheme [35] is unaffected by the numbers of voters. Therefore, it has an advantage in total time cost. However, it cannot achieve the security requirement of coercion resistance in e-voting. Although the improved e-voting scheme increases the total time cost, it achieves the coercion-resistant security requirement. Moreover, comparing [32, 33], the improved e-voting scheme takes less time overall.In Figure4, we select n=10000 voters to test the total time cost with different numbers of candidates. As shown in Figure 4, both the improved e-voting scheme and the scheme [35] increase with the numbers of candidates in the total time cost. Similarly, the total time cost of the improved e-voting scheme is slightly higher than the scheme [35]. In order to achieve the security requirement of coercion resistance, the improved e-voting scheme adds masked values on the basis of the scheme [35]. Thus, the computation cost is higher than Liu et al.’s scheme [35]. However, the total time consumption is still smaller than those in [32, 33].


## 7. Conclusions

In this paper, we first show that the e-voting scheme recently proposed by Liu et al. in [35] suffers from the coercive attack by internal voter. Then, we proposed an improved e-voting scheme to achieve coercion resistance and solve abstention from voting. Different from the scheme proposed by Liu et al., the improved e-voting scheme uses the sum of the masked value and the value of the original ballot to achieve the construction of shared polynomial. The scheme prevents malicious voter proving the content of his ballot to others, which achieves the security requirement of coercion resistance. Besides, VS sets the ballot of the abstainer as 0, and correct tallying result can be obtained in subsequent voting process. Moreover, theoretical analysis shows that our proposed scheme not only inherits all security requirements of Liu et al.’s scheme but also achieves the integrity of ballots, privacy of ballots, multiple-voting detection, and fairness. The performance evaluation results also indicate our scheme can achieve higher efficiency than other e-voting schemes in terms of total time consumption. In future, with the increasing application of blockchain, we are going to combine blockchain technology to propose novel and secure e-voting scheme.



---

*Source: 5448370-2021-10-18.xml*