Receipt-free remote electronic elections with everlasting privacy

Abstract

We present a new cryptographic voting protocol for remote electronic voting that offers three of the most challenging features of such protocols: verifiability, everlasting privacy, and receipt-freeness. Trusted authorities and computational assumptions are only needed during vote casting and tallying to prevent the creation of invalid ballots and to achieve receipt-freeness and fairness, but not to guarantee vote privacy. The implementation of everlasting privacy is based on perfectly hiding commitments and non-interactive zero-knowledge proofs, whereas receipt-freeness is realized with mix networks and homomorphic tallying.

1 Introduction

Voter coercion and vote buying are two serious threats in electronic elections. They have not newly emerged with the introduction of Internet elections, but they have reached a new dimension regarding their scalability. While both selling the right to vote and voting in someone else’s name is usually regarded as a serious disruption of the normal voting process and may therefore imply severe legal consequences to both the seller and the buyer, the voting system should at least not encourage the practice of vote buyers paying rewards to voters for providing sufficient evidence that they voted in a particular way.

Benaloh and Tuinstra first remarked the important difference between concealing a vote and not revealing a vote to a third party [7]. A polling both in the traditional setting achieves both by physical measures. But this is not automatically the case in remote electronic voting. To achieve verifiability, many existing systems provide a receipt to voters, which allows them to verify the inclusion of their vote in the final result, but also to reveal their vote to someone else. Consequently, such systems are prone to vote buying and coercion. Receipt-freeness is therefore an important aspect of vote secrecy when the voter is dishonest.

In a system offering vote privacy, neither the system nor a third party can link a plaintext vote to a particular voter. If this property is not based on computational intractability assumptions, like the impossibility of computing discrete logarithms or factoring large numbers, nor on the availability of trusted authorities, then the privacy is called everlasting in a information-theoretical sense. Everlasting privacy is a desirable property to avoid vote privacy violations by much more powerful adversaries far in the future.

1.1 Contribution

The contribution of this paper is a new cryptographic voting protocol for verifiable electronic elections offering receipt-freeness and everlasting privacy. The protocol is a continuation of the one described in [28], which offers everlasting privacy without the need of trusted authorities but not receipt-freeness. In the new protocol, trusted authorities are needed to guarantee receipt-freeness and fairness, but not for privacy. Consequently, if all trusted authorities collude and publish their private values, then voters are able to obtain a receipt, but the privacy of the vote is still given. The same applies to computational intractability assumptions. They are only needed to prevent the creation of invalid ballots during vote casting and to prevent voters from creating a receipt, but not to protect privacy in the long run.

The core of the protocol is a combination of a set membership proof [6] and a proof of known representation of a committed value [4]. When casting a vote, the voter provides a non-interactive zero-knowledge proof of knowledge of the representation of one of the registered public voter credentials. The same voter may cast multiple votes, but what counts at the end is the sum of all valid votes cast. In this way, precedent votes can be canceled out or overridden. The votes of a given voter are linked over an encrypted election credential, but the links remain hidden to an observer using a mix-net. The entire voting procedure consists of four consecutive steps:

• Registration: Each voter creates a pair of private and public voter credentials and sends the public credential over an authentic channel to the election administration.

• Election preparation: The election administration publishes the list of public voter credentials—one for every registered voter—on the public bulletin board.

• Vote casting: The voter creates an electronic ballot and sends it over an anonymous channel to the public bulletin board. The ballot consists of the encrypted vote, a commitment to the public credential, an encryption of the election credential, and the above-mentioned composition of zero-knowledge proofs.

• Tallying: The trusted authorities verify the proofs included in the ballots, shuffle the list of valid ballots in a mix-net, decrypt the election credentials, and accumulate under encryption the votes for each voter. The accumulated votes are shuffled in another mix-net and decrypted into plaintext votes.

This protocol provides everlasting privacy for the same reasons as its predecessor protocol presented in [28], i.e., all the identifying information contained in a ballot is either a perfectly hiding commitment or a zero-knowledge proof. Receipt-freeness is achieved by not revealing the number of votes cast by a single voter. The voter obtains a receipt for every single vote and can hand them over to the vote buyer, but the vote buyer will not know if the obtained amount of receipts is complete. The voter can therefore cheat the vote buyer by submitting an additional vote that cancels out or overrides all previous ones. For this to work, vote buyers must remain passive during the voting period, i.e., they do not cast votes in behalf of the voters. Generally, our protocol is not safe against active adversaries running impersonation or forced-abstention attacks.

1.2 Related work

A considerable amount of research has been conducted on receipt-free and coercion-resistant voting protocols and on systems offering everlasting privacy. But to the best of our knowledge, none of the existing approaches provides both properties simultaneously.

Benaloh and Tuinstra first mentioned the important difference between traditional paper-based voting in private voting booths and remote electronic voting based on a cryptographic voting protocol [7]. They were the first to define receipt-freeness and provide an approach for a possible solution based on an abstract model of a voting booth and the assumption that such voting booths exist. Based on a slightly weaker assumption of an untappable channel, Sako and Kilian described a receipt-free voting protocol for yes/no votes based on mix-nets [34]. Various other receipt-free protocols based on untappable channels have been proposed by different authors [24, 32, 39]. At the time of writing this paper, Kulyk et al. presented a method for achieving receipt-freeness in Helios by allowing voters to submit multiple votes and by considering the sum of all submitted votes in the final tally [27]. Their basic idea for achieving receipt-freeness is identical to the one presented in this paper, but their protocol does not offer everlasting privacy. The idea that the final counted vote is a composition of all submitted votes goes back to the non-cryptographic voting protocol ThreeBallot [33].

Juels et al. introduced an extended definition of coercion-resistance, which considers general impersonation, randomization, and forced-abstention attacks in addition to vote buying based on receipts [26]. Their solution requires an untappable channel only for registration. Additionally, the protocol assumes that voters have access to an anonymous channel at some point during the vote casting process. Unlike untappable channels, which require strong physical assumptions, anonymous channels can be implemented in practice, for example using mix-nets. Several follow-up papers have been published to speed up the tallying [2, 3, 15, 35, 36] or to prevent board flooding attacks [23].

With respect to vote privacy, Chaum argued that votes must be unconditionally secure, meaning that the partial tally of a group of voters can only be determined by a coalition of all other voters [14]. Moran and Noar introduced the term everlasting privacy in the context of a traditional setting, in which ballots are cast in a private polling booth [29–31]. In their definition, everlasting privacy is a weaker form of unconditional privacy, which only excludes that an attacker with unlimited computational power can break vote privacy. All three protocol are based on trusted authorities. Demirel et al. proposed several ways of achieving everlasting privacy in the context of remote electronic elections [10, 18, 19]. While the information published on the public bulletin board does not reveal anything about somebody’s vote, the trusted server could potentially break the ciphertext votes transmitted over the private channel between voter and server. The same restriction applies to the method presented in [17], which uses commitment consistent encryption to generate a perfectly private audit trail. The first protocol that offers everlasting privacy without trusted authorities is the one on which this paper is based [28].

Another important line of related work are the protocols based on blind signatures [16, 21, 25, 39]. They are also based on submitting votes over an anonymous channel, but they achieve everlasting privacy under much stronger trust assumptions. Their main problem is ballot-stuffing by malicious signing authorities, which cannot be detected. More generally speaking, protocols based on blind signatures do not support the verification of the electorate. Other disadvantages are the facts that voters need to interact with the authorities during vote casting and that the authorities learn who actually voted. To overcome some of the drawbacks of blind signatures, Canard and Traor introduced a system based on list signatures [13].

1.3 Paper overview

In the next section, we introduce the cryptographic building blocks of our protocol. In Section 3, we explain first the adversary model before we provide a detailed description of our protocol. We conclude the section with a discussion of the resulting security properties and possible protocol extensions. In Section 4, we analyze the running times and memory consumptions of the different protocol procedures and present the results from corresponding performance tests. Finally, we summarize the findings of this paper in Section 5.

2 Cryptographic preliminaries

Let $\mathcal {G}_{p}$ be a multiplicative cyclic group of prime order p, for which the discrete logarithm assumption is believed to hold. Furthermore, let $\mathbb {G}_{q} \subset \mathbb {Z}^{*}_{p}$, be a large prime-order subgroup of the group of integers modulo p, where k=(p−1)/q denotes the corresponding co-factor. Finally, suppose that independent generators $g_{0},g_{1}\in \mathcal {G}_{p}$ and $h,h_{0},h_{1},\ldots ,h_{n}\in \mathbb {G}_{q}$ are publicly known. Independence with respect to generators of a cyclic group means that their relative discrete logarithms are unknown.¹

2.1 Homomorphic commitments and encryptions

In our protocol, we use two instances of the perfectly hiding Pedersen commitment scheme, one over $\mathcal {G}_{p}$ and one over $\mathbb {G}_{q}$. We distinguish them by $\text {com}_{p}(u,r)={g_{0}^{r}}{g_{1}^{u}}$ for a commitment to $u\in \mathbb {Z}_{p}$ with randomization $r\in \mathbb {Z}_{p}$ and $\text {com}_{q}(v,s)={h_{0}^{s}}{h_{1}^{v}}$ for a commitment to $v\in \mathbb {Z}_{q}$ with randomization $s\in \mathbb {Z}_{q}$. In the case of $\mathbb {G}_{q}$, we write $\text {com}_{q}(v_{1},\ldots ,v_{n},s)={h_{0}^{s}}h_{1}^{v_{1}}{\cdots } h_{n}^{v_{n}}$ for a commitment to n values $v_{1},\ldots ,v_{n}\in \mathbb {Z}_{q}$. Recall that Pedersen commitments are perfectly hiding, computationally binding, and additively homomorphic.

The protocol also requires two instances of a homomorphic encryption scheme such as ElGamal or Paillier. One of them needs to be additively homomorphic. In our presentation, we choose ElGamal for its simplicity and compatibility with the above setting. We use one instance of standard ElGamal and one instance of exponential ElGamal, both over $\mathbb {G}_{q}$ and with a common key pair $x\in \mathbb {Z}_{q}$ and $y=h^{x}\in \mathbb {G}_{q}$. In our protocol, we will have a shared private key x generated in a distributed manner. Corresponding key shares x _i can be used to perform the decryption in a distributed way. Recall that ElGamal is IND-CPA secure under the decisional Diffie-Hellman (DDH) assumption. Furthermore, standard ElGamal is multiplicatively and exponential ElGamal additively homomorphic.

In case of standard ElGamal, we write $E=\text {enc}^{\times }_{y}(m,r)=(h^{r},my^{r})\in \mathbb {G}_{q}\times \mathbb {G}_{q}$ for encrypting a message $m\in \mathbb {G}_{q}$ with randomization $r\in \mathbb {Z}_{q}$ and $m=\text {dec}^{\times }_{x}(E)=b a^{-x}$ for decrypting a given ciphertext E=(a,b) with the private key x. To decrypt multiple ciphertexts E={E ₁,…,E _n } using the same private key x, we write $\mathbf {M}=\text {dec}^{\times }_{x}(\mathbf {E})$ for the resulting list M=(m ₁,…,m _n ) of plaintext messages $m_{i}=\text {dec}^{\times }_{x}(E_{i})$.

In the case of exponential ElGamal, let $E=\text {enc}^{+}_{y}(m,r)=(h^{r},h^{m}y^{r})\in \mathbb {G}_{q}\times \mathbb {G}_{q}$ denote the encryption of a message $m\in \mathcal {M}\subset \mathbb {Z}_{q}$ with randomization $r\in \mathbb {Z}_{q}$, where $\mathcal {M}$ is small enough to conduct an exhaustive search. The restriction on the message space is necessary to perform the decryption $m=\text {dec}^{+}_{x}(E)=\log _{h}(b a^{-x})$ of a ciphertext E=(a,b) efficiently. Again, to decrypt multiple ciphertexts using the same private key x, we write $\mathbf {M}=\text {dec}^{+}_{x}(\mathbf {E})$. To re-encrypt a given ciphertext $E=\text {enc}^{+}_{y}(m,r)$ with a new randomization $r^{\prime }$, we use the standard procedure $E^{\prime }=\text {reEnc}^{+}_{y}(E,r^{\prime })=E\cdot \text {enc}^{+}_{y}(0,r^{\prime })=\text {enc}^{+}_{y}(m,r+r^{\prime })$ of multiplying the ciphertext with an encryption of 0.

2.2 Zero-knowledge proofs

The main cryptographic tools in our protocol are non-interactive zero-knowledge proofs of knowledge. The voter uses them to demonstrate knowledge of some secret values involved in a mathematical statement, but without revealing any information about the secret values. One of the most fundamental type of zero-knowledge proofs of knowledge is a preimage proof for a one-way group homomorphism $\phi :X\rightarrow Y$, denoted by

$$\mathit{NIZKP}[(a): b = \phi(a)],$$

where a∈X is the secret preimage of a public value b = ϕ(a)∈Y. Examples of such preimage proofs result from the above homomorphic Pedersen commitment and ElGamal encryption schemes, for example N I Z K P[(u,r):C=com _p (u,r)] for proving knowledge of the opening of a commitment, $\mathit {NIZKP}[(m,r): E = \text {enc}^{+}_{y}(m,r)]$ for proving knowledge of the plaintext and randomization of an exponential ElGamal ciphertext, or $\mathit {NIZKP}[(x): \mathbf {M}=\text {dec}^{\times }_{x}(\mathbf {E}) \wedge y=h^{x}]$ for proving knowledge of the private key used in a batch decryption.

The most common construction of a non-interactive preimage proof is the ##Σ##-protocol in combination with the Fiat-Shamir heuristic [20]. Proofs constructed in this way are perfect zero-knowledge in the random oracle model. Their transcript consists of one or multiple commitments and one or multiple responses to a challenge obtained from querying the random oracle with the public inputs and the commitments. In practice, the random oracle is implemented with a cryptographic hash function. In Section 3, we will write π _i = N I Z K P[⋅] for the transcripts of the non-interactive proofs used in the voting protocol.

2.2.1 Set membership proof

Let U={u ₁ …,u _M } be a finite set of values $u_{i}\in \mathbb {Z}_{p}$ and C=com _p (u,r) a commitment to an element u∈U. Both U and C are publicly known. With a set membership proof, denoted by

$$\mathit{NIZKP}[(u,r): C = \text{com}_{p}(u,r) \wedge u\in U],$$

the prover demonstrates knowledge of corresponding values u∈U and $r \in \mathbb {Z}_{p}$, but without revealing any information about them. Such a proof can be constructed by a standard OR combination of individual preimage proofs for each u∈U, but this proof has a size linear to M and is therefore not efficient. The first set membership proof with a sub-linear size has been given by Camenisch et al. [11].

As suggested by Brands et al. [9], a general way of constructing a set membership proof is to compute the polynomial $P(X) = {\prod }_{i=1}^{M}(X-u_{i})$ and to demonstrate that P(u)=0. This proof, denoted by

$$\mathit{NIZKP}[(u,r): C = \text{com}_{p}(u,r) \wedge P(u)=0],$$

is a particular case of a polynomial evaluation proof. In a recent publication [6], Bayer and Groth proposed a polynomial evaluation proof with a logarithmic size, which is the current state-of-the-art. A summary of the proof generation and verification using the same formal notation and cryptographic setting as introduced above is given in [28].

2.2.2 Proof of known representation

In a cyclic group such as $\mathbb {G}_{q}$ with generators h ₁,…,h _n , a tuple (v ₁,…,v _n ) of values $v_{i}\in \mathbb {Z}_{q}$ is called DL-representation (or simply representation) of $u\in \mathbb {G}_{q}$ with respect to values (h ₁,…,h _n ), if $u=h_{1}^{v_{1}}{\cdots } h_{n}^{v_{n}}$ [8]. Note that the general definition of DL-representation does not require the values h ₁,…,h _n to be generators, nor do they need to be independent or distinct. On the other hand, every opening of a Pedersen commitment is clearly a DL-representation of the commitment with respect to the given independent generators.

Let C=com _p (u,r) be a commitment to a single value $u\in \mathbb {G}_{q}\subset \mathbb {Z}_{p}$ and D=com _q (v ₁,…,v _n ,s) a commitment to multiple values $v_{1},\ldots ,v_{n}\in \mathbb {Z}_{q}$. Both C and D are publicly known. Following Au et al. [4], a proof of known representation of a committed value (or simply representation proof), denoted by

$$\begin{array}{@{}rcl@{}} &&\mathit{NIZKP}[(u,r,v_{1},\ldots,v_{n},s):C = \text{com}_{p}(u,r) ~\wedge\\&& ~~~~~~~~~~~~~~~~~~~~~~D \,=\, \text{com}_{q}(v_{1},\ldots,v_{n},s) \wedge u\,=\,h_{1}^{v_{1}}{\cdots} h_{n}^{v_{n}}], \end{array} $$

demonstrates that the tuple of committed values in D is a DL-representation of the committed value in C. Note that this is a generalization of proof of knowledge of double discrete logarithms, $\mathit {NIZKP}\{(v):C=g^{(h^{v})}\}$, by Camenisch and Stadler [12]. A summary of the representation proof generation and verification is given in [28].

2.3 Cryptographic shuffling

The input of a cryptographic shuffle is a list Z=(z ₁,…,z _n ) of input values z _i ∈Z. The mixer applies a keyed one-way function $f_{k_{i}}:Z\rightarrow Z$ to each input value z _i and permutes the results by picking a random permutation $\phi :\{1,\ldots ,n\}\rightarrow \{1,\ldots ,n\}$ from the set Φ _n of permutations of length n. The output of a cryptographic shuffle is therefore a list $\mathbf {Z}^{\prime }=(z^{\prime }_{1},\ldots ,z^{\prime }_{n})$ of values $z^{\prime }_{j}=f_{k_{i}}(z_{i})$ for indices j = ϕ(i). We write

$$\mathbf{Z}^{\prime}=\text{shuffle}_{f_{K}}^{\phi}(\mathbf{Z})$$

for the whole procedure, where K=(k ₁,…,k _n ) denotes the list of involved keys. Since the goal of a cryptographic shuffle is to unlink the output values from corresponding inputs, the shuffling is usually performed multiple times in a mix network by independent mixers. The unlinkability in such a network is guaranteed as long as at least one permutation remains secret. Additionally, each mixer needs to provide a non-interactive zero-knowledge proof,

$$\mathit{NIZKP}[(K,\phi):\mathbf{Z}^{\prime}=\text{shuffle}_{f_{K}}^{\phi}(\mathbf{Z})],$$

to prove the correctness of the shuffle. There are several competing techniques for providing such proofs [5, 37].

In our protocol, we need two instances of a cryptographic shuffle. In the first case, the input values are pairs of ElGamal ciphertexts $(E_{i},F_{i})\in (\mathbb {G}_{q}\times \mathbb {G}_{q})\times (\mathbb {G}_{q}\times \mathbb {G}_{q})$. For random values $\delta \in _{R}\mathbb {Z}_{q}\setminus \{0\}$ and $\sigma _{i}\in _{R}\mathbb {Z}_{q}$, the function $f_{\delta ,\sigma _{i}}(E_{i},F_{i})=(E_{i}^{\delta },\text {reEnc}^{+}_{y}(F_{i},\sigma _{i}))$ is applied to each input for keys k _i =(δ,σ _i ). Note that raising E _i to the power of δ disconnects both the plaintext and ciphertext from their original values, whereas re-encrypting F _i only disconnects the ciphertext. To prove the correctness of the shuffle, the mixer computes

$$\mathit{NIZKP}[(\delta,\sigma_{1},\ldots,\sigma_{n},\phi):\mathbf{Z}^{\prime}=\text{shuffle}_{f_{(\delta,\sigma_{1}),\ldots,(\delta,\sigma_{n})}}^{\phi}(\mathbf{Z})]$$

to prove knowledge of K=((δ,σ ₁),…,(δ,σ _n )) and ϕ.

The second instance of a cryptographic shuffle is a special case of the first one. The inputs are single ElGamal ciphertexts $F_{i}\in \mathbb {G}_{q}\times \mathbb {G}_{q}$, which are re-encrypted using $f_{\sigma _{i}}(F_{i})=\text {reEnc}^{+}_{y}(F_{i},\sigma _{i})$ for random values $\sigma _{i}\in _{R}\mathbb {Z}_{q}$. With the corresponding non-interactive proof,

$$\mathit{NIZKP}[(\sigma_{1},\ldots,\sigma_{n},\phi):\mathbf{Z}^{\prime}=\text{shuffle}_{f_{\sigma_{1},\ldots,\sigma_{n}}}^{\phi}(\mathbf{Z})],$$

the mixer proves knowledge of K=(σ ₁,…,σ _n ) and ϕ.

3 Receipt-free elections with everlasting privacy

In this section, we present our new protocol for receipt-free electronic elections with everlasting privacy. We start with a discussion of the adversary model and the underlying trust assumptions. Then, we provide a detailed formal description of the protocol, analyze its security properties, and propose three protocol extensions.

3.1 Adversary model and trust assumptions

We consider three types of adversaries with different capabilities and goals. An adversary of the first type acts at the present time, i.e., before, during, or shortly after an election, whereas an adversary of the second type acts at any point in the future. We call them present adversary and future adversary, respectively. The vote buyer is a special case of a present adversary.

The general goal of present adversaries is to break the integrity or secrecy of the votes during an election, for example by submitting votes in the name of someone else or by linking votes to voters. We assume present adversaries to be polynomially bounded and thus incapable of solving the DL or DDH problems in large prime order groups or breaking cryptographic primitives such as contemporary hash functions. This implies that present adversaries cannot efficiently find valid openings of Pedersen commitments or valid proof transcripts for zero-knowledge proofs of knowledge without knowing the secret inputs. We also assume that present adversaries cannot control the machines used for vote casting² and that voters do not reveal their private credentials.

The goal of a vote buyer is to manipulate the outcome of an election by paying rewards to voters if they can prove that they voted in a particular way. The information required to convince the vote buyer is called receipt. We assume that vote buyers pay rewards for such receipts, but not for obtaining the voters’ private credentials. In other words, we exclude active impersonation attacks by buying someone’s right to vote. Vote buyers remain entirely passive during an election and therefore do not interfere with the vote casting process.

For a future adversary, the only goal is breaking the secrecy of the votes of an election that took place at the present time. To avoid the problem of estimating the available computational resources far in the future, we simply assume the strongest possible adversary, one with unlimited resources in terms of computational power and time. Although contemporary cryptography will be completely useless in the presence of such an adversary, the secrets hidden in perfectly hiding commitments or in zero-knowledge proofs of knowledge will never be revealed, even if they were generated today.

From the point of view of the necessary communication infrastructure, the protocol requires an authentic channel between voter and election administration during the registration process. In the basic protocol version of Section 3.2, voters need to re-register in every new election, but we will show later how to circumvent this limitation. Furthermore, the protocol requires a broadcast channel with memory, for example in the form of a robust append-only public bulletin board collecting the entire election data. We assume that the election administration and the trusted authorities have their own designated areas on the bulletin board for posting their messages. Finally, for sending their votes to the bulletin board, voters need access to an anonymous channel. We assume that no adversary is capable of intercepting and recording the whole traffic over this channel during an election and storing the data for future vote privacy attacks [1].

3.2 Protocol description

As outlined in Section 1.1, the protocol consists of four consecutive phases. We will now present the details of each phase using the cryptographic primitives and formal notation introduced in the previous section. Summaries of all phases are included in corresponding figures at the end of each subsection. Note that the registration and election preparation phase are identical to the predecessor protocol [28], and vote casting is very similar. To achieve receipt-freeness, complexity has been added mainly to the tallying phase. At the end of this subsection, we will also give an overview of the verification process.

3.2.1 Registration

The first step of the protocol is the registration of voters before an election. To register, voter V picks a private credential $(\alpha ,\beta ,\gamma )\in _{R}\mathbb {Z}_{q}\times \mathbb {Z}_{q}\times \mathbb {Z}_{q}$ at random and computes the public credential $u = h_{1}^{\alpha }h_{2}^{\beta } h_{3}^{\gamma }\in \mathbb {G}_{q}$. Note that the private credential is a representation of the public credential with respect to (h ₁,h ₂,h ₃). Finally, the voter sends u over an authentic channel to the election administration (Fig. 1).³

Fig. 1

Summary of the registration phase

3.2.2 Election preparation

After the registration phase, the election administration defines the list $\mathbf {U}=((V_{1},u_{1}), \dots , (V_{M},u_{M}))$ based on the electoral roll. Each pair (V _i ,u _i )∈U links a public credential to the corresponding voter. Next, the list $\mathbf {A}=(a_{0}, \dots , a_{M})$ of coefficients $a_{i}\in \mathbb {Z}_{p}$ of the polynomial $P(X)={\prod }_{i=1}^{M}(X-u_{i}) \in \mathbb {Z}_{p}[X]$ is computed to allow voters creating the set membership proof during the vote casting phase. As the computation of those coefficients is quite expensive ($\frac {1}{2}M^{2}$ multiplications in $\mathbb {Z}_{p}$), it is performed by the election administration, possibly already during the registration phase in an incremental way. Note that the coefficients can be re-computed and verified by anyone, and voters can efficiently verify the inclusion of their public credential u by checking P(u)=0. Finally, two independent election generators $\hat {h}_{1},\hat {h}_{2} \in \mathbb {G}_{q}$ are defined in some publicly reproducible way and $(\mathbf {U},\mathbf {A},\hat {h}_{1},\hat {h}_{2})$ is posted into the administration’s designated area of the public bulletin board (Fig. 2).

Fig. 2

Summary of the election preparation phase

3.2.3 Vote casting

During the election, voters select their vote by choosing their preferred election options and encoding them by an element of the set $\mathbb {V}\subseteq \mathbb {Z}_{q}$ of valid votes. We assume that the election options and their encoding in $\mathbb {V}$ are publicly known. Note that nothing prevents the voter from selecting and submitting an invalid vote $v\notin \mathbb {V}$. In fact, we explicitly allow the submission of arbitrary values $v\in \mathbb {Z}_{q}$ as a mechanism for canceling out or overriding votes submitted previously by the same voter. In our protocol, the sum of all submitted votes is what counts at the end for a single voter, and this value must be in $\mathbb {V}$ to be included in the final tally. Therefore, submitting −v cancels out a previously submitted value v, whereas $v^{\prime }-v$ overrides v with $v^{\prime }$.

To cast the vote, the voter computes two commitments C=com _p (u,r) and D=com _q (α,β,γ,s) to the public and private credentials. Next, the voter computes a standard ElGamal encryption $E=\text {enc}_{y}^{\times }(\hat {u},\rho )$ of the election credential $\hat {u}=\hat {h}_{1}^{\alpha }\hat {h}_{2}^{\beta } \in \mathbb {G}_{q}$ and an exponential ElGamal encryption $F=\text {enc}^{+}_{y}(v, \sigma )$ of the vote v. For this, we assume that the public key y of the trusted authorities is known to everyone. Finally, the voter generates three non-interactive zero-knowledge proofs. The first proof,

$$\pi_{1}=\mathit{NIZKP}[(u,r): C = \text{com}_{p}(u,r) \wedge P(u)=0],$$

is a set membership proof proving that C is indeed a commitment to the public credential of one of the eligible voters listed in U. The second proof,

$$\begin{array}{@{}rcl@{}} ~~~\pi_{2}=\mathit{NIZKP}[(r,\alpha,\beta,\gamma,s): C = \text{com}_{p}(u,r) \,\wedge\\ D = \text{com}_{q}(\alpha,\beta,\gamma,s)\wedge u=h_{1}^{\alpha}h_{2}^{\beta}h_{3}^{\gamma}], \end{array} $$

is a proof of known representation of the committed value in C. Its purpose is to prevent voters from taking just any credential from U. The third proof,

$$\begin{array}{@{}rcl@{}} \pi_{3}=\mathit{NIZKP}[(\alpha,\beta,\gamma,s,\rho,v,\sigma)\!:\! D = \text{com}_{q}(\alpha,\beta,\gamma,s) \!\wedge\\ E = \text{enc}_{y}^{\times}(\hat{u},\rho) \wedge F=\text{enc}^{+}_{y}(v,\sigma)\wedge\hat{u}=\hat{h}_{1}^{\alpha}\hat{h}_{2}^{\beta}], \end{array} $$

is a standard preimage proof showing that D and E have been generated using the same values α and β and that the vote contained in F is known to the voter.⁴

The ballot B=(C,D,E,F,π ₁,π ₂,π ₃) consisting of the two commitments, the two ciphertexts, and the three proofs is posted over an anonymous channel to the bulletin board. The voter may submit multiple such ballots during the election period. If multiple identical copies of the same ballot are posted to the bulletin board, we assume that only one of them is stored (Fig. 3).⁵

Fig. 3

Summary of the vote casting phase

3.2.4 Tallying

At the end of the election period, the ballots submitted to the bulletin board need to be processed by the trusted authorities. We present this process by looking at the group of trusted authorities as a single entity performing the necessary shuffling and decryption tasks jointly. In reality, different trusted authorities will perform respective tasks using their own secret inputs and random values. The cryptographic shuffling is a serial and the distributed decryption (usually) a parallel process.⁶

To initiate the tallying process, the trusted authority retrieves the list B of all ballots from the bulletin board and verifies the non-interactive proofs π ₁, π ₂, π ₃ for each ballot B=(C,D,E,F,π ₁,π ₂,π ₃)∈B. Ballots with invalid proofs are dropped. Then the two ElGamal ciphertexts (E,F) are selected from all ballots with valid proofs. We denote the resulting list of such pairs by E F=((E ₁,F ₁),…,(E _N ,F _N )). The validity of the proofs guarantees that each (E _i ,F _i )∈E F originates from an eligible voter with valid private credentials. Clearly, two distinct pairs (E _i ,F _i ),(E _j ,F _j )∈E F originate from the same eligible voter, whenever E _i and E _j contain the same plaintext.

In the next step, the trusted authority performs a cryptographic shuffle on the list E F. The two ciphertexts of each element (E _i ,F _i ) of the input list are treated differently: E _i is disguised by raising it to the power of a single random value $\delta \in _{R}\mathbb {Z}_{q}\setminus \{0\}$, whereas F _i is disguised by re-encrypting it using an individual random value $\sigma _{i}\in _{R}\mathbb {Z}_{q}$. Therefore, the trusted authority applies the keyed one-way function

$$f_{\delta,\sigma_{i}}(E_{i},F_{i})=(E_{i}^{\delta},\text{reEnc}^{+}_{y}(F_{i},\sigma_{i}))$$

to each input (E _i ,F _i )∈E F, where k _i =(δ,σ _i ) represents the individual key. By selecting a random permutation ϕ∈ _R Φ _N and applying it to the resulting list, the trusted authority generates a new list

$$\mathbf{EF}^{\prime}=\text{shuffle}_{f_{(\delta,\sigma_{1}),\ldots,(\delta,\sigma_{N})}}^{\phi}(\mathbf{EF})$$

of shuffled ciphertext pairs. Note that $\mathbf {EF}^{\prime }$ inherits from E F the property that two distinct pairs $(E^{\prime }_{i},F^{\prime }_{i}),(E^{\prime }_{j},F^{\prime }_{j})\in \mathbf {EF}^{\prime }$ originate from the same eligible voter, whenever $E^{\prime }_{i}$ and $E^{\prime }_{j}$ contain the same plaintext.

To collect the votes that originate from a single voter, the trusted authority selects $E^{\prime }_{i}$ from every $(E^{\prime }_{i},F^{\prime }_{i})\in \mathbf {EF}^{\prime }$ and decrypts the resulting list $\mathbf {E}^{\prime }=(E^{\prime }_{1},\ldots ,E^{\prime }_{N})$ into $\mathbf {H}=\text {dec}_{x}^{\times }(\mathbf {E}^{\prime })$. Each plaintext H∈H is a value of the form $H=\text {dec}_{x}^{\times }(E^{\prime }_{i})=\hat {u}^{\delta }=(\hat {h}_{1}^{\alpha }\hat {h}_{2}^{\beta })^{\delta }=(\hat {h}_{1}^{\delta })^{\alpha }(\hat {h}_{2}^{\delta })^{\beta }$, where $\hat {h}_{1}^{\delta }$ and $\hat {h}_{2}^{\delta }$ are unique values for the current election and (α,β) belongs to some voter’s private credential. In other words, all $(E^{\prime }_{i},F^{\prime }_{i})\in \mathbf {EF}^{\prime }$ satisfying $H=\text {dec}^{\times }_{x}(E^{\prime }_{i})$ for some H∈H originate from the same voter, which implies that $F_{H}=\prod F^{\prime }_{i}$ is an encryption of the corresponding sum of votes. Recall that this sum is what counts in our protocol for a particular voter. Let F _H denote the list of all values F _H aggregated in this way and $N^{\prime }=|\mathbf {F}_{H}|\leq N$ the size of the list.

Before decrypting the aggregated votes, the trusted authority performs a final cryptographic shuffle on F _H , in which the input values are re-encrypted. For this, random values $\sigma ^{\prime }_{1},\ldots ,\sigma ^{\prime }_{N^{\prime }} \in _{R} \mathbb {Z}_{q}$ are selected to perform the re-encryption and a random permutation $\phi ^{\prime }\in _{R} {\Phi }_{N^{\prime }}$ is selected for the shuffling. The result is a new list

$$\mathbf{F}^{\prime}_{H}=\text{shuffle}_{f_{\sigma^{\prime}_{1},\ldots,\sigma^{\prime}_{N^{\prime}}}}^{\phi^{\prime}}(\mathbf{F}_{H})$$

of ciphertext votes, which can then be decrypted into a list $\mathbf {V}=\text {dec}^{+}_{x}(\mathbf {F}^{\prime }_{H})$ of plaintext votes. Note that each resulting plaintext vote is a value from $\mathbb {Z}_{q}$, but not necessarily all of them represent valid votes. We denote the process of filtering out invalid votes by $\mathbf {V}^{\prime }=\mathbf {V}\cap \mathbb {V}$.⁷ The resulting list $\mathbf {V}^{\prime }$ is the election result.

In addition to the above computational steps, the trusted authority needs to provide convincing evidence that respective shuffling and decryption tasks have been performed properly. The following non-interactive proofs are necessary for this:

$$\begin{array}{@{}rcl@{}} \pi_{E}\!&\,=\,&\!\mathit{NIZKP}[(\delta,\sigma_{1},\ldots,\sigma_{N},\phi):\\ &&\hskip2.8cm\mathbf{EF}^{\prime}=\text{shuffle}_{f_{(\delta,\sigma_{1}),\ldots,(\delta,\sigma_{N})}}^{\phi}(\mathbf{EF})],\\ \pi_{H}\!&\,=\,&\!\mathit{NIZKP}[(x):\mathbf{H}=\text{dec}_{x}^{\times}(\mathbf{E}^{\prime}) \wedge y=h^{y}],\\ \pi_{F}\!&\,=\,&\!\mathit{NIZKP}[(\sigma^{\prime}_{1},\ldots,\sigma^{\prime}_{N^{\prime}},\phi^{\prime})\!:\!\mathbf{F}^{\prime}_{H}\,=\,\text{shuffle}_{f_{\sigma^{\prime}_{1},\ldots,\sigma^{\prime}_{N^{\prime}}}}^{\phi^{\prime}}(\mathbf{F}_{H})],\\ \pi_{V}\!&\,=\,&\!\mathit{NIZKP}[(x):\mathbf{V}=\text{dec}_{x}^{+}(\mathbf{F}^{\prime}_{H}) \wedge y=h^{y}]. \end{array} $$

By posting $\hspace *{-.2pt}(\hspace *{-.2pt}\mathbf {E\hspace *{-.2pt}F\hspace *{-.2pt}},\hspace *{-.2pt}\mathbf {E\hspace *{-.2pt}F\hspace *{-.2pt}}^{\prime },\hspace *{-.2pt}\mathbf {E\hspace *{-.2pt}}^{\prime },\hspace *{-.2pt}\mathbf {H\hspace *{-.2pt}},\hspace *{-.2pt}\mathbf {F\hspace *{-.2pt}}_{H},\hspace *{-.2pt}\mathbf {F\hspace *{-.2pt}}^{\prime }_{H}\hspace *{-.2pt},\mathbf {V\hspace *{-.2pt}}\hspace *{-.2pt},\mathbf {V\hspace *{-.2pt}}^{\prime }\hspace *{-.2pt},\pi _{E}\hspace *{-.2pt},\hspace *{-.2pt}\pi _{H},\hspace *{-.2pt}\pi _{F}\hspace *{-.2pt},\hspace *{-.2pt}\pi _{V}\hspace *{-.2pt})$ to the bulletin board, the trusted authority completes the tallying process.⁸

3.2.5 Verification

To verify the election result, the election data must be retrieved from the bulletin board. It consists of everything that has been posted to the bulletin board during the election preparation, vote casting, and tallying phase:

$$(\mathbf{U}, \mathbf{A}, \hat{h}_{1}, \hat{h}_{2},\mathbf{B}, \mathbf{EF},\mathbf{EF}^{\prime},\mathbf{E}^{\prime},\mathbf{H},\mathbf{F}_{H},\mathbf{F}^{\prime}_{H},\mathbf{V},\mathbf{V}^{\prime},\pi_{E},\pi_{H},\pi_{F},\pi_{V}). $$

The full verification process consists of the following steps:

• Verify the electoral roll U by checking the identities of all eligible voters.

• Reproduce the list of coefficients A of the polynomial defined by U.

• Reproduce the election generators $\hat {h}_{1}$ and $\hat {h}_{2}$.

• For each ballot B=(C,D,E,F,π ₁,π ₂,π ₃)∈B, verify the proofs π ₁, π ₂, π ₃.

• Reproduce E F from B.

• Verify the shuffle proof π _E relative to E F and $\mathbf {EF}^{\prime }$.

• Reproduce $\mathbf {E}^{\prime }$ from $\mathbf {EF}^{\prime }$.

• Verify the decryption proof π _H relative to $\mathbf {E}^{\prime }$ and H.

• Reproduce F _H from H and $\mathbf {EF}^{\prime }$.

• Verify the shuffle proof π _F relative to F _H and $\mathbf {F}^{\prime }_{H}$.

• Verify the decryption proof π _V relative to $\mathbf {F}^{\prime }_{H}$ and V.

• Reproduce $\mathbf {V}^{\prime }$ from V.

Verifying the correctness of the cryptographic setting would be another item in the above list, but usually one can assume that the setting has been checked by others.

3.3 Security properties

We will now look at our protocol from the perspective of its security properties. We provide an informal discussion of how correct election results, everlasting privacy, and receipt-freeness is achieved. Fairness is achieved in a trivial way by submitting votes encrypted.

Correctness

For a present adversary not colluding with any of the trusted authorities and not in possession of a private credential, there are two principle ways of creating a ballot that will be accepted in the final tally. First, the adversary may try to find $(\alpha ^{\prime },\beta ^{\prime },\gamma ^{\prime })$ such that $u=h_{1}^{\alpha ^{\prime }} h_{2}^{\beta ^{\prime }}h_{3}^{\gamma ^{\prime }}$ for some u in U, but this is equivalent to solving the discrete logarithm problem. Second, the adversary may try to fake a proof transcript without knowing such values $(\alpha ^{\prime },\beta ^{\prime },\gamma ^{\prime })$, but this is impossible due to the computational soundness of the proofs π ₁, π ₂, and π ₃.

If the present adversary is an eligible voter in possession of a valid private credential, then using it for submitting more than one ballot is explicitly allowed by the protocol and results in one final accumulated vote. The malicious voter could try to prevent the vote accumulation by submitting ballots with different election credentials, but the soundness of π ₃ does not allow this. Without using the private credential, the voter is not more powerful than any other present adversary.

A present adversary colluding with one or several trusted authorities—or even the authorities themselves—may try to delete, modify, or add votes in the mixing or decryption steps of the protocol, but this is prevented by the computational soundness of the proofs π _E , π _H , π _F , and π _V . Their correctness can be verified by anyone.

Everlasting privacy

A ballot posted over an anonymous channel to the bulletin board contains no information for identifying the voter. Clearly, the future adversary will be able to determine the private key x and use it to decrypt E into $\hat {u}=\hat {h}_{1}^{\alpha }\hat {h}_{2}^{\beta }$, but this value is perfectly hiding with respect to both α and β. Similarly, $u=h_{1}^{\alpha }h_{2}^{\beta } h_{3}^{\gamma }$ is perfectly hiding with respect to α, β, and γ. Therefore, knowing x does not establish a link from $E=\text {enc}_{y}^{\times }(\hat {u}, \rho )$ to u. Since the proofs π ₁, π ₂, and π ₃ are zero-knowledge and therefore of no additional help, even a future adversary is unable to break vote privacy.

Receipt-freeness

A voter may send multiple ballots with valid proofs during the vote casting phase, and all of them will count in the final tally. By disclosing the randomizations used in the encryptions F, the authorship of a single ballot can be proven and its plaintext vote can be revealed. However, it is impossible to prove that every other ballots was cast by somebody else (this would mean to prove not knowing corresponding randomizations). As a single additional ballot can cancel out or overrule all precedent votes, proving the authorship of one or multiple ballots does not give a conclusive receipt.

In case the voter reveals the encryption randomizations for some (but not all) ballots to the vote buyer, the link to the voter’s other ballots must remain hidden during tallying. By disclosing the randomization of E in addition to the randomization of F, the voter can also reveal the election credential $\hat {u}=\hat {h}_{1}^{\alpha }\hat {h}_{2}^{\beta }$. In the first shuffle, by raising $E=\text {enc}_{y}^{\times }(\hat {u},\rho )$ to the power of δ, the elections credentials are disguised under encryption. Since δ is only known to the trusted authorities (by holding corresponding shares of δ), decrypting the resulting value E ^δ into $\hat {u}^{\delta }$ does not reveal a link to $\hat {u}$ to anyone not in possession of δ and unable to compute discrete logarithms efficiently. The outcome of the first shuffle and the subsequent decryption is therefore not uncovering the voter’s remaining ballots. This could only happen if all trusted authorities collude or by someone capable of solving the discrete logarithm problem, but the trust assumptions in our adversary model excludes this.

Another potential way of uncovering the ballots of a given voter during tallying is by marking the submitted votes with some additional information that the vote buyer would accept as a receipt. This could be done in three different ways: by submitting a unique combinations of annihilating values $v\in \mathbb {Z}_{q}$ in addition to the real vote, by submitting a unique total number of votes, or by submitting a unique valid vote when $\mathbb {V}$ is large enough. Each of these cases would give a conclusive receipt.

• To prevent the first type of receipt, the ciphertext votes obtained from the first mix-net are not decrypted directly. Instead, the ciphertext votes are accumulated and shuffled in a second mix-net. In this way, the selected combination of annihilating votes remains hidden between the two mix-nets, only the sum of all votes is decrypted.

• Regarding the second type of receipt, the protocol as described in the previous section does not include any counter-measures. The voter and the vote buyer could therefore agree in advance on the total number of submitted votes. To receive the reward, the voter will then disclose the same number of encryption randomizations. If the list H from step 4 contains exactly one value with again the same number of identical copies, the vote buyer will accept the disclosed randomizations as receipt. Because the agreed amount of votes must be unique for each voter, the scalability of constructing receipts of this type is limited for a large electorate. In Section 3.4, we propose a possible protocol extension to limit the scalability even for a small electorate.

• The third type of receipt is known as the Italian attack. An Italian attack is always possible if the final votes are decrypted individually and if $\mathbb {V}$ is much larger than the electorate. The problem is therefore limited to elections with many options and complex rules or to elections with a small electorate. The protocol as presented so far does not include any counter-measures to prevent the attack in these cases, but we will present in Section 3.4 an extended tallying procedure that avoids the decryption of the accumulated votes of individual voters.

3.4 Extensions

In the basic version of the protocol as presented in Section 3.2, we have ignored some problems regarding receipt-freeness and some important practical aspects. The following discussion of corresponding extensions rounds off the description of our protocol.

Null votes

This extension addresses the problem that voters and vote buyers may agree in advance on the total number of submitted votes. The idea is to artificially increase the number of votes of a given voter by supplying the bulletin board with additional null votes. This idea has been proposed in [27] for a receipt-free version of Helios, but it needs to be adjusted to the particularities of our protocol. Generally, ballots containing additional null votes must satisfy two properties: (1) they are indistinguishable from regular ballots; (2) anyone can generate them. To avoid that the bulletin board gets flooded with a large amount of null votes, we propose that only trusted authorities can generate them. This can be realized by combining an additional proof

$$\pi_{4} = \mathit{NIZKP}[(\sigma,x):F=\text{enc}^{+}_{y}(0,\sigma)\wedge y=h^{x}]$$

disjunctively with π ₁₂₃=(π ₁,π ₂,π ₃). A voter will therefore generate π ₁₂₃ and simulate π ₄, whereas the trusted authorities will simulate π ₁₂₃ and generate π ₄.⁹ To connect a ballot containing a null vote to a real ballot from an eligible voter, the trusted authorities copies and re-encrypts $E=\text {enc}_{y}^{\times }(\hat {u}, \rho )$ from a ballot already published on the bulletin board. The remaining problem then is to decide about the number of submitted null votes. Finding an optimal strategy that maximizes the obfuscation of the total number of votes of a single voter, and therefore minimizes to risk of a vote buying attack based on receipts of this type, is an open question for further research.

Extended homomorphic tallying

To avoid the decryption of accumulated votes of individual voters, which is responsible for the Italian attack, we can modify the last steps of the tallying procedure. Instead of performing $\mathbf {V}=\text {dec}^{+}_{x}(\mathbf {F}^{\prime }_{H})$ and publishing V, the trusted authorities prove for every $F^{\prime }_{H} \in \mathbf {F}^{\prime }_{H}$ one of the two following proofs:

$$\mathit{NIZKP}[(x):\text{dec}^{+}_{x}(F^{\prime}_{H}) \in \mathbb{V}],$$

if $F^{\prime }_{H}$ contains a valid vote, or

$$\mathit{NIZKP}[(x):\text{dec}^{+}_{x}(F^{\prime}_{H}) \not\in \mathbb{V}],$$

if $F^{\prime }_{H}$ contains an invalid vote. The list of these proofs is published together with $\mathbf {F}^{\prime }_{H}$. To obtain the final election results, all values $F^{\prime }_{H}$ containing a valid vote are accumulated under encryption and the resulting sum of votes is decrypted in one single step.¹⁰ The above proofs can be constructed in different ways, for example by decrypting $F^{\prime }_{H}$ into v, encrypting v with a fresh randomization into $F^{\prime \prime }_{H}$, proving the plaintext equivalence of $F^{\prime }_{H}$ and $F^{\prime \prime }_{H}$, and demonstrating the validity (or invalidity) of the vote in $F^{\prime \prime }_{H}$ using methods from [22].

Multiple elections

If the protocol as presented so far is used for multiple elections, but without requiring voters to renew their credentials, then a future adversary will be able to link the votes from the same voter by finding pairs (α,β) that match with election credentials from different elections. This does not provide a direct link to the voters’ identities, but it allows creating voter profiles which will eventually leak information. To overcome this problem, the protocol must be modified to ensure that a pair (α,β) is used for only one election. This can be achieved by extending the private and public credentials to $(\alpha , \beta _{1},\dots ,\beta _{L},\gamma )$ and $u = h_{1}^{\alpha }h_{2,1}^{\beta _{1}}{\ldots } h_{2,L}^{\beta _{L}}h_{3}^{\gamma }$, respectively, where L is the maximal number of elections the credentials can be used for. The corresponding commitment to the extended private credential, D=com _q (α,β ₁,…,β _L ,γ,s), implies that π ₂ needs to be extended to a representation proof of size L+1. Finally, a modified election credential $\hat {u}=\hat {h}_{1}^{\alpha }\hat {h}_{2}^{\beta _{l}}$ and a modified proof π ₃ are computed for l=(ε mod L)+1, where ε=1,2,… is the election number published beforehand by the elections administration.

4 Performance and implementation

Given the complexity of generating and verifying the necessary set membership, representation, and shuffle proofs, we need to look closely at the computational resources required by our voting protocol. We will first analyze the generation of a single ballot during vote casting. Then, we will determine the cost of the tallying procedure, and finally examine the verification of an entire election. The subject of our analysis is the basic protocol version from Section 3.2 without any extension.

4.1 Vote casting

The size and the cost of generating of a ballot in our protocol is mainly determined by the sizes of π ₁ and π ₂. Note that π ₁ depends on the number of eligible voters M, whereas π ₂ depends on a security parameter K.¹¹ In Table 1, we recapitulate the number of group elements for $\mathcal {G}_{p}$, $\mathbb {Z}_{p}$, $\mathbb {G}_{q}$, and $\mathbb {Z}_{q}$ and sum them up for an entire ballot. Since $\mathbb {Z}_{p}$ and $\mathbb {G}_{q}$ share the same modulo p, their elements are counted together. Similarly, Table 2 recapitulates and sums up the number of exponentiations in $\mathcal {G}_{p}$ and $\mathbb {G}_{q}$ and multiplications in $\mathbb {Z}_{p}$ required for generating a single ballot.

Table 1 Ballot size as a function of M and K. Elements of $\mathbb {Z}_{p}$ and $\mathbb {G}_{q}$ are counted together

Table 2 Number of exponentiations and multiplications required to generate a single ballot

Compared to the complexity analysis for the predecessor protocol as presented in [28], the results given here are very similar. The only differences come from the encryptions E and F and the proof π ₃, which require a few more exponentiations in $\mathbb {G}_{q}$ and corresponding group elements. Since K will usually be a value ≥80, the estimated ballot sizes and running times given in [28, Table 2 and 4] do not change much (for example ten additional exponentiations in $\mathbb {G}_{q}$). We will therefore not repeat the discussion of the analysis. We only conclude that we expect our protocol to work reasonably well except for a a very large electorate.

4.2 Tallying

The tallying procedure is what makes this protocol more complex compared to its predecessor. To analyze its complexity, let $N\geq N^{\prime }$ be the total number of submitted ballots and $N^{\prime }\leq M$ the number of eligible voters submitting at least one ballot, i.e, $N/N^{\prime }$ is the average number of ballots per voter and $N^{\prime }/M$ the voter turnout. We assume that all submitted ballots contain valid proofs, which implies N=|E F| and $N^{\prime }=|\mathbf {F}_{H}|$. In Table 3, we show the total number of group elements generated during tallying and the number of necessary exponentiations in $\mathbb {G}_{q}$. We assume that the two shuffle proofs π _E and π _F are generated using Wikstrm’s method [37, 38]. The results are given for a single authority. In case of multiple authorities, the numbers need to be multiplied accordingly.

Table 3 Number of group elements and exponentiations required during tallying in case of a single authority and assuming that all ballots are valid

Together with the results for the ballot size in Table 1, which can be multiplied by N to obtain the size of B, we can calculate an estimation of the size of the election data published on the bulletin board. Note that the lists E F, $\mathbf {E}^{\prime }$, F _H , and $\mathbf {V}^{\prime }$ need not to be stored explicitly (see footnote on 8). To simplify the setting, we assume that every eligible voter submits one single ballot, which implies $M=N=N^{\prime }$. Furthermore, to allow comparison with the results given in [28], we adopt the security parameters K=80, |p|=1024, and |q|=160. The results of this calculation are given in Table 4.

Table 4 Size of the election data for different numbers of voters and parameters K=80, |p|=1024, and |q|=160, and assuming that $M=N=N^{\prime }$

We conclude from the results of Table 4 that the total size of the election data increases only slightly compared to the predecessor protocol. An overhead of 10 % is needed for M=10, but this number gets even smaller when M gets larger, for example less than 7 % for M=1,000,000. This observation reflects the fact that the tallying procedure requires only O(N) space and therefore contributes much less to the total election data than the $O(N\log M)$ space of the ballots (assuming that K is a constant value), especially when M gets large.

A similar conclusion can be drawn with respect to computation time. Recall from step 2 in Fig. 4 that verifying all ballots is an important part of the tallying procedure. As we will see in Table 5 (upper part), the verification of the proofs in each of the N ballots requires $O(N\log M)$ exponentiations in $\mathcal {G}_{p}$ and $\mathbb {G}_{q}$ and O(M N) multiplications in $\mathbb {Z}_{p}$, which is much more expensive than O(N) exponentiations in $\mathbb {G}_{q}$ required to execute the remaining steps of the tallying procedure. For estimating the running times of verifying all ballots, we refer to [28, Table 6]. For M = 1,000,000, for example, we calculated an negligible 0.1 % overhead for the whole tallying procedure. Therefore, we refer again to the discussion and conclusions given in [28] and do not repeat them here.

Fig. 4

Summary of the tallying phase with a single trusted authority

Table 5 Number of exponentiations and multiplications required to verify the election data for M eligible voters, N submitted ballots, $N^{\prime }$ participating voters, security parameter K, and a single trusted authority

4.3 Verification

Compared to the predecessor protocol from [28], a complete verification of the election data as presented at the end of Section 3.2 requires a number of steps in addition to the verification of the proofs contained in the submitted ballots. Table 5 summarizes the number of exponentiations in $\mathcal {G}_{p}$ and $\mathbb {G}_{q}$ and the number of multiplications in $\mathbb {Z}_{p}$. Note that π ₁ requires a linear number of multiplications, which cannot be neglected when M gets very large [6].

Again, it turns out that the additional work to verify the proofs generated during tallying is marginal compared to the verification of the ballots. In terms of asymptotic running times, O(N) exponentiations in $\mathbb {G}_{q}$ are required for verifying the proofs from the tallying procedure, whereas $O(N\log M)$ exponentiations in $\mathcal {G}_{p}$ and $\mathbb {G}_{q}$ and O(N M) multiplications in $\mathbb {Z}_{p}$ are required for verifying the ballots. For example, we calculated that the overall verification takes only 3 % longer for M=10 and less than 0.05 % longer for M=1,000,000. In [28, Table 6], we estimated the time to verify the proofs included in 1,000,000 ballots on a single ordinary machine to be more than 4000 h, which seems to be at the limit of what is feasible today, possibly with multiple and more powerful machines. The same conclusion holds for the extended protocol from this paper.

5 Conclusion

In this paper, we introduced the first practical cryptographic voting protocol offering everlasting vote privacy and receipt-freeness simultaneously. Everlasting privacy is realized with perfectly hiding commitments and zero-knowledge proofs of knowledge, and hence does not depend on trusted authorities or computational intractability assumptions. Receipt-freeness, on the other hand, is achieved by a combination of cryptographic mixing and homomorphic tallying, for which trusted authorities and computational intractability assumptions are obviously required. These characteristics of our protocol exclude vote buying attacks, if we assume them to take place at the time of an election and that rewards are paid off shortly afterwards, but not many years later. Attacks against vote privacy will always remain impossible.

We presented the protocol in two steps. For the basic version, which includes all central mechanisms, some restrictions must be applied to both everlasting privacy and receipt-freeness. To eliminate these problems, we proposed corresponding protocol extensions, which can be added individually or jointly. The protocol is captivating in its relatively simple vote casting procedure, but the complex tallying and verification procedures—especially if all proposed extensions are implemented—might be subject of further research.

To check if our protocol is practicable for real-world elections, we analyzed the computational resources in terms of memory space consumption and computation time. Compared to the predecessor protocol, it turned out that the overhead for the extended tallying procedure is marginal. The results of the analysis and the conclusions are therefore very similar to those given in [28]. For a medium-sized or even a large electorate (up to approximately 1 million voters), our protocol is feasible with today’s technology. An even larger electorate can always be divided into smaller partitions without severe consequences.

Some problems remain unsolved in the current version of our protocol. First, some aspects of coercion-resistance are not addressed, for example forced-abstention, impersonation, or randomization attacks. Another open issue is the problem of flooding the bulletin board with a very large number of valid ballots. This problem is a direct consequence of our mechanism of achieving receipt-freeness by allowing voters to vote multiple times and consider them all in the final tally. Finally, our protocol provides no solution for the problem of a malicious voting platform. Enhancing our protocol with existing solutions to the open problems is another subject for future research.