Véronique Cortier

Pierrick Gaudry

Quentin Yang

Is the JCJ voting system really coercion-resistant?

Keywords:

Coercion-resistance is a security property of electronic voting, often considered as a must-have for high-stake elections. The JCJ voting scheme, proposed in 2005 by Juels, Catalano and Jakobsson, is still the reference paradigm when designing a coercion-resistant protocol. We highlight a weakness in JCJ that is also present in all the systems following its general structure. This comes from the procedure that precedes the tally, where the trustees remove the ballots that should not be counted. This phase leaks more information than necessary, leading to potential threats for the coerced voters. Fixing this leads to the notion of cleansing-hiding, that we apply to form a variant of JCJ that we call CHide. One reason for the problem not being seen before is the fact that the associated formal definition of coercion-resistance was too weak. We therefore propose a definition that takes into account more behaviors such as revoting or the addition of fake ballots by authorities. We then prove that CHide is coercion-resistant for this definition.

I. INTRODUCTION

Internet voting allows to take part in an election without being physically present at a polling station. It can be used for many reasons, such as providing people with low mobility or expatriates with a way to vote beside postal voting, or as a necessary alternative during a pandemic. As of today, electronic voting has been used for politically-binding elections in several countries (e.g. Australia, Switzerland, Estonia, to name but a few). For such high-stakes contexts, coercion may be an important threat. It occurs when an attacker forces a voter to vote in a specific way, using a threat or a reward. This phenomenon is known to exist in real-world elections, with traditional voting at polling stations. However, compared to a paper-based solution, an electronic voting solution which is not designed to tackle coercion could allow the attacker to coerce a larger number of voters, or to gain a more convincing evidence that the coerced voters actually obeyed. Also, since Internet voting is a remote voting process, this introduces new attacks compared to polling station voting. For instance, the coercer can ask the voter to give all the voting materials that they received. The classical verifiability mechanisms will then provide a proof to the coercer that the voter did not cheat.

The JCJ protocol. A seminal protocol which aims to counter coercion was proposed in 2005 by Juels, Catalano and Jakobsson [START_REF] Juels | Coercion-resistant electronic elections[END_REF]. They also provide a formalization of the notion, allowing to give security arguments. This is now called the This work benefited from funding managed by the French National Research Agency under the France 2030 programme with the reference ANR-22-PECY-0006.

JCJ protocol and remains the reference for the research on coercion-resistance in electronic voting. The key idea of JCJ is that voters can give fake voting material (a fake credential) to the coercer, and pretend that it is genuine. The coercer, who votes with the provided credential, has no way to detect whether the credential is valid or not. In order to guarantee that, during the voting phase, ballots are accepted in the ballot box regardless of their credentials; those which use an invalid or a duplicate one are removed later, during a cleansing phase. The output of this cleansing phase is a set of ballots that is tallied in the usual way. The main security feature is that, given a credential and all the publicly available information, the coercer is unable to tell whether the credential is real or fake. At the same time, for the legitimate voters, verifiability is preserved. Hence JCJ aims at offering coercion-resistance in a context where voters:

• are not fully controlled by the coercer and may cast their true vote at some point, when they are not under coercion; • may access to a tool (e.g. a free online website) that generates randoms fake credentials of the expected format; • did receive their valid credential at an earlier step, outside the control of the attacker.

For coercion-resistance, the cleansing phase is critical. In JCJ, some information is leaked, namely the number of ballots sent to the public board and to the tallying procedure, before and after the cleansing phase. It is known that the difference ∆ between those two can reveal some information to the coercer. Therefore it is important to ensure some "noise", coming from revotes or dummy ballots, that would mask the action of a voter resisting a coercer. Still, depending on its exact definition, the cleansing phase could leak more than just ∆. For instance, in [START_REF] Spycher | A New Approach towards Coercion-Resistant Remote E-Voting in Linear Time[END_REF], the authors present a protocol where the coercer can deduce the number of ballots which pretend to be from each voter, and exploit this additional information (which is not available in the original JCJ). To mitigate this leakage, they propose that the authorities add a random number of dummy ballots for each voter, which mitigates the leakage.

A weakness in JCJ. We have discovered that even in the original JCJ protocol, the cleansing step leaks more than the difference ∆ between the sizes of its input and output. First, the ballots with the same credentials (i.e. revotes) are handled, keeping only one ballot per credential. Second, the ballots that use an invalid credential are removed. The size of the intermediate ballot box is leaked; moreover, anyone can observe the distribution of the number of revotes. Those pieces of information can be analyzed by the coercer and help to determine if a coerced voter obeyed or not. In particular, we provide a few examples where this leakage allows the coercer to fully break coercion-resistance, even if dummy ballots are used. Admittedly, our examples are rather extreme scenarios, that are unlikely to happen. Therefore, we explore more realistic scenarios where major revoting may occur, for example due to a technical incident where voters are encouraged to revote. Another case is when a discredit of a candidate happens during the voting phase, inducing voters to flip their votes. In such cases, coercion-resistance is not fully broken but the coercer gains some non-negligible advantage due to the extra leakage of JCJ: using their a priori knowledge about the behavior of the honest voters, the coercer can use bayesian inference to decide whether it is more likely that the voter obeyed or not. In order to measure the loss of coercionresistance, we follow the approach of Kuesters et al [START_REF] Küsters | A Game-Based Definition of Coercion-Resistance and Its Applications[END_REF] and show that JCJ guarantees a lower level of coercion resistance than a more ideal protocol which only leaks ∆. All the variants and improvements on JCJ that we know of are also affected by this vulnerability. Note that our attacks assume that the coercer knows a precise description of the expected behavior of honest voters, which includes the probability of revoting. In practice, a reasonably good approximation can be obtained thanks to social media or exit polls.

A cleansing-hiding protocol. We propose a modification of JCJ, called CHide, that is not subject to this weakness. The key modification is the introduction of a cleansing hiding procedure, that replaces the original cleansing phase. More precisely, while JCJ uses plaintext equivalence tests (PET) as the main cryptographic tool, CHide relies on more complex MPC building blocks. Instead of PETs that return a bit telling whether two ciphertexts represent the same cleartext, we use a primitive Eq that returns an encrypted version of this bit, in order to hide which ballots are removed and for which reason (being a revote or having a fake credential). Then, a few logical gates primitives (e.g. Or, And, etc.) must be operated on these encrypted bits to obtain an encrypted validity bit. Finally, we use a Conditional Set Zero primitive that conditionally sets the ballots to (fixed) invalid ones, depending on their encrypted validity bit. Thanks to its cleansing hiding procedure, CHide only reveals the minimal information, namely the number ∆ of ballots that have been removed. Of course, each step comes with a zero-knowledge proof that the expected operations have been performed, so that anyone can check that the result of the election is correct.

A stronger notion of coercion-resistance. One of the probable reasons why the leakage in JCJ was not noticed before is because their definition of coercion-resistance was too weak. A flaw was already noted in [START_REF] Haines | Surveying definitions of coercion resistance[END_REF], which shows that the definition could not be realized. The fix proposed in [START_REF] Haines | Surveying definitions of coercion resistance[END_REF] repairs this but still does not consider the cases where voters may revote and hence misses the situation where JCJ leaks too much information. These definitions also model the addition of ballots with fake credentials in a contrived way in the sense that each fake ballot must be cast by a voter that sacrifices their vote.

We propose a more generic definition of coercion-resistance that accounts for revoting as well as the addition of fake ballots by authorities. We prove that CHide is coercionresistant according to this definition, and that JCJ is not, thus showing that we indeed capture the weakness of the leakage during the cleansing phase. We also prove that CHide ensures vote privacy (under weaker assumptions than for coercionresistance) as well as universal verifiability.

Summary of the contributions.

• We discover a vulnerability in the JCJ scheme, which shows that it is not perfectly coercion-resistant. • We formally measure the loss of coercion-resistance in JCJ in two realistic scenarios. • We propose CHide, a cleansing-hiding variant of JCJ, that is not subject to this problem. • We propose a new definition of coercion-resistance, which properly takes revoting and dummy ballots into account.

• We prove that CHide is coercion-resistant for this definition, while JCJ is not, thus showing the definition is precise enough to capture the leakage during cleansing. We provide the detailed specification of CHide and the full proofs in Appendix.

Related work. To provide coercion-resistance, many authors used the core idea of JCJ, that is the fake credential paradigm. Civitas [START_REF] Clarkson | Civitas: Toward a Secure Voting System[END_REF] is one of the most notable examples. It is widely considered as an important step towards a practical version of JCJ. Among other things, it introduces the notion of ballot blocks, that mitigates the quadratic cost of the cleansing phase of JCJ. This reduces somehow its coercion-resistance, which can be captured with our approach.

Other attempts were made to improve the efficiency of JCJ. In [START_REF] Spycher | A New Approach towards Coercion-Resistant Remote E-Voting in Linear Time[END_REF], Spycher et al. claim a linear time cleansing, but this comes with a deterioration of the coercion-resistance, as explained above. Later on, the same authors proposed other schemes with a clear trade-off between efficiency and coercion-resistance, thanks to anonymity sets [START_REF]Achieving Meaningful Efficiency in Coercion-Resistant, Verifiable Internet Voting[END_REF]. Other improvements include [START_REF] Araújo | A practical and secure coercionresistant scheme for remote elections[END_REF], where Araújo et al. propose a way to perform the cleansing phase in linear time, and [START_REF] Clark | Selections: Internet Voting with Over-the-Shoulder Coercion-Resistance[END_REF], where Clark and Hengartner introduce the idea of over-theshoulder coercion-resistance. Both schemes suffer from the same cleansing leakage as JCJ, as we further discuss in Section VI.

Apart from the fake credential paradigm, a natural approach is to use deniable revoting, where the coerced voter first complies with the coercer but revotes later. The ballot cast under coercion is invalidated by the subsequent revote, in a way that the coercer cannot detect. The Estonian voting system [START_REF] Madise | E-voting in Estonia 2005. The first Practice of Country-wide binding Internet Voting in the World[END_REF] completely relies on revoting to mitigate coercion, and examples of recent academic proposals based on revoting are VoteAgain by Lueks et al. [START_REF] Lueks | VoteAgain: A scalable coercion-resistant voting system[END_REF] and the scheme of Locher et al. [START_REF] Locher | Coercion-Resistant Internet Voting with Everlasting Privacy[END_REF]. This approach assumes a weaker adversary which can no longer submit ballots past a certain point.

All these schemes (including JCJ) do not address the socalled Italian attacks. The latter exist independently of the use of electronic voting and are based on the information given by the tally. They can occur when the ballots are complex enough, so that voters can "sign" them using a specific pattern on the low-stake parts of the answer. When using electronic voting, the typical way to prevent such attacks is tally hiding, i.e. to decrypt only the winners of the election, without decrypting the individual ballots. The challenge is then to preserve verifiability. Therefore tally-hiding usually relies on homomorphic encryption, or more generally on multiparty computation (MPC) techniques [START_REF] Benaloh | Shufflesum: coercion-resistant verifiable tallying for STV voting[END_REF], [START_REF] Cortier | A Toolbox for Verifiable Tally-Hiding E-Voting Systems[END_REF], [START_REF] Huber | Kryvos: Publicly tally-hiding verifiable evoting[END_REF], [START_REF] Küsters | Ordinos: A Verifiable Tally-Hiding E-Voting System[END_REF]. Designing a tally-hiding scheme is out of scope of this paper but interestingly, CHide could be easily coupled with such tally-hiding schemes, right after the cleansing phase.

Regarding formal definition of coercion-resistance, we already mentioned the recent work of Haines and Smyth [START_REF] Haines | Surveying definitions of coercion resistance[END_REF] that attempts to survey and unify the various definitions of the literature, starting with the one of JCJ where the adversary must distinguish between a real and an ideal game modeling the protocol. Another approach to define coercion-resistance is given by Küsters et al. in [START_REF] Küsters | A Game-Based Definition of Coercion-Resistance and Its Applications[END_REF]. The authors define δ-coercionresistance with two conditions: first, the coerced voter must have a strategy to meet their objective with overwhelming probability (i.e. they can actually vote for the desired candidate); second, the adversary cannot distinguish the case when the voter uses their evasion strategy from the case where the voter forwards all received messages to the adversary, with an advantage greater than δ. Our definition of coercion-resistance can be seen as an instance of [START_REF] Küsters | A Game-Based Definition of Coercion-Resistance and Its Applications[END_REF] where we compare the δcoercion-resistance of the real protocol with the δ ′ -coercionresistance of the ideal one, requiring them to be equal up to negligible difference. While [START_REF] Küsters | A Game-Based Definition of Coercion-Resistance and Its Applications[END_REF] provides a very general and abstract definition, we instead consider a fixed objective for the coerced voter (voting for a given candidate), a fixed evasion strategy (the one considered in JCJ) and a formal framework to model the trust assumptions on how messages are delivered. This part is left unspecified in [START_REF] Küsters | A Game-Based Definition of Coercion-Resistance and Its Applications[END_REF] and needs to be shaped for each protocol.

II. UNVEILING A SHORTCOMING IN JCJ

We provide a high level description of the JCJ protocol and show why coercion-resistance is undermined in case of revoting.

A. Overview of JCJ

The JCJ voting system consists of the following phases. Setup. The Election Trustees jointly generate the election public key pk T , that is sent to the public board. Then, the Registrars jointly compute one credential c for each voter. Each credential is sent privately to the voter, possibly with designated zero-knowledge proofs to guarantee voters that their credential is valid [START_REF] Jakobsson | Designated Verifier Proofs and Their Applications[END_REF]. The Registrars send to the public board the list R = {Enc(c 1 , pk T ), . . . , Enc(c n , pk T )} of encrypted credentials, in some random order. Voting. To cast a ballot, a voter encrypts their vote ν with the election public key pk T . They also encrypt their credential c and prove knowledge of ν and c. They prove that the encryptions are valid and linked, yielding a proof π. The resulting ballot b = (Enc(ν, pk T ), Enc(c, pk T ), π) is sent anonymously to the bulletin board. The voting phase is depicted in Figure 1.

Tallying. The tally phase consists of four steps.

1. Ballots with duplicated credentials are detected using Plaintext Equivalence Tests [START_REF] Jakobsson | Mix and Match: Secure Function Evaluation via Ciphertexts[END_REF] (PET). At most one ballot (typically, the last) is kept per credential. 2. The trustees mix the remaining ballots. 3. PETs are used again to remove ballots with invalid credential, i.e. whose credential is not encrypted in R. 4. Finally, each remaining ballot is decrypted so that the result can be computed. Each step includes a zero-knowledge proof that the correct operations are performed. Remark that the PETs originally used in JCJ were not verifiable when all the participants are corrupted, as stated in [START_REF] Mcmurtry | When Is a Test Not a Proof?[END_REF] which also proposes a fix.

Evading coercion: The JCJ voting system provides an evasion strategy that a voter under coercion must follow to safely disobey a coercer. If Alice is under coercion, she provides her coercer with a random (and fake) credential c ′ . At any moment, Alice can use her real credential c to cast her vote. Ballots containing c ′ will be removed at Step 3 of the tally phase. Thanks to the mixnet, the coercer is unable to learn that their ballot has been suppressed.

B. Leakage in case of revoting

For a verifiable voting system, it seems unavoidable to leak the number of received ballots in the public board. The number of valid ballots is also leaked unless more sophisticated tally methods are used such as tally-hiding schemes [START_REF] Cortier | A Toolbox for Verifiable Tally-Hiding E-Voting Systems[END_REF], [START_REF] Huber | Kryvos: Publicly tally-hiding verifiable evoting[END_REF], [START_REF] Küsters | Ordinos: A Verifiable Tally-Hiding E-Voting System[END_REF].

However, JCJ leaks much more information when revoting is allowed, namely:

• n b , the total number of received ballots;

• n v , the total number of valid (and counted) ballots;

• n r , the total number of revotes;

• the complete distribution of revotes, per (encrypted) credential (hence, for all k, the number of credentials used to revote k times). This can be exploited by a coercer to detect when a coerced voter disobeys. Indeed, there is no reason to assume that revoting is independent from the choice of candidate. On the contrary, revoting is often due to voters changing their mind between candidates, for instance due to some late announcements in the press.

An attack against coercion-resistance: We consider an extreme case, with two candidates A and B. Suppose that voters voting for A do not revote while those voting for B always revote, exactly once, and suppose that the coercer knows this. We denote r A (resp. r B ) the number of votes for A (resp. B). Due to the considered revoting behaviors, the number of revotes n r corresponds to the number of votes for B sent by the honest voters.

Assume now that Alice wants to vote for B but is instructed by her coercer to vote for A (or abstain).

• If Alice obeys, the coercer will observe r B = n r .

• If Alice disobeys and casts one ballot for B, the coercer will observe that r B = n r + 1. Hence the coercer will detect that Alice has disobeyed, which breaks coercion-resistance.

One could argue that Alice should follow a different evasion strategy and cast one ballot if she votes for A and two if she votes for B. This does not work either. Indeed, assume now that Alice wants to vote for A, but is instructed to vote for B.

• If she obeys, she gives her real credential c to her coercer.

The latter then casts exactly one ballot for B using c. • Otherwise, she provides a fake credential c ′ , that the coercer uses to vote for B. Alice then votes for A using c. In the first case, r B = n r + 1, while in the second case, r B = n r . Once again, the coercer is able to detect that Alice disobeyed and coercion-resistance is broken.

C. Discussion

1) The information available to the adversaries: To succeed in the above scenario, the adversary must know that the honest voters who revote always vote for B while the others always vote for A. In what follows, we consider less extreme scenarios when voters do not have such a deterministic revoting behavior but we still assume that the coercer knows the probability that the voters vote for A (or B) when they revote or when they do not. Such an information can be learned for instance thanks to a poll where the voters tell what was their final choice and whether they revoted. We leave as future work the quantitative evaluation of the leakage when the adversary only knows some approximation of the distribution.

2) Considering other evasion strategies: One possibility to correct JCJ's flaw is to define other evasion strategies in case of revoting. Indeed, if Alice wants to vote, JCJ's evasion strategy instructs her to do so exactly once. Consequently, if it is usual for everyone to revote several times, the leakage in JCJ allows the coercer to detect that a single person voted once without revoting, and thus that Alice disobeyed. However, it seems very hard to instruct voters to use revoting, according to a certain distribution, when they are under coercion. As illustrated in Section II-B, the natural way to proceed does not work. This is made even harder by the fact that the strategy may evolve depending on new events that could change the revoting distribution for the honest voters.

Hence we propose another option (see Section IV) that consists in reinforcing JCJ in case of revoting, such that there is no leakage besides the total number of ballots and the number of valid ballots. For our proposed protocol, we prove coercion-resistance with the original evasion strategy of JCJ. We acknowledge that the latter is not perfect; in particular, it does not allow a voter under coercion to change their mind and revote. However, modeling a wide variety of behaviors for the coerced voter is too complex and is out of the scope of this article.

3) More noise is needed: A known issue of JCJ is that fake ballots should be randomly added, in order to hide to a coercer that their ballot has been removed. Indeed, if it is usual that absolutely no ballot with a fake credential is removed at Step 3 of the tally, then a coercer, who observes that exactly one ballot is removed, would suspect that the coerced voter has disobeyed.

Hence, it is necessary that an unpredictable number of ballots is removed during the tally. In JCJ, this "noise" comes from honest voters sending dummy ballots, but this source alone may not be sufficient. A natural approach is to have the authorities add a random number of dummies. For instance, [START_REF] Spycher | A New Approach towards Coercion-Resistant Remote E-Voting in Linear Time[END_REF] uses this to mitigate a leakage during the tally. The number of fake ballots to add should however be carefully calibrated. Indeed, the more fake ballots are added, the better coercion-resistance is improved. However. adding fake ballots induces an important computation overhead at the tally phase. In a context where revoting is a well spread behavior, it could be judicious to rely on revoting, at least partially, as an additional source of noise. This is not possible in JCJ where a dummy can be distinguished from a revote, but becomes a possibility if our solution from Section IV is used.

III. THE IMPACT ON COERCION-RESISTANCE

In Section II, we explained the leakage of the JCJ protocol and we illustrate, in an extreme scenario, how this can be exploited to completely break coercion-resistance. In this section, we estimate the impact of the leakage in more realistic scenarios. For this purpose, we use the framework of [START_REF] Küsters | A Game-Based Definition of Coercion-Resistance and Its Applications[END_REF] which allows to quantify the coercion level of a voting protocol. The generic assumptions that we make are given in Section III-A; the two scenarios that we consider are detailed in Section III-B and Section III-C.

A. Quantifying coercion-resistance

We consider n V voters, among which one is under coercion. The others are supposed honest and independent. They choose a voting option among C + 1 possibilities, which includes abstention. We suppose that the choices follow a probability distribution (P 0 , . . . , P C ), where P 0 is the probability to abstain. Let α be the voting option corresponding to the intention of the coerced voter, and β be the one that is the instruction of the coercer. The coerced voter either disobeys, gives a fake credential and votes with option α (the evasion strategy does not imply any revote), or obeys and gives their real credential which the coercer uses to vote with option β. The coercer must decide whether the voter obeyed or not, given only the result.

The ideal result is R Ideal = -→ res = (res 0 , • • • , res C ), the number of voters who opted for each option. In JCJ, however, the real result R Real is -→ res, as well as, for all k, the number of voters who revoted k times. In addition, both results should also include the number of invalid ballots. However, to focus on the leakage of JCJ, we assume that a large and unpredictable number of ballots with a fake credential are cast, so that the adversary cannot gain information by observing the number of invalid ballots. This approximation is necessary to use the framework of [START_REF] Küsters | A Game-Based Definition of Coercion-Resistance and Its Applications[END_REF], which does not model the possibility to cast a ballot with an invalid credential in the ideal setting.

We now instantiate [START_REF] Küsters | A Game-Based Definition of Coercion-Resistance and Its Applications[END_REF] in our scenario. To simplify the analysis, we assume that a voter revotes at most once, so that R Real = ( -→ res, n R ), where n R is the total number of revotes. We also assume that all the parties are honest except for the coercer, and that the cryptography is perfect, so that the coercer does not learn any other information than the result. With these assumptions, we define the real and ideal games, where the behavior of the coerced voter is decided at random. The coercer wins the real (resp. ideal) game if they correctly guess the behavior of the coerced voter given the real (resp. ideal) result. For g ∈ {Real, Ideal} and for a pair (α, β), we denote W g α,β the event when the coercer wins the game, and δ g α,β = 2| Pr(W g α,β ) -1/2|. Furthermore, we consider the worst case for the voter, and analyze the quantity δ g = max α,β δ g α,β . We call δ Real (resp. δ Ideal ) the coercion level of the real (resp. ideal) game. Intuitively, it measures how much better the adversary's strategy is compared to a random guess, in a scale from 0 to 1.

We denote by Pr(R g |α) (resp. Pr(R g |β)) the probability that the result R g is obtained, assuming the voter votes for α (resp. obeys the coercer and votes for β). According to [START_REF] Küsters | A Game-Based Definition of Coercion-Resistance and Its Applications[END_REF], the best strategy for the coercer is to assume that the voter obeyed if and only if Pr(R g |β) ≥ Pr(R g |α). This gives a close formula for the coercion level which can be written as

δ g = max (α,β) R g ∈M α,β Pr(R g |β) -Pr(R g |α), (1)
where M α,β is the set of all possible results R g such that Pr(R g |β) ≥ Pr(R g |α). In Appendix D, we explain in more details how this formula can be computed. In the remainder of this section, we compare δ Real and δ Ideal in two scenarios, where external events provoke many revotes. In these scenarios, we assume that there are two candidates A and B, no blank vote, but the possibility to abstain or to revote once. Also, we consider revoting to be rare. Changing a vote once casted is something that is typically not allowed in classical paper-based elections. So, in a context where electronic voting is recent, voters will not be using this possibility. Even in a country such as Estonia, where revoting is available for internet voters since 2005, a recent study revealed a revoting rate of about 2% [START_REF] Ehin | Internet voting in Estonia 2005-2019: Evidence from eleven elections[END_REF]. We sum-up the assumptions as follows.

• The honest voters behave independently from each other;

• The honest voters may revote at most once;

• The honest voters would usually not revote, unless a specific event encourages them to do so; • The adversary knows the vote (and revote) distribution;

• The cryptography is perfect, so that we can focus on the information leaked by the protocol; • There is a large and unpredictable number of ballots sent with a fake credential, so that the adversary does not learn any information by observing the number of ballots removed because of an invalid credential; • We focus on a situation where there are only two candidates and where the adversary tries to coerce a single candidate.

B. The technical incident scenario

Although we consider natural revoting to be rare, many revotes can occur if an announcement is made about a technical incident, and encourages to revote to be on the safe side. In this case, many voters could be inclined to revote with the same voting option, which would seem harmless if they are not aware of the weaknesses of JCJ. Note that the coercer could be the source of such an announcement, and spread fake news about the necessity to revote.

In Fig. 2, we consider the situation in which a proportion of voters (that already voted) revote for the same voting option.

We plot the coercion level in both the real and ideal settings when the proportion x of revotes ranges from 0 to 1. When x = 0, both coercion levels are the same since there is no revote. However, when x = 1, there is no coercion-resistance in JCJ because the coerced voter would be the only one to cast a ballot without revoting. Note that the ideal coercion level remains constant since the overall probability to choose each voting option is unaffected by x.

C. A discredit in the press

In this scenario, we assume that during the period of the voting phase, the candidate A is discredited by an announcement in the press. As a consequence, some of the voters who initially voted for A will change their mind and revote for B.

Note that such discredits have happened in the past. For instance, Dominique Strauss-Kahn, a former IMF managing director, was highly expected to become the next French president in 2012. However, due to an accusation of sexual assault, his political party chose to support another candidate. This occurred before the time of the election, and no electronic voting was involved. But we can mention the 2022 Tory leadership election for the succession of Boris Johnson: the members could vote by Internet, and revote was initially authorized (before a security concern forced the organizers to forbid it). The duration was more than a month, which is more than enough for a discredit event to occur (even though it did not occur). First, we fix a small number of voters, so that the effect is more visible, and we study the influence of the other parameters.

In Fig. 3, we plot the real and ideal coercion levels as the proportion x of voters who change their mind from A to B ranges from 0 to 1. When x = 0, there is no difference since there is no revote. When x = 1, there is no difference either since nobody votes for A anymore, so that there is no coercionresistance in both the real and ideal games. However, a nonnegligible difference can be observed for the intermediate values of x.

In Fig. 4, we plot the real and ideal coercion levels with a fixed value of x = 0.3 (i.e. 30% of the voters who voted for A revote for B) and we let the initial proportion p in favor of A vary from 0 to 1. When p = 0, everyone votes for B so that there is no coercion-resistance. When p is large, we get close to the scenario presented in Section II-B, so that there is no coercion-resistance in the real game while the ideal game still offers some coercion-resistance.

In Fig. 5, we plot the real and ideal coercion levels with fixed x = 0.3 and p = 0.7 and we let the abstention rate P 0 range between 0 and 1. When P 0 = 0, there is no coercion-resistance because forced-abstention attacks are trivial; similarly, there is no coercion-resistance when P 0 = 1. However, a non-negligible difference can be observed for the intermediate values.

Finally, in Fig. 6, we plot the real and ideal coercion levels with fixed x = 0.3, p = 0.7 and P 0 = 0.3, for a number of uncoerced honest voters equals to 16, 32, 64, 128, 256, 512 and 1024. This shows that the difference between both coercion levels remains non-negligible even when the number of voters is large. An asymptotic analysis (see e.g. [START_REF] Mestel | How Efficient are Replay Attacks against Vote Privacy? A Formal Quantitative Analysis[END_REF], which also uses the quantitative framework of [START_REF] Küsters | A Game-Based Definition of Coercion-Resistance and Its Applications[END_REF]) reveals that the coercion level decreases in 1/ √ n V , so the level of coercion is small anyway. Fig. 3: Coercion levels as a function of the impact for 20 voters, 2 candidates, 30% abstention and a 70%-30% distribution between the candidates.

IV. CHIDE: A CLEANSING-HIDING PROTOCOL

We propose a modification of JCJ that provides full coercion-resistance. During the tally phase, the trustees perform the same tasks of cleansing, mixing and decrypting than in JCJ, but in a hidden way, so that the coercer (or anyone) does not learn how many ballots were deleted because they correspond to revotes or to invalid credentials. For this purpose, we propose a novel cleansing algorithm based on MPC primitives.

Interestingly, some alternatives to the JCJ protocol were already presented in the literature with the purpose of reducing the leaked information. For instance, Caveat coercitor [START_REF] Grewal | Caveat coercitor: Coercion-evidence in electronic voting[END_REF] proposes a protocol in which the PETs do not reveal the total number of revotes for each credential, since the process is stopped as soon as one match is found. However, this approach is not designed in order to completely remove the leakage: even if we stop as soon as a match is found, how fast we stop still gives some information about how many matches there is.

A. Cryptographic primitives

The security of the following primitives relies on the Decisional Diffie-Hellman (DDH) assumption and the Random Oracle Model.

ElGamal encryption. We use the exponential ElGamal encryption scheme on elliptic curves, which is convenient for its efficiency and its homomorphic property. Let g be a public generator and pk the public key, i.e. a group element, the discrete logarithm of which is the corresponding secret key. One encrypts m by choosing a random exponent r and computing Enc(m, pk) = (g r , g m pk r ). In general, recovering m from g m is hard so that exponential ElGamal requires m to be in a small list of valid messages, so that decryption is feasible. An important special case is when m is a bit, because this is the kind of input used by the MPC primitives we mention below. For a generic message m, we call bit-wise encryption of m the list of the encryptions of the bits of m. Zero Knowledge Proofs. We use Non-Interactive Zero Knowledge Proofs (ZKP) based on the Fiat-Shamir transformation, mostly for proving relations involving discrete logarithms, à la Chaum-Pedersen.

Distributed key generation / threshold decryption. A DKG is a protocol which allows the participants to generate an ElGamal public key pk in such a way that each participant gets a share of the secret key. The protocol also generates a public commitment to each participant's share. A threshold t is set, such that a collusion of t or less participants can not deduce any information about the secret key, or about the cleartext of any ciphertext. If t + 1 or more participants collaborate, they can combine their shares to recover the secret key. They can also run a threshold decryption protocol which allows to jointly decrypt any ciphertext without recovering the secret key nor revealing anything about their shares. The result comes with a ZKP of correct decryption that anyone can verify. An UC-secure instantiation is given in [START_REF]Universally Composable DKG with Linear Number of Exponentiations[END_REF]; a more popular DKG protocol is described in [START_REF] Gennaro | Secure Distributed Key Generation for Discrete-Log Based Cryptosystems[END_REF].

Verifiable decryption mixnets. A decryption mixnet is an MPC protocol where the participants take a list of ciphertexts and reveal the corresponding plaintexts, in an order that is unrelated to the initial order, so that it is not possible to tell which one comes from which ciphertext. We will assume that the output plaintexts are sorted in the lexicographic order. The result comes with a corresponding ZKP, for correctness. An UC-secure instantiation is given in [START_REF] Wikström | A Universally Composable Mix-Net[END_REF]; a more popular protocol is described in [START_REF]A commitment-consistent proof of a shuffle[END_REF], that is the basis of the Verificatum library [START_REF] Wikström | Open Verificatum[END_REF].

Logical operations on encrypted bits. We use MPC protocols that allow the owners of the shares to jointly perform logical operations on encrypted bits, based on their threshold decryption protocol. This is done without revealing the cleartexts to anyone, and in a verifiable manner. The main building block we use is the CGate protocol [START_REF] Schoenmakers | Practical Two-Party Computation Based on the Conditional Gate[END_REF], that allows to conditionally set an encrypted value X to (an encryption of) 0, given an encrypted bit Y . In other words, if x and y are the corresponding plaintexts with y ∈ {0, 1}, CGate(X, Y ) is a random encryption of xy. By combining this with the homomorphic property of the ElGamal encryption, one can derive a protocol for all the logical operations on bits (e.g. negation, disjunction).

More precisely, we use the And (conjunction) and the Eq (equality test) protocols. The latter is extended to bitwise encrypted data, by computing the conjunction of all the equality tests on encrypted bits. See Appendix A for more details about these MPC protocols.

Sorting encrypted data. Using the above logical operations, it is straightforward to design a comparison test Lt and a conditional swap CSwap. Therefore, it is possible to sort encrypted data, without revealing anything about the data (the conditional swap uses reencryptions, so that it is not possible to determine whether the data were swapped or not). For this purpose, we need a data-oblivious sorting algorithm, that is an algorithm whose control flow does not depend on the result of the comparisons. Since popular fast sorting algorithms, such as Quicksort, Mergesort or Heapsort, do not have this property, we use OddEvenMergeSort by Batcher [START_REF] Batcher | Sorting Networks and Their Applications[END_REF], which has a quasilinear complexity.

B. Description of the CHide protocol

Participants. The CHide protocol is similar to JCJ, and the list of participants is the same. We recall the trust assumptions on them, and note that they are the same as in JCJ. For simplicity, we assume that there is a single honest registrar. The literature following the JCJ approach contains techniques to have several registrars and appropriate trust assumptions on them [START_REF] Clarkson | Civitas: Toward a Secure Voting System[END_REF]; this is orthogonal to the present discussion.

• The public board is an append-only list of data where all the participants can write. At any time, the content of the board can be read by anyone, and the view is the same. The board is assumed to be honest; see [START_REF] Hirschi | Fixing the Achilles Heel of E-Voting: The Bulletin Board[END_REF] for a possible realization of this. • The auditors check the consistency of the board, including the validity of all the ZKPs. We assume that there is at least one honest auditor that reveals any detected problem.

• The registrar sends their voting material to the legitimate voters. It is assumed that the registrar is honest. • The n T election trustees hold the key shares and perform the cleansing and the tally. It is assumed that at most t dishonest trustees can collaborate, where t < n T is the threshold used in the DKG. • There are n V voters. Some of them may be dishonest and collude with the attacker. Honest voters may be subject to a coercion attempt by the attacker. Setup phase. During this phase, a security parameter λ is chosen. The election trustees jointly run the DKG protocol, yielding a public key pk for this security level, and a secret share for each trustee. The DKG also produces public data that is sent to the public board for verifiabilty. We denote Setup the corresponding protocol.

Registration phase. For 1 ≤ i ≤ n V , the registrar generates λ encryptions R i = (R i,1 , . . . , R i,λ ) of random bits (c i,1 , . . . , c i,λ ). These are called credentials. The registrar sends them to the board as a roster R = (R i ) 1≤i≤n V . The registrar shuffles the list of credentials and sends one of them to each voter. Just as in JCJ, we consider that the registration is perfect; but it can be augmented with DVZKPs [START_REF] Jakobsson | Designated Verifier Proofs and Their Applications[END_REF] to allow the voter to verify the validity of their credential with respect to the public roster. This simplified registration protocol assumes a single honest registrar. For several registrars, the (encrypted) bits of the credentials can be jointly generated, and the credentials can be sent to the voters without revealing them to the registrars, as long as one of them is honest [START_REF] Clarkson | Civitas: Toward a Secure Voting System[END_REF]. The registrars can also jointly prove that the credentials are indeed encrypted bit by bit, and thus that the public roster is well-formed (see e.g. [START_REF] Boneh | Zero-Knowledge Proofs on Secret-Shared Data via Fully Linear PCPs[END_REF]).

Voting phase. In order to cast a vote for the option ν (encoded as a group element), a voter computes C 1 = Enc(ν, pk) and C 2 = (Enc(c 1 , pk), . . . , Enc(c λ , pk)), where c = (c 1 , . . . , c λ ) is their credential. The neutral element 1 (the encoding g 0 of the zero bit) should not represent any voting option as it will be used to encode invalid ballots. The voter also produces a ZKP π 1 that proves the knowledge of ν and c j for all j. To ensure a strong Fiat-Shamir transformation [START_REF] Bernhard | How Not to Prove Yourself: Pitfalls of the Fiat-Shamir Heuristic and Applications to Helios[END_REF], the computation of the challenge from the commitment of the Σ-protocol must include all public informations in the hash, such as g, pk, C 1 and C 2 . Finally, a ZKP π 2 that ν is a valid voting option and that c 1 , . . . , c λ are bits must be added to prevent forced-abstention attacks which use writeins. The ballot (C 1 , C 2 , π 1 , π 2 ) = Vote pk (c, ν) is sent to the public board, using an anonymous channel. The voters check that their ballot is present on the board; this defines the verification step Check. The auditors verify that the ZKPs are valid and that there is no other ballot on the board with the same (C 1 , C 2 ); this defines the verification isVal.

Cleansing and tallying phase. Just as in JCJ, the election trustees keep only one ballot per valid credential and remove all the other ones. However, they do so in an oblivious way, by replacing the voting option of an invalid ballot by an encryption of 0, which represents an invalid voting option. For this purpose, the trustees first compute an encrypted validity boolean for each ballot. Using the toolbox from [START_REF] Cortier | A Toolbox for Verifiable Tally-Hiding E-Voting Systems[END_REF], we could simply propose an MPC variant of JCJ, with a quadratic number of comparisons, as in JCJ. We instead propose a quasi linear approach, which relies on sorting.

The idea is to create a list of pairs of encrypted data (V i , K i ) 1≤i≤n b +n V , both for ballots posted to the board and credentials from the roster. For ballots, V i contains the voting option (the C 1 part), and

K i = (K ⊥ i , K ⊤ i )
is formed of the encrypted order of appearance on the public board (i.e., K ⊥ i is a bitwise-encrypted integer between 0 and n B -1), and from the encrypted credential (i.e., K ⊤ i is the C 2 part). This step can be performed by anyone using a fixed randomness for K ⊥ i (e.g. using the random 0) and is publicly verifiable. For entries coming from the roster, V i is the encryption of an invalid option, and

K i = (K ⊥ i , K ⊤ i )
contains the encrypted integer n B in the first part, and the credential in the second part. Again, this step is performed using a fixed randomness for V i and K ⊥ i . Then the talliers use the toolbox from [START_REF] Cortier | A Toolbox for Verifiable Tally-Hiding E-Voting Systems[END_REF] to sort this list in MPC, in quasi linear time. They use the following order:

• first sort according to K ⊤ i in increasing order. The effect is to group the ballots by credentials; • for equal K ⊤ i (i.e. for equal credentials), sort in increasing order of K ⊥ i . The effect is to position the entry coming

+ n V ) log(n B + n V ) 2 (log n B + λ)n T ) Data exchanged O(λ(n B + n V ) log(n B + n V ) 2 (log n B + λ)n T )
from the roster at the end of the group and the valid ballot (if there is one) just before it. After this step, an entry is valid iff 1) its K ⊤ i part is the same as the one from its successor in the sorted list; and 2) the K ⊥ i part of its successor encodes n B . These tests can be efficiently implemented with the MPC toolbox and we need only a linear number of such tests, yielding an overall procedure in quasi linear time.

The P tally protocol is more precisely presented as follows. A more detailed description is available in Appendix A.

1. Discard all the ballots marked as invalid by the audit procedure. Let

(C i 1 , C i 2 ) n B
i=1 be the remaining ballots, without the ZKPs. We denote m = ⌈log n B ⌉ + 1.

For all

1 ≤ k ≤ n B , set V k = C k 1 and K k = U k-1 ||C k 2
, where U k-1 is a bit-wise encryption of k -1 over m bits (least significant bit first), using the null randomness.

For all n

B + 1 ≤ k ≤ n B + n V , set K k = U n B ||R k-n B
and V k is the encryption of 0, using the null randomness. 4. Sort the (V k , K k ) using the keys K k , in increasing order.

This produces a result

(V ′ k , K ′ k ) n B +n V k=1 and a transcript Π Sort . 5. For all 1 ≤ k < n B + n V , compute D k = Eq(K ′ ⊤ k , K ′ ⊤ k+1 )
, where K ′ ⊤ k refers to the λ most significant bits of K ′ k . This produces the transcript Π Eq k,1 .

6. For all 1 ≤ k < n B + n V , compute F k = Eq(K ′ ⊥ k+1 , U n B )
, where K ′ ⊥ k+1 refers to the m least significant bits of K ′ k+1 . This produces the transcript

Π Eq k,2 . 7. For all 1 ≤ k < n B + n V , replace V ′ k by CGate(V ′ k , And(D k , F k )). 8.
Apply the decryption mixnet protocol on the

(V ′ k ) n B +n V -1 k=1
. This produces the result of the election as well as a verification transcript Π Mixnet . Each step produces a transcript, published on the board, and verified by the auditors.

Evading coercion. We provide the same evasion strategy as in JCJ, which consists of giving a fake credential to the coercer and to vote (once, if the voter wants to) with the real credential.

Assumptions on the communication channels. As in the original JCJ protocol, the communications between the voters and the registrars must be untapable, and the communication between the voters and the public board must be anonymous.

C. Complexity and efficiency considerations

On the tallier side, CHide has a quasi-linear complexity in n B + n V , both in terms of computational cost and in term of communications. Due to the fact that the encrypted credentials require λ ciphertexts instead of a single one, a factor λ occurs multiplicatively in these complexities. We give the precise asymptotic complexities in Table I. In this table, for the computational cost, we count the number of exponentiations, which is the dominant part, and for the communications, we give the total volume of the messages exchanged (in bits, hence the additional λ factor for the communications, to take into account the bit-size of the group elements and of the exponents). Note that, in our case, this value is the same as the size of the transcript that an external verifier would need to download in order to verify the result. For the voters, forming a ballot has a complexity of O(λ) exponentiations for the encryptions and the zero-knowledge proofs, due, again, to the credential that is encrypted bit by bit.

Let us now consider the practical cost for non-asymptotic parameters. For this purpose, we fix a number of n T = 3 talliers with a threshold t = 2, a security parameter of λ = 128 and a number of n C = 2 voting options. We can estimate the running times, based on an approximation of 5,000 exponentiations per second on the client side, and 10,000 per second on the server side. For the voters, the time for preparing the ballot remains in the realm of the second, which is satisfactory. For the talliers, as expected from the complexity, the time grows a bit faster than linearly with the number of voters, and we estimate that for an election of 1000 voters, the tally would require 2.8 days of computation on a single core, and can easily be parallelized on a few dozens of cores to turn this into a couple of hours. The amount of data to be exchanged would be around 39 GB. Assuming a 100 Mbit/s connection between the trustees, this would take about one hour. Furthermore, the CHide MPC protocol has only few strong synchronization points, so that communications and computations can be done in parallel. In Table II, we give estimates of the number of exponentiations and of the total volume exchanged for both JCJ and CHide, for various number of voters. This allows to check the quasi-linear cost of CHide.

Table II also illustrates how CHide compares to JCJ. This confirms that the bit-wise encryption of the credential induces a heavy cost for CHide, that is balanced for large elections by the fact that JCJ has a quadratic compexity. The cross-over point is between 100,000 and 1,000,000 voters, according to our estimates. For such very large elections, while the cost is high, this is not out of reach since the computations are highly parallelizable and hence could be conducted within one day on a large cluster.

Of course, CHide remains slower than the variants of JCJ that have a linear complexity, like [START_REF] Araújo | Remote Electronic Voting Can Be Efficient, Verifiable and Coercion-Resistant[END_REF]. However, these other schemes also suffer from some leakage similar to JCJ's. We discuss these in Section VI.

Finally, we mention that a recent work by Arahna et al. [START_REF] Aranha | Faster coercion-resistant e-voting by encrypted sorting[END_REF] proposes a variant of CHide that improves its efficiency.

V. DEFINING COERCION-RESISTANCE

We guess that one of the reasons why the flaw was not discovered in the original proposition of the JCJ protocol is that the definition of coercion-resistance itself was flawed, in the sense that no scheme can be proved secure w.r.t. this definition. We then introduce our own definition, that is used to analyse the security of CHide.

A. Voting system

A voting system is a tuple of eight algorithms or protocols P Setup , register, Vote, Check, isVal, Fakecred, P tally , Verify such that:

• P Setup (λ, n T , t) is a protocol run by n T authorities for the security parameter λ and the threshold t. It computes the public key pk, as well as the secret and public shares (s i , h i ) for each authority, using a DKG. • register(λ, pk, n V ) generates a private credential c i for each voter ∈ [1, n V ]. It also returns some public information R that contains the public part of the credentials, and any necessary transcript for proving their validity. • The algorithm Vote pk (c, ν) takes as input the public key of the election pk, a credential c, and a vote ν, and returns a ballot. The public key is often omitted for simplicity. • The algorithm Check(BB , pk, b, c, ν) takes the bulletin board BB , the public key, a ballot b, a private credential c and a voting option ν. It is run by the voters to check that their ballot has been added to the public board. • The algorithm isVal(pk, b, BB ) takes as input the public key, a ballot and the ballot box. It outputs a bit which states whether the ballot is valid w.r.t. BB . • Fakecred(c) takes a credential and returns a fake one c. • P tally (BB , R, pk, {h i , s i }, t) is a protocol run by the authorities that possess the secret shares {s i } with public commitments {h i }. It takes as input a list of ballots BB , the public roster R, the public key pk, the threshold t and returns the result X of the election together with a proof Π. • Verify(BB , Π, res) takes as input a ballot box BB , a transcript Π and a result res. It outputs a bit which states whether the result is valid with respect to BB .

B. The original definition of JCJ

The intuition of the JCJ definition of coercion-resistance is that an adversary must not guess whether a coerced voter obeyed or evaded coercion. When the voter obeys (b = 1 in the definition), they give their real credential and abstain from doing any other action. Note that a coercer may ask the voter to cast some specific vote or to perform some specific computations, but this is not considered in the definition as the adversary might as well do it themself, with the given credential. When the voter evades (b = 0 in the definition), they give a fake credential and cast a single vote for the desired voting option (or abstain, depending on their personal choice).

This yields the game Real CR JCJ presented in Algorithm 1. Voting choices are represented as integers between 1 and n C , and ϕ represents the choice to abstain. During this game, the adversary selects the set of corrupted voters. It is given the corresponding private credentials as well as all the public information R (i.e. the encrypted credentials in the JCJ protocol). It then chooses (j, α), where j denotes the voter under coercion and α their desired voting option. The evasion strategy is modeled in lines 11 and 13: when the voter disobeys, they create a fake credential and cast a vote for α (or abstain if α = ϕ). Otherwise, they give their real credential.

Honest voters vote according to a distribution which depends on the number of options n C and returns a value that may be:

• any valid vote ν ∈ [1, n C ];
• ϕ, which represents abstention; • λ, which represents casting a vote with a fake credential.

We extend the Vote function to votes equal to λ as follows.

Vote pk (c, λ) = Vote pk (c, ν),

where c = Fakecred(c) and ν is sampled from [1, n C ].
It is worth noting that the advantage of an adversary in game Real CR JCJ will always be non negligible since one can compare the result of the tally with the expected result, given the distribution D of the voting intentions. For example, if the adversary wants to cast a vote for a very unpopular candidate, they may observe cases where the latter does not get a single vote in the result, which is a clear indication that the coerced voter disobeyed. Hence, the JCJ definition compares the advantage of an adversary in game Real CR JCJ with the one in an ideal game Ideal CR JCJ , where there is no other information than what is unavoidably leaked, that is, the result. The game Ideal CR JCJ is presented in Algorithm 2. Compared to the original definition, we present a slightly modified version that reasons on the clear votes only. This simplifies the understanding by focusing on the information given to the adversary. All our claims and remarks hold on the original definition as well.

Definition 1 (adapted from [START_REF] Juels | Coercion-resistant electronic elections[END_REF]). A voting system is JCJcoercion resistant if for all PPT adversary A, for all parame- ters n T , t, n V , n A , n C , and for all distributions D, there exists a PPT adversary B and a negligible function µ such that

Algorithm 1: Real CR JCJ Require: A, λ, n T , t, n V , n A , n C , D 1 BB ←-∅ 2 pk, (s i , h i ) n T i=1 ←-Setup A (λ, n T , t) 3 A ←-A() 4 {c i ; i ∈ [1, n V ]}, R ←-register(λ, pk, n V ) 5 (j, α) ←-A({c i ; i ∈ V }, R) 6 if |A| ̸ = n A ∨ j ̸ ∈ [1, n V ]\A ∨ α ̸ ∈ [1, n C ] {ϕ} then 7 Return 0 8 b $ ←-{0, 1} 9 c ←-c j if b == 0 then c ←-Fakecred(c j ) if α ̸ = ϕ then BB ←-BB {Vote pk (c j , α)} for i ∈ [1, n V ]\(A {j}) do ν i ←-D n C () if ν i ̸ = ϕ then BB ←-BB {Vote pk (c i , ν i )} BB ←-BB A(c, BB ) X, Π ←-P A tally (BB , R, pk, {h i , s i }, t) b ′ ←-A() Return 1 if b ′ == b else 0 Algorithm 2: Ideal CR JCJ Require: A, λ, n V , n A , n C , D 1 D ←-∅ 2 3 A ←-A(λ) 4 5 (j, α) ←-A() 6 if |A| ̸ = n A ∨ j ̸ ∈ [1, n V ]\A ∨ α ̸ ∈ [1, n C ] {ϕ} then 7 Return 0 8 b $ ←-{0, 1} 9
10 if b == 0 ∧ α ̸ = ϕ then 11 D ←-D {α} 12 13
14 for i ∈ [1, n V ]\(A {j}) do 15 ν i ←-D n C () 16 if ν i ̸ ∈ {ϕ, λ} then 17 D ←-D {ν i } 18 (ν i ) i∈A , β ←-A() 19 if b == 1 ∧ β ∈ [1, n C ] then 20 D ←-D {β} 21 X ←-result(D {ν i | i ∈ A, ν i ∈ [1, n C ]}) 22 b ′ ←-A(X) 23 Return 1 if b ′ == b else 0
| Pr(Ideal CR JCJ (B, λ, n V , n A , n C , D) = 1) -Pr(Real CR JCJ (A, λ, n T , t, n V , n A , n C , D) = 1)| ≤ µ(λ) .
As noted in [START_REF] Haines | Surveying definitions of coercion resistance[END_REF], this definition cannot be realized by a scheme which uses a public board. Indeed, in the real game, the adversary observes the length n B of the board which corresponds to the total number of ballots cast by noncorrupted voters. Then the adversary learns the result and in particular its size n v , that is the number of valid ballots counted. Hence the total number ∆ = n B -n v of ballots discarded can be deduced, which is not available in the ideal game Ideal CR JCJ . The value of ∆ can be compared with its expected number, according to the distribution D. Since there is an additional ballot discarded (the one of the coercer) when the voter evades coercion, the adversary has a non-negligible advantage in the real game. For instance, if D is such that no voters cast a ballot with an invalid credential, either n B = n v , which means that the adversary's ballot has been counted, or n B = n v + 1, meaning that the adversary's ballot has been discarded and that the voter has disobeyed. Of course, the same issue applies to the JCJ definition as stated in [START_REF] Juels | Coercion-resistant electronic elections[END_REF].

The authors of [START_REF] Haines | Surveying definitions of coercion resistance[END_REF] proposed a patch to the issue they discovered: the length of the board should be given to the adversary in the ideal game as well. Intuitively, this corresponds to simply rewriting line 18 of Algorithm 2 as (ν i ) i∈V , α ←-A(|D|). However, this still does not allow to detect the leakage of the JCJ protocol during the tally. Indeed, the distribution D fails to model several aspects:

• First, the addition of a ballot with an invalid credential only happens when a honest voter sacrifices their own vote. This is unlikely in practice, and does not model ballots sent by non-eligible voters (for instance, by the authorities). • Second, revoting is not considered in D, which explains why the leakage of the JCJ protocol was not detected.

A final remark about the definition of JCJ concerns its underlying trust assumptions. For clarity, we recall them here. First of all, it is assumed that all the registrars are honest and that the adversary is inactive during the registration phase (or, alternatively, the registration is untapable). Second, the adversary can only corrupt a minority of decryption authorities. Also, ballots are cast through anonymous channels. Finally, the bulletin board is honest.

C. The quantitative definition of KTV

Apart from the definition of JCJ, there are other definitions in the literature (see [START_REF] Haines | Surveying definitions of coercion resistance[END_REF] for a survey). The most prominent one is the quantitative definition of [START_REF] Küsters | A Game-Based Definition of Coercion-Resistance and Its Applications[END_REF] (KTV), where the notion of δ-coercion-resistance comes with two conditions: first, the coerced voter must have a strategy to meet their objective with overwhelming probability; second, the adversary cannot decide, with an advantage greater than δ, whether the voter used this strategy or forwarded all received messages (including their credential).

The KTV definition is abstract. To use it, it is necessary to model the voting protocol, its participants and the evasion strategy. In addition, it does not say much about how ballots sent with an invalid credential should be handled since the honest participants are assumed to vote following a fixed distribution of valid voting options. Finally, it does not tell if a specific δ is acceptable or not. Our definition can be seen as an instance of KTV, where δ is shown to be minimal, that is, not greater than that of an ideal protocol.

D. Our definition of coercion-resistance

If we compare the advantage of the adversary in the real game with its advantage in the ideal one, we need to cover a large family of vote distributions. Otherwise, we may miss security flaws. In particular, we need to cover cases explicitly planned by the protocol such as revote and addition of ballots with fake credentials. Therefore, given a set S of unique identifiers and the number n C of voting options (excluding abstention), we consider a distribution B(S, n C ) of sequences of pairs of the form (j, ν) where ν ∈ [1, n c ] represents a vote and j represents either a valid voter (when j ∈ S) or a fake voter, with a fake credential. Typically, if A is the set of corrupted voters, S = [1, n V ]\A. To avoid collisions with identifiers which may be in A, we consider that any i ̸ ∈ S holds a negative value. The distribution B captures the abstention of a voter i with the absence of a couple of the form (i, * ). It models both revoting and the addition of fake ballots, typically by authorities:

• revoting is reflected in B by the fact that a voter may appear several times in the same sequence; • fake ballots are modeled by pairs (j, ν) where j / ∈ S. They may be added by authorities or voters. Note that B also models the case of a revote with a fake credential. For example, in the sequence (1, 1), (2, 1), (1, 2), (-1, 2), (1, 1) with n V = 3, we have three voters V 1 , V 2 and V 3 . V 1 first votes 1, V 2 votes 1, then V 1 revotes for 2, then a fake vote for 2 is added, then V 1 changes back her vote to 1. V 3 simply chooses to abstain.

Our Real CR game, given in Algorithm 3, is similar to Real CR JCJ . Votes are drawn according to B([1, n V ]\A, n C ), yielding a sequence B. It typically contains pairs (i, ν) with i < 0, which corresponds to the addition of ballots with fake credentials. For such a pair, we therefore generate a fake credential at lines 11-12. Just as in the definition of JCJ, the adversary must guess a bit b. If b = 1, the coerced voter j obeys, hence any vote from j is removed from B and the real credential is provided to the adversary. If b = 0, the voter follows the evasion strategy, namely they cast one vote for β (if β ̸ = ϕ) and provides a fake credential. Hence the votes from j in B are replaced by a single vote for β (if β ̸ = ϕ). Then ballots are added according to B. They correspond either to real or fake votes (or revotes). Compared to the original JCJ definition, we also slightly improve the power of the adversary by letting them observe the board after each vote and add ballots if they want to, which better reflects the reality.

Again, the advantage of the adversary in the real game is compared with its advantage in an ideal game Ideal CR , where the adversary can only observe the number of ballots and the result (see Algorithm 4). We assume a function cleanse that removes votes from invalid voters j / ∈ [1, n V ] and that takes care of revotes according to the policy (typically, the last vote is kept). The function result, given a set of valid votes, returns the result of the election. Definition 2. A voting system is coercion resistant if for all PPT adversary A, for all parameters n T , t, n V , n A , n C , and for all distribution B, there exists a PPT adversary B and a negligible function µ such that

| Pr(Ideal CR (B, λ, n V , n A , n C , B) = 1) -Pr(Real CR (A, λ, n T , t, n V , n A , n C , B) = 1)| ≤ µ(λ) .
The main difference between our definition and the original one is that we consider a larger family of distributions, which allows to analyze a protocol in the context of revotes and fake ballots.

Another difference is that the adversary shall not gain any advantage for any distribution B, while the JCJ definition defines coercion-resistance with respect to a particular distribution. This is preferable since a protocol should be as secure as the ideal one, whatever the considered distribution. It is counter-intuitive to design a cryptographic protocol that resists only for particular distributions. Of course, it makes sense to analyze the exact advantage in the ideal game for a particular distribution, and devise whether voters are reasonably protected in that case of not. But the cryptographic protocol itself should be as solid as the ideal one nevertheless.

E. CHide is coercion-resistant

Thanks to our cleansing procedure, we show that CHide achieves coercion-resistance. This is stated in Theorem 1, proven in Appendix C-B. In this theorem, we suppose secure DKG and Mixnet protocols in the SUC security framework [START_REF] Canetti | A Simpler Variant of Universally Composable Security for Standard Multiparty Computation[END_REF]. Simply speaking, it is a Universally Composable security framework which is suitable for MPC protocols. Examples of UC-secure DKG and decryption mixnet can be found in [START_REF] Wikström | A Universally Composable Mix-Net[END_REF], [START_REF]Universally Composable DKG with Linear Number of Exponentiations[END_REF].

We mention that we also prove privacy and verifiability in Appendices C-C and C-D, using a similar approach. Theorem 1. Under the DDH assumption, assuming SUCsecure DKG and Mixnet protocols and in the Programmable Random Oracle Model, CHide is coercion-resistant.

Algorithm 3: Real CR Require: A, λ, n T , t, n V , n A , n C , B 1 BB ←-∅ 2 pk, (s i , h i ) n T i=1 ←-P A Setup (λ, n T , t) (* run the DKG *) 3 {c i ; i ∈ [1, n V ]}, R ←-register(λ, pk, n V ) 4 A ←-A(R) (* corrupt voters *) 5 (j, α) ←-A({c i ; i ∈ A})
6 (* coerce a voter j who has the intention α *)

7 if |A| ̸ = n A ∨ j ̸ ∈ [1, n V ]\A ∨ α ̸ ∈ [1, n C ] {ϕ} then 8 Return 0 9 B ←-B([1, n V ]\A, n C ) 10 (* samples a sequence of pairs (i, ν i ) with i ∈ ([1, n V ]\A) {n ∈ Z | n < 0} and ν i ∈ [1, n C ] *) 11 for (i, * ) ∈ B, i / ∈ [1, n V ] do 12 c i ←-Fakecred() 13
(* this captures ballots sent with invalid creds *)

14 b $ ←-{0, 1} 15 c ←-c j 16 if b == 1 then 17 Remove all (j, * ) ∈ B 18 else 19
Remove all (j, * ) ∈ B but the last, which is replaced by (j, α) if α ̸ = ϕ and removed otherwise

20 c ←-Fakecred(c j ) 21 A(c) (* A learns c *) 22 for (i, ν i ) ∈ B (in this order) do 23 M ←-A(BB ) (* cast ballots *) 24 BB ←-BB {m ∈ M | isVal(pk, m, BB ) = 1} 25 BB ← BB {Vote pk (c i , ν i )} 26 M ←-A(BB , "last honest ballot sent") 27 BB ←-BB {m ∈ M | isVal(pk, m, BB ) = 1} 28 X, Π ← P A tally (BB , R, pk, {h i , s i }, t) 29 b ′ ←-A() 30 Return 1 if b ′ == b else 0 Algorithm 4: Ideal CR Require: A, λ, n V , n A , n C , B 1 2 3 4 A ←-A(λ) (* corrupt voters *) 5 (j, α) ←-A() 6
(* coerce a voter j who has the intention α *) We can check that JCJ is not coercion-resistant according to our definition. This is due to the leakage during the cleansing phase, as explained in Section II-B.

7 if |A| ̸ = n A ∨ j ̸ ∈ [1, n V ]\A ∨α ̸ ∈ [1, n C ] {ϕ} then 8 Return 0 9 B ←-B([1, n V ]\A, n C ) 10 (* samples a sequence of pairs (i, ν i ) with i ∈ ([1, n V ]\A) {n ∈ Z | n < 0} and ν i ∈ [1, n C ] *)
(ν i ) i∈A , β ←-A(|B|) 23 if (b == 1) ∧ (β ∈ [1, n C ]) then 24 B ←-B {(j, β)} 25 B ←-B {(i, ν i ) | i ∈ A, ν i ∈ [1, n C ]} 26
Proposition 1. The JCJ protocol is not coercion-resistant.

VI. LEAKAGE OF JCJ VARIANTS

The JCJ scheme is not the only one affected by our finding. In fact, the whole JCJ family suffers from a similar leakage. In this section, we explain how the other JCJ-like schemes are affected, and whether an MPC version of their protocol can be used to address the leakage while preserving their efficiency.

We start with the scheme presented by Araújo, Foulle and Traoré (AFT) in [START_REF] Araújo | A practical and secure coercionresistant scheme for remote elections[END_REF]. Its main feature is that it has a linear time complexity for the cleansing and tallying phases. While they use different cryptographic primitives from JCJ, their scheme has a similar structure: voters are given credentials to vote with, and can provide a fake credential to a coercer. Assuming that the cryptography is perfect, we can analyze their leakage and compare it with that of JCJ.

During the tally, both the number of duplicates and the number of ballots with an invalid credential are revealed. However, it is possible to deduce, by observing the board, how many revotes each ballot has. This is because each ballot is attached with a public (and deterministic) commitment of the credential, so that anyone can detect that two ballots use the same credential. In JCJ, this information is only available during the tally, when it is no longer possible for the adversary to submit a ballot (also, the ballots are shuffled beforehand).

Hence, the AFT suffers from the same leakage as in JCJ, but it might be easier to exploit since the adversary can use this information to cast their ballots in some specific way.

By contrast with the JCJ protocol, it is not easy to adapt the AFT scheme in MPC while preserving its time complexity. Indeed, one of the key feature is that anyone can detect that two ballots use the same credential, so that the duplicated credentials can be removed in linear time thanks to a hash map. In MPC, we cannot think of a way to adapt this strategy while preserving the linear time complexity: the most natural way would take a quadratic complexity, and a more advanced strategy, based on sorting, would achieve a complexity similar to that of CHide. Note that the above remarks about the leakage and the difficulty to adapt the scheme in MPC are also valid for the subsequent schemes such as [START_REF] Araújo | Towards Practical and Secure Coercion-Resistant Electronic Elections[END_REF] and [START_REF] Araújo | Remote Electronic Voting Can Be Efficient, Verifiable and Coercion-Resistant[END_REF].

A similar situation is encountered when analyzing the proposal of Spycher et al. [START_REF] Spycher | A New Approach towards Coercion-Resistant Remote E-Voting in Linear Time[END_REF]. First, the revotes are taken care of during a phase which also relies on detecting the duplicated values from a list of cleartexts. Second, the invalid credentials are eliminated thanks to PETs; however, this only requires one PET per ballot because each ballot indicates to which encrypted credential it must be compared with. Just as for the AFT protocol, this scheme leaks the same information as JCJ (namely the number of revotes per credential), but also leaks how many ballots pretend to be from each credential. As acknowledged by the authors, this extra information deteriorates the coercion-resistance of the scheme when compared to that of JCJ. Note that adapting this solution in MPC would also be difficult: first, we have the same difficulty as when trying to adapt the solution of AFT; second, we do not see how to eliminate the invalid credentials in linear time without leaking the number of ballots attached to each credential. Finally, another interesting example is Civitas [START_REF] Clarkson | Civitas: Toward a Secure Voting System[END_REF], a scheme considered as an implementation of JCJ. Among the few differences that could have an impact, we concentrate on the leakage during the cleansing and tallying phases. Interestingly, Civitas actually leaks more information than JCJ. First, it provides the same leakage as the AFT protocol: the number of revotes for each ballot can be directly deduced from the board. Furthermore, in order to reduce the quadratic number of PETs, Civitas proposes to group voters by blocks: each credential is publicly assigned to one block, and the voter indicates their block in clear when casting their ballot. Compared to JCJ, the adversary still learns how many revotes each ballot has and how many invalid ballots there is, but also has access to this information block by block. Similarly to the AFT scheme, it is difficult to adapt Civitas' approach in MPC without leaking any side-channel information. Indeed, if we group the voters by blocks, then the number of ballots that each block has is a side-channel information (if the coerced voter evades coercion, the corresponding block has one extra ballot). Hence, using this approach would either require to cast a large number of dummies for each block (which would undermine the efficiency), or to use an advanced MPC strategy to hide how many ballots each block has. Once again, we cannot think of a way to achieve this in linear time.

While JCJ does not satisfy our definition of coercionresistance, it does provide a certain level of security. We could identify the exact nature of the leakage in JCJ and propose an alternative (weaker) definition of coercion-resistance that is achieved by JCJ. Beyond giving a concrete description of the leakage, this would show that there are several shades of coercion-resistance depending on the leakage which is considered acceptable. More generally, for any variant of JCJ in the literature, if the leakage during the cleansing is different from the one in JCJ, our definition of coercion-resistance could (in principle) be adapted to capture this. Still, CHide shows that a better notion of coercion-resistance can be achieved.

APPENDIX A FULL SPECIFICATION OF P T A L L Y

In this appendix, we give every details that are necessary to understand the tally protocol. First of all, the CGate protocol [START_REF] Schoenmakers | Practical Two-Party Computation Based on the Conditional Gate[END_REF], built upon the exponential ElGamal encryption system and its threshold decryption protocol, is given in Algorithm 5, where we used the adapted version of [START_REF]A toolbox for verifiable tally-hiding e-voting systems (long version)[END_REF] (which is the full version of [START_REF] Cortier | A Toolbox for Verifiable Tally-Hiding E-Voting Systems[END_REF]), for which there is a security proof in the SUC framework. The CGate protocol enables to perform multiple functionalities, such as computing a logical conjunction And of two encrypted bits and conditionally set an encrypted value to 0, given an encrypted boolean (we denote this functionality CSZ). Note that in addition to the output Z, a transcript Π CGate is obtained, which allows to verify that the participants performed the correct operations on X and Y , and that Z is indeed an encryption of xy.

Algorithm 5: CGate (see [START_REF] Cortier | A Toolbox for Verifiable Tally-Hiding E-Voting Systems[END_REF]). The total cost is 33n T exponentiations per participants, and a transcript size of 34n T elements of 256 bits.

Require: G, a group of prime order q and public generator g pk, an exponential ElGamal public key, whose shares are distributed among the n T participants h ∈ G, a public element independent from pk X, an encryption of some x ∈ Z q Y , an encryption of y ∈ {0, 1} Ensure: Z, a random encryption of xy

1 Y 0 ←-E -1 Y 2 ; X 0 ←-X 2 for i = 1 to n T , for the authority i, do 3 (u, v) ←-X i-1 4 r 1 , r 2 $ ← Z q ; s $ ← {-1, 1} 5 X i ←-(u s g r1 , v s pk r1 ); e ←-hr1 6 Y i ←-ReEnc pk (Y s i-1 , r 2 ) 7
Broadcast X i , e, Y i and a ZKP π i that they are well formed

8 We denote Π = (X n T , Y n T , π n T )|| • • • ||(X 1 , Y 1 , π 1 )
9 Each authority verifies the proof of the other authorities They collectively rerandomize X n T and Y n T into X ′ and Y ′ , which produces a transcript Π ReEnc They collectively decrypt Y ′ into y n T , which produces a transcript Π Dec . They output Z = (XX ′yn T )

1 2 . The verification transcript is Π CGate = (y n T , Π Dec )||(X ′ , Y ′ , Π ReEnc )||Π
As shown in [START_REF] Schoenmakers | Practical Two-Party Computation Based on the Conditional Gate[END_REF], due to the homomorphic property of the ElGamal cryptosystem, we can readily deduce protocols for computing a disjunction (see Algorithm 6), and an equality test (Algorithm 7) between two bits. In addition, the logical negation of an encrypted bit B Not(B) can be obtained without interaction by computing Enc(1)/B (for this purpose, a fixed encryption of 1 with a trivial randomness can be used).

Algorithm 6: Or

Require: X, Y such that X (resp. Y ) is an encryption of x (resp. y), with x, y ∈ {0, 1} Ensure: Z = Enc(z), with z = 1 if x = 1 or y = 1; 0 otherwise 1 Return XY /CGate(X, Y ) and Π CGate Algorithm 7: Eq Require: X, Y such that X (resp. Y ) is an encryption of x (resp. y), with x, y ∈ {0, 1} Ensure:

Z = Enc(z), with z = 1 if x = y; 0 otherwise 1 Return Enc(1)CGate(X, Y ) 2 /(XY ) and Π Eq = Π CGate
Now, since the logical disjunction (resp. conjunction) operator is associative, we immediately deduce a protocol to extend this binary operator into a n-ary operator (by abuse of notation, we still denote it Or; resp. And). By using a binary tree structure, the protocol

Or(B 1 , • • • , B n ) (resp. And(B 1 , • • • , B n ))
; which returns an encryption of 1 if one (resp. all) of the inputs is an encryption of 1, and 0 otherwise; can be performed in O(log n) rounds and a total of n -1 instances of CGate.

We can also extend the Eq protocol to bitwise encrypted integers (see Algorithm 8). By combining logical operations, it is straightforward to build a comparison protocol Lt (see Algorithm 9 from [START_REF] Cortier | A Toolbox for Verifiable Tally-Hiding E-Voting Systems[END_REF]) which, given two bitwise encryptions of the integers x and y, returns an encryption of 1 if x < y and an encryption of 0 otherwise. We also give the conditional swap protocol in Algorithm 10. By combining those two protocols, we can readily adapt the OddEvenMergeSort algorithm in MPC (see Algorithm 11, adapted from [27, Section 5.2.2, Algorithm M]). This sorting algorithm requires approximately 1 4 n log(n) 2 comparisons and conditional swaps, where n is the number of elements

APPENDIX B THE SUC SECURITY OF P T A L L Y

In our security proofs, we use the SUC framework [START_REF] Canetti | A Simpler Variant of Universally Composable Security for Standard Multiparty Computation[END_REF] which is a simpler variant of the Universally Composable (UC) framework [START_REF] Canetti | Universally Composable Security: A New Paradigm for Cryptographic Protocols[END_REF]. In this appendix, we give a brief introduction to the SUC framework and prove that P tally is SUC-secure.

A. Definitions, notations and composition

In the SUC framework, a protocol is a collection of participants, which are modeled as Interactive Turing Machines (ITM). As the name implies, the ITMs communicate with each others using common tapes. An execution of a protocol is called a process, during which the participants are executed concurrently. In turn, a process can invoke sub-processes, but with the same participants. Some of the participants may be impersonated by an adversary A which also has a full control over the communication network: it can read, block and deliver the messages as it sees fit, which includes changing the order of two messages. However, the adversary cannot change (or forge) the content nor the recipient of a message, nor can it replay a message which was already delivered. In a sense, this is the same as considering strongly authenticated (but insecure) channels with enforced integrity. In addition to A, there is a second adversarial ITM Z which represents the environment. It may only interact with A, and can output either 0 or 1.

The security of a process is assessed by a comparison with an ideal process, where a trusted party computes the output of the process with the inputs of the participants. Intuitively, a protocol is SUC-secure if, for all adversary A in the real process, there exists a simulator S in the ideal process such that for all environment Z, the latter cannot tell whether it interacts with A in the real process or S in the ideal process.

1) The real and ideal processes: The real process is mostly determined by the adversary and the protocol, which is the specification of every participants. Conversely, the ideal process is mostly determined by the simulator and the trusted party. If F is a functionality, the trusted party which computes F from the inputs of the participants is denoted T F . In the ideal process, it is assumed that the simulator (but not the environment) can interact with T F , which may react in various manners depending on the functionality. Typically, if the adversary corrupts so many participants that it becomes impossible for the remaining honest ones to run the protocol successfully, it is reasonable to expect that the protocol aborts and output ⊥. In this case, in the ideal process, the simulator is given the possibility to have the trusted party abort and output ⊥. Another quirk of the ideal process is that the simulator and the trusted parties know which participants are corrupted.

In both the ideal and real processes, the environment is given an arbitrary auxiliary input z ∈ {0, 1} * and chooses the inputs of all the participants. When the process terminates, Z can also read the output of all the participants (which is the output of the trusted party in the ideal process).

2) The hybrid process: In the hybrid process, we consider an ideal functionality G and the corresponding trusted party T G . In addition to regular operations, we suppose that the participants can send (secure) queries to T G which answers according to its specification. (For instance, computing the mean of several values can only be done when all values are known, so that T G may have to wait until sufficiently many inputs are sent.) Contrary to the other communication channels, the one which connects the participants to T G in the hybrid model is secure, meaning that the adversary cannot read the queries nor their answers (except if the participant communicating with T G is corrupted). However, it can still block or delay the messages.

In this article, we denote Real SUC,G P,A,Z (λ, z) (resp. Ideal SUC T F ,S,Z (λ, z)) the probability that Z outputs 1, given the auxiliary input z, when interacting with A in the G-hybrid process (resp. with S which interacts with T F in the ideal process), where λ is the security parameter. We can now give the definition of SUC-security.

Definition 3 ( [11]

). Let P be a protocol and T F and T G two trusted parties, which computes the functionalities F and G respectively. We say that P SUC-securely computes F in the G-hybrid model if, for all PPT real adversary A, there exists a PPT ideal simulator S such that for every PPT environment Z and every constant d ∈ N, there exists a negligible function µ such that every security parameter λ ∈ N and every auxiliary input z ∈ {0, 1} λ d ,

Real SUC,G P,A,Z (λ, z) -Ideal SUC T F ,S,Z (λ, z) ≤ µ(λ).
3) The composition theorem: UC frameworks are extremely powerful due to their composition theorem, which allow to deduce the security of a protocol from the security of its sub-protocols. More precisely, suppose that P is a protocol to compute F in the G-hybrid model. Suppose, in addition, that there exists a protocol Q to compute G in the H-hybrid model. Then we can consider the protocol P Q in the H-hybrid model, where every query to T G is replaced by an instance of Q. Given this transformation, the composition theorem can be written as follows.

Theorem 2 ( [START_REF] Canetti | A Simpler Variant of Universally Composable Security for Standard Multiparty Computation[END_REF]). Let P be a protocol that SUC-securely computes F in the G-hybrid model and Q a protocol that SUC-securely computes T G in the H-hybrid model. Then P Q , as defined above, SUC-securely computes F in the H-hybrid model.

B. Application to CHide

To assert the security of CHide, we use the SUC framework. For this purpose, we consider a static and malicious adversary which can fully impersonate the corrupted parties, but can only corrupt a fixed set of participants, which is decided at the beginning of the protocol. (We also consider that this set's cardinal may not exceed the threshold.) We consider a fixed number of participants with a fixed threshold (participants cannot leave or arrive and the threshold may not change). We use the so-called programmable random oracle model which is modeled as an ideal functionality F RO , and we also suppose that the DKG and the decryption mixnet are SUC-secure. We denote F DKG and F DecMixnet the corresponding ideal functionalities. For more details, including a construction to obtain a UC-secure protocol for those, see for instance the work of Wikström [START_REF] Wikström | A Universally Composable Mix-Net[END_REF], [START_REF]Universally Composable DKG with Linear Number of Exponentiations[END_REF].

Hence, we place ourselves in the G-hybrid model, where G = (F RO , F DecMixnet ).

Following [START_REF] Cortier | A Toolbox for Verifiable Tally-Hiding E-Voting Systems[END_REF], we restrict ourselves to environment which only gives as input "valid" bulletin boards; i.e. the ballots are of the form (C 1 , C 2 , π 1 , π 2 ) with valid ZKP π 1 , π 2 as defined in Section IV, where C 1 is a valid ElGamal encryption (that is, any pair of group elements) and C 2 λ valid ElGamal encryptions of bits. In his PhD thesis [35, Section 3.5], Nielsen proves that the composition theorem still holds if the inputs chosen by the environment are restricted to some decidable language. This allows to use [START_REF] Cortier | A Toolbox for Verifiable Tally-Hiding E-Voting Systems[END_REF]'s result, where the CGate protocol is shown to SUC-securely computing T CSZ in the G-hybrid model, where CSZ is the Conditional Set Zero functionality (i.e. CSZ(A, B), for any ciphertext A and any encryption B of 0 or 1, returns a random reencryption of A if B is an encryption of 1 and a random encryption of 0 otherwise). We can now state Theorem 3, which is a direct consequence of the composition theorem. In this theorem, we consider T tally , the trusted party that computes the result of the election protocol from the public board and the inputs of all the parties, and returns the result as well as the output of all the conditional gate protocols. Theorem 3. Under the DDH assumption, P tally SUC-securely computes T tally in the G-hybrid model.

Proof sketch. As shown in [START_REF] Cortier | A Toolbox for Verifiable Tally-Hiding E-Voting Systems[END_REF], CGate SUC-securely computes T CSZ in the G-hybrid model. Consequently, by the composition theorem, it is sufficient to show that Q = P T CSZ ,T DecMixnet tally SUC-securely computes T tally in the (G, F CSZ )-hybrid model, where Q is P tally where all the instances of CGate are replaced by a query to T CSZ while the instance of the decryption mixnet protocol is replaced by a query to T DecMixnet . In other words, it is sufficient to show that, given the ideal result computed by T tally , the simulator can simulate the output of all the trusted parties, which comes immediately since it can use the result for the output of the decryption mixnet, and that it has the output of the conditional gate protocols from T tally .

APPENDIX C SECURITY PROOFS FOR CHIDE

A. Preliminary: on the IND-PA0 game

To prove coercion-resistance, we use a reduction to the IND-PA0 security of the encryption scheme. This security notion is defined, for instance, in [START_REF] Bellare | Non-malleable Encryption: Equivalence between Two Notions, and an Indistinguishability-Based Characterization[END_REF], where it is shown to be equivalent to NM-CPA. In this section, we recall the definition of IND-PA0 and formalize the voting protocol as an IND-PA0 encryption scheme.

First, using the notations of Bellare and Sahai, let (K, E, D) be an encryption scheme. We say that it is IND-PA0 if, for all (stateful) PPT adversary A, its advantage in the game depicted in Algorithm 13 is negligible in the security parameter λ. Note that at line 5, the adversary can send a list of several ciphertexts, and gets the element-wise decryptions of those ciphertexts at the following line. Now, let (Gen, Enc, Dec) be the ElGamal encryption scheme, which is known to be IND-CPA secure under DDH assumption. For simplicity, we assume that any voting option can be encoded as a single group element. For any λ-bits credential c = c 1 , • • • , c λ and voting option ν, recall that Vote pk (c, ν) is obtained by computing the encryptions C 1 = Enc pk (ν) and

C 2 = (Enc pk (g c1 ), • • • , Enc pk (g c λ )
), where g is a public group element. Then, a NIZKPoK π 1 of the plaintexts (c, ν) is computed using the Fiat-Shamir heuristic. To make sure that the ballot remains non-malleable, all the public informations such as the public encryption key, g, C 1 and C 2 are included into the hash to compute the challenge from the commitment of the Σ-protocol. Finally, a ZKP π 2 that (c, ν) is valid is computed and the ballot (C 1 , C 2 , π 1 , π 2 ) is formed. Clearly, Vote pk (c, ν) can be seen as an encryption of the tuple (c, ν) by the encryption scheme (Gen, Vote, Extract), where the Extract algorithm first checks the ZKPs and outputs ⊥ if any of the proof is invalid. Otherwise, it decrypts all the ciphertexts with the secret key and returns the tuple (c, ν). By a result of [START_REF] Bernhard | How Not to Prove Yourself: Pitfalls of the Fiat-Shamir Heuristic and Applications to Helios[END_REF], this defines an NM-CPA encryption scheme, which is therefore IND-PA0 secure. Note that π 2 is not necessary for the IND-PA0 security but does not deteriorate it either. It is useful for other properties of the protocol. In the following section, whenever we use the IND-PA0 security, we refer to the security of this encryption scheme whose plaintext (resp. ciphertext) space consists of (λ + 1)-tuples of plaintexts (resp. ciphertexts, along with the corresponding ZKP).

Algorithm 13: IND-PA0 game 1 (pk, sk) ←-K(λ) 2 (x 0 , x 1 ) ←-A(pk) 3 b $ ← {0, 1} 4 y ←-E pk (x b ) 5 c ←-A(y) 6 p ←-D sk (c) 7 b ′ ←-A(p) 8 Return 1 if and only if (y ̸ ∈ c) ∧ (b ′ = b)

B. Proof of coercion-resistance

The definition of coercion-resistance is given in Definition 2. In this section, we prove Theorem 1, that we restate below. For this purpose, we give a succession of games such that Game 0 is the real game and Game 10 is the ideal game. We consider a PPT A 0 for Game 0. For Game i, we construct a PPT adversary A i for this game and we denote S i the probability that A i wins this game. (To ease the notation, we drop the dependency in λ when the context is clear.) For all i, we show that |S i+1 -S i | is negligible, which proves that |S 0 -S 9 | is also negligible.

Theorem 1. Under the DDH assumption, assuming SUC-secure DKG and Mixnet protocols and in the Programmable Random Oracle Model, CHide is coercion-resistant.

Proof. Game 1: In this game, the adversary no longer takes part into the tally process at line 28. Instead, it is given the output of T tally .

By Theorem 3, there exists a simulator S such that, for all environment Z, |Real SUC,G Ptally,A0,Z (λ, z)(λ, 0) -Ideal SUC Ttally,S,Z (λ, 0)| is negligible. In particular, we consider the environment which defines Game 0, so that Real SUC,G Ptally,A0,Z (λ, z)(λ, 0) = S 0 . Then, A 1 can interact with A 0 by simulating the real game using S, so that Ideal SUC Ttally,S,Z (λ, 0) = S 1 . Hence, |S 1 -S 0 | is negligible. Game 2: In this game, we remove line 2. Instead, we generate a perfectly random public encryption key pk and give it to the adversary at line 4. Just as in the previous transition, assuming an ideal DKG protocol, there exists a negligible function µ 2 and an adversary A 2 for Game 2 such that |S 2 -S 1 | ≤ µ 2 .

Game 3: In this game, the adversary is no longer given the output of the conditional gates, that we denote Π Z . We construct A 3 that interacts with A 2 by simulating Π Z . For this purpose, A 3 uses uniformly random ciphertexts.

To argue the validity of this transition, we construct an adversary B for DDH as follows. First, B gets the challenge tuple (g, g 2 , g 3 , g 4 ) from the DDH game and sets pk = g 2 . To run the setup, B recovers the set S of the corrupted participants from A 2 , and picks s i ∈ Z q at random for all i ∈ S. It the completes S into I by picking some additional s i ∈ Z q at random for all i ∈ I\S, where I ⊂ [1, n T ] is a set of size t that contains S, and n T is the number of talliers. For i ∈ I, it computes h i = g si 1 and, for i ∈ [1, n T ]\I, it deduces h i with Lagrange interpolation.

It then runs the remaining of Game 3honestly, but each time A 2 casts a ballot, B extracts the corresponding voting option from A 2 's proof of knowledge. In the ROM, this is possible in polynomial time, as a consequence of the forking lemma (see for instance Theorem [8, Theorem 1]). This way, B can compute the result r of the tally without knowing the secret key sk. Finally, since B knows the cleartexts of the ballots to tally, B can run the tally protocol "on the cleartexts", i.e. it can compute the cleartext of each of the outputs of each conditional gate, as the product of two cleartexts. To simulate the output of a conditional gate, B "encrypts" the corresponding cleartext z by choosing two random ρ 1 , ρ 2 ∈ Z q and computing Z = (g ρ1 g ρ2

3 , g z g ρ1 2 g ρ2 4 ). Finally, if A 2 wins the game, B states that the challenge was a DDH tuple; otherwise, it states that is was a random tuple. Remark that if (g, g 2 , g 3 , g 4 ) is a DDH tuple, then B played a perfect simulation of Game 2to A 2 and hence wins with probability S 2 . On the other hand, if the challenge tuple is a random tuple, B played A 3 's simulation of Game 2and wins with probability 1 -S 3 . Yet, under the DDH assumption, B's advantage in the DDH game must be negligible, hence |S 2 -S 3 | is negligible.

Game 4: In this game, we modify the sequence B so that the honest voters no longer revote. Instead, for all honest voter x, we replace all but the last occurrence of the form (x, ν) in B by an occurrence of the form (x, ν) which uses a fresh and unique x < 0. This way, the last vote remains the same but the previous votes are replaced by a vote with a fresh, random (and fake) credential. Note that this modification happens on the sequence B, before the voters actually cast their votes according to this sequence.

Let n r be the number of revotes. We set A 4 = A 3 and to argue that |S 4 -S 3 | is negligible, we give another succession of hops H 0 , • • • , H nr such that in game H i , we replace the last i revotes as described above. This way, H 0 is Game 3 and H nr is Game 4. For each of these games, we denote W i the probability that A 4 wins this game. Now, let i be some index. We construct an adversary B for IND-PA0 (see Section C-A) as follows. First, B receives pk from the IND-PA0 game. It simulates game H i by giving this pk to A 4 and generating the credentials at random. It then gets (j, α) from H i and chooses b at random. Afterwards, B generates B from the distribution B, (j, α) and b. It then continues the simulation of H i by replacing the i last revotes as necessary. However, for the next remaining revote, it looks up for the previous vote (x, ν) with the same x and generates a random, fresh credential c. It plays (c x , ν), (c, ν) in the IND-PA0 game and gets an encrypted ballot C which it plays in the simulation of H i instead of a honestly generated ballot for (c x , ν) (therefore, C is added on the board). Finally, to compute the tally, B simply plays the concatenation of all the valid ballots sent by A 4 in the IND-PA0 game, which returns a decryption of these ballots. Remark that due to the nature of isVal which uses a form of weeding, a valid ballot is not already on the board. Therefore, none of the valid ballots sent by A 4 can be equal to C, so that the IND-PA0 will indeed accept to decrypt them. B computes the result of the tally from the plaintexts and gives it to A 4 which answers with some bit b ′ . This is possible because every valid ballot of the board has a valid ZKP π 2 , whose soundness guarantees that the corresponding plaintext (c, ν) is such that c is a λ-bit credential and ν a valid voting option. If b = b ′ , B states that the IND-PA0 game encrypted (c x , ν), and (c, ν) otherwise.

Clearly, when the IND-PA0 game encrypts (c x , ν) (resp. (c, ν)), B plays a perfect simulation of game

H i (resp. H i+1 ) so that b = b ′ with probability W i (resp. W i+1 ). Hence, B's advantage in the IND-PA0 game is | 1 2 (W i + 1 -W i+1 ) -1 2 | ≤ ε PA0 . By the triangular inequality, |S 4 -S 3 | ≤ 2n r ε PA0 .
Game 5: In this game, the adversary no longer has access to the roster R at line 4. We construct A 5 which interacts with A 4 by simulating Game 4. For this purpose, it generates n V λ ElGamal encryptions of random bits and uses it to simulate R. For the remaining of the game, it can play a perfect simulation since both games are identical. To argue that |S 5 -S 4 | is negligible, we construct a succession of hop H 0 , • • • , H n V such that in game H i , the last i elements of R are replaced by a random encryption. This way, H 0 is Game 4 and H n V is Game 5. For each of these games, we denote W i the probability that A 4 wins this game. Now, let i be some index. We construct an adversary B for IND-PA0 as follows. B gets pk from the IND-PA0 game and plays this pk to A 4 to simulate H i . It generates the credentials and replaces the last i elements of the roster by encryptions of random bits just as in H i . However, for the (n V -i)th element of R, it generates a second random credential c and plays the pair (c n V -i , 1), (c, 1) in the IND-PA0 game which answers with some encryption C. B retrieves an ElGamal bitwise encryption of the credential from C and uses it as the (n V -i)th element of R instead of an honest bitwise encryption of c n V -i . Afterwards, B continues the simulation of H i (see the transition to Game 4 for more details) and outputs 1 if and only if A 4 wins the game.

Clearly, when the IND-PA0 encrypts (c n V -i , 1) (resp. (c, 1)), B plays a perfect simulation of game H i (resp. H i+1 ) to A 4 , so that the advantage of B in the IND-PA0 game is

| 1 2 (W i + 1 -W i+1 ) -1 2 | ≤ ε PA0
. By the triangular inequality,

|S 5 -S 4 | ≤ 2n V ε PA0 .
Game 6: In this game, before computing the tally, we decrypt every valid ballot sent by the adversary at lines 23 and 26. If one of these ballots uses the same credential as a ballot sent by an honest voter (i.e. a ballot added to the board at line 25 for some (i, ν i ) with i ∈ [1, n V ]\(A {j}), we abort the game and output a random bit. Now, we set A 6 = A 5 and, to argue that |S 6 -S 5 | is negligible, we remark that |S 6 -S 5 | = ε/2, where ε is the probability that we abort in Game 6. Let E be the event of an abortion. We construct an adversary B for IND-PA0 which wins with a non-negligible advantage whenever E occurs and wins with probability 1/2 otherwise, which shows that ε is negligible.

First, B gets pk from the IND-PA0 game and forwards it to A 5 . It simulate Game 5 as in the transition to Game 4. However, it chooses a random honest voter x that would send a ballot (if no honest voter votes, E cannot happen) and, for this voter, generates a fresh, second random credential c. When this voter votes (which happens at most once due to the transition to Game 4), B plays the pair (c x , ν), (c, ν) in the IND-PA0 game, where ν is the voting option chosen by x. It gets back an encrypted ballot C, which it uses in the simulation instead of the ballot from x. Afterwards, B gets the list of all valid ballots sent by A 5 in the simulation and plays them in the IND-PA0 game to get their decryption. If there is a ballot which uses the credential c x (resp. c), B states that the IND-PA0 encrypted (c x , ν) (resp. (c, ν)). If there is no such ballot, a ballot which uses c and a ballot which uses c x or if no honest voter votes, B guesses at random. Now, suppose that b = 0 (resp. 1) in the IND-PA0 game; in other words, that C is an encryption of (c x , ν) (resp. (c, ν)). Let q be the number of valid ballots sent by A 5 . With probability ε, A 5 managed to produce a ballot which uses the same credential as a ballot sent by some honest voter. In this case, with probability at least 1/n H , one of the concerned honest voter is x. Then, when B gets the decryption from the IND-PA0 game, there is a ballot of the form (c x , γ) (resp. (c, γ)). In addition, A 5 has no information about c (resp. c x ) so that with probability at least 1 -q/2 λ , there is no ballot of the form (c, γ) (resp. (c x , γ)). Hence B wins with probability at least 1 -q/2 λ+1 . Otherwise, no ballot uses the credential c x (resp. c) and since the adversary has no information about c (resp. c x ), the probability that a ballot uses the credential c (resp. c x ) is at most q/2 λ . Therefore, the probability that B wins the IND-PA0 game is at least (1 -q/2 λ )/2. Overall, B's probability to win is at least

ε n H (1 -q/2 λ+1 ) + (1 - ε n H )(1 -q/2 λ )/2 = 1 2 + ε 2n H - q 2 λ+1 . Therefore, we have ε 2n H - q 2 λ+1 ≤ Adv IND-PA0 B ≤ ε PA0 , hence |S 6 -S 5 | = ε/2 ≤ n H ε PA0 + qn H 2 λ+1
, where q is the number of valid ballots sent by the adversary. Game 7: In this game, we remove lines 23 and 24 so that the adversary can no longer insert its own ballots between two honest ballots. In other words, the adversary must send all its ballots at the end, after every honest voter has voted. We construct A 7 which interacts with A 6 by simulating Game 6. For this purpose, A 7 gets BB = (B 1 , • • • , B n ) at line 26 and creates a fake empty ballot box BB ′ . Then, in the kth iteration of the for loop, it simply appends to BB ′ the valid ballots output by A 6 and then B k . The remaining of the simulation is similar to that of the transition to Game 4.

Clearly, A 7 plays a perfect simulation of Game 6 if the result of the tally is the same. Besides, the latter can only differ if the credential of a ballot sent by A 6 is the same as the credential of a ballot sent by some honest voter. In this case, both games abort with a random output and A 7 's probability to win is the same as A 6 's in Game 6. Consequently, S 7 = S 6 .

Game 8: In this game, the adversary has no longer access to the ballot box BB at line 26 but instead has |B| (which is equal to |BB |). With a similar argument as in Game 5, we construct A 8 and we have

|S 8 -S 7 | ≤ |BB |ε PA0 .
Game 9: In this game, the lines 22 to 27 are replaced by lines 22 to 25 of the ideal game. We construct an adversary A 9 which interacts with A 8 by simulating Game 8. For this purpose, A 9 creates a hashmap with keys {c i ; i ∈ A} and c and values (ν i ) i∈A and β which are initially ϕ. For each ballot C ∈ M , A 9 extracts (c, ν) from the ZKPoK and, if c is a key of the hashmap, it changes the corresponding value to ν. It plays the obtained values in Game 9 and receives the result of the tally which it forwards to A 8 . Finally, it outputs A 8 's output. Clearly, S 9 = S 8 .

Game 10: The final game is the ideal game, where the credentials and the public encryption key have been removed. Note that they did not play any role in Game 9 so that the adversary might as well generate them itself. Clearly, S 10 = S 9 .

Conclusion. With all the above transitions, we showed that for all adversary A for the real game, there exists an adversary B for the ideal game which wins with the same probability (up to a negligible difference. By definition, this shows that CHide is coercion-resistant.

C. Privacy 1) Our definition of privacy: In [START_REF]Verifiability, Privacy, and Coercion-Resistance: New Insights from a Case Study[END_REF], a quantitative definition of privacy is proposed. In this definition, the adversary is an observer who can corrupt some voters and talliers. The honest voters vote according to a fixed distribution s in Section III-A and a voter under observation either chooses option ν 0 or ν 1 , where (ν 0 , ν 1 ) can be chosen by the adversary. The latter must decide which was chosen, and do so with an advantage Adv(A). A Voting system is then said δ-private if, for all adversary, 2Adv(A) ≤ δ + µ, where µ is some negligible function.

This definition can be turned into a qualitative one when δ is shown to be minimal, in a sense that an ideal protocol achieves δ ′ -privacy with a negligible |δ -δ ′ |. Hence, a natural definition of privacy is to compare the probability of success of the adversary in a real process to that in an ideal one, and to show that the difference is negligible. Just as in [START_REF]Verifiability, Privacy, and Coercion-Resistance: New Insights from a Case Study[END_REF], we consider a definition where the adversary tries to guess the vote of a single voter. Note that, as opposed to the coercion-resistance case, we do not assume that ballots are sent anonymously. Consequently, the adversary can always determine whether a voter abstained or voted. Finally, we consider that the registrar is honest and that up to t talliers can be corrupted by the adversary. To model this, we consider a fixed set [1, n C ] of valid voting options (excluding abstention) and we give Algorithms 14 and 15.

The real process can be read as follows. First, the public encryption key and the shares are generated with P Setup , in which the adversary can impersonate up to t corrupted authorities. Then the voters are registered and the roster R is published. The adversary can corrupt voters and chooses a voter under observation j. Then the honest voters vote according to a distribution B and, as in Definition 2, we let the adversary freely insert any number of ballots between two ballots cast by an honest voter. To model the fact that the ballots are not sent anonymously, we give away the identity of the voter to the adversary at line 13. Also, to take into account the fact that the latter could revote a certain number of times we include j as a possible identity for the honest voters at line 9. Then the adversary must choose the voting options (ν 0 , ν 1 ) and the voter under observation (re)votes with one of those two options. The adversary is given a last opportunity to cast ballots; after this, the tally is computed with P tally , during which the adversary can impersonate the corrupted authorities (we only consider static corruption). Finally, the adversary must guess whether ν 0 or ν 1 was chosen.

Algorithm 14: Real Priv

Require: A, λ, nT , t, nV , nA, nC , 9: Definition of privacy, λ is the security parameter, n T the number of talliers, t the threshold, n V the number of voters, n A the number of corrupted voters, n C the number of voting options (excluding abstention) and B the distribution.

B 1 BB ←-∅ 2 pk, (s i , h i ) n T i=1 ←-P A Setup (λ, n T , t) 3 {c i ; i ∈ [1, n V ]}, R ←-register(λ, pk, n V ) 4 A ←-A(R) 5 j, ν 0 , ν 1 ←-A({c i ; i ∈ A}) 6 (* A chooses the voter under observation *) 7 if |A| ̸ = n A ∨ j ̸ ∈ [1, n V ]\A then 8 Return 0 9 B ←-B([1, n V ]\A, n C ) for (i, ν i ) ∈ B do M ←-A(BB ) BB ← BB {m ∈ M | isVal(pk, m, BB ) = 1} BB ←-BB {Vote pk (c i , ν i )}; A(i) M ←-A(BB , "last honest ballot sent") BB ←-BB {m ∈ M | isVal(pk, m, BB ) = 1} b $ ← {0, 1} BB ←-BB {Vote pk (c j , ν b )} M ←-A(BB ) BB ←-BB {m ∈ M | isVal(pk, m, BB ) = 1} X, Π ←-P A tally (BB , R, pk, {h i , s i }, t) b ′ ←-A() Return 1 if ν 0 , ν 1 ∈ [1, n C ] ∧ b ′ == b else 0 Algorithm 15: Ideal Priv Require: A, λ, nT , t, nV , nA, nC , B 1 2 3 4 A ←-A(λ) 5 j, ν 0 , ν 1 ←-A() 6 7 if |A| ̸ = n A ∨ j ̸ ∈ [1, n V ]\A then 8 Return 0 9 B ←-B([1, n V ]\(A {j}), n C ) 10 I ←-(i) (i,ν)∈B 11 12 13 14 (α i ) i∈A ←-A(I) 15 B ←-B {(i, α i ) | i ∈ A, α i ∈ [1, n C ]} 16 b $ ← {0, 1} 17 B ←-B {(j, ν b )} 18 19 20 r ←-tally(cleanse(B)) 21 b ′ ←-A(r) 22 Return 1 if ν 0 , ν 1 ∈ [1, n C ] ∧ b ′ == b else 0 Fig.
The ideal process is simpler. The adversary still corrupts n A voters and chooses (ν 0 , ν 1 ), but must guess which option was chosen given only the result r of the election, and the list I that indicates which voter (re)votes at which moment. The latter is given in the ideal game to model that the ballots are not sent anonymously. Definition 4 (Vote privacy). We say that a voting protocol (P Setup ,register,Vote,Check,isVal,Fakecred,P tally ,Verify) guarantees vote privacy w.r.t. a result function tally if, for all parameters n T , t, n V , n A , n C with t < a and n A ≤ n V , for all distribution B and for all PPT adversary A, there exists a PPT adversary B and a negligible function µ such that

|P r(Real

Priv (A, λ, n T , t, n V , n A , n C , B) = 1) -Pr(Ideal Priv (B, λ, n T , t, n V , n A , n C , B) = 1)| ≤ µ(λ).
2) Proof that CHide is private: We now prove that CHide is private, as of Definition 4. The proof is extremely similar to that of coercion-resistance in Section C-B and uses roughly the same transitions. We reproduce the transitions, with a few little tweaks to take into account the differences between Real CR and Real Priv . Just as for coercion-resistance, we make several assumptions; the main difference is that we no longer assume anonymous channels for voting. Proof. We give a succession of games such that Game 0 is the real game and Game 9 is the ideal game. We consider a PPT A 0 for Game 0. For Game i, we construct a PPT adversary A i for this game and we denote S i the probability that A i wins this game. (To ease the notations, we drop the dependency in λ when the context is clear.) For all i, we show that |S i+1 -S i | is negligible, which proves that |S 0 -S 9 | is also negligible.

Game 1: In this game, the adversary no longer takes part into the tally process at line 28. Instead, it is given the output of T tally .

Game 2: In this game, we remove line 2. Instead, we generate a perfectly random public encryption key pk and give it to the adversary at line 4.

Game 3: In this game, the adversary is no longer given the output of the conditional gates, that we denote Π Z . Game 4: In this game, we modify the sequence B so that the honest voters no longer revote. Instead, for all honest voter x, we replace all but the last occurrence of the form (x, ν) in B by an occurrence of the form (x → x, ν) where x is a fresh and unique negative number. Then, at line 13, when i is of the form x → x, we give x to the adversary but we add a ballot of the form Vote pk (c, ν) with a fresh random (fake) credential c.

Although this transition is slightly different from the transition to Game 4 in the proof of coercion resistance, the reduction argument is the same.

Game 5: In this game, the adversary no longer has access to the roster R at line 4. Game 6: In this game, before computing the tally, we decrypt every valid ballot sent by the adversary at lines 11, 14 and 18. If one of these ballots uses the same credential as a ballot sent by an honest voter (i.e. a ballot added to the board at line 13 for some (i, ν i ) with i ∈ [1, n V ]\A, we abort the game and output a random bit.

Game 7: In this game, we remove lines 11, 12, 14 and 15 so that the adversary can no longer insert its own ballots between two honest ballots (including those sent by the voter under observation). In other words, the adversary must send all its ballots at the end, after every honest voter has voted.

Game 8: In this game, the adversary has no longer access to the ballot box BB at lines 18 and 5 but instead is given I.

Compared to the transition to Game 8 in the proof of coercion resistance, the adversary know has access to I instead of |B|. This extra information is used to simulate line 13.

Game 9: The final game is the ideal game.

We construct an adversary A 9 which interacts with A 8 by simulating Game 8. For this purpose, A 9 runs the setup and the registration honestly, by generating the secret key and the credentials. This allows A 9 to get j, ν 0 , ν 1 from A 8 , that it plays in the ideal game. Then, when given I in the ideal game, it forwards it to A 8 which answers with M . To deduce the corresponding voting options (ν i ) i∈A , A 9 creates a hashmap with the keys {c i ; i ∈ A}, and values (ν i ) i∈A (initially ϕ, for abstention). For each valid ballot cast by A 8 , A 9 decrypts the ballot using the secret key and deduces (ν, c). Since the ballot is valid, by the soundness of the ZKP, c consists of λ bits and ν is a valid voting option. If c is a key of the hashmap, A 9 changes the corresponding value to ν. (Otherwise, it ignores the ballot.) It plays the obtained values in Game 9 and receives the result of the tally which it forwards to A 8 . Finally, it outputs A 8 's output. Remark that A 9 played a perfect simulation of Game 8, so that S 9 = S 8 .

D. Verifiability 1) Our definition of verifiability:

Verifiability is often split into several sub-properties, namely cast-as-intended, where the voters can verify that their voting device produced a ballot which indeed contains the desired voting option; recorded-as-cast, where the voters can verify that the ballot produced by their voting device is indeed added to the ballot box (typically, a public bulletin board); tally-as-recorded, where anyone can verify that the result obtained with the tally protocol indeed corresponds to that obtained by opening every (valid) ballot of the ballot box and then applying the counting function on the cleartexts; and eligibility, where anyone can verify that the ballot box indeed contains ballot that comes from an eligible voter, and that each voter can have at most one ballot counted. The first two properties form the individual verifiability while the two last form the universal verifiability.

In this paper, we focus on the universal verifiability. We do not consider cast-as-intended verification and assume that the voting device is not compromised. Achieving both cast-as-intended verification and coercion-resistance is a non-trivial task that is out of the scope of this article. In addition, we assume that each time a honest voter casts a ballot, they verify that the ballot appears on the board. Since the bulletin board is considered honest, this immediately gives individual verifiability.

To formalize the notion of universal privacy, we use the approach of [START_REF] Cortier | Election Verifiability for Helios under Weaker Trust Assumptions[END_REF] which gives a game-based definition. Originally, their definition mixes the universal and individual verifiability and divides the honest voters into two subsets, depending on whether they perform the verification or not. For those who do not check, they require that their ballots can be dropped but that their content cannot be modified. This, however, comes with a difficulty when revoting is allowed. Indeed, if a voter's votes are, in order, (ν 1 , ν 2 , ν 3 ) and if the voter does not verify that the corresponding ballots appear on the board, then the adversary might drop any of those ballots and have the voter abstain, or have their vote counted as ν 1 , ν 2 or ν 3 as it sees fit. A stronger and more desirable definition would require the adversary to either have the voter abstain or have their last choice ν 3 be counted. This, however, requires specific measures which are yet to appear in the literature. In this paper, we consider that those considerations are out of scope and thus consider a weaker definition where every voter systematically verifies that their ballot appears on the board. This gives Definition 5, where the adversary first takes part in the setup and corrupts a subset A of the voters. Then, given the roster and the credentials of the corrupted voters, the adversary must generate a valid bulletin board. For this purpose, it has access to the oracle O cast which takes as input a ballot b (see Algorithm 17). If the ballot is valid w.r.t. BB , O cast adds b to BB . The adversary also has access to O vote , which models the ballots sent by the honest voters (see Algorithm 16). However, O vote modifies two inner tables H and HV. The first one model the fact that a honest voter is supposed to check that their ballot appears on the board. If a honest voter vote but does not check or if their check fails, they become unhappy. The second tabular represent the state of a voter, and contains their ballot, their credential and their chosen voting option. The adversary . Let q v be the number of (valid) calls to O vote and q c be the number of ballots from BB which are not an output of O vote . With probability ε, A 5 managed to produce a ballot which uses the same credential as a ballot output by O vote . In this case, with probability at least 1/q v , one of the concerned ballot is b. Then, when B gets the decryption from the IND-PA0 game, there is a ballot of the form (c, γ) (resp. (c, γ)). In addition, A 5 has no information about c (resp. c) so that with probability at least 1 -q c /2 λ , there is no ballot of the form (c, γ) (resp. (c, γ)). Hence B wins with probability at least 1 -q c /2 λ+1 . Otherwise, no ballot uses the credential c (resp. c) and since the adversary has no information about c (resp. c), the probability that a ballot uses the credential c (resp. c) is at most q c /2 λ . Therefore, the probability that B wins the IND-PA0 game is at least (1 -q c /2 λ )/2. Overall, B's probability to win is at least

ε q v (1 -q c /2 λ+1 ) + (1 - ε q v )(1 -q c /2 λ )/2 = 1 2 + ε 2q v - q c 2 λ+1 .
Therefore, we have

ε 2q v - q c 2 λ+1 ≤ Adv IND-PA0 B ≤ ε PA0 , hence |S 6 -S 5 | = ε/2 ≤ q v ε PA0 + qcqv 2 λ+1
, where q v is the number of calls to O vote and q c the number of ballots in BB which are not an output of O vote .

Conclusion. Now, remark that due to the nature of O vote which overwrite HV, it is clear that the adversary must call O check (i) between each call of O vote with the same voter i, otherwise H i < 1 at line 6. Since O check erases HV i , it is also necessary for the adversary to call O cast (b) before O check (i), where b is the output of O vote (i, ν). Note that due to the randomness involved in Vote, except with negligible probability µ, the adversary cannot call O cast (b) before O vote (i, ν) (at which point it has no information about b). Therefore, the order of the revotes of each voter is enforced in BB and, because of the last transition and the nature of the tally, we readily have that the condition at line 9 always result in a 0 output, which concludes the proof.

APPENDIX D QUANTIFYING COERCION-RESISTANCE

As explained in Section III, the coercion level can be evaluated thanks to Eq. ( 1). This assumes that the cryptography is perfect, that a large and unpredictable number of ballots is removed during the tally phase and that the adversary is able to compare Pr(R g |α) and Pr(R g |β), given R g with g ∈ {Real CR , Ideal CR }. In this appendix, we give more details about how this comparison can be done as well as some efficient ways to evaluate the formula from Eq. (1). In particular, this allows to understand how the figures from Section III were obtained.

A. The coercion level in the ideal game

In the ideal game, R Ideal is the vector -→ res, and computing Pr( -→ res|α) for any α can be done thanks to a formula given in the following result from [START_REF] Küsters | A Game-Based Definition of Coercion-Resistance and Its Applications[END_REF]. Thanks to this result, it appears that the adversary can compare Pr(R Ideal |α) and Pr(R Ideal |β) in O(1) floating operations, as long as it has access to P α and P β (note that it does not need the whole distribution), and where the asymptotic analysis is done for n H growing to infinity and other parameters are fixed. We can further analyze this expression to give a representation which is easier to compute. For this purpose, we give Lemma 1, which allows to compute δ Ideal in O(n H ) floating operations. Proof. First, we partition M α,β into n H x=0 M x α,β , where M x α,β is the subset of all results in M α,β where the options other than α and β received exactly x votes. Then, we further partition M x α,β into subsets where res β = y (and, thus, res α = N x -y). Note that due to the condition from Theorem 6, res β P α ≥ res α P β hence y ranges from T x to N x . To express the formula from Theorem 6 using this partition, we assume that α and β are the last two voting options (otherwise we reorder them For this purpose, we first fix some N ≥ 0 and we proceed by backward iteration over T . First, it is true when T = N . Now, suppose that it is true for some 0 < T ≤ N ; we show that it is also true for T -1: Indeed, the last summation is the sum over all possibilities of a multinomial distribution, which is 1.

B. Modeling the real game

For the real game where revoting is possible, we propose a model in which each honest voter does the following

• Abstain with probability P 0 ,

• Otherwise, vote for option l > 0 with probability p l ,

• Revote with probability r l ,

• In this case, choose option k > 0 with probability r l,k . In this model, a voter may revote at most once. Also, a voter who abstains does not "revote". If a voter who initially wanted to abstain changes their mind, it will count as voting once. This approximation is made because the adversary has access to the number of revotes, and not the number of voters who changed their mind. Also, the probability to revote depends on the n 0 , P 0 a b s t .

P initial choice. This is to capture the fact that an announcement on the press can make some voter revote if their candidate has been compromised. Similarly, the probability distribution when revoting depends on the first choice. See Fig. 11 for an illustration. In this figure, the label on the left of an edge denotes the nature of the transition and the label on the right denotes the probability of the transition. On leafs, we used labels of the form (n, P ) when n denotes the total number of honest voters who choose this path and P the probability to choose this path. For instance, P 1,2 is the probability to first vote for option 1 but to finally revote for option 2 while P 2,∅ is the probability to vote for option 2 and not to revote. Since abstention plays a specific role, we denote it as choice 0, while the other choices actually imply to send a ballot. Now, we must decide on the information the adversary has access to. The most conservative approach is that it may have access to anything which is not a secret; here, all the probability transitions. With this assumption, if -→ res = (res 0 , • • • , res C ) is the number of votes for each option and n r is the number of revotes, then Pr(( -→ res, n r )|α) is the probability that the honest voters votes res k -1 k=α times for each candidate k and revote n r times. Given the above tree, for any possible outcome

where H nr C. Quantifying the coercion level in some specific cases

Because of the complexity of Eq. ( 2), we only consider the specific cases where there are two candidates and the possibility to abstain (i.e. C = 2). In these simpler cases, we give Lemma 2 which allows to compute the coercion level in O(n H 4 ) floating operations. Interestingly, δ Real does not depend on the P l,k directly but only on the sums P r1 and P r2 , which correspond to the probability to revote for 1 or 2 respectively. This is because the adversary can only observe the number of revotes and has no information about the initial intention of the voter. Hence, they cannot exploit the dependency between the final choice and the first choice. In practice, we can imagine a scenario where the probability to revote and the probability distributions when revoting and when not revoting are known to the adversary, for instance thanks to exit poll or social media, where the voters tell whether they revote and what was their final choice. In this more realistic scenario when the adversary does not know all the probabilities on the tree, the latter can still compare Pr(R Real |α) and Pr(R Real |β), which takes O(n H ) floating operations.

Voter c, ν Fig. 1 :

 ν1 Fig. 1: Voting phase in JCJ.

Fig. 2 :

 2 Fig.2: Coercion levels as a function of the revote, with 20 voters, 2 candidates, 30% abstention and a 50%-50% distribution of votes between the candidates.

Fig. 4 :Fig. 5 :Fig. 6 :

 456 Fig. 4: Coercion levels as a function of the proportion in favor of A for 20 voters, 2 candidates and 30% abstention.

Fig. 7 :

 7 Fig.7: JCJ definition of coercion resistance. λ is the security parameter, n T the number of talliers, t the threshold, n V the number of voters, n A the number of corrupted voters, n C the number of voting options and D the distribution of votes.

19

 19 Remove all (j, * ) ∈ B but the last, which is replaced by (j, α) if α ̸ = ϕ and removed 20 otherwise 21 22

27 28 XFig. 8 :

 288 Fig.8: Definition of coercion-resistance. λ is the security parameter, n T the number of talliers, t the threshold, n V the number of voters, n A the number of corrupted voters, n C the number of voting options and B the distribution.

Theorem 4 .

 4 Under the DDH assumption and in the ROM, CHide has privacy as of Definition 4.

  c. B plays the pair (c, ν), (c, ν) in the IND-PA0 game, where c is the last credential in Cred x . It gets back an encrypted ballot b, which it uses in the simulation as the output of O vote . Afterwards, B removes from BB any ballot output by O vote (including b) and plays BB in the IND-PA0 game to get the decryption of the remaining ballots. If one uses the credential c (resp. c), B states that the IND-PA0 encrypted (c, ν) (resp. (c, ν)). If there is no such ballot or if there is a ballot which uses c and a ballot which uses c, B guesses at random. Now, suppose that b = 0 (resp. 1) in the IND-PA0 game; in other words, that b is an encryption of (c, ν) (resp. (c, ν))

Theorem 6 (

 6 [START_REF] Küsters | A Game-Based Definition of Coercion-Resistance and Its Applications[END_REF]). Let (α, β) be two options, n H the number of honest voters and a pure result -→ res such that C i=0 res i = n H + 1. Let -→ P be the probability distribution for the honest voters. Assuming P α P β ̸ = 0, we have Pr( -→ res|β) ≥ Pr( -→ res|α) if and only if res β P α ≥ res α P β .In addition, we havePr( M α,β = { -→ res | Pr( -→ res|β) ≥ Pr( -→ res|α)}, the optimal value of δ Ideal α,β is δ Ideal CR α,β = -→ res∈M α,β (Pr( -→ res|β) -Pr( -→ res|α)) = -→ res∈M α,β n H ! C k=0 res k ! C k=0 P res k k res β P β -res α P α .

Lemma 1 .

 1 Let (α, β) be two options, n H the number of honest voters and a pure result -→ res such that C i=0 res i = n H + 1. Let -→ P be the probability distribution for the honest voters. Assuming P α P β ̸ = 0, we have x !(N x -T x )! (1 -P β -P α ) x , where N x = n H -x + 1 and T x = P β P β + P α N x .

2 k=0T

 2 ) and denoteM x = { -→ res ∈ N C-2 | Cres k = x}.With these notations, we have Now, we show that, for all 0 ≤ T ≤ N , !(N -T )! .

P 1 βP

 1 1)!(N -T + 1)! .Hence, with T = T x and N = N x , we deduce that Nx-Tx αT x !(N x -T x )! = n H ! n H x=0 T x P Tx-Nx-Tx α x!T x !(N x -T x )! (1 -P β -P α ) x x !(N x -T x )! (1 -P β -P α ) x .

Fig. 11 :

 11 Fig. 11: Tree structure for two candidates.

  ( -→ res, n r ) with n H honest voters, we have Pr( -→ res, n r ) =

  (n k,∅ ), (n l,k ) | l,k n l,k = n r , ∀k > 0, n k,∅ + C k=1n l,k = res k } is the set of all possible atomic outcomes compatible with -→ res and n r .

Fig. 16 :

 16 Fig. 16: Coercion level as a function of the number of voters; with 2 candidates and 30% abstention.

TABLE I :

 I Asymptotic cost of the CHide protocol in terms of computations and communications, n B is the size of the board, n V is the number of voters, λ is the security parameter and n T is the number of talliers.

	# exponentations	O((n B

TABLE II :

 II Estimated number of exponentiations and volume of communication in JCJ and CHide, with λ = 128.

	# voters	# exp.	estimated CPU time	data exchanged
	any	JCJ	CHide	JCJ	CHide	JCJ	CHide
	(Vote)	27	1.4k	5.4ms	0.28s	1.1kB	58kB
	10	JCJ	CHide	JCJ	CHide	JCJ	CHide
	(Tally)	4.26k	4.1M	0.43s	6.8min	170kB	65MB
	100	JCJ	CHide	JCJ	CHide	JCJ	CHide
	(Tally)	380k	120M	38s	3.3h	16.0MB	1, 9GB
	1000	JCJ	CHide	JCJ	CHide	JCJ	CHide
	(Tally)	37.5M	2.4G	1.0h	2.8d	1.59GB	39GB
	10000	JCJ	CHide	JCJ	CHide	JCJ	CHide
	(Tally)	3.75G	41G	4, 3d	48d	158GB	668GB
	100000	JCJ	CHide	JCJ	CHide	JCJ	CHide
	(Tally)	375G	658G	1.2y	2.1y	15.8TB	10.6TB
	1000000	JCJ	CHide	JCJ	CHide	JCJ	CHide
	(Tally)	37.5T	9.4T	120y	30y	1.58PB	152TB

Algorithm 8: Eq (for bitwise encrypted integers)

Require: X 0 , • • • , X m , Y 0 , • • • , Y m bit-wise encryptions of x and y. Ensure: Z, an encryption of 1 if x = y, 0 otherwise. 1 for all i (in parallel) do 2 A i ←-Eq(X i , Y i )

3 Return Z = And(A 0 , • • • , A m-1 ) and the concatenation of all the verification transcript to be sorted. In the P tally protocol, if λ is the security parameter, n B the number of valid ballots received and n V the number of eligible voters, then n = n B + n V and performing a comparison and a conditional swap costs about 3(λ + m) CGate in total, where m = ⌈log(n B )⌉ + 1. If n T is the number of talliers, this translates into O((λ + m)n T (n B + n V ) log(n B + n V ) 2 ) exponentiations.

Algorithm 9: Lt

Require:

), bit-wise encryptions of x and y. Ensure: R, an encryption of 1 if x < y and 0 otherwise.

10 Return R and the concatenation of all the verification transcripts Algorithm 10: CSwap Require: X, Y, B, encryptions of x, y and b with b ∈ {0, 1} Ensure: X ′ , Y ′ , reencryptions of y and x if b = 1; of x and y otherwise 1 A ←-CGate(Y /X, B); X ′ ←-XA; Y ′ ←-Y /A 2 Return X ′ , Y ′ and Π CSwap = Π CGate Algorithm 11: OddEvenMergeSort Require: (V i , K i ) n-1 i=0 , where, for all i, V i is an encryption while K i is a bitwise encryption of an integer k i Ensure: (V ′ i , K ′ i ) n-1 i=0 , reencryptions of the same values, but sorted with increasing k i 1 t ←-⌈log n⌉; p ←-2 t-1 ; Π Sort ←-∅ 2 while p > 0 do

i=0 and the transcript Π Sort With all the above protocols, P tally can be written as Algorithm 12, where BB is the ballot box; R is the public roster that contains the encrypted credentials.

Algorithm 12: P tally

Require: A t-threshold setup phase is assumed to have been run between the n T participants.

For k = 0 to n B , we denote U k a bitwise encryption of k with m bits (least significant bits first)

Fig. 10: Definition of verifiability, λ is the security parameter, n T the number of talliers, t the threshold, n V the number of voters, n A the number of corrupted voters and n C the number of voting options (excluding abstention) can have a voter i check their vote by calling O check (i) (see Algorithm 18) which calls the Check procedure with the current state HV i of the voter and the current bulletin board. The adversary can call O cast , O vote and O check any (polynomial) number of times, in any order. It then takes part into the tally to produce the result X as well as the transcript Π. The goal of the adversary is to produce a valid X, Π which is different from any result obtained with the sequence (i, HV i ) i concatenated with another sequence (cor i , α i ) i , where the cor i 's are corrupted voters. In addition, all honest voter who have voted must be happy.

We acknowledge that, in our definition, we assume that the registrar is honest, and that up to t decryption trustees can be corrupted. Usually, one would want verifiability even if all the talliers and the registrar are corrupted. In [START_REF] Cortier | Election Verifiability for Helios under Weaker Trust Assumptions[END_REF], for instance, it is assumed that either the registrar or the bulletin board is honest. However, in JCJ-like voting systems, the registrar knows the credential of the voter and can therefore break eligibility by voting instead of the abstaining voters (ballot stuffing), or even change the choice of any voter by revoting with their credential afterwards. Similarly, since an encryption of the credentials is published in the roster R, if more than a threshold t of talliers is corrupted, they can decrypt the credentials and perform the same attacks. Therefore, it is necessary to assume that the registrar is honest and that up to a threshold of talliers can be corrupted. Those shortcomings were already present in JCJ.

Definition 5 (Verifiability). We say that the a voting protocol (P Setup ,register,Vote,Check,isVal,Fakecred,P tally ,Verify ) is verifiable if, for all adversary A, for all parameters (n T , t, n V , n C ), there exists a negligible function µ such that Pr(Ver(A, λ, n T , t, n V , n A , n C ) = 1) ≤ µ(λ).

Algorithm 16: O vote (updates the tabulars HV and H)

Require: i, ν (n V is the number of voters, A the corrupted voters, n C the number of voting options, pk the public key and c i the credential of voter i)

2) Proof that CHide is verifiable: We now prove that CHide is verifiable, as of Definition 5. Just as for coercion-resistance, we make several assumptions; the main difference is that the adversary has a complete control over the vote of the honest voters.

Theorem 5. Under the DDH assumption and in the ROM, CHide is verifiable as of Definition 5.

Proof. Despite the difference between coercion-resistance and verifiability, there are arguments in common in the two proofs and the first transitions are the same.

Game 1: In this game, the adversary no longer takes part into the tally process at line 28. Instead, it is given the output of T tally .

Game 2: In this game, we remove line 2. Instead, we generate a perfectly random public encryption key pk and give it to the adversary at line 4.

Game 3: In this game, the adversary is no longer given the output of the conditional gates, that we denote Π Z . Game 4: In this game, we create a secret internal state Cred i for each voter. It contains a sequence of credentials which is initially [c i ], where c i is i's credential. In addition, we also modify O vote so that it uses the last element of Cred i instead of c i . It also generates a fresh random credential c which is added at the end of Cred i , so that the next instance of O vote with the same voter will use this new credential instead of the old one. (In case if c is a collision with another voter, we pick another random credential.) Finally, we change the way the tally X is computed. Now, we decrypt each ballot of BB into a couple (c, ν). For each ballot, we look for a voter i such that c appears in the sequence Cred i and we set i's vote as ν (since there is no collision, there may be up to one such voter). Finally, we define X as the voters' votes.

We take A 4 = A 3 and we show that |S 4 -S 3 | is negligible. For this purpose, for all honest voter j, we consider another succession of games H j 0 , • • • , H j nj , where n j is the number of times that A 3 calls O vote with the voter j and a valid ν. (For the sake of notations, we set n j = 0 when j is a corrupted voter.) Game H j k is like Game 4, except that the first n j -k times O vote is called with voter j, we do not add the new credential c in Cred j , so that the next instance of O vote with voter j will still use the credential c j . As for all voter i > j, we never update their Cred i , so that they are treated as in Game 3. This way,

is Game 4. For each of these games, we denote W j k the probability that A 3 wins the game. Now, let k be some index and j be some voter. We construct B for IND-PA0 as follows. B gets pk from the IND-PA0 game and uses this value to play a simulation of H j k to A 3 . For this purpose, it creates and updates BB , HV, H and Cred, and simulates the oracles. It also simulates the register procedure by generating a random credential for each voter and computing R by encrypting the bits of those credentials, using pk. However, the (n j -k -1)th time O vote is called with voter j, B generates a new c in Cred j as in game H j k+1 . In addition, the next time O vote is called with voter j (let ν be the corresponding voting option), instead of using the last credential of Cred j (which is c), B plays (c i , ν), (c, ν) in the IND-PA0 game and uses the result as the output b. At some point, A 3 terminates and B must decide whether the IND-PA0 game encrypted (c i , ν) or (c, ν). For this purpose, B uses BB , the list of the ballots cast by B. If b ∈ BB , B removes it from BB but keeps in memory its index. For the remaining ballots, B decrypts them using the decryption oracle of the IND-PA0 game. With all these informations, B can compute the tally as in Game 4. If the condition of line 9 is not verified (i.e. A 3 won the simulation), B states that (c i , ν) was encrypted; otherwise, it states that (c, ν was encrypted.

Clearly, when (c i , ν) is encrypted, B plays a perfect simulation of H j k while, when (c, ν) is encrypted, B plays a perfect simulation of H j k+1 . Therefore, B's advantage in the IND-PA0 game is

, where q is the number of calls to O vote . Game 5: In this game, the adversary no longer has access to the roster R at line 3. We construct A 5 which interacts with A 4 by simulating Game 4. For this purpose, it generates n V λ ElGamal encryptions of random bits and uses it to simulate R. For the remaining of the game, it can play a perfect simulation since both games are identical. To argue that |S 5 -S 4 | is negligible, we construct a succession of hop H 0 , • • • , H n V such that in game H i , the last i elements of R are replaced by a random encryption. This way, H 0 is Game 4 and H n V is Game 5. For each of these games, we denote W i the probability that A 4 wins this game. Now, let i be some index. We construct an adversary B for IND-PA0 as follows. B gets pk from the IND-PA0 game and plays this pk to A 4 to simulate H i . It generates the credentials and replaces the last i elements of the roster by encryptions of random bits just as in H i . However, for the (n V -i)th element of R, it generates a second random credential c and plays the pair (c n V -i , 1), (c, 1) in the IND-PA0 game which answers with some encryption C. B retrieves an ElGamal bitwise encryption of the credential from C and uses it as the (n V -i)th element of R instead of an honest bitwise encryption of c n V -i . Afterwards, B continues the simulation of H i (see the transition to Game 4 for more details) and outputs 1 if and only if A 4 wins the game.

Clearly, when the IND-PA0 encrypts (c n V -i , 1) (resp. (c, 1)), B plays a perfect simulation of game

Game 6: In this game, before computing the result, we decrypt every valid ballot of BB which is not the output of some O vote . If one of these ballots uses the same credential as a ballot output by O vote , we abort the game and output a random bit. Now, we set A 6 = A 5 and, to argue that |S 6 -S 5 | is negligible, we remark that |S 6 -S 5 | = ε/2, where ε is the probability that we abort in Game 6. Let E be the event of an abortion. We construct an adversary B for IND-PA0 which wins with a non-negligible advantage whenever E occurs and wins with probability 1/2 otherwise, which shows that ε is negligible.

First, B gets pk from the IND-PA0 game and forwards it to A 5 . It simulate Game 5 as in the transition to Game 4. However, it chooses a random instance of O vote (let (x, ν) be its inputs) and, for this instance, generates a fresh, second random credential Lemma 2. Let n H be the number of honest voters, (res 0 , res 1 , res 2 ) such that res 0 + res 1 + res 2 = n H + 1 and n r ≤ n H -res 0 . Let β ∈ {0, 1, 2} be a voting option. Then the probability Pr((res 0 , res 1 , res 2 ), n r |β) that there are res 0 abstentions, res 1 votes for option 1, res 2 votes for option 2 and n r revotes when the coerced voter chooses the voting option β is given by the following algorithm.

• First, set -→ res = (res 0 , res 1 , res 2 ).

• If res β = 0, return 0, otherwise, do res β ← res β -1.

• Set N = n H -res 0 -n r , P r1 = P 1,1 + P 2,1 and P r2 = P 1,2 + P 2,2 . Return

where max(0, res 1 -n r ) ≤ n 1,∅ ≤ min(res 1 , n H -res 0 -n r ).

Proof. As shown in Section D-B, Pr((res 0 , res 1 , res 2 ), n r |β) is given by Eq. ( 2). We explicit the sum over H nr

In addition, n 1,∅ + n 1,1 + n 2,1 = res 1 and 0 ≤ n 2,1 ≤ n r so that

Considering all these inequalities, we have

Now, res 1 -n 1,∅ is equal to the number of revotes for 1, so that res 1 -n 1,∅ ≤ n r . Therefore, the innermost summation is also on the full domain for n 1,2 . Hence,

where P r1 = P 1,1 + P 2,1 and P r2 = P 1,2 + P 2,2 .

Note that this can be computed in O(n H ) floating operations. Since we must range over all possibilities for res 0 , res 1 , res 2 , n r , the overall δ Real can be computed in O(n H 4 ) floating operations.

In Section III, we used the formulas from Lemma 2 and 1 to evaluate the coercion level. The only exceptions are Figures 16 and6, where the real coercion level for 513 and 1025 voters were obtained with a Monte-Carlo estimates with 1, 000, 000 iterations, which gives a sufficiently small confidence interval for our purpose. The reason why is that evaluating the formula from Lemma 2 would be too long for such values of n V . a b s t . P 0 p a r t . Fig. 13: Coercion levels as a function of the probability of revoting; with 20 voters, 2 candidates and 30% abstention, with three different distributions between the candidates.

D. The impact of the parameters

In Lemma 2, we saw that δ Real only depends on P 0 , the probability of abstention, P r1 (resp. P r2 ), the probability to revote for option 1 (resp. 2) and P 1,∅ (resp. P 2,∅ ), the probability to vote for option 1 (resp. 2) without revoting. To give a better representation of these parameters, we define r = (P r1 + P r2 )/(P r1 + P r2 + P 1,∅ + P 2,∅ ), which is the probability to revote (after voting), p 1 = P 1,∅ /(P 1,∅ + P 2,∅ ) and p 2 = P 2,∅ /(P 1,∅ + P 2,∅ ), which are the probabilities to vote for option 1 and option 2 when voting exactly once and r 1 = P r1 /(P r1 + P r2 ) and r 2 = P r2 /(P r1 + P r2 ), the probabilities to vote for option 1 and 2 when revoting (see Fig. 12 for an illustration).

A first important parameter is r, the probability of revoting. In Fig. 13, we let it vary from 0 to 1, and we plot the coercion level in JCJ and in the ideal protocol for various values of (p 1 , p 2 ) and (r 1 , r 2 ). As expected, since the leakage we detected comes from the revotes, both are the same when there is no revote. Note that when everyone revotes, there is no coercion resistance anymore. This is due to the considered evasion strategy, which instructs the voter to vote once (which is detected if they are the only one to do so). Now, an important point to notice is that, if (p 1 , p 2 ) and (r 1 , r 2 ) are close, the difference between the ideal and the real coercion level is small, unless there are a lot of revotes. On the other hand, if both distributions are opposite, the difference is noticeable, even with a reasonable proportion of revotes. Therefore, another interesting parameter to consider is the distance between (p 1 , p 2 ) and (r 1 , r 2 ), defined as 2|p 1 -r 1 |, which we call the bias. In Fig. 14, we let the bias vary from 0 to 2 and we plot the coercion level in the real and ideal protocols, for various probability of revoting. As expected, when the bias is maximal, there is no coercion resistance at all (this corresponds to the scenario of Section II-B). Note, however, that the leakage is non-zero when there is no bias. This, once again, is due to the fact that the adversary can count the number of revotes, and therefore have a non-negligible advantage to decide whether the coerced voter voted or abstained. Another natural parameter to consider is the abstention rate. Until now, it was fixed at 0.3 in our experimentations. However, it can variate a lot in real-life elections. In Fig. 15, we plot the real and ideal coercion levels as a function of the abstention rate, with various probabilities of revoting and bias. As expected, when there is no abstention, the attacker can trivially break coercion-resistance with a forced-abstention attack. Similarly, when everyone but the coerced voter abstains, there is no coercion-resistance (both situations are captured by the ideal model).

Finally, the last parameter of interest is the number of honest voters. In Fig. 16, we plot the real and ideal coercion levels for 16, 32, 64, 128, 256, 512 and 1024 honest uncoerced voters, with various probabilities of revoting and bias. As expected, the coercion level decreases as n H grows for both the ideal and real game. Interestingly, the difference remains noticeable as long as there is enough revotes.