1 Introduction

Electronic voting (eVoting) systems allow voters to generate ballots containing their vote intent, and submit these ballots to an electronic server. When all the ballots have been recorded, the talliers compute the result of the election and, hopefully, provide information allowing to check the validity of the tallying process. This verification mechanism ensures voters that their individual ballots have been faithfully recorded and counted in the tally. However, the information supporting verifiability can often be leveraged by malicious observers to demand voters to convincingly demonstrate how they voted, e.g., by disclosing all the random coins used to produce their ballots. eVoting systems preventing this kind of attacks are called receipt-free.

1.1 Receipt-Freeness

Since the introduction of Receipt-Freeness (RF) by Benaloh and Tuinstra [1], there has been a large amount of work targeting a well-balanced combination of receipt-freeness and verifiability. One such approach requires the use of fully trusted devices during the election [10, 12]. Hirt [9] refined this approach by proposing a scheme in which every voter must have their encrypted vote re-randomized by a ballot processing server, which must be trusted for receipt-freeness. The re-randomized ballot is then posted on a public bulletin board. Since the randomness contained in that ballot is no longer known by the voters, the voters cannot prove how they voted. This results in receipt-freeness. The ballot processing server of Hirt [9] serves as an observer [5] establishing receipt-freeness, but cannot violate the privacy of the votes or the correctness of the tally. However, the server must interact with the voter to confirm the correctness of the randomization, and the observer and the voter must jointly generate a proof of the validity of the randomized ballot.

To avoid such interactions between parties, the more recent line of work [3, 4, 7, 8] has designed mechanisms that make it possible to achieve non-interactive receipt-freeness. A voter generates a signed encrypted vote in a manner that allows the ciphertext and signature to be re-randomized by any individual, knowing neither the signing key nor the encrypted message, but the re-randomized signature will only be valid as long as the plaintext has not been modified. This creates a single-pass voting system [2] in which the ballot is sent from the voter, processed by a ballot processing server, and then posted on the bulletin board.

An encryption primitive designed to capture the desired form of non-interactive receipt-freeness was named traceable receipt-free encryption (TREnc) by Devillez et al. [6], who propose a mechanism realizing this primitive based on the signature of randomizable ciphertext with a one-time linearly homomorphic signature scheme, a primitive proposed by Libert et al. [11].

Yet, it is worth noting that even though the ballot processing server is not trusted for ballot privacy and election integrity, all of the aforementioned proposals rely on the assumption that the ballot processing server to which the voter submits his vote is trusted for RF, i.e., it does not collaborate with any vote-seller or coercer. This maintains a single point of failure. For instance, if the random coins utilized for re-randomizing ballots are transmitted to malicious voters, then the voters can demonstrate how they voted to any third party.

1.2 Our Contributions

We design an approach that removes the single point of failure of the existing receipt-free voting solutions. We first extend the traditional voting models to account for the involvement of multiple ballot processing servers. More precisely, the voting algorithm creates a ballot that can be split into n ballot pieces. Each ballot piece is processed in parallel by a ballot processing server before being gathered at a single place, usually a public bulletin board. Second, based on this enlarged syntax, we propose a security notion of threshold receipt freeness, and define a related correctness security notion. These security definitions capture the property that the voting system will accurately record the voter intent, while guaranteeing receipt-freeness as long as the number of malicious servers remains below the chosen threshold.

More precisely, we enhance the security model by introducing two thresholds: (1) the threshold for receipt-freeness (\(\ensuremath {\mathsf {t_{rf}}} \)), which sets the maximum number of malicious ballot processing servers that the system can tolerate without compromising RF; and (2) the threshold for correctness (\(\ensuremath {\mathsf {t_{corr}}} \)), which specifies the maximum number of ballot pieces that can be missing (intentionally or not) while still allowing the ballot to be processed in the tally. To reflect the fact that voters must be able to cast their intentions vote as in the single ballot processing model when \(\ensuremath {\mathsf {t_{rf}}} =0\), our threshold RF notions is defined in two steps. The first step ensures that as long as at most \(\ensuremath {\mathsf {t_{rf}}} \) ballot processing servers fix the content of any voter’s incoming ballot pieces, the voter can still cast a ballot containing any vote intent. The second step is a natural RF extension of the indistinguishable notion due to Devillez et al. [6].

Eventually, as a feasibility result, we build a generic voting system from a linear secret sharing scheme and a TREnc. In a nutshell, the voter simply relies on a t-out-of-n threshold secret sharing to split the vote in n pieces, and on a TREnc to encrypt all these pieces independently. As long as an homomorphic part of the TREnc ciphertexts can be stripped from the published randomized ballot pieces, the recombination of the vote can be made on the bulletin board during the tally before executing a mixnet. We show that this construction is threshold RF up to \(\ensuremath {\mathsf {t_{rf}}} =t-1\) malicious servers and threshold correct up to \(\ensuremath {\mathsf {t_{corr}}} =n-t\) missing ballot pieces.

Roadmap. The remainder of this paper is organized as follows. The background is provided in Sect. 2. In Sect. 3, we extend the traditional model of voting systems to the context of multiple ballot processing servers, and define out notions of threshold receipt-freeness and correctness. Section 4 describes our generic construction, and we demonstrate the security of this construction in Sect. 5. We conclude in Sect. 6.

2 Background on Traceable Receipt-Free Encryption

We start by reminding the notion of Traceable Receipt-Free Encryption (TREnc), a public key encryption primitive supporting the receipt-free submission of secret ballots [6].

Definition 1

(TREnc) A TREnc is a public key encryption \(({\textsf {Gen}}, {\textsf {Enc}}, {\textsf {Dec}})\) that is augmented with a 5-tuple of algorithms \(({\textsf {LGen}}, {\textsf {LEnc}}, {\textsf {Trace}}, {\textsf {Rand}}, {\textsf {Ver}})\):

  • \({\textsf {LGen}} (\ensuremath {\textsf{pk}})\): The link generation algorithm takes as input a public encryption key \(\ensuremath {\textsf{pk}} \) in the range of \({\textsf {Gen}} \) and outputs a link key \(\ensuremath {\textsf{lk}} \).

  • \({\textsf {LEnc}} (\ensuremath {\textsf{pk}}, \ensuremath {\textsf{lk}}, m)\): The linked encryption algorithm takes as input a pair of public/link keys \((\ensuremath {\textsf{pk}}, \ensuremath {\textsf{lk}})\) and a message m, outputs a ciphertext.

  • \({\textsf {Trace}} (\ensuremath {\textsf{pk}}, c)\) : The tracing algorithm takes as input a public key \(\ensuremath {\textsf{pk}} \), a ciphertext c and outputs a trace \(\tau \). We call \(\tau \) the trace of c.

  • \({\textsf {Rand}} (\ensuremath {\textsf{pk}}, c)\): The randomization algorithm takes as input a public key \(\ensuremath {\textsf{pk}} \) and a ciphertext c, outputs another ciphertext.

  • \({\textsf {Ver}} (\ensuremath {\textsf{pk}}, c)\): The verification algorithm takes as input a public key \(\ensuremath {\textsf{pk}} \), a ciphertext c and outputs 1 if the ciphertext is valid, 0 otherwise.

Definition 2

(TREnc correctness ) A TREnc scheme is required to satisfy the following correctness requirements:

Encryption compatibility: For every \(\ensuremath {\textsf{pk}} \) in the range of Gen and message m, the distributions of \({\textsf {Enc}} (\ensuremath {\textsf{pk}}, m)\) and \({\textsf {LEnc}} (\ensuremath {\textsf{pk}}, {\textsf {LGen}} (\ensuremath {\textsf{pk}}), m)\) are identical;

Link traceability: For every \(\ensuremath {\textsf{pk}} \) in the range of Gen, every \(\ensuremath {\textsf{lk}} \) in the range of \({\textsf {LGen}} (\ensuremath {\textsf{pk}})\), the encryptions of every pair of messages \((m_0, m_1)\) trace to the same trace, that is, \({\textsf {Trace}} (\ensuremath {\textsf{pk}},{\textsf {LEnc}} (\ensuremath {\textsf{pk}},\ensuremath {\textsf{lk}},m_0)) = {\textsf {Trace}} (\ensuremath {\textsf{pk}},{\textsf {LEnc}} (\ensuremath {\textsf{pk}},\ensuremath {\textsf{lk}},m_1))\), always;

Publicly Traceable Randomization: For every \(\ensuremath {\textsf{pk}} \) in the range of \({\textsf {Gen}} \), every message m and every c in the range of \({\textsf {Enc}} (\ensuremath {\textsf{pk}}, m)\), we have that \({\textsf {Dec}} (\ensuremath {\textsf{sk}}, c) = {\textsf {Dec}} (\ensuremath {\textsf{sk}}, {\textsf {Rand}} (\ensuremath {\textsf{pk}}, c))\) and \({\textsf {Trace}} (\ensuremath {\textsf{pk}}, c) = {\textsf {Trace}} (\ensuremath {\textsf{pk}}, {\textsf {Rand}} (\ensuremath {\textsf{pk}}, c))\);

Honest verifiability: For every \(\ensuremath {\textsf{pk}} \) in the range of \({\textsf {Gen}} \) and every messages m, it holds that \({\textsf {Ver}} (\ensuremath {\textsf{pk}}, {\textsf {Enc}} (\ensuremath {\textsf{pk}}, m)) = 1\).

A voter encrypts his vote m by picking a link key \(\ensuremath {\textsf{lk}} \) using \({\textsf {LGen}} \) and computing \({\textsf {LEnc}} \) to generate a ciphertext c, which is then submitted to a ballot processing server. The server runs \({\textsf {Rand}} \) to produce a re-randomized ciphertext \(c'\), which is included in the tally as long as \({\textsf {Ver}} (\ensuremath {\textsf{pk}}, c') = 1\). The correctness ensures that the voter’s intent is accurately reflected in the resulting ciphertext. The voter can also store the trace of the ciphertext \({\textsf {Trace}} (\ensuremath {\textsf{pk}}, c)\), which is equal to \({\textsf {Trace}} (\ensuremath {\textsf{pk}}, c')\), and confirms that it has been correctly recorded on the public bulletin board.

The traceability notion ensures that no corrupt authority would be able to modify a ciphertext in a way that modifies the plaintext without modifying the trace at the same time. Moreover, the trace cannot serve as a receipt for an encrypted message, since the trace and the message are independent, as guaranteed by the link traceability correctness. The traceability guarantees that, if the voter only produced a single ciphertext with a given trace, then any other ciphertext with the same trace will be an encryption of the same plaintext.

Definition 3

(Traceability) A TREnc is traceable if for every PPT adversary \(\mathcal {A}= (\mathcal {A}_1, \mathcal {A}_2)\), the experiment \( {\textsf {Exp}^{trace}_{\mathcal {A}}(\lambda )}\) defined in Fig. 1 (right) returns 1 with a probability negligible in \(\lambda \).

While the traceability relates to a model in which the voter is honest but the ballot processing server might be corrupted, the traceable-CCA notion (TCCA) focuses on protecting the privacy of the vote against a malicious voter. This is achieved through an indistinguishable experiment that guarantees that any malicious ballots computed with an identical trace cannot be recognized after randomization. This essentially guarantees the absence of a vote receipt.

Definition 4

(TCCA ) A TREnc is TCCA secure if for every PPT adversary \(\mathcal {A}= (\mathcal {A}_1, \mathcal {A}_2)\) the experiment \( {\textsf {Exp}^{{\text {TCCA}}}_{\mathcal {A}}(\lambda )}\) defined in Fig. 1 (left) returns 1 with a probability negligibly close in \(\lambda \) to \(\frac{1}{2}\).

Fig. 1.
figure 1

Security experiments. In the case of TCCA, \(\mathcal {A}_2\) has access to an oracle \({\textsf {Dec}} ^\star (\cdot )\) which, on input c, returns \({\textsf {Dec}} (c)\) if \({\textsf {Trace}} (\ensuremath {\textsf{pk}}, c) \ne {\textsf {Trace}} (\ensuremath {\textsf{pk}}, c^\star )\) and \(\bot \) otherwise.

Full size image

Homomorphic Part. In this paper we assume that it is easy to strip an homomorphic part of any TREnc ciphertext that carries the encrypted vote and allows decryption. The constructions of [6] satisfy this condition.

3 Voting Scheme with Multiple Ballot Processing Severs

We adapt the general e-voting definition of [6] to cope with multiple ballot processing servers, and formalize threshold receipt-freeness and correctness.

3.1 Definitions and Notations

The election adminstrator (\({\textsf {EA}}\)) is in charge of generating the keys of the system by running \({\textsf {SetupElection}} \). Given the public parameter of the system, voters can cast their intentions through \({\textsf {Vote}}\) which creates a ballot \(\textsf{b} =\{{\textsf {b}}_i\}_{i=1}^n\). Each ballot piece \({\textsf {b}}_i\) is processed by the i-th ballot processing server which simply runs the algorithm \({\textsf {ProcessBallot}}\). The other algorithms are unchanged.

Definition 5

(Voting System) A voting system equipped with n ballot processing servers is a tuple of PPT algorithms \(({\textsf {SetupElection}}, {\textsf {Vote}}, {\textsf {ProcessBallot}}, {\textsf {TraceBallot}}, {\textsf {Valid}}, {\textsf {Append}}, {\textsf {Publish}}, {\textsf {VerifyVote}}, {\textsf {Tally}}, {\textsf {VerifyResult}})\) associated to a result function \(\rho _m: \mathbb {V}^m \cup \{\bot \} \rightarrow \mathbb {R}\) where \(\mathbb {V}\) is the set of valid votes and \(\mathbb {R}\) is the result space such that:

  • \({\textsf {SetupElection}} (1^\lambda )\): on input security parameter \(1^\lambda \), generate the public and secret keys \((\ensuremath {\textsf{pk}}, \ensuremath {\textsf{sk}})\) of the election. Below, \(\ensuremath {\textsf{pk}} \) is an implicit input.

  • \({\textsf {Vote}}({\textsf {id}}, \textsf{v})\): when receiving a voter \({\textsf {id}}\) and a vote \(\textsf{v}\), output a ballot \(\textsf{b} =\{{\textsf {b}}_i\}_{i=1}^n\) and auxiliary data \(\textsf{aux}\). Given \(\textsf{aux}\), running \({\textsf {Vote}}({\textsf {id}}, \textsf{v}, \textsf{aux})\) allows computing ballots that can be related (in our case, ciphertexts with the same traces). \({\textsf {Vote}}({\textsf {id}}, \textsf{v};\rho )\) denotes the deterministic computation of the algorithm given random coin \(\rho \).

  • \({\textsf {ProcessBallot}}(\textsf{b}_i)\): on input a ballot share \(\textsf{b}_i\), output an updated ballot share \(\textsf{b}_i'\).

  • \({\textsf {TraceBallot}}(\textsf{b})\): on input ballot \(\textsf{b}\), outputs a tag \(\tau \). The tag is the information that a voter can use to trace his ballot, using \({\textsf {VerifyVote}}\).

  • \({\textsf {Valid}}({\textsf {BB}}, \textsf{b})\): on input ballot box \({\textsf {BB}}\) and ballot \(\textsf{b}\), outputs 0 or 1. The algorithm outputs 1 if and only if the ballot is valid.

  • \({\textsf {Append}}({\textsf {BB}}, \textsf{b})\): on input ballot box \({\textsf {BB}}\) and ballot \(\textsf{b}\), appends \(\textsf{b}\) to \({\textsf {BB}}\) if \({\textsf {Valid}}({\textsf {BB}}, {\textsf {b}}) = 1\).

  • \({\textsf {Publish}}({\textsf {BB}})\): on input ballot box \({\textsf {BB}}\), outputs the public view \({\textsf {PBB}}\) of \({\textsf {BB}}\), which is the one that is used to verify the election. Depending on the context, it may be used to remove some voter credentials for instance.

  • \({\textsf {VerifyVote}}(\textsf{PBB}, \tau )\): on input public ballot box \({\textsf {PBB}}\) and tag \(\tau \), outputs 0 or 1. This algorithm is used by voters to check if their ballot has been processed and recorded properly.

  • \({\textsf {Tally}}({\textsf {BB}}, \ensuremath {\textsf{sk}})\): on input ballot box \(\textsf{BB}\) and private key of the election \(\ensuremath {\textsf{sk}} \), outputs the tally \(\textsf{r}\) and a proof \(\mathsf {\Pi }\) that the tally is correct w.r.t. the result function \(\rho _m\).

  • \({\textsf {VerifyResult}}({\textsf {PBB}}, \textsf{r}, \mathsf {\Pi })\): on input public ballot box \({\textsf {PBB}}\), result of the tally \(\textsf{r}\) and proof of the tally \(\mathsf {\Pi }\), outputs 0 or 1. The algorithm outputs 1 only if \(\mathsf {\Pi }\) is a valid proof that \(\textsf{r}\) is the correct election result.

When voters cast their votes, they record the tracking code computed from \({\textsf {TraceBallot}}\) to trace their processed ballots on the public bulletin board \({\textsf {PBB}}\). Processed ballot shares that originate from the same voter are gathered and pushed to the ballot box \({\textsf {BB}}\), using \({\textsf {Append}}\). Recombined processed ballots are made publicly available on \({\textsf {PBB}}\) by running \({\textsf {Publish}}\). Voters can verify that their ballots have been correctly recorded on \({\textsf {PBB}}\) by relying on \({\textsf {VerifyVote}}\) and their tracking codes. Other algorithms are as usual. If we write \({\textsf {ProcessBallot}}({\textsf {b}}) = \{{\textsf {ProcessBallot}}({\textsf {b}}_i)\}_{i=1}^n\), it is easy to see that our syntax is indeed a generalization of [6] which corresponds to the particular case of \(n=1\).

3.2 Threshold Receipt-Freeness

We formalize receipt-freeness in the multi-ballot processing model. Intuitively, the receipt-free threshold \(\ensuremath {\mathsf {t_{rf}}} \) is the maximum number of malicious ballot processing servers tolerated by the system to guarantee receipt freeness.

Definition 6 (Threshold receipt-freeness)

A voting system \(\mathcal {V}\) with n ballot processing severs has receipt-freeness with threshold \(\ensuremath {\mathsf {t_{rf}}} \le n\) if

  1. 1.

    There exists an algorithm \({\textsf {Deceive}} \) such that, for every PPT adversary \(\mathcal {A}\), \(\Pr [{\textsf {Exp}^{\textsf {deceive}}_{\mathcal {A},\mathcal {V},\ensuremath {\mathsf {t_{rf}}}}(\lambda )}=1]\) negligible in \(\lambda \). (The experiment is defined in Fig. 2.)

  2. 2.

    There exist algorithms \(\textsf{SimSetupElection}\) and \(\textsf{SimProof}\) such that, for every \({\textsf {PPT}} \) adversary \(\mathcal {A}\), the following advantage is negligible in \(\lambda \)

    $$\textsf{Adv}_{\mathcal {A},\mathcal {V}}^{\textsf{rf},\ensuremath {\mathsf {t_{rf}}}}(1^\lambda ) =\left| \Pr \left[ {\textsf {Exp}^{\textsf {rf}, \ensuremath {\mathsf {t_{rf}}},0}_{\mathcal {A},\mathcal {V}}(\lambda )} = 1\right] - \Pr \left[ {\textsf {Exp}^{\textsf {rf}, \ensuremath {\mathsf {t_{rf}}},1}_{\mathcal {A},\mathcal {V}}(\lambda )} = 1 \right] \right| ,$$

    where the experiment \({\textsf {Exp}^{\textsf {rf}, \ensuremath {\mathsf {t_{rf}}},\beta }_{\mathcal {A},\mathcal {V}}(\lambda )}\) is defined in Fig. 3.

The Experiment. \({\textsf {Exp}^{\textsf {deceive}}_{\mathcal {A},\mathcal {V},\ensuremath {\mathsf {t_{rf}}}}(\lambda )}\). The setup of the election creates the public and secret keys (\(\ensuremath {\textsf{pk}}, \ensuremath {\textsf{sk}} \)) and \(\ensuremath {\textsf{pk}} \) is given to \(\mathcal {A}\). Then \(\mathcal {A}\) chooses at most \(\ensuremath {\mathsf {t_{rf}}} \) indexes of the corrupt ballot processing servers I. It also chooses the votes \(v_0, v_1\) and the random coin \(\rho \) in the hope that \(\rho \) is a receipt ensuring that the computed ballot \({\textsf {b}}\) contains \(v_0\). However, \(\mathcal {A}\) only sees the at most \(\ensuremath {\mathsf {t_{rf}}} \) ballot pieces \(({\textsf {b}}_i)_{i\in I}\) and the public tracking codes for which the \({\textsf {Deceive}} \) algorithm allows computing the complement ballot pieces so that \({\textsf {b}}\) is a valid vote for \(v_1\). (See Fig. 2.)

Fig. 2.
figure 2

Deceive experiment.

Full size image

The Experiment. \({\textsf {Exp}^{\textsf {rf},\ensuremath {\mathsf {t_{rf}}}, \beta }_{\mathcal {A},\mathcal {V}}(\lambda )}\). The experiment given in Fig. 3 is parameterized by a bit \(\beta \), and the adversary has access to the following oracles:

  • \(\mathcal {O}\textsf{init}\): Is called a single time and generates the secret and public keys for the election. The public key is shared with the adversary. When \(\beta =1\), depending on the computational model, a simulated setup may be performed. This setup provides trapdoor information that can be used to produce a simulated tally correctness proof. Two empty ballot boxes \({\textsf {BB}}_0\) and \({\textsf {BB}}_1\) are initialized. The adversary will only have access to \({\textsf {Publish}}({\textsf {BB}}_\beta )\) that is updated throughout the experiment.

  • \(\mathcal {O}\textsf{receiptLR}\): Allows the adversary to cast valid ballots and query the honest ballot processing servers to process their respective ballot pieces so that, on input \(({\textsf {id}}, \textsf{B}_0, \textsf{B}_1, \textsf{B}_2)\) for voter \({\textsf {id}}\), the oracle runs \({\textsf {ProcessBallot}}\) on both sets \(\textsf{B}_0\) and \(\textsf{B}_1\) of valid ballot pieces if they share the same traces for the same index and gets \(\textsf{B}_0'\) and \(\textsf{B}_1'\). As long as \(|B_0\cup B_2|=|B_1\cup B_2|\le n\) and \(|B_2|\le \ensuremath {\mathsf {t_{rf}}} \), \({\textsf {b}}_0 = \textsf{B}_0' || \textsf{B}_2\) is appended to \({\textsf {BB}}_0\) and \({\textsf {b}}_1 = \textsf{B}_1' || \textsf{B}_2\) is appended to \({\textsf {BB}}_1\). Up to reordering, we can always assume that the first servers are honest. \(B_2\) represents the ballot pieces for which the malicious vote seller and the corrupt servers together know their whole content.

  • \(\mathcal {O}\textsf{board}\): Returns the view \({\textsf {Publish}}({\textsf {BB}}_\beta )\) of the public bulletin board.

  • \(\mathcal {O}\textsf{tally}\): Allows the adversary to see the result of the election obtained by tallying valid \({\textsf {BB}}_0\), as well as a proof of correctness of the tally. If \(\beta = 1\), this proof is simulated with respect to the content derived from \({\textsf {BB}}_1\).

The adversary first calls \(\mathcal {O}\textsf{init}\). Following this, it can call the oracles \(\mathcal {O}\textsf{receiptLR}\) and \(\mathcal {O}\textsf{board}\) in any order and any number of times. Finally, the adversary calls the oracle \(\mathcal {O}\textsf{tally}\) to receive the (simulated) result of the election. It must then return its guess of the bit \(\beta \), which is the output of the experiment. If \(n=1\) and \(\ensuremath {\mathsf {t_{rf}}} =0\), we get back the receipt freeness definition of [6].

Fig. 3.
figure 3

Threshold receipt freeness oracles from experiment \({\textsf {Exp}^{\textsf {rf}, \ensuremath {\mathsf {t_{rf}}}, \beta }_{\mathcal {A},\mathcal {V}}(\lambda )}\), for \(\beta = 0,1\).

Full size image

3.3 Threshold Correctness

We formalize correctness in the multi-ballot processing model. Intuitively, the correctness threshold \(\ensuremath {\mathsf {t_{corr}}} \) is the maximum number of ballot pieces of any ballot that could not reach the bulletin board while still allowing to include the corresponding underlying voter’s intention in the tally.

Definition 7 (Theshold correctness)

A voting system \(\mathcal {V}\) with n ballot processing servers satisfies correctness with threshold \(\ensuremath {\mathsf {t_{corr}}} < n\) if for every PPT adversary \(\mathcal {A}\), \(\Pr [{\textsf {Exp}^{\textsf {corr},\ensuremath {\mathsf {t_{corr}}}}_{\mathcal {A},\mathcal {V}}(\lambda )}=1]\) is negligible in \(\lambda \). (The experiment is defined in Fig. 4.)

The Experiment. \({\textsf {Exp}^{\textsf {corr}, \ensuremath {\mathsf {t_{corr}}}}_{\mathcal {A},\mathcal {V}}(\lambda )}\). The experiment is given in Fig. 4, and the adversary is given access to the following oracles:

  • \(\mathcal {O}\textsf{init}\): Generates and returns both the secret and public keys of the election.

  • \(\mathcal {O}\textsf{vote}\): Takes a potential vote \(\mathsf v\) for a user \({\textsf {id}}\), honestly produces and outputs a ballot \({\textsf {b}}\) using \({\textsf {Vote}}\). The tracking code \({\textsf {TraceBallot}}{{\textsf {b}}}\) is stored in the list \(\mathcal {L}\). This represents ballots and tracing information from honest voters.

  • \(\mathcal {O}\textsf{append}\): Allows the adversary to select two valid ballots \({\textsf {b}}_0\) and \({\textsf {b}}_1\) of at least \(n-\ensuremath {\mathsf {t_{corr}}} \) valid ballot pieces as if there were potentially maliciously processed from honest ballots output by \(\mathcal {O}\textsf{vote}\). That is, both ballots must have their respective sets of tracking codes included in a single set of codes from \(\mathcal {L}\). Both ballots are then respectively appended to \({\textsf {BB}}_0\) and \({\textsf {BB}}_1\). It represents maliciously processed ballot pieces that use the same tracing information as honest ballots but for which the adversary tries to change the content of the votes and blocks at most \(\ensuremath {\mathsf {t_{corr}}} \) pieces of them.

  • \(\mathcal {O}\textsf{cast}\): Allows the adversary to cast a malicious valid ballot \({\textsf {b}}\) in \({\textsf {BB}}_0\) and \({\textsf {BB}}_1\).

  • \(\mathcal {O}\textsf{board}\): Returns the views \({\textsf {Publish}}({\textsf {BB}}_0)\) and \({\textsf {Publish}}({\textsf {BB}}_1)\) of the public bulletin boards.

  • \(\mathcal {O}\textsf{tally}\): Allows the adversary to get the results of the election obtained by honestly tallying \({\textsf {BB}}_0\) and \({\textsf {BB}}_1\).

The adversary \(\mathcal {A}\) initiates the experiment by invoking the oracle \(\mathcal {O}\textsf{init}\), and the experiment terminates when it calls \(\mathcal {O}\textsf{tally}\). The output of the experiment is a bit that is equal to 1 only if the adversary managed to compute valid ballots providing distinct outcomes from both ballot boxes. To attempt creating such ballots, the adversary can query all the other oracles many times in many orders.

Fig. 4.
figure 4

Threshold correctness experiment \({\textsf {Exp}^{\textsf {corr}, \ensuremath {\mathsf {t_{corr}}}}_{\mathcal {A},\mathcal {V}}(\lambda )}\) which outputs 1 only if \(\textsf{r}_0 \ne \textsf{r}_1\).

Full size image

Remarks. We leave it open to define a stronger threshold correctness notion where the adversary would remain unable to modify the result of the election by selecting distinct ballot pieces from a maliciously generated ballot. Here malicious ballots are equally processed on both ballot boxes. In our construction, this is not an issue as we implicitly define the vote as the one contained in the recombination of all the stripped ciphertexts included in the ballot pieces of each voter. The recombined ciphertexts are then tallied based on a mixnet. Achieving the stronger notion in a construction with an homomorphic tally requires designing new malleable proofs that can be adapted through all the randomness used by the n servers. Indeed, if the vote v is represented with a bit, the randomizable shared proof that \(v(1-v)=0\) is hardly adaptable locally by the n servers as their adaptation must depend on the others’ randomizing factors.

4 Our Construction Based on TREnc

Our voting system is based on a TREnc. As recalled in Sect. 1, a TREnc consists of various algorithms including \({\textsf {Gen}},\) \( {\textsf {Enc}},\) \( {\textsf {Trace}}, {\textsf {Rand}}, {\textsf {Ver}} \), and \({\textsf {Dec}} \) in particular. We will use these algorithms to demonstrate how to design a voting system that can provide the properties of threshold receipt-freeness and correctness as previously described in Sects. 3.2 and 3.3.

The message (or the vote) \(\mathsf v\) is divided into n message shares using a t-out-of-n threshold secret sharing scheme, originally proposed by Shamir [13], where at least t message pieces must be combined to reconstruct the message. Moreover, any \(t-1\) pieces remain independent of \(\mathsf v\). To generate the ballot \({\textsf {b}}\), the voter encrypts each share of his message by calling the \({\textsf {Enc}} \) function of TREnc, which produces a ballot share \({\textsf {b}}_i\). The process is repeated n times for n message shares, resulting in the creation of a full ballot consisting of n ballot shares, i.e., \({\textsf {b}}= \{{\textsf {b}}_i\}_{i=1}^n\). Each share is processed by a specific ballot processing server. For instance, server i exclusively receives the ballot share \({\textsf {b}}_i\), and does not have access to any other share \({\textsf {b}}_j\) where \(j \ne i\). The instantiation of our voting scheme is illustrated in Fig. 5, where n is the implicit input of all the algorithms.

Fig. 5.
figure 5

Instantiation of our voting scheme.

Full size image

First, \({\textsf {EA}}\) runs the \(\textsf{SetupElection}\) algorithm to generate the public and secret keys of the election. This is achieved by running the key generation algorithm from TREnc, denoted by TREnc.Gen. The public key \(\ensuremath {\textsf{pk}} \) is published and stored on the \({\textsf {PBB}}\), while \(\ensuremath {\textsf{sk}} \) is only known by the talliers (\(\ensuremath {\textsf{sk}} \) can be securely generated in a distributed way in our prime-order groups using standard techniques). For the sake of simplicity, we consider a model with a single tallier.

When a voter wants to cast a vote \(\mathsf v\), he prepares a ballot using the \({\textsf {Vote}}\) algorithm. First, the \(\textsf{Share}\) is executed to implement the t-out-of-n threshold secret-sharing scheme. This function takes as input the number of ballot processing parties n, the threshold t, and the secret \(\mathsf v\) to output the shares \(M =\{x_1, \dots , x_n\}\). Then, it calls the encryption function \({\textsf {Enc}} \) of TREnc (which includes \({\textsf {LGen}} (\ensuremath {\textsf{pk}}) = \ensuremath {\textsf{lk}} \) and \({\textsf {LEnc}} (\ensuremath {\textsf{pk}}, \ensuremath {\textsf{lk}}, \mathsf v)\)) on each message share \(x_i\) to produce a ballot share \({\textsf {b}}_i\) for \(i=1\) to n. In the end, \({\textsf {Vote}}\) returns a ballot \({\textsf {b}}\) and \(\textsf{aux}=\ensuremath {\textsf{lk}} \).

Each \({\textsf {b}}_i\) is then submitted to a distinct ballot processing server, while the full trace \(\tau = {\textsf {TraceBallot}}({\textsf {b}}) \) is sent directly to the PBB. We have that \(\tau = \{\tau _i\}_{i=1}^{|{\textsf {b}}|}\) including all traces of available ballot shares in \({\textsf {b}}\), where \(\tau _i = {\textsf {TREnc}}.{\textsf {Trace}} ({\textsf {b}}_i)\). When a server receives a \({\textsf {b}}_i\), it extracts its trace using \({\textsf {TREnc}}.{\textsf {Trace}} ({\textsf {b}}_i)\) and verifies that no shares with the same trace were recorded before. If \({\textsf {b}}_i\) is valid, i.e., \({\textsf {TREnc}}.{\textsf {Ver}} ({\textsf {b}}_i) =1\), it will be re-randomized with the help of \({\textsf {ProcessBallot}}({\textsf {b}}_i) = {\textsf {TREnc}}.{\textsf {Rand}} ({\textsf {b}}_i)\), while invalid shares are discarded. Although each randomizer processes only one share of each voter at a time, the \({\textsf {ProcessBallot}}\) algorithm can be executed in parallel for n number of randomizers. The resulting ballot share is then made available on the BB.

The tallying process commences with the gathering of ballot shares from the same ballot. To do this, the tallier compares traces received on \({\textsf {BB}}\) to the full trace \(\tau \) posted by each voter on the public board earlier. Subsequently, the validity of each ballot is verified using the function \({\textsf {TREnc}}.{\textsf {Ver}} \) on each ballot share. The function \({\textsf {Valid}}({\textsf {BB}}, {\textsf {b}})\) in Fig. 5 returns 1 if there are at least t valid ballot shares of \({\textsf {b}}\) on the public board, and 0 otherwise. Consequently, the combination algorithm \(\textsf{Combine}\) takes as input the homomorphic parts of all valid ballot shares available, which may be at most n, and outputs the combined encryption of the original message \(\mathsf v\). The resulting (CPA-secure) ciphertext contains the reconstruction of the vote from the encrypted shares. According to the principles of Lagrange polynomial interpolation, the final message remains unaltered even when more than t valid shares are combined.

The Validity of the Vote. The purpose of the \({\textsf {Valid}}\) function is to ensure that the input of the tally is valid. However, this function does not guarantee that the encrypted vote is within the range of the vote space. To address this issue, a verifiable mixnet will be added after the combination process is completed, which disassociates the ballots from their corresponding voters. This anonymization process will be carried out by shuffling the resulting combined encryptions through multiple shuffling centers, after which they will be decrypted individually. Invalid votes are discarded. The tallier returns the result of the election \(\textsf{r}\) along with proof of its correctness \(\mathsf {\Pi }\), which can be verified by anyone with \({\textsf {VerifyResult}}\). Voters also can verify the presence of their vote on the bulletin board by utilizing \({\textsf {VerifyVote}}({\textsf {PBB}},\tau )\) to confirm if any entry in \({\textsf {PBB}}\) matches \(\tau \).

Correlation Between. \(\ensuremath {\mathsf {t_{rf}}} \) and \(\ensuremath {\mathsf {t_{corr}}} \). In accordance with the threshold secret sharing scheme used, the voting system requires that at least t of a ballot’s valid shares are available on the \({\textsf {BB}}\) to reconstruct the ballot. By definition, \(\ensuremath {\mathsf {t_{corr}}} = n-t\). In terms of receipt-freeness, since a \({\textsf {b}}_i\) is computed as a TREnc ciphertext, first, the TREnc ’s traceability ensures that as long as the \(\ensuremath {\textsf{lk}} \) remains secret, it is infeasible for anyone to change the message share \(x_i\) while keeping the trace \(\tau _i\) unchanged even with \(\ensuremath {\textsf{sk}} \). Additionally, knowing the link keys \(\ensuremath {\textsf{lk}} = \{\ensuremath {\textsf{lk}} _i\}_{i=1}^n\) allows voting for any voting shares even for fixed traces (that an RF adversary would like to see on \({\textsf {PBB}}\)) and the secret sharing properties allows computing shares of any vote \(\mathsf v\) even with \(t-1\) chosen shares. Moreover, the TCCA security of TREnc guarantees that an honest randomization will erase all malicious information that can be introduced in the ballot, rendering it infeasible for the individual who generated it to prove to anyone that it is the ballot of a particular vote. Consequently, as long as the combination includes at least one honestly re-randomized ballot share if \(t-1\) ciphertexts are corrupt, RF is achieved. As a result, the number of allowed malicious randomizers, i.e., process ballot servers should be no greater than \(\ensuremath {\mathsf {t_{rf}}} =t-1\). See Sect. 5.1 for the proof.

Given that \( 1 \le \ensuremath {\mathsf {t_{corr}}} \le n-t\), the proposed voting system offers a solution for scenarios where some randomizers are not functioning properly, whether intentionally or unintentionally. In such cases, incomplete ballots will nevertheless be proceeded to the tally. This ensures that the system can provide flexibility by handling unflavored cases and maintaining the integrity of the election process. In a specific case where a n-out-of-n threshold secret-sharing scheme is employed, \(\ensuremath {\mathsf {t_{corr}}} = 0\) and \(\ensuremath {\mathsf {t_{rf}}} = n-1\). That means, provided that all n valid ballot shares arrive on the BB, the system achieves RF even when only one honest randomizing server exists. To the best of our knowledge, this represents the strongest security notion for single-pass RF that has been proposed in the literature to date.

5 Security of the Voting Scheme

In this section, we prove that our generic voting scheme described in the previous section is threshold receipt-free (Sect. 5.1) and threshold correct (Sect. 5.2).

5.1 Threshold Receipt-Freeness

Theorem 1

If the TREnc used in the voting scheme is TCCA secure and verifiable, and if the proof system used to prove the correctness of the tally is zero-knowledge, our voting scheme has threshold receipt freeness. More precisely, for a t-out-of-n secret sharing of the vote, \(\ensuremath {\mathsf {t_{rf}}} =t-1\), \(\Pr [{\textsf {Exp}^{\textsf {deceive}}_{\mathcal {A},\mathcal {V},\ensuremath {\mathsf {t_{rf}}}}(\lambda )}=1]\le \varepsilon _{verif }\), where \(\varepsilon _{verif }\) is the verifiability advantage of any adversary against TREnc, and \(\textsf{Adv}_{\mathcal {A},\mathcal {V}}^{\textsf{rf},\ensuremath {\mathsf {t_{rf}}}}(1^\lambda )\le \varepsilon _{ZK }+ q(n-\ensuremath {\mathsf {t_{rf}}})\varepsilon _{tcca }\), where \(\varepsilon _{ZK }\) is the zero-knowledge advantage of any adversary against the proof system, \(\varepsilon _{tcca }\) is the TCCA advantage of any adversary against TREnc (recalled in Definition 4), and q is the number of queries made to \({\mathcal {O}\textsf {receiptLR}}\) made by the adversary \(\mathcal {A}\).

Proof. The experiment \({\textsf {Exp}^{\textsf {deceive},\ensuremath {\mathsf {t_{rf}}}}_{\mathcal {A},\mathcal {V}}(\lambda )}\).:

Given \(\rho =\{r_{ss},r_{enc}\}\), where \(r_{ss}\) contains all random coins for the secret sharing scheme \(\textsf{Share}\), i.e., the coefficients of the polynomial f in the Shamir’s t-out-of-n threshold scheme, while \(r_{enc}\) contains \(\ensuremath {\textsf{lk}} \) and all the random coins in TREnc.LEnc, the \({\textsf {Deceive}} \) function aborts and outputs 0 if either \(v_0, v_1, \rho \), or I fail to parse correctly. Otherwise,

  1. 1.

    It selects \(r_{ss}\) from \(\rho \) to output \(\{v_0^i\}_{i \in I} = \textsf{Share}(\ensuremath {\textsf{pk}}, n, t, v_0;r_{ss})\), where each \(v_0^i\) is an evaluation of a degree-\((t-1)\) polynomial f at a point i. The adversary will be able to verify if \(\{v_0^i\}_{i \in I} \) are in \(\{{\textsf {b}}_0^i\}_{i \in I}\) since these will be processed by dishonest randomizers and with known randomness \(r_{enc}\).

  2. 2.

    To secretly share \(v_1\), it produces another polynomial g of degree \(t-1\) such that \(g(0)=v_1\). To this end, the evaluation of g at a point i is fixed to be \(v_0^i\) for all \({i \in I}\), thereby providing at most t linear conditions. If \(|I|< \ensuremath {\mathsf {t_{rf}}} = t-1\), add random input-output evaluation pairs to the interpolation to reach the appropriate degree. Subsequently, evaluate g at the point \(i \in [n] \backslash I\) to compute \(v_1^i\).

  3. 3.

    To generate \({\textsf {b}}_1\), it selects \(r_{enc}\) from \(\rho \) to run TREnc.LEnc on message shares \(\{v_0^i\}_{i \in I} \) and \(\{v_1^i\}_{i \in [n] \backslash I}\), which keeps the traces as \(\ensuremath {\textsf{lk}} \in r_{enc}\).

Since the \(\textsf{Share}\) operation based on the polynomial g is carried out honestly, any combination of t ballot shares in \({\textsf {b}}_1\) will result in the decryption of the same encrypted message. Eventually, even if the random coin \(r_{enc}\) are maliciously distributed, the TREnc verifiability guarantees that \({\textsf {b}}_1 \in {\textsf {Vote}}({\textsf {id}}, v_1)\).

  • The experiment \({\textsf {Exp}^{\textsf {rf}, \ensuremath {\mathsf {t_{rf}}}, \beta }_{\mathcal {A},\mathcal {V}}(\lambda )}\). To proceed with the \(\mathcal {O}\textsf{receiptLR}\) oracle defined in Fig. 3, an attacker must produce two valid ballots, namely \({\textsf {b}}_0 = \textsf{B}_0||\textsf{B}_2\) and \({\textsf {b}}_1 = \textsf{B}_1||\textsf{B}_2\). The oracle then verifies that both ballots have identical traces. More precisely, the conditions \({\textsf {Valid}}({\textsf {b}}_0)= {\textsf {Valid}}({\textsf {b}}_1) = 1\) and \({\textsf {TraceBallot}}({\textsf {b}}_0) = {\textsf {TraceBallot}}({\textsf {b}}_1)\) must be met before processing them. The proof involves a series of indistinguishable games, starting with the experiment \({\textsf {Exp}^{\textsf {rf}, \ensuremath {\mathsf {t_{rf}}}, 0}_{\mathcal {A},\mathcal {V}}(\lambda )}\) (\(\beta =0\)) and ending with \({\textsf {Exp}^{\textsf {rf}, \ensuremath {\mathsf {t_{rf}}}, 1}_{\mathcal {A},\mathcal {V}}(\lambda )}\) (\(\beta =1\)).

  • \(\textsf {Game}_{1}(\lambda )\): This is the experiment \({\textsf {Exp}^{\textsf {rf, \ensuremath {\mathsf {t_{rf}}}, 0}}_{\mathcal {A},\mathcal {V}}(\lambda )}\) given in Fig. 3 with \(\beta =0\). By definition, \(\Pr [S_1] = \Pr [{\textsf {Exp}^{\textsf {rf},\ensuremath {\mathsf {t_{rf}}},0}_{\mathcal {A},\mathcal {V}}(\lambda )}=1] \).

  • \(\textsf {Game}_{2}(\lambda )\): This game is as Game 1, with the exception that the keys of the election are generated using \(\textsf{SimSetupElection}\) which still produces the secret key \(\ensuremath {\textsf{sk}} \) of TREnc but also creates the additional trapdoor key to simulate proof for the tally. Moreover, we still honestly run \({\textsf {Tally}}\) to get the result of the election but we erase the proof and instead run \(\textsf{SetupElection}\) on input the honest result. Since the proof system of the tally is zero-knowledge, we have \(|\Pr [S_1] - \Pr [S_2] | \le \varepsilon _{ZK }\).

  • \(\textsf {Game}_{3}(\lambda )\): This game is as the previous game, except that the decryption is executed on-the-fly using \({\textsf {Dec}} (\ensuremath {\textsf{sk}},\cdot )\) of TREnc in each call to \(\mathcal {O}\textsf{receiptLR}\) before the (perfect) randomization in \({\textsf {ProcessBallot}}\). The result of the election is then computed from the resulting function. Since the view in Game 2 is identical to that of Game 1, we have \(\Pr [S_2] = \Pr [S_3]\).

  • \(\textsf {Game}_{4}(\lambda )\): In this game, we introduce the following modification in the way we answer to the \({\mathcal {O}\textsf {receiptLR}}\) queries made by the adversary, by gradually replacing processed ballots from \(B_0\) by those of \(B_1\) in \(BB_0\).

    • \(\mathsf Game_{4,1}(\lambda )\): In order to compute \(\mathsf B_0'\), instead of re-randomizing \({\textsf {b}}_0^1\), we re-randomize \({\textsf {b}}_1^1\). In other words, \(\mathsf B_0' = ( {\textsf {b}}_1^{1'}, {\textsf {b}}_0^{2'}, \dots , {\textsf {b}}_0^{n-\ensuremath {\mathsf {t_{rf}}} '})\). The probability that \(\mathcal {A}\) distinguishes the difference after this modification is the probability that one is able to distinguish whether the first element of \(\mathsf B_0'\) is the randomization of \({\textsf {b}}_0^{1}\) or \({\textsf {b}}_1^{1}\). Since each ballot share is a valid TREnc ciphertext and that \({\textsf {Valid}}\) rejects replaying the same traces, the TCCA challenger can call its own TCCA decryption oracle to compute the result as in Game 3 before the challenge phase since the corresponding trace has never been involved in an earlier query in another ballot piece, it follows that \(|\Pr [S_3] - \Pr [S_{4,1}] | \le \varepsilon _{tcca }\).

    • \(\mathsf Game_{4,i}(\lambda )\): Keep doing the same way, we replace each element of \(\mathsf B_0'\) by a corresponding element in \(\mathsf B_1'\). Hence, \(|\Pr [S_{4,i-1}] - \Pr [S_{4,i}] | \le \varepsilon _{tcca }\).

At the end of Game 4, we have \(\mathsf B_0' = ( {\textsf {b}}_1^{1'}, \dots , {\textsf {b}}_1^{n-\ensuremath {\mathsf {t_{rf}}} '})\), which is identical to \(\mathsf B_1'\). Consequently, for the first query to \({\mathcal {O}\textsf {receiptLR}}\) query, we have \(|\Pr [S_3] - \Pr [S_{4}] | \le (n-\ensuremath {\mathsf {t_{rf}}})\varepsilon _{tcca }\). Then, by an hybrid argument on all the q queries made by the adversary, we get \(|\Pr [S_3] - \Pr [S_{4}] | \le q(n-\ensuremath {\mathsf {t_{rf}}})\varepsilon _{tcca }\). The view of \(\mathcal {A}\) in Game 4 is exactly its view in \({\textsf {Exp}^{\textsf {rf}, \ensuremath {\mathsf {t_{rf}}}, 1}_{\mathcal {A},\mathcal {V}}(\lambda )}\). We thus have \(\textsf{Adv}_{\mathcal {A},\mathcal {V}}^{\textsf{rf},\ensuremath {\mathsf {t_{rf}}}}(1^\lambda )\le \varepsilon _{ZK }+ q(n-\ensuremath {\mathsf {t_{rf}}})\varepsilon _{tcca }\).    \(\square \)

5.2 Threshold Correctness

Theorem 2

If the TREnc used in the voting scheme is traceable and verifiable, then the proposed voting scheme has threshold correctness. More precisely, for a t-out-of-n secret sharing of the vote, we have \(\ensuremath {\mathsf {t_{corr}}} =t-1\) and for any efficient adversary \(\mathcal {A}\), \(\Pr [{\textsf {Exp}^{\textsf {corr},\ensuremath {\mathsf {t_{corr}}}}_{\mathcal {A},\mathcal {V}}(\lambda )}=1]\le qn\varepsilon _{trace }\), where \(\varepsilon _{trace }\) is the advantage of any adversary against traceability of TREnc (recalled in Definition 3), and q is the number of \({\mathcal {O}\textsf {append}}\) queries.

Proof

In the experiment \({\textsf {Exp}^{\textsf {corr}, \ensuremath {\mathsf {t_{corr}}}}_{\mathcal {A},\mathcal {V}}(\lambda )}\), to append ballots to \({\textsf {BB}}_1\) and \({\textsf {BB}}_0\), \(\mathcal {A}\) can make \({\mathcal {O}\textsf {cast}}\) and \({\mathcal {O}\textsf {append}}\) queries.

  • \({\mathcal {O}\textsf {cast}}\) appends the same malicious valid ballot to both bulletin boards. Since the identical ballot is published to both bulletin boards, this will not assist the adversary in winning the game, as it will not result in any difference in the tally results. That is also because the recombination is made deterministically on all the valid pieces.

  • \({\mathcal {O}\textsf {append}}\) records two valid ballots, \({\textsf {b}}_0\) and \({\textsf {b}}_1\), which are maliciously processed from an honestly generated ballot \({\textsf {b}}\), to the bulletin board \({\textsf {BB}}_0\) and \({\textsf {BB}}_1\) respectively. As defined, \({\textsf {b}}= \{{\textsf {b}}^i\}_{i=1}^n= {\textsf {Vote}}({\textsf {id}}, \mathsf v)\), \(T = {\textsf {TraceBallot}}({\textsf {b}})\), and \({\textsf {TraceBallot}}({\textsf {b}}_0), {\textsf {TraceBallot}}({\textsf {b}}_1) \subset T\). Let us call \(I_0, I_1\) two subset indexes of [n], we denote \({\textsf {b}}_0 =\{{\textsf {b}}_0^i\}_{i\in I_0}\) and \({\textsf {b}}_1 =\{{\textsf {b}}_1^i\}_{i\in I_1}\) with \(|I_0|, |I_1| \ge n-\ensuremath {\mathsf {t_{corr}}} \). As a result, \({\textsf {TraceBallot}}({\textsf {b}}_j^i) \in T\) for all \(j =0,1\) and \(i \in I_j\). First, since each ballot share is a TREnc ciphertext and TREnc is traceable, it is infeasible for anyone to produce another ciphertext that traces to the same trace and would decrypt to a different message. We thus have \({\textsf {Dec}} (\ensuremath {\textsf{sk}},\textsf{Combine}(\{{\textsf {b}}_j^i\})) = {\textsf {Dec}} (\ensuremath {\textsf{sk}},\textsf{Combine}(\{{\textsf {b}}^i\}))\) for all \(j = 0,1\) and for each \(i \in I_j\), except with a negligible probability \(\varepsilon _{trace }\). Second, since \({\textsf {b}}\) is generated honestly, a combination of any subgroup of at least \(n-\ensuremath {\mathsf {t_{corr}}} \) shares returns the same message \(\mathsf v\). Consequently, it always holds that \({\textsf {Dec}} (\ensuremath {\textsf{sk}},\textsf{Combine}(\{{\textsf {b}}^i\}_{i \in I_0})) = {\textsf {Dec}} (\ensuremath {\textsf{sk}},\textsf{Combine}(\{{\textsf {b}}^i\}_{i \in I_1}))\). The first and second points above infer that \({\textsf {Dec}} (\ensuremath {\textsf{sk}},\textsf{Combine}(\{{\textsf {b}}_0^i\}_{i \in I_0})) = {\textsf {Dec}} (\ensuremath {\textsf{sk}},\textsf{Combine}(\{{\textsf {b}}_1^i\}_{i \in I_1}))\) but with a negligible probability.

It is easy to see that with \(\ensuremath {\textsf{sk}} \) we can always decrypt each ballot pieces and figure it out whether the adversary managed to compute a TREnc ciphertext that reuses a trace but does not contain the original honest voting shares as message. Hence, \(\Pr [{\textsf {Exp}^{\textsf {corr}, \ensuremath {\mathsf {t_{corr}}}}_{\mathcal {A},\mathcal {V}}(\lambda )} =1] \le qn \varepsilon _{trace }\) by a standard guessing technique.    \(\square \)

As previously discussed, the current threshold correctness notion does not account for scenarios where an adversary introduces a malicious ballot with distinct ballot pieces. In such cases, different combinations of ballot shares could yield different combined messages. However, since all valid ballot shares on the bulletin board (possibly more than t) are combined, only one message can be reconstructed. As the adversary cannot predict which ballot shares will be available due to any potential non-operational randomizers, it should produce truthful ballots to ensure the resulting vote accurately reflects its intent.

Verifiability. Our voting scheme satisfies both individual and universal verifiability. Individual verifiability is guaranteed through the \({\textsf {VerifyVote}}\) steps, which allow voters to confirm the accurate recording of their votes and ensure that their preference remains unaltered. Universal verifiability is upheld by the verifiable mixnet, ensuring accurate tally computation and trustworthy final results.

6 Conclusion

We propose the notion threshold receipt-freeness, an extension of receipt-freeness that involves multiple ballot processing servers, removing a single point of failure of previous methodologies. Apart from preventing a malicious voter from providing proof of their vote to any third party, the novel definition allows an honest voter to cast their vote for their preferred candidate, even if some servers are compromised, provided that the adversary cannot vote on their behalf.

Additionally, we develop a generic construction of a single-pass verifiable voting system, based on traceable receipt-free encryption. Given any number n of ballot processing servers and \(1\le t\le n\), the resulting system maintains receipt-freeness and correctness as long as only t valid processed ballot pieces reach the bulletin board and even if \(t-1\) of them were processed by the malicious servers who may reveal their random coins. Moreover, the trustworthy servers might differ for each voter. Practically, one may setup an election with only 3 servers so that any voter trusts at least any 2 of them, and their intentions will be taken into account if any 2 ciphertexts among the 3 computed are posted on the bulletin board after re-randomization.

Since the ballots are composed of n TREnc ciphertexts, their size is linear in the number of servers. We think that designing ballots of sub-linear size in n would require new techniques. Moreover, we leave it open to design a threshold receipt-free and correct election system compatible with homomorphic tally. Designing randomizable proof in a single-pass that maintains validity of the vote, for instance in an approval voting scenario, through the n servers which do not interact together seems to be challenging.