## THE SUC SECURITY OF $P_{\text{tally}}$

In our security proofs, we use the SUC framework [11] which is a simpler variant of the Universally Composable (UC) framework [10]. In this appendix, we give a brief introduction to the SUC framework and prove that $P_{\text{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 $\mathcal{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 $\mathcal{A}$, there is a second adversarial ITM $\mathcal{Z}$ which represents the environment. It may only interact with $\mathcal{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 $\mathcal{A}$ in the real process, there exists a simulator $\mathcal{S}$ in the ideal process such that for all environment $\mathcal{Z}$, the latter cannot tell whether it interacts with $\mathcal{A}$ in the real process or $\mathcal{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 $\mathcal{F}$ is a functionality, the trusted party which computes $\mathcal{F}$ from the inputs of the participants is denoted $T_{\mathcal{F}}$. In the ideal process, it is assumed that the simulator (but not the environment) can interact with $T_{\mathcal{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 $\perp$. In this case, in the ideal process, the simulator is given the possibility to have the trusted party abort and output $\perp$. 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 \in \{0, 1\}^*$ and chooses the inputs of all the participants. When the process terminates, $\mathcal{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 $\mathcal{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 $\text{Real}_{P, \mathcal{A}, \mathcal{Z}}^{\text{SUC}, \mathcal{G}}(\lambda, z)$ (resp. $\text{Ideal}_{T_{\mathcal{F}}, S, \mathcal{Z}}^{\text{SUC}}(\lambda, z)$) the probability that $\mathcal{Z}$ outputs 1, given the auxiliary input $z$, when interacting with $\mathcal{A}$ in the $\mathcal{G}$-hybrid process (resp. with $\mathcal{S}$ which interacts with $T_{\mathcal{F}}$ in the ideal process), where $\lambda$ is the security parameter. We can now give the definition of SUC-security.

**Definition 3** ([11]). Let $P$ be a protocol and $T_{\mathcal{F}}$ and $T_G$ two trusted parties, which computes the functionalities $\mathcal{F}$ and $\mathcal{G}$ respectively. We say that $P$ SUC-securely computes $\mathcal{F}$ in the $\mathcal{G}$-hybrid model if, for all PPT real adversary $\mathcal{A}$, there exists a PPT ideal simulator $\mathcal{S}$ such that for every PPT environment $\mathcal{Z}$ and every constant $d \in \mathbb{N}$, there exists a negligible function $\mu$ such that every security parameter $\lambda \in \mathbb{N}$ and every auxiliary input $z \in \{0, 1\}^d$,

$$ \left| \text{Real}_{P, \mathcal{A}, \mathcal{Z}}^{\text{SUC}, \mathcal{G}}(\lambda, z) - \text{Ideal}_{T_{\mathcal{F}}, S, \mathcal{Z}}^{\text{SUC}}(\lambda, z) \right| \le \mu(\lambda). $$

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 $\mathcal{F}$ in the $\mathcal{G}$-hybrid model. Suppose, in addition, that there exists a protocol $Q$ to compute $\mathcal{G}$ in the $\mathcal{H}$-hybrid model. Then we can consider the protocol $P^Q$ in the $\mathcal{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** ([11]). Let $P$ be a protocol that SUC-securely computes $\mathcal{F}$ in the $\mathcal{G}$-hybrid model and $Q$ a protocol that SUC-securely computes $T_G$ in the $\mathcal{H}$-hybrid model. Then $P^Q$, as defined above, SUC-securely computes $\mathcal{F}$ in the $\mathcal{H}$-hybrid model.
THE SUC SECURITY OF $P_{\text{tally}}$

In our security proofs, we use the SUC framework [11] which is a simpler variant of the Universally Composable (UC) framework [10]. In this appendix, we give a brief introduction to the SUC framework and prove that $P_{\text{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 $\mathcal{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 $\mathcal{A}$, there is a second adversarial ITM $\mathcal{Z}$ which represents the environment. It may only interact with $\mathcal{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 $\mathcal{A}$ in the real process, there exists a simulator $\mathcal{S}$ in the ideal process such that for all environment $\mathcal{Z}$, the latter cannot tell whether it interacts with $\mathcal{A}$ in the real process or $\mathcal{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 $\mathcal{F}$ is a functionality, the trusted party which computes $\mathcal{F}$ from the inputs of the participants is denoted $T_{\mathcal{F}}$. In the ideal process, it is assumed that the simulator (but not the environment) can interact with $T_{\mathcal{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 $\perp$. In this case, in the ideal process, the simulator is given the possibility to have the trusted party abort and output $\perp$. 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 \in \{0, 1\}^*$ and chooses the inputs of all the participants. When the process terminates, $\mathcal{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 $\mathcal{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 $\text{Real}_{P, \mathcal{A}, \mathcal{Z}}^{\text{SUC}, \mathcal{G}}(\lambda, z)$ (resp. $\text{Ideal}_{T_{\mathcal{F}}, S, \mathcal{Z}}^{\text{SUC}}(\lambda, z)$) the probability that $\mathcal{Z}$ outputs 1, given the auxiliary input $z$, when interacting with $\mathcal{A}$ in the $\mathcal{G}$-hybrid process (resp. with $\mathcal{S}$ which interacts with $T_{\mathcal{F}}$ in the ideal process), where $\lambda$ is the security parameter. We can now give the definition of SUC-security.

**Definition 3** ([11]). Let $P$ be a protocol and $T_{\mathcal{F}}$ and $T_G$ two trusted parties, which computes the functionalities $\mathcal{F}$ and $\mathcal{G}$ respectively. We say that $P$ SUC-securely computes $\mathcal{F}$ in the $\mathcal{G}$-hybrid model if, for all PPT real adversary $\mathcal{A}$, there exists a PPT ideal simulator $\mathcal{S}$ such that for every PPT environment $\mathcal{Z}$ and every constant $d \in \mathbb{N}$, there exists a negligible function $\mu$ such that every security parameter $\lambda \in \mathbb{N}$ and every auxiliary input $z \in \{0, 1\}^d$,

$$ \left| \text{Real}_{P, \mathcal{A}, \mathcal{Z}}^{\text{SUC}, \mathcal{G}}(\lambda, z) - \text{Ideal}_{T_{\mathcal{F}}, S, \mathcal{Z}}^{\text{SUC}}(\lambda, z) \right| \leq \mu(\lambda). $$

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 $\mathcal{F}$ in the $\mathcal{G}$-hybrid model. Suppose, in addition, that there exists a protocol $Q$ to compute $\mathcal{G}$ in the $\mathcal{H}$-hybrid model. Then we can consider the protocol $P^Q$ in the $\mathcal{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** ([11]). Let $P$ be a protocol that SUC-securely computes $\mathcal{F}$ in the $\mathcal{G}$-hybrid model and $Q$ a protocol that SUC-securely computes $T_G$ in the $\mathcal{H}$-hybrid model. Then $P^Q$, as defined above, SUC-securely computes $\mathcal{F}$ in the $\mathcal{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 $\mathcal{F}_{RO}$, and we also suppose that the DKG and the decryption mixnet are SUC-secure. We denote $\mathcal{F}_{DKG}$ and $\mathcal{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 [40], [41].

Hence, we place ourselves in the $\mathcal{G}$-hybrid model, where $\mathcal{G} = (\mathcal{F}_{RO}, \mathcal{F}_{DecMixnet})$.

Following [15], 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, \pi_1, \pi_2)$ with valid ZKP $\pi_1, \pi_2$ as defined in Section IV, where $C_1$ is a valid ElGamal encryption (that is, any pair of group elements) and $C_2 \lambda$ 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 [15]'s result, where the CGate protocol is shown to SUC-securely computing $T_{CSZ}$ in the $\mathcal{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 $\mathcal{G}$-hybrid model.*

*Proof sketch.* As shown in [15], CGate SUC-securely computes $T_{CSZ}$ in the $\mathcal{G}$-hybrid model. Consequently, by the composition theorem, it is sufficient to show that $Q = P_{tally}^{T_{CSZ}, T_{DecMixnet}}$ SUC-securely computes $T_{tally}$ in the $(\mathcal{G}, \mathcal{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}$. $\square$

# 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 [6], 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 $(\mathcal{K}, \mathcal{E}, \mathcal{D})$ be an encryption scheme. We say that it is IND-PA0 if, for all (stateful) PPT adversary $\mathcal{A}$, its advantage in the game depicted in Algorithm 13 is negligible in the security parameter $\lambda$. 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 $\lambda$-bits credential $c = c_1, \dots, c_\lambda$ and voting option $\nu$, recall that $\text{Vote}_{pk}(c, \nu)$ is obtained by computing the encryptions $C_1 = \text{Enc}_{pk}(\nu)$ and $C_2 = (\text{Enc}_{pk}(g^{c_1}), \dots, \text{Enc}_{pk}(g^{c_\lambda}))$, where $g$ is a public group element. Then, a NIZKPoK $\pi_1$ of the plaintexts $(c, \nu)$ 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 $\Sigma$-protocol. Finally, a ZKP $\pi_2$ that $(c, \nu)$ is valid is computed and the ballot $(C_1, C_2, \pi_1, \pi_2)$ is formed. Clearly, $\text{Vote}_{pk}(c, \nu)$ can be seen as an encryption of the tuple $(c, \nu)$ by the encryption scheme (Gen, Vote, Extract), where the Extract algorithm first checks the ZKPs and outputs $\perp$ if any of the proof is invalid. Otherwise, it decrypts all the ciphertexts with the secret key and returns the tuple $(c, \nu)$. By a result of [8], this defines an NM-CPA encryption scheme, which is therefore IND-PA0 secure. Note that $\pi_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 $(\lambda+1)$-tuples of plaintexts (resp. ciphertexts, along with the corresponding ZKP).
## 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 $\mathcal{F}_{RO}$, and we also suppose that the DKG and the decryption mixnet are SUC-secure. We denote $\mathcal{F}_{DKG}$ and $\mathcal{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 [40], [41].

Hence, we place ourselves in the $\mathcal{G}$-hybrid model, where $\mathcal{G} = (\mathcal{F}_{RO}, \mathcal{F}_{DecMixnet})$.

Following [15], 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, \pi_1, \pi_2)$ with valid ZKP $\pi_1, \pi_2$ as defined in Section IV, where $C_1$ is a valid ElGamal encryption (that is, any pair of group elements) and $C_2 \lambda$ 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 [15]'s result, where the CGate protocol is shown to SUC-securely computing $T_{CSZ}$ in the $\mathcal{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 $\mathcal{G}$-hybrid model.*

*Proof sketch.* As shown in [15], CGate SUC-securely computes $T_{CSZ}$ in the $\mathcal{G}$-hybrid model. Consequently, by the composition theorem, it is sufficient to show that $Q = P_{tally}^{T_{CSZ}, T_{DecMixnet}}$ SUC-securely computes $T_{tally}$ in the $(\mathcal{G}, \mathcal{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}$. $\square$

# 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 [6], 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 $(\mathcal{K}, \mathcal{E}, \mathcal{D})$ be an encryption scheme. We say that it is IND-PA0 if, for all (stateful) PPT adversary $\mathcal{A}$, its advantage in the game depicted in Algorithm 13 is negligible in the security parameter $\lambda$. 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 $\lambda$-bits credential $c = c_1, \dots, c_\lambda$ and voting option $\nu$, recall that $\text{Vote}_{pk}(c, \nu)$ is obtained by computing the encryptions $C_1 = \text{Enc}_{pk}(\nu)$ and $C_2 = (\text{Enc}_{pk}(g^{c_1}), \dots, \text{Enc}_{pk}(g^{c_\lambda}))$, where $g$ is a public group element. Then, a NIZKPoK $\pi_1$ of the plaintexts $(c, \nu)$ 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 $\Sigma$-protocol. Finally, a ZKP $\pi_2$ that $(c, \nu)$ is valid is computed and the ballot $(C_1, C_2, \pi_1, \pi_2)$ is formed. Clearly, $\text{Vote}_{pk}(c, \nu)$ can be seen as an encryption of the tuple $(c, \nu)$ by the encryption scheme (Gen, Vote, Extract), where the Extract algorithm first checks the ZKPs and outputs $\perp$ if any of the proof is invalid. Otherwise, it decrypts all the ciphertexts with the secret key and returns the tuple $(c, \nu)$. By a result of [8], this defines an NM-CPA encryption scheme, which is therefore IND-PA0 secure. Note that $\pi_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 $(\lambda+1)$-tuples of plaintexts (resp. ciphertexts, along with the corresponding ZKP).
<table>
  <caption>Algorithm 13: IND-PA0 game</caption>
  <thead>
    <tr>
      <th>Step</th>
      <th>Description</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>1</td>
      <td>(pk, sk) ← K(λ)</td>
    </tr>
    <tr>
      <td>2</td>
      <td>(x<sub>0</sub>, x<sub>1</sub>) ← A(pk)</td>
    </tr>
    <tr>
      <td>3</td>
      <td>b ← {0, 1}</td>
    </tr>
    <tr>
      <td>4</td>
      <td>y ← E<sub>pk</sub>(x<sub>b</sub>)</td>
    </tr>
    <tr>
      <td>5</td>
      <td>c ← A(y)</td>
    </tr>
    <tr>
      <td>6</td>
      <td>p ← D<sub>sk</sub>(c)</td>
    </tr>
    <tr>
      <td>7</td>
      <td>b' ← A(p)</td>
    </tr>
    <tr>
      <td>8</td>
      <td>Return 1 if and only if (y ∉ c) ∧ (b' = b)</td>
    </tr>
  </tbody>
</table>

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 $\mathbb{A}_0$ for Game 0. For Game $i$, we construct a PPT adversary $\mathbb{A}_i$ for this game and we denote $S_i$ the probability that $\mathbb{A}_i$ wins this game. (To ease the notation, we drop the dependency in $\lambda$ 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_{\text{tally}}$.

By Theorem 3, there exists a simulator $S$ such that, for all environment $Z$, $|\text{Real}_{P_{\text{tally}}, \mathbb{A}_0, Z}^{\text{SUC}, G}(\lambda, z)(\lambda, 0) - \text{Ideal}_{T_{\text{tally}}, S, Z}^{\text{SUC}}(\lambda, 0)|$ is negligible. In particular, we consider the environment which defines Game 0, so that $\text{Real}_{P_{\text{tally}}, \mathbb{A}_0, Z}^{\text{SUC}, G}(\lambda, z)(\lambda, 0) = S_0$. Then, $\mathbb{A}_1$ can interact with $\mathbb{A}_0$ by simulating the real game using $S$, so that $\text{Ideal}_{T_{\text{tally}}, S, Z}^{\text{SUC}}(\lambda, 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 $\mu_2$ and an adversary $\mathbb{A}_2$ for Game 2 such that $|S_2 - S_1| \le \mu_2$.

**Game 3:** In this game, the adversary is no longer given the output of the conditional gates, that we denote $\Pi^Z$.

We construct $\mathbb{A}_3$ that interacts with $\mathbb{A}_2$ by simulating $\Pi^Z$. For this purpose, $\mathbb{A}_3$ uses uniformly random ciphertexts.

To argue the validity of this transition, we construct an adversary $\mathbb{B}$ for DDH as follows. First, $\mathbb{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, $\mathbb{B}$ recovers the set $S$ of the corrupted participants from $\mathbb{A}_2$, and picks $s_i \in \mathbb{Z}_q$ at random for all $i \in S$. It completes $S$ into $I$ by picking some additional $s_i \in \mathbb{Z}_q$ at random for all $i \in I \setminus S$, where $I \subset [1, n_T]$ is a set of size $t$ that contains $S$, and $n_T$ is the number of talliers. For $i \in I$, it computes $h_i = g_1^{s_i}$ and, for $i \in [1, n_T] \setminus I$, it deduces $h_i$ with Lagrange interpolation.

It then runs the remaining of Game 3honestly, but each time $\mathbb{A}_2$ casts a ballot, $\mathbb{B}$ extracts the corresponding voting option from $\mathbb{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, $\mathbb{B}$ can compute the result $r$ of the tally without knowing the secret key sk. Finally, since $\mathbb{B}$ knows the cleartexts of the ballots to tally, $\mathbb{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, $\mathbb{B}$ “encrypts” the corresponding cleartext $z$ by choosing two random $\rho_1, \rho_2 \in \mathbb{Z}_q$ and computing $Z = (g^{\rho_1}g_3^{\rho_2}, g^zg_2^{\rho_1}g_4^{\rho_2})$. Finally, if $\mathbb{A}_2$ wins the game, $\mathbb{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 $\mathbb{B}$ played a perfect simulation of Game 2to $\mathbb{A}_2$ and hence wins with probability $S_2$. On the other hand, if the challenge tuple is a random tuple, $\mathbb{B}$ played $\mathbb{A}_3$'s simulation of Game 2and wins with probability $1 - S_3$. Yet, under the DDH assumption, $\mathbb{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, \nu)$ in $B$ by an occurrence of the form $(\tilde{x}, \nu)$ which uses a fresh and unique $\tilde{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 $\mathbb{A}_4 = \mathbb{A}_3$ and to argue that $|S_4 - S_3|$ is negligible, we give another succession of hops $H_0, \dots, H_{n_r}$ such that in game $H_i$, we replace the last $i$ revotes as described above. This way, $H_0$ is Game 3 and $H_{n_r}$ is Game 4. For each of these games, we denote $W_i$ the probability that $\mathbb{A}_4$ wins this game.
<table>
  <caption>Algorithm 13: IND-PA0 game</caption>
  <thead>
    <tr>
      <th>Step</th>
      <th>Description</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>1</td>
      <td>(pk, sk) ← K(λ)</td>
    </tr>
    <tr>
      <td>2</td>
      <td>(x<sub>0</sub>, x<sub>1</sub>) ← A(pk)</td>
    </tr>
    <tr>
      <td>3</td>
      <td>b ← {0, 1}</td>
    </tr>
    <tr>
      <td>4</td>
      <td>y ← E<sub>pk</sub>(x<sub>b</sub>)</td>
    </tr>
    <tr>
      <td>5</td>
      <td>c ← A(y)</td>
    </tr>
    <tr>
      <td>6</td>
      <td>p ← D<sub>sk</sub>(c)</td>
    </tr>
    <tr>
      <td>7</td>
      <td>b' ← A(p)</td>
    </tr>
    <tr>
      <td>8</td>
      <td>Return 1 if and only if (y ∉ c) ∧ (b' = b)</td>
    </tr>
  </tbody>
</table>

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 $\mathbb{A}_0$ for Game 0. For Game $i$, we construct a PPT adversary $\mathbb{A}_i$ for this game and we denote $S_i$ the probability that $\mathbb{A}_i$ wins this game. (To ease the notation, we drop the dependency in $\lambda$ 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_{\text{tally}}$.

By Theorem 3, there exists a simulator $S$ such that, for all environment $Z$, $|\text{Real}_{P_{\text{tally}}, \mathbb{A}_0, Z}^{\text{SUC}, G}(\lambda, z)(\lambda, 0) - \text{Ideal}_{T_{\text{tally}}, S, Z}^{\text{SUC}}(\lambda, 0)|$ is negligible. In particular, we consider the environment which defines Game 0, so that $\text{Real}_{P_{\text{tally}}, \mathbb{A}_0, Z}^{\text{SUC}, G}(\lambda, z)(\lambda, 0) = S_0$. Then, $\mathbb{A}_1$ can interact with $\mathbb{A}_0$ by simulating the real game using $S$, so that $\text{Ideal}_{T_{\text{tally}}, S, Z}^{\text{SUC}}(\lambda, 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 $\mu_2$ and an adversary $\mathbb{A}_2$ for Game 2 such that $|S_2 - S_1| \le \mu_2$.

**Game 3:** In this game, the adversary is no longer given the output of the conditional gates, that we denote $\Pi^Z$.

We construct $\mathbb{A}_3$ that interacts with $\mathbb{A}_2$ by simulating $\Pi^Z$. For this purpose, $\mathbb{A}_3$ uses uniformly random ciphertexts.

To argue the validity of this transition, we construct an adversary $\mathbb{B}$ for DDH as follows. First, $\mathbb{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, $\mathbb{B}$ recovers the set $S$ of the corrupted participants from $\mathbb{A}_2$, and picks $s_i \in \mathbb{Z}_q$ at random for all $i \in S$. It completes $S$ into $I$ by picking some additional $s_i \in \mathbb{Z}_q$ at random for all $i \in I \setminus S$, where $I \subset [1, n_T]$ is a set of size $t$ that contains $S$, and $n_T$ is the number of talliers. For $i \in I$, it computes $h_i = g_1^{s_i}$ and, for $i \in [1, n_T] \setminus I$, it deduces $h_i$ with Lagrange interpolation.

It then runs the remaining of Game 3honestly, but each time $\mathbb{A}_2$ casts a ballot, $\mathbb{B}$ extracts the corresponding voting option from $\mathbb{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, $\mathbb{B}$ can compute the result $r$ of the tally without knowing the secret key sk. Finally, since $\mathbb{B}$ knows the cleartexts of the ballots to tally, $\mathbb{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, $\mathbb{B}$ “encrypts” the corresponding cleartext $z$ by choosing two random $\rho_1, \rho_2 \in \mathbb{Z}_q$ and computing $Z = (g^{\rho_1}g_3^{\rho_2}, g^zg_2^{\rho_1}g_4^{\rho_2})$. Finally, if $\mathbb{A}_2$ wins the game, $\mathbb{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 $\mathbb{B}$ played a perfect simulation of Game 2to $\mathbb{A}_2$ and hence wins with probability $S_2$. On the other hand, if the challenge tuple is a random tuple, $\mathbb{B}$ played $\mathbb{A}_3$'s simulation of Game 2and wins with probability $1 - S_3$. Yet, under the DDH assumption, $\mathbb{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, \nu)$ in $B$ by an occurrence of the form $(\tilde{x}, \nu)$ which uses a fresh and unique $\tilde{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 $\mathbb{A}_4 = \mathbb{A}_3$ and to argue that $|S_4 - S_3|$ is negligible, we give another succession of hops $H_0, \dots, H_{n_r}$ such that in game $H_i$, we replace the last $i$ revotes as described above. This way, $H_0$ is Game 3 and $H_{n_r}$ is Game 4. For each of these games, we denote $W_i$ the probability that $\mathbb{A}_4$ wins this game.
Now, let $i$ be some index. We construct an adversary $\mathbb{B}$ for IND-PA0 (see Section C-A) as follows. First, $\mathbb{B}$ receives pk from the IND-PA0 game. It simulates game $H_i$ by giving this pk to $\mathbb{A}_4$ and generating the credentials at random. It then gets $(j, \alpha)$ from $H_i$ and chooses $b$ at random. Afterwards, $\mathbb{B}$ generates $\mathcal{B}$ from the distribution $\mathcal{B}$, $(j, \alpha)$ 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, \nu)$ with the same $x$ and generates a random, fresh credential $c$. It plays $(c_x, \nu)$, $(c, \nu)$ 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, \nu)$ (therefore, $C$ is added on the board). Finally, to compute the tally, $\mathbb{B}$ simply plays the concatenation of all the valid ballots sent by $\mathbb{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 $\mathbb{A}_4$ can be equal to $C$, so that the IND-PA0 will indeed accept to decrypt them. $\mathbb{B}$ computes the result of the tally from the plaintexts and gives it to $\mathbb{A}_4$ which answers with some bit $b'$. This is possible because every valid ballot of the board has a valid ZKP $\pi_2$, whose soundness guarantees that the corresponding plaintext $(c, \nu)$ is such that $c$ is a $\lambda$-bit credential and $\nu$ a valid voting option. If $b = b'$, $\mathbb{B}$ states that the IND-PA0 game encrypted $(c_x, \nu)$, and $(c, \nu)$ otherwise.

Clearly, when the IND-PA0 game encrypts $(c_x, \nu)$ (resp. $(c, \nu)$), $\mathbb{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, $\mathbb{B}$'s advantage in the IND-PA0 game is $|\frac{1}{2}(W_i + 1 - W_{i+1}) - \frac{1}{2}| \le \varepsilon_{PA0}$. By the triangular inequality,

$$|S_4 - S_3| \le 2n_r \varepsilon_{PA0}.$$

**Game 5:** In this game, the adversary no longer has access to the roster $\mathcal{R}$ at line 4. We construct $\mathbb{A}_5$ which interacts with $\mathbb{A}_4$ by simulating Game 4. For this purpose, it generates $n_V \lambda$ ElGamal encryptions of random bits and uses it to simulate $\mathcal{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, \dots, H_{n_V}$ such that in game $H_i$, the last $i$ elements of $\mathcal{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 $\mathbb{A}_4$ wins this game.

Now, let $i$ be some index. We construct an adversary $\mathbb{B}$ for IND-PA0 as follows. $\mathbb{B}$ gets pk from the IND-PA0 game and plays this pk to $\mathbb{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 $\mathcal{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$. $\mathbb{B}$ retrieves an ElGamal bitwise encryption of the credential from $C$ and uses it as the $(n_V - i)$th element of $\mathcal{R}$ instead of an honest bitwise encryption of $c_{n_V - i}$. Afterwards, $\mathbb{B}$ continues the simulation of $H_i$ (see the transition to Game 4 for more details) and outputs 1 if and only if $\mathbb{A}_4$ wins the game.

Clearly, when the IND-PA0 encrypts $(c_{n_V - i}, 1)$ (resp. $(c, 1)$), $\mathbb{B}$ plays a perfect simulation of game $H_i$ (resp. $H_{i+1}$) to $\mathbb{A}_4$, so that the advantage of $\mathbb{B}$ in the IND-PA0 game is $|\frac{1}{2}(W_i + 1 - W_{i+1}) - \frac{1}{2}| \le \varepsilon_{PA0}$. By the triangular inequality,

$$|S_5 - S_4| \le 2n_V \varepsilon_{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, \nu_i)$ with $i \in [1, n_V] \setminus (A \cup \{j\})$), we abort the game and output a random bit.

Now, we set $\mathbb{A}_6 = \mathbb{A}_5$ and, to argue that $|S_6 - S_5|$ is negligible, we remark that $|S_6 - S_5| = \varepsilon/2$, where $\varepsilon$ is the probability that we abort in Game 6. Let $E$ be the event of an abortion. We construct an adversary $\mathbb{B}$ for IND-PA0 which wins with a non-negligible advantage whenever $E$ occurs and wins with probability $1/2$ otherwise, which shows that $\varepsilon$ is negligible.

First, $\mathbb{B}$ gets pk from the IND-PA0 game and forwards it to $\mathbb{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), $\mathbb{B}$ plays the pair $(c_x, \nu)$, $(c, \nu)$ in the IND-PA0 game, where $\nu$ 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, $\mathbb{B}$ gets the list of all valid ballots sent by $\mathbb{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$), $\mathbb{B}$ states that the IND-PA0 encrypted $(c_x, \nu)$ (resp. $(c, \nu)$). If there is no such ballot, a ballot which uses $c$ and a ballot which uses $c_x$ or if no honest voter votes, $\mathbb{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, \nu)$ (resp. $(c, \nu)$). Let $q$ be the number of valid ballots sent by $\mathbb{A}_5$. With probability $\varepsilon$, $\mathbb{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 $\mathbb{B}$ gets the decryption from the IND-PA0 game, there is a ballot of the form $(c_x, \gamma)$ (resp. $(c, \gamma)$). In addition, $\mathbb{A}_5$ has no information about $c$ (resp. $c_x$) so that with probability at least $1 - q/2^{\lambda}$, there is no ballot of the form $(c, \gamma)$ (resp. $(c_x, \gamma)$). Hence $\mathbb{B}$ wins with probability at least $1 - q/2^{\lambda+1}$. Otherwise, no ballot uses the credential $c_x$ (resp. $c$) and since the
Now, let $i$ be some index. We construct an adversary $\mathbb{B}$ for IND-PA0 (see Section C-A) as follows. First, $\mathbb{B}$ receives pk from the IND-PA0 game. It simulates game $H_i$ by giving this pk to $\mathbb{A}_4$ and generating the credentials at random. It then gets $(j, \alpha)$ from $H_i$ and chooses $b$ at random. Afterwards, $\mathbb{B}$ generates $B$ from the distribution $\mathcal{B}$, $(j, \alpha)$ 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, \nu)$ with the same $x$ and generates a random, fresh credential $c$. It plays $(c_x, \nu)$, $(c, \nu)$ 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, \nu)$ (therefore, $C$ is added on the board). Finally, to compute the tally, $\mathbb{B}$ simply plays the concatenation of all the valid ballots sent by $\mathbb{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 $\mathbb{A}_4$ can be equal to $C$, so that the IND-PA0 will indeed accept to decrypt them. $\mathbb{B}$ computes the result of the tally from the plaintexts and gives it to $\mathbb{A}_4$ which answers with some bit $b'$. This is possible because every valid ballot of the board has a valid ZKP $\pi_2$, whose soundness guarantees that the corresponding plaintext $(c, \nu)$ is such that $c$ is a $\lambda$-bit credential and $\nu$ a valid voting option. If $b = b'$, $\mathbb{B}$ states that the IND-PA0 game encrypted $(c_x, \nu)$, and $(c, \nu)$ otherwise.

Clearly, when the IND-PA0 game encrypts $(c_x, \nu)$ (resp. $(c, \nu)$), $\mathbb{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, $\mathbb{B}$'s advantage in the IND-PA0 game is $|\frac{1}{2}(W_i + 1 - W_{i+1}) - \frac{1}{2}| \le \varepsilon_{PA0}$. By the triangular inequality,

$$|S_4 - S_3| \le 2n_r \varepsilon_{PA0}.$$

**Game 5:** In this game, the adversary no longer has access to the roster $\mathcal{R}$ at line 4. We construct $\mathbb{A}_5$ which interacts with $\mathbb{A}_4$ by simulating Game 4. For this purpose, it generates $n_V \lambda$ ElGamal encryptions of random bits and uses it to simulate $\mathcal{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, \dots, H_{n_V}$ such that in game $H_i$, the last $i$ elements of $\mathcal{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 $\mathbb{A}_4$ wins this game.

Now, let $i$ be some index. We construct an adversary $\mathbb{B}$ for IND-PA0 as follows. $\mathbb{B}$ gets pk from the IND-PA0 game and plays this pk to $\mathbb{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 $\mathcal{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$. $\mathbb{B}$ retrieves an ElGamal bitwise encryption of the credential from $C$ and uses it as the $(n_V - i)$th element of $\mathcal{R}$ instead of an honest bitwise encryption of $c_{n_V - i}$. Afterwards, $\mathbb{B}$ continues the simulation of $H_i$ (see the transition to Game 4 for more details) and outputs 1 if and only if $\mathbb{A}_4$ wins the game.

Clearly, when the IND-PA0 encrypts $(c_{n_V - i}, 1)$ (resp. $(c, 1)$), $\mathbb{B}$ plays a perfect simulation of game $H_i$ (resp. $H_{i+1}$) to $\mathbb{A}_4$, so that the advantage of $\mathbb{B}$ in the IND-PA0 game is $|\frac{1}{2}(W_i + 1 - W_{i+1}) - \frac{1}{2}| \le \varepsilon_{PA0}$. By the triangular inequality,

$$|S_5 - S_4| \le 2n_V \varepsilon_{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, \nu_i)$ with $i \in [1, n_V] \setminus (A \cup \{j\})$), we abort the game and output a random bit.

Now, we set $\mathbb{A}_6 = \mathbb{A}_5$ and, to argue that $|S_6 - S_5|$ is negligible, we remark that $|S_6 - S_5| = \varepsilon/2$, where $\varepsilon$ is the probability that we abort in Game 6. Let $E$ be the event of an abortion. We construct an adversary $\mathbb{B}$ for IND-PA0 which wins with a non-negligible advantage whenever $E$ occurs and wins with probability $1/2$ otherwise, which shows that $\varepsilon$ is negligible.

First, $\mathbb{B}$ gets pk from the IND-PA0 game and forwards it to $\mathbb{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), $\mathbb{B}$ plays the pair $(c_x, \nu)$, $(c, \nu)$ in the IND-PA0 game, where $\nu$ 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, $\mathbb{B}$ gets the list of all valid ballots sent by $\mathbb{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$), $\mathbb{B}$ states that the IND-PA0 encrypted $(c_x, \nu)$ (resp. $(c, \nu)$). If there is no such ballot, a ballot which uses $c$ and a ballot which uses $c_x$ or if no honest voter votes, $\mathbb{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, \nu)$ (resp. $(c, \nu)$). Let $q$ be the number of valid ballots sent by $\mathbb{A}_5$. With probability $\varepsilon$, $\mathbb{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 $\mathbb{B}$ gets the decryption from the IND-PA0 game, there is a ballot of the form $(c_x, \gamma)$ (resp. $(c, \gamma)$). In addition, $\mathbb{A}_5$ has no information about $c$ (resp. $c_x$) so that with probability at least $1 - q/2^{\lambda}$, there is no ballot of the form $(c, \gamma)$ (resp. $(c_x, \gamma)$). Hence $\mathbb{B}$ wins with probability at least $1 - q/2^{\lambda+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^\lambda$. Therefore, the probability that $\mathbb{B}$ wins the IND-PA0 game is at least $(1 - q/2^\lambda)/2$. Overall, $\mathbb{B}$'s probability to win is at least

$$ \frac{\varepsilon}{n_H}(1 - q/2^{\lambda+1}) + (1 - \frac{\varepsilon}{n_H})(1 - q/2^{\lambda})/2 = \frac{1}{2} + \frac{\varepsilon}{2n_H} - \frac{q}{2^{\lambda+1}}. $$

Therefore, we have

$$ \frac{\varepsilon}{2n_H} - \frac{q}{2^{\lambda+1}} \le \mathrm{Adv}_{\mathbb{B}}^{\mathrm{IND}-\mathrm{PA0}} \le \varepsilon_{\mathrm{PA0}}, $$

hence $|S_6 - S_5| = \varepsilon/2 \le n_H \varepsilon_{\mathrm{PA0}} + \frac{q n_H}{2^{\lambda+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 $\mathbb{A}_7$ which interacts with $\mathbb{A}_6$ by simulating Game 6. For this purpose, $\mathbb{A}_7$ gets $BB = (B_1, \dots, B_n)$ at line 26 and creates a fake empty ballot box $BB'$. Then, in the $k$th iteration of the for loop, it simply appends to $BB'$ the valid ballots output by $\mathbb{A}_6$ and then $B_k$. The remaining of the simulation is similar to that of the transition to Game 4.

Clearly, $\mathbb{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 $\mathbb{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 $\mathbb{A}_7$'s probability to win is the same as $\mathbb{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 $\mathbb{A}_8$ and we have

$$ |S_8 - S_7| \le |BB| \varepsilon_{\mathrm{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 $\mathbb{A}_9$ which interacts with $\mathbb{A}_8$ by simulating Game 8. For this purpose, $\mathbb{A}_9$ creates a HashMap with keys $\{c_i; i \in A\}$ and $\tilde{c}$ and values $(\nu_i)_{i \in A}$ and $\beta$ which are initially $\phi$. For each ballot $C \in M$, $\mathbb{A}_9$ extracts $(c, \nu)$ from the ZKPoK and, if $c$ is a key of the HashMap, it changes the corresponding value to $\nu$. It plays the obtained values in Game 9 and receives the result of the tally which it forwards to $\mathbb{A}_8$. Finally, it outputs $\mathbb{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 $\mathbb{A}$ for the real game, there exists an adversary $\mathbb{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. $\square$)

### C. Privacy

1) *Our definition of privacy:* In [30], 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 in Section III-A and a voter under observation either chooses option $\nu_0$ or $\nu_1$, where $(\nu_0, \nu_1)$ can be chosen by the adversary. The latter must decide which was chosen, and do so with an advantage $\mathrm{Adv}(\mathbb{A})$. A Voting system is then said $\delta$-private if, for all adversary, $2\mathrm{Adv}(\mathbb{A}) \le \delta + \mu$, where $\mu$ is some negligible function.

This definition can be turned into a qualitative one when $\delta$ is shown to be minimal, in a sense that an ideal protocol achieves $\delta$-privacy with a negligible $|\delta - \delta'|$. 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 [30], 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_{\mathrm{Setup}}$, in which the adversary can impersonate up to $t$ corrupted authorities. Then the voters are registered and the roster $\mathbb{R}$ is published. The adversary can corrupt voters and chooses a voter under observation $j$. Then the honest voters vote according to a distribution $\mathbb{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 $(\nu_0, \nu_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_{\mathrm{tally}}$, during which the adversary can impersonate the corrupted authorities (we only consider static corruption). Finally, the adversary must guess whether $\nu_0$ or $\nu_1$ was chosen.
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^\lambda$. Therefore, the probability that $\mathbb{B}$ wins the IND-PA0 game is at least $(1 - q/2^\lambda)/2$. Overall, $\mathbb{B}$'s probability to win is at least

$$ \frac{\varepsilon}{n_H}(1 - q/2^{\lambda+1}) + (1 - \frac{\varepsilon}{n_H})(1 - q/2^{\lambda})/2 = \frac{1}{2} + \frac{\varepsilon}{2n_H} - \frac{q}{2^{\lambda+1}} $$

Therefore, we have

$$ \frac{\varepsilon}{2n_H} - \frac{q}{2^{\lambda+1}} \le \mathrm{Adv}_{\mathbb{B}}^{\mathrm{IND}-\mathrm{PA0}} \le \varepsilon_{\mathrm{PA0}}, $$

hence $|S_6 - S_5| = \varepsilon/2 \le n_H \varepsilon_{\mathrm{PA0}} + \frac{q n_H}{2^{\lambda+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 $\mathbb{A}_7$ which interacts with $\mathbb{A}_6$ by simulating Game 6. For this purpose, $\mathbb{A}_7$ gets $BB = (B_1, \dots, B_n)$ at line 26 and creates a fake empty ballot box $BB'$. Then, in the $k$th iteration of the for loop, it simply appends to $BB'$ the valid ballots output by $\mathbb{A}_6$ and then $B_k$. The remaining of the simulation is similar to that of the transition to Game 4.

Clearly, $\mathbb{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 $\mathbb{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 $\mathbb{A}_7$'s probability to win is the same as $\mathbb{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 $\mathbb{A}_8$ and we have

$$ |S_8 - S_7| \le |BB| \varepsilon_{\mathrm{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 $\mathbb{A}_9$ which interacts with $\mathbb{A}_8$ by simulating Game 8. For this purpose, $\mathbb{A}_9$ creates a hashtable with keys $\{c_i; i \in A\}$ and $\tilde{c}$ and values $(\nu_i)_{i \in A}$ and $\beta$ which are initially $\phi$. For each ballot $C \in M$, $\mathbb{A}_9$ extracts $(c, \nu)$ from the ZKPoK and, if $c$ is a key of the hashtable, it changes the corresponding value to $\nu$. It plays the obtained values in Game 9 and receives the result of the tally which it forwards to $\mathbb{A}_8$. Finally, it outputs $\mathbb{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 $\mathbb{A}$ for the real game, there exists an adversary $\mathbb{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. $\square$)

### C. Privacy

1) *Our definition of privacy:* In [30], 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 in Section III-A and a voter under observation either chooses option $\nu_0$ or $\nu_1$, where $(\nu_0, \nu_1)$ can be chosen by the adversary. The latter must decide which was chosen, and do so with an advantage $\mathrm{Adv}(\mathbb{A})$. A Voting system is then said $\delta$-private if, for all adversary, $2\mathrm{Adv}(\mathbb{A}) \le \delta + \mu$, where $\mu$ is some negligible function.

This definition can be turned into a qualitative one when $\delta$ is shown to be minimal, in a sense that an ideal protocol achieves $\delta$-privacy with a negligible $|\delta - \delta'|$. 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 [30], 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_{\mathrm{Setup}}$, in which the adversary can impersonate up to $t$ corrupted authorities. Then the voters are registered and the roster $\mathbb{R}$ is published. The adversary can corrupt voters and chooses a voter under observation $j$. Then the honest voters vote according to a distribution $\mathbb{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 $(\nu_0, \nu_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_{\mathrm{tally}}$, during which the adversary can impersonate the corrupted authorities (we only consider static corruption). Finally, the adversary must guess whether $\nu_0$ or $\nu_1$ was chosen.
<table>
  <thead>
    <tr>
      <th colspan="2">Algorithm 14: Real<sup>Priv</sup></th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td colspan="2">Require: A, λ, n<sub>T</sub>, t, n<sub>V</sub>, n<sub>A</sub>, n<sub>C</sub>, B</td>
    </tr>
    <tr>
      <td>1</td>
      <td>BB ← ∅</td>
    </tr>
    <tr>
      <td>2</td>
      <td>pk, (s<sub>i</sub>, h<sub>i</sub>)<sup>n<sub>T</sub></sup><sub>i=1</sub> ← P<sup>A</sup><sub>setup</sub>(λ, n<sub>T</sub>, t)</td>
    </tr>
    <tr>
      <td>3</td>
      <td>{c<sub>i</sub>; i ∈ [1, n<sub>V</sub>]}, R ← register(λ, pk, n<sub>V</sub>)</td>
    </tr>
    <tr>
      <td>4</td>
      <td>A ← A(R)</td>
    </tr>
    <tr>
      <td>5</td>
      <td>j, ν<sub>0</sub>, ν<sub>1</sub> ← A({c<sub>i</sub>; i ∈ A})</td>
    </tr>
    <tr>
      <td>6</td>
      <td>(* A chooses the voter under observation *)</td>
    </tr>
    <tr>
      <td>7</td>
      <td>if |A| ≠ n<sub>A</sub> ∨ j ∉ [1, n<sub>V</sub>] \ A then</td>
    </tr>
    <tr>
      <td>8</td>
      <td>Return 0</td>
    </tr>
    <tr>
      <td>9</td>
      <td>B ← B([1, n<sub>V</sub>] \ A, n<sub>C</sub>)</td>
    </tr>
    <tr>
      <td>10</td>
      <td>for (i, ν<sub>i</sub>) ∈ B do</td>
    </tr>
    <tr>
      <td>11</td>
      <td>M ← A(BB)</td>
    </tr>
    <tr>
      <td>12</td>
      <td>BB ← BB ∪ {m ∈ M | isVal(pk, m, BB) = 1}</td>
    </tr>
    <tr>
      <td>13</td>
      <td>BB ← BB ∪ {Vote<sub>pk</sub>(c<sub>i</sub>, ν<sub>i</sub>)}; A(i)</td>
    </tr>
    <tr>
      <td>14</td>
      <td>M ← A(BB, "last honest ballot sent")</td>
    </tr>
    <tr>
      <td>15</td>
      <td>BB ← BB ∪ {m ∈ M | isVal(pk, m, BB) = 1}</td>
    </tr>
    <tr>
      <td>16</td>
      <td>b ← {0, 1}</td>
    </tr>
    <tr>
      <td>17</td>
      <td>BB ← BB ∪ {Vote<sub>pk</sub>(c<sub>j</sub>, ν<sub>b</sub>)}</td>
    </tr>
    <tr>
      <td>18</td>
      <td>M ← A(BB)</td>
    </tr>
    <tr>
      <td>19</td>
      <td>BB ← BB ∪ {m ∈ M | isVal(pk, m, BB) = 1}</td>
    </tr>
    <tr>
      <td>20</td>
      <td>X, Π ← P<sup>A</sup><sub>tally</sub>(BB, R, pk, {h<sub>i</sub>, s<sub>i</sub>}, t)</td>
    </tr>
    <tr>
      <td>21</td>
      <td>b' ← A()</td>
    </tr>
    <tr>
      <td>22</td>
      <td>Return 1 if ν<sub>0</sub>, ν<sub>1</sub> ∈ [1, n<sub>C</sub>] ∧ b' == b else 0</td>
    </tr>
  </tbody>
</table>

<table><caption>Fig. 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.</caption>
  <thead>
    <tr>
      <th colspan="2">Algorithm 15: Ideal<sup>Priv</sup></th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td colspan="2">Require: A, λ, n<sub>T</sub>, t, n<sub>V</sub>, n<sub>A</sub>, n<sub>C</sub>, B</td>
    </tr>
    <tr>
      <td>1</td>
      <td></td>
    </tr>
    <tr>
      <td>2</td>
      <td></td>
    </tr>
    <tr>
      <td>3</td>
      <td></td>
    </tr>
    <tr>
      <td>4</td>
      <td>A ← A(λ)</td>
    </tr>
    <tr>
      <td>5</td>
      <td>j, v<sub>0</sub>, v<sub>1</sub> ← A()</td>
    </tr>
    <tr>
      <td>6</td>
      <td></td>
    </tr>
    <tr>
      <td>7</td>
      <td>if |A| ≠ n<sub>A</sub> ∨ j ∉ [1, n<sub>V</sub>] \ A then</td>
    </tr>
    <tr>
      <td>8</td>
      <td>Return 0</td>
    </tr>
    <tr>
      <td>9</td>
      <td>B ← B([1, n<sub>V</sub>] \ (A ∪ {j})), n<sub>C</sub>)</td>
    </tr>
    <tr>
      <td>10</td>
      <td>I ← (i) (i,v)∈B</td>
    </tr>
    <tr>
      <td>11</td>
      <td></td>
    </tr>
    <tr>
      <td>12</td>
      <td></td>
    </tr>
    <tr>
      <td>13</td>
      <td></td>
    </tr>
    <tr>
      <td>14</td>
      <td>(α<sub>i</sub>)<sub>i∈A</sub> ← A(I)</td>
    </tr>
    <tr>
      <td>15</td>
      <td>B ← B ∪ {(i, α<sub>i</sub>) | i ∈ A, α<sub>i</sub> ∈ [1, n<sub>C</sub>]};</td>
    </tr>
    <tr>
      <td>16</td>
      <td>b ← {0, 1}</td>
    </tr>
    <tr>
      <td>17</td>
      <td>B ← B ∪ {(j, v<sub>b</sub>)};</td>
    </tr>
    <tr>
      <td>18</td>
      <td></td>
    </tr>
    <tr>
      <td>19</td>
      <td></td>
    </tr>
    <tr>
      <td>20</td>
      <td>r ← tally(cleanse(B))</td>
    </tr>
    <tr>
      <td>21</td>
      <td>b' ← A(r)</td>
    </tr>
    <tr>
      <td>22</td>
      <td>Return 1 if v<sub>0</sub>, v<sub>1</sub> ∈ [1, n<sub>C</sub>] ∧ b' == b else 0</td>
    </tr>
  </tbody>
</table>

The ideal process is simpler. The adversary still corrupts $n_A$ voters and chooses $(v_0, v_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 \le n_V$, for all distribution $B$ and for all PPT adversary $A$, there exists a PPT adversary $\mathcal{B}$ and a negligible function $\mu$ such that

$$|\Pr(\text{Real}^{\text{Priv}}(A, \lambda, n_T, t, n_V, n_A, n_C, \mathcal{B}) = 1) - \Pr(\text{Ideal}^{\text{Priv}}(\mathcal{B}, \lambda, n_T, t, n_V, n_A, n_C, \mathcal{B}) = 1)| \le \mu(\lambda).$$

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<sup>CR</sup> and Real<sup>Priv</sup>. Just as for coercion-resistance, we make several assumptions; the main difference is that we no longer assume anonymous channels for voting.

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

*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 $\lambda$ 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 $\Pi^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, v)$ in $B$ by an occurrence of the form $(x \to \tilde{x}, v)$ where $\tilde{x}$ is a fresh
<table><thead><tr><th></th><th></th></tr></thead><tbody><tr><td>Algorithm 14: Real<sup>Priv</sup></td><td></td></tr><tr><td>Require: A, λ, n<sub>T</sub>, t, n<sub>V</sub>, n<sub>A</sub>, n<sub>C</sub>, B</td><td></td></tr><tr><td>1</td><td>BB ← ∅</td></tr><tr><td>2</td><td>pk, (s<sub>i</sub>, h<sub>i</sub>)<sup>n<sub>T</sub></sup><sub>i=1</sub> ← P<sup>A</sup><sub>setup</sub>(λ, n<sub>T</sub>, t)</td></tr><tr><td>3</td><td>{c<sub>i</sub>; i ∈ [1, n<sub>V</sub>]}, R ← register(λ, pk, n<sub>V</sub>)</td></tr><tr><td>4</td><td>A ← A(R)</td></tr><tr><td>5</td><td>j, ν<sub>0</sub>, ν<sub>1</sub> ← A({c<sub>i</sub>; i ∈ A})</td></tr><tr><td>6</td><td>(* A chooses the voter under observation *)</td></tr><tr><td>7</td><td>if |A| ≠ n<sub>A</sub> ∨ j ∉ [1, n<sub>V</sub>] \ A then</td></tr><tr><td>8</td><td>Return 0</td></tr><tr><td>9</td><td>B ← B([1, n<sub>V</sub>] \ A, n<sub>C</sub>)</td></tr><tr><td>10</td><td>for (i, ν<sub>i</sub>) ∈ B do</td></tr><tr><td>11</td><td>M ← A(BB)</td></tr><tr><td>12</td><td>BB ← BB ∪ {m ∈ M | isVal(pk, m, BB) = 1}</td></tr><tr><td>13</td><td>BB ← BB ∪ {Vote<sub>pk</sub>(c<sub>i</sub>, ν<sub>i</sub>)}; A(i)</td></tr><tr><td>14</td><td>M ← A(BB, "last honest ballot sent")</td></tr><tr><td>15</td><td>BB ← BB ∪ {m ∈ M | isVal(pk, m, BB) = 1}</td></tr><tr><td>16</td><td>b ← {0, 1}</td></tr><tr><td>17</td><td>BB ← BB ∪ {Vote<sub>pk</sub>(c<sub>j</sub>, ν<sub>b</sub>)}</td></tr><tr><td>18</td><td>M ← A(BB)</td></tr><tr><td>19</td><td>BB ← BB ∪ {m ∈ M | isVal(pk, m, BB) = 1}</td></tr><tr><td>20</td><td>X, Π ← P<sup>A</sup><sub>tally</sub>(BB, R, pk, {h<sub>i</sub>, s<sub>i</sub>}, t)</td></tr><tr><td>21</td><td>b' ← A()</td></tr><tr><td>22</td><td>Return 1 if ν<sub>0</sub>, ν<sub>1</sub> ∈ [1, n<sub>C</sub>] ∧ b' == b else 0</td></tr></tbody></table>

<table><caption>Fig. 9: Definition of privacy, λ is the security parameter, n<sub>T</sub> the number of talliers, t the threshold, n<sub>V</sub> the number of voters, n<sub>A</sub> the number of corrupted voters, n<sub>C</sub> the number of voting options (excluding abstention) and B the distribution.</caption><thead><tr><th></th><th></th></tr></thead><tbody><tr><td>Algorithm 15: Ideal<sup>Priv</sup></td><td></td></tr><tr><td>Require: A, λ, n<sub>T</sub>, t, n<sub>V</sub>, n<sub>A</sub>, n<sub>C</sub>, B</td><td></td></tr><tr><td>1</td><td></td></tr><tr><td>2</td><td></td></tr><tr><td>3</td><td></td></tr><tr><td>4</td><td>A ← A(λ)</td></tr><tr><td>5</td><td>j, ν<sub>0</sub>, ν<sub>1</sub> ← A()</td></tr><tr><td>6</td><td></td></tr><tr><td>7</td><td>if |A| ≠ n<sub>A</sub> ∨ j ∉ [1, n<sub>V</sub>] \ A then</td></tr><tr><td>8</td><td>Return 0</td></tr><tr><td>9</td><td>B ← B([1, n<sub>V</sub>] \ (A ∪ {j})), n<sub>C</sub>)</td></tr><tr><td>10</td><td>I ← (i)<sub>(i,ν)∈B</sub></td></tr><tr><td>11</td><td></td></tr><tr><td>12</td><td></td></tr><tr><td>13</td><td></td></tr><tr><td>14</td><td>(α<sub>i</sub>)<sub>i∈A</sub> ← A(I)</td></tr><tr><td>15</td><td>B ← B ∪ {(i, α<sub>i</sub>) | i ∈ A, α<sub>i</sub> ∈ [1, n<sub>C</sub>]}</td></tr><tr><td>16</td><td>b ← {0, 1}</td></tr><tr><td>17</td><td>B ← B ∪ {(j, ν<sub>b</sub>)}</td></tr><tr><td>18</td><td></td></tr><tr><td>19</td><td></td></tr><tr><td>20</td><td>r ← tally(cleanse(B))</td></tr><tr><td>21</td><td>b' ← A(r)</td></tr><tr><td>22</td><td>Return 1 if ν<sub>0</sub>, ν<sub>1</sub> ∈ [1, n<sub>C</sub>] ∧ b' == b else 0</td></tr></tbody></table>

The ideal process is simpler. The adversary still corrupts n<sub>A</sub> voters and chooses (ν<sub>0</sub>, ν<sub>1</sub>), 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<sub>setup</sub>, register, Vote, Check, isVal, Fakecred, P<sub>tally</sub>, Verify) guarantees vote privacy w.r.t. a result function tally if, for all parameters n<sub>T</sub>, t, n<sub>V</sub>, n<sub>A</sub>, n<sub>C</sub> with t < a and n<sub>A</sub> ≤ n<sub>V</sub>, for all distribution B and for all PPT adversary A, there exists a PPT adversary B and a negligible function μ such that

$$|\Pr(\text{Real}^{\text{Priv}}(A, \lambda, n_T, t, n_V, n_A, n_C, B) = 1) - \Pr(\text{Ideal}^{\text{Priv}}(B, \lambda, n_T, t, n_V, n_A, n_C, B) = 1)| \le \mu(\lambda).$$

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<sup>CR</sup> and Real<sup>Priv</sup>. Just as for coercion-resistance, we make several assumptions; the main difference is that we no longer assume anonymous channels for voting.

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

*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<sub>0</sub> for Game 0. For Game i, we construct a PPT adversary A<sub>i</sub> for this game and we denote S<sub>i</sub> the probability that A<sub>i</sub> wins this game. (To ease the notations, we drop the dependency in λ when the context is clear.) For all i, we show that |S<sub>i+1</sub> - S<sub>i</sub>| is negligible, which proves that |S<sub>0</sub> - S<sub>9</sub>| 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<sub>tally</sub>.

**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 Π<sup>Z</sup>.

**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, v)$ 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 $\mathbf{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, v_i)$ with $i \in [1, n_V] \setminus 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 now 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, v_0, v_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 $(v_i)_{i \in A}$, $A_9$ creates a hashtable with the keys $\{c_i; i \in A\}$, and values $(v_i)_{i \in A}$ (initially $\phi$, for abstention). For each valid ballot cast by $A_8$, $A_9$ decrypts the ballot using the secret key and deduces $(v, c)$. Since the ballot is valid, by the soundness of the ZKP, $c$ consists of $\lambda$ bits and $v$ is a valid voting option. If $c$ is a key of the hashtable, $A_9$ changes the corresponding value to $v$. (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$.

<figure><img src="image_9.png" /></figure>

## 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 [14] 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, $(v_1, v_2, v_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 $v_1$, $v_2$ or $v_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 $v_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_{\text{cast}}$ which takes as input a ballot $b$ (see Algorithm 17). If the ballot is valid w.r.t. $BB$, $O_{\text{cast}}$ adds $b$ to $BB$. The adversary also has access to $O_{\text{vote}}$, which models the ballots sent by the honest voters (see Algorithm 16). However, $O_{\text{vote}}$ modifies two inner tables H and HV. The first one models 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
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, v)$ 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 $\mathbf{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, v_i)$ with $i \in [1, n_V] \setminus 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 now 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 $\mathcal{A}_9$ which interacts with $\mathcal{A}_8$ by simulating Game 8. For this purpose, $\mathcal{A}_9$ runs the setup and the registration honestly, by generating the secret key and the credentials. This allows $\mathcal{A}_9$ to get $j, v_0, v_1$ from $\mathcal{A}_8$, that it plays in the ideal game. Then, when given $I$ in the ideal game, it forwards it to $\mathcal{A}_8$ which answers with $M$. To deduce the corresponding voting options $(v_i)_{i \in A}$, $\mathcal{A}_9$ creates a hashmap with the keys $\{c_i; i \in A\}$, and values $(v_i)_{i \in A}$ (initially $\phi$, for abstention). For each valid ballot cast by $\mathcal{A}_8$, $\mathcal{A}_9$ decrypts the ballot using the secret key and deduces $(v, c)$. Since the ballot is valid, by the soundness of the ZKP, $c$ consists of $\lambda$ bits and $v$ is a valid voting option. If $c$ is a key of the hashmap, $\mathcal{A}_9$ changes the corresponding value to $v$. (Otherwise, it ignores the ballot.) It plays the obtained values in Game 9 and receives the result of the tally which it forwards to $\mathcal{A}_8$. Finally, it outputs $\mathcal{A}_8$'s output. Remark that $\mathcal{A}_9$ played a perfect simulation of Game 8, so that $S_9 = S_8$.

<figure><img src="image_8.png" /></figure>

## 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 [14] 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, $(v_1, v_2, v_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 $v_1$, $v_2$ or $v_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 $v_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_{\text{cast}}$ which takes as input a ballot $b$ (see Algorithm 17). If the ballot is valid w.r.t. $BB$, $O_{\text{cast}}$ adds $b$ to $BB$. The adversary also has access to $O_{\text{vote}}$, which models the ballots sent by the honest voters (see Algorithm 16). However, $O_{\text{vote}}$ modifies two inner tables H and HV. The first one models 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
<table><caption>Fig. 10: Definition of verifiability, λ is the security parameter, n<sub>T</sub> the number of talliers, t the threshold, n<sub>V</sub> the number of voters, n<sub>A</sub> the number of corrupted voters and n<sub>C</sub> the number of voting options (excluding abstention)</caption><thead><tr><th></th><th></th></tr></thead><tbody><tr><td>Algorithm 19: Ver</td><td><b>Require:</b> A, λ, n<sub>T</sub>, t, n<sub>V</sub>, n<sub>A</sub>, n<sub>C</sub></td></tr><tr><td>1</td><td>pk, (s<sub>i</sub>, h<sub>i</sub>)<sup>n<sub>T</sub></sup><sub>i=1</sub> ← P<sup>A</sup><sub>Setup</sub>(λ, n<sub>T</sub>, t)</td></tr><tr><td>2</td><td>{c<sub>i</sub>; i ∈ [1, n<sub>V</sub>]}, R ← register(λ, pk, n<sub>V</sub>)</td></tr><tr><td>3</td><td>A ← A(R)</td></tr><tr><td>4</td><td>BB ← ∅; for i ∈ [1, n<sub>V</sub>]\A do HV<sub>i</sub> ← ⊥; H<sub>i</sub> ← 1</td></tr><tr><td>5</td><td>A<sup>O<sub>vote</sub>, O<sub>cast</sub>, O<sub>check</sub></sup>({c<sub>i</sub>; i ∈ A})</td></tr><tr><td>6</td><td>if |A| ≠ n<sub>A</sub> ∨ ∃i ∈ [1, n<sub>V</sub>]\A | H<sub>i</sub> &lt; 1 then Return 0</td></tr><tr><td>7</td><td>X, Π ← P<sup>A</sup><sub>tally</sub>(BB, R, pk, {h<sub>i</sub>, s<sub>i</sub>}, t)</td></tr><tr><td>8</td><td>if Verify(BB, Π, X) = 0 then Return 0</td></tr><tr><td>9</td><td>if ∃(cor<sub>i</sub>, α<sub>i</sub>)<sup>n<sub>i</sub></sup><sub>i=1</sub> ∈ (A × [1, n<sub>C</sub>]) |<br>X = tally(cleanse({(i, HV<sub>i</sub>[4]) | i ∈ [1, n<sub>V</sub>]\A, HV<sub>i</sub> ≠ ⊥} ∪ {(cor<sub>i</sub>, α<sub>i</sub>) | i ∈ [1, n<sub>V</sub>]})) then Return 0 else<br>Return 1</td></tr></tbody></table>

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<sub>i</sub> 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<sub>i</sub>)<sub>i</sub> concatenated with another sequence (cor<sub>i</sub>, α<sub>i</sub>)<sub>i</sub>, where the cor<sub>i</sub>'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 [14], 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<sub>T</sub>, t, n<sub>V</sub>, n<sub>C</sub>), there exists a negligible function μ such that $Pr(Ver(A, λ, n_T, t, n_V, n_A, n_C) = 1) \le \mu(\lambda)$.

<table><thead><tr><th></th><th></th></tr></thead><tbody><tr><td>Algorithm 16: $O_{vote}$ (updates the tabulars HV and H)</td><td><b>Require:</b> i, ν (n<sub>V</sub> is the number of voters, A the corrupted voters, n<sub>C</sub> the number of voting options, pk the public key and c<sub>i</sub> the credential of voter i)</td></tr><tr><td>1</td><td>if i ∈ [1, n<sub>V</sub>]\A ∧ ν ∈ [1, n<sub>C</sub>] then</td></tr><tr><td>2</td><td>H<sub>i</sub> ← H<sub>i</sub> − 1;</td></tr><tr><td>3</td><td>b ← Vote<sub>pk</sub>(c<sub>i</sub>, ν);</td></tr><tr><td>4</td><td>HV<sub>i</sub> ← (pk, b, c<sub>i</sub>, ν);</td></tr><tr><td>5</td><td>Return b</td></tr></tbody></table>

<table><thead><tr><th></th><th></th></tr></thead><tbody><tr><td>Algorithm 17: $O_{cast}$ (updates the bulletin board BB)</td><td><b>Require:</b> b</td></tr><tr><td>1</td><td>if isVal(pk, BB, b) = 1 then BB ← BB ∪ {b}</td></tr><tr><td>2</td><td>if Check(BB, pk, b, c<sub>i</sub>, ν) = 1 then H<sub>i</sub> ← H<sub>i</sub> + 1</td></tr></tbody></table>

**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}$.

<footnote n="2">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.</footnote>
<table><caption>Fig. 10: Definition of verifiability, $\lambda$ 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)</caption>
  <thead>
    <tr>
      <th>Algorithm 19: Ver</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>
        <b>Require:</b> A, λ, n<sub>T</sub>, t, n<sub>V</sub>, n<sub>A</sub>, n<sub>C</sub><br>
        1 pk, (s<sub>i</sub>, h<sub>i</sub>)<sup>n<sub>T</sub></sup><sub>i=1</sub> ← P<sup>A</sup><sub>Setup</sub>(λ, n<sub>T</sub>, t)<br>
        2 {c<sub>i</sub>; i ∈ [1, n<sub>V</sub>]}, R ← register(λ, pk, n<sub>V</sub>)<br>
        3 A ← A(R)<br>
        4 BB ← ∅; for i ∈ [1, n<sub>V</sub>]\A do HV<sub>i</sub> ← ⊥; H<sub>i</sub> ← 1<br>
        5 A<sup>O<sub>vote</sub>, O<sub>cast</sub>, O<sub>check</sub></sup>({c<sub>i</sub>; i ∈ A})<br>
        6 if |A| ≠ n<sub>A</sub> ∨ ∃i ∈ [1, n<sub>V</sub>]\A | H<sub>i</sub> &lt; 1 then Return 0<br>
        7 X, Π ← P<sup>A</sup><sub>tally</sub>(BB, R, pk, {h<sub>i</sub>, s<sub>i</sub>}, t)<br>
        8 if Verify(BB, Π, X) = 0 then Return 0<br>
        9 if ∃(cor<sub>i</sub>, α<sub>i</sub>)<sup>n<sub>i</sub></sup><sub>i=1</sub> ∈ (A × [1, n<sub>C</sub>]) |<br>
        &nbsp;&nbsp;&nbsp;&nbsp;X = tally(cleanse({(i, HV<sub>i</sub>[4]) | i ∈ [1, n<sub>V</sub>]\A, HV<sub>i</sub> ≠ ⊥} ∪ {(cor<sub>i</sub>, α<sub>i</sub>) | i ∈ [1, n<sub>V</sub>]})) then Return 0 else<br>
        &nbsp;&nbsp;&nbsp;&nbsp;Return 1
      </td>
    </tr>
  </tbody>
</table>

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 $\Pi$. The goal of the adversary is to produce a valid $X$, $\Pi$ which is different from any result obtained with the sequence $(i, HV_i)_i$ concatenated with another sequence $(cor_i, \alpha_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 [14], 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 $\mu$ such that $\Pr(\text{Ver}(A, \lambda, n_T, t, n_V, n_A, n_C) = 1) \le \mu(\lambda)$.

<table>
  <thead>
    <tr>
      <th>Algorithm 16: O<sub>vote</sub> (updates the tabulars HV and H)</th>
      <th>Algorithm 17: O<sub>cast</sub> (updates the bulletin board BB)</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>
        <b>Require:</b> i, v (n<sub>V</sub> is the number of voters, A the corrupted voters, n<sub>C</sub> the number of voting options, pk the public key and c<sub>i</sub> the credential of voter i)<br>
        1 if i ∈ [1, n<sub>V</sub>] \ A ∧ v ∈ [1, n<sub>C</sub>] then
        <br><br>
        2 H<sub>i</sub> ← H<sub>i</sub> - 1;
        <br>
        3 b ← Vote<sub>pk</sub>(c<sub>i</sub>, v);
        <br>
        4 HV<sub>i</sub> ← (pk, b, c<sub>i</sub>, v);
        <br>
        5 Return b
      </td>
      <td>
        <b>Require:</b> b<br>
        1 if isVal(pk, BB, b) = 1 then BB ← BB ∪ {b}
      </td>
    </tr>
    <tr>
      <td>
        <b>Require:</b> i<br>
        1 pk, b, c<sub>i</sub>, v ← HV<sub>i</sub>; HV<sub>i</sub>[2] ← ⊥
        <br>
        2 if Check(BB, pk, b, c<sub>i</sub>, v) = 1 then H<sub>i</sub> ← H<sub>i</sub> + 1
      </td>
      <td>
        <b>Require:</b> i<br>
        1 pk, b, c<sub>i</sub>, v ← HV<sub>i</sub>; HV<sub>i</sub>[2] ← ⊥
        <br>
        2 if Check(BB, pk, b, c<sub>i</sub>, v) = 1 then H<sub>i</sub> ← H<sub>i</sub> + 1
      </td>
    </tr>
  </tbody>
</table>

**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}$.

<footnote n="2">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.</footnote>
**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 $\Pi^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_{\text{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_{\text{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, \nu)$. 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 $\nu$ (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_0^j, \dots, H_{n_j}^j$, where $n_j$ is the number of times that $A_3$ calls $O_{\text{vote}}$ with the voter $j$ and a valid $\nu$. (For the sake of notations, we set $n_j = 0$ when $j$ is a corrupted voter.) Game $H_k^j$ is like Game 4, except that the first $n_j - k$ times $O_{\text{vote}}$ is called with voter $j$, we do not add the new credential $c$ in $Cred_j$, so that the next instance of $O_{\text{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, $H_0^0$ is Game 3, $H_{n_j}^j$ is $H_0^{j+1}$ for all $j$ and $H_{n_{n_V}}^{n_V}$ is Game 4. For each of these games, we denote $W_k^j$ the probability that $A_3$ wins the game.

Now, let $k$ be some index and $j$ be some voter. We construct $\mathbb{B}$ for IND-PA0 as follows. $\mathbb{B}$ gets pk from the IND-PA0 game and uses this value to play a simulation of $H_k^j$ 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_{\text{vote}}$ is called with voter $j$, $\mathbb{B}$ generates a new $c$ in $Cred_j$ as in game $H_{k+1}^j$. In addition, the next time $O_{\text{vote}}$ is called with voter $j$ (let $\nu$ be the corresponding voting option), instead of using the last credential of $Cred_j$ (which is $c$), $\mathbb{B}$ plays $(c_i, \nu)$, $(c, \nu)$ in the IND-PA0 game and uses the result as the output $b$. At some point, $A_3$ terminates and $\mathbb{B}$ must decide whether the IND-PA0 game encrypted $(c_i, \nu)$ or $(c, \nu)$. For this purpose, $\mathbb{B}$ uses $BB$, the list of the ballots cast by $\mathbb{B}$. If $b \in BB$, $\mathbb{B}$ removes it from $BB$ but keeps in memory its index. For the remaining ballots, $\mathbb{B}$ decrypts them using the decryption oracle of the IND-PA0 game. With all these informations, $\mathbb{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), $\mathbb{B}$ states that $(c_i, \nu)$ was encrypted; otherwise, it states that $(c, \nu)$ was encrypted.

Clearly, when $(c_i, \nu)$ is encrypted, $\mathbb{B}$ plays a perfect simulation of $H_k^j$ while, when $(c, \nu)$ is encrypted, $\mathbb{B}$ plays a perfect simulation of $H_{k+1}^j$. Therefore, $\mathbb{B}$'s advantage in the IND-PA0 game is $|1/2(W_k^j + 1 - W_{k+1}^j) - 1/2| \le \varepsilon_{\text{PA0}}$. By triangular inequality, $|S_4 - S_3| \le \sum_{j=1}^{n_V} 2n_j \varepsilon_{\text{PA0}} = 2q \varepsilon_{\text{PA0}}$, where $q$ is the number of calls to $O_{\text{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 \lambda$ 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, \dots, 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 $\mathbb{B}$ for IND-PA0 as follows. $\mathbb{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$. $\mathbb{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, $\mathbb{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)$), $\mathbb{B}$ plays a perfect simulation of game $H_i$ (resp. $H_{i+1}$) to $A_4$, so that the advantage of $\mathbb{B}$ in the IND-PA0 game is $|\frac{1}{2}(W_i + 1 - W_{i+1}) - \frac{1}{2}| \le \varepsilon_{\text{PA0}}$. By the triangular inequality,

$$|S_5 - S_4| \le 2n_V \varepsilon_{\text{PA0}}.$$

**Game 6:** In this game, before computing the result, we decrypt every valid ballot of $BB$ which is not the output of some $O_{\text{vote}}$. If one of these ballots uses the same credential as a ballot output by $O_{\text{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| = \varepsilon/2$, where $\varepsilon$ is the probability that we abort in Game 6. Let $E$ be the event of an abortion. We construct an adversary $\mathbb{B}$ for IND-PA0 which wins with a non-negligible advantage whenever $E$ occurs and wins with probability $1/2$ otherwise, which shows that $\varepsilon$ is negligible.

First, $\mathbb{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_{\text{vote}}$ (let $(x, \nu)$ be its inputs) and, for this instance, generates a fresh, second random credential
**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 $\Pi^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, \nu)$. 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 $\nu$ (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_0^j, \dots, H_{n_j}^j$, where $n_j$ is the number of times that $A_3$ calls $O_{vote}$ with the voter $j$ and a valid $\nu$. (For the sake of notations, we set $n_j = 0$ when $j$ is a corrupted voter.) Game $H_k^j$ 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, $H_0^0$ is Game 3, $H_{n_j}^j$ is $H_0^{j+1}$ for all $j$ and $H_{n_{n_V}}^{n_V}$ is Game 4. For each of these games, we denote $W_k^j$ the probability that $A_3$ wins the game.

Now, let $k$ be some index and $j$ be some voter. We construct $\mathbb{B}$ for IND-PA0 as follows. $\mathbb{B}$ gets pk from the IND-PA0 game and uses this value to play a simulation of $H_k^j$ 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$, $\mathbb{B}$ generates a new $c$ in $Cred_j$ as in game $H_{k+1}^j$. In addition, the next time $O_{vote}$ is called with voter $j$ (let $\nu$ be the corresponding voting option), instead of using the last credential of $Cred_j$ (which is $c$), $\mathbb{B}$ plays $(c_i, \nu)$, $(c, \nu)$ in the IND-PA0 game and uses the result as the output $b$. At some point, $A_3$ terminates and $\mathbb{B}$ must decide whether the IND-PA0 game encrypted $(c_i, \nu)$ or $(c, \nu)$. For this purpose, $\mathbb{B}$ uses $BB$, the list of the ballots cast by $\mathbb{B}$. If $b \in BB$, $\mathbb{B}$ removes it from $BB$ but keeps in memory its index. For the remaining ballots, $\mathbb{B}$ decrypts them using the decryption oracle of the IND-PA0 game. With all these informations, $\mathbb{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), $\mathbb{B}$ states that $(c_i, \nu)$ was encrypted; otherwise, it states that $(c, \nu)$ was encrypted.

Clearly, when $(c_i, \nu)$ is encrypted, $\mathbb{B}$ plays a perfect simulation of $H_k^j$ while, when $(c, \nu)$ is encrypted, $\mathbb{B}$ plays a perfect simulation of $H_{k+1}^j$. Therefore, $\mathbb{B}$'s advantage in the IND-PA0 game is $|1/2(W_k^j + 1 - W_{k+1}^j) - 1/2| \le \varepsilon_{PA0}$. By triangular inequality, $|S_4 - S_3| \le \sum_{j=1}^{n_V} 2n_j\varepsilon_{PA0} = 2q\varepsilon_{PA0}$, 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 \lambda$ 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, \dots, 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 $\mathbb{B}$ for IND-PA0 as follows. $\mathbb{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$. $\mathbb{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, $\mathbb{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)$), $\mathbb{B}$ plays a perfect simulation of game $H_i$ (resp. $H_{i+1}$) to $A_4$, so that the advantage of $\mathbb{B}$ in the IND-PA0 game is $|\frac{1}{2}(W_i + 1 - W_{i+1}) - \frac{1}{2}| \le \varepsilon_{PA0}$. By the triangular inequality,

$$|S_5 - S_4| \le 2n_V \varepsilon_{PA0}.$$

**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| = \varepsilon/2$, where $\varepsilon$ is the probability that we abort in Game 6. Let $E$ be the event of an abortion. We construct an adversary $\mathbb{B}$ for IND-PA0 which wins with a non-negligible advantage whenever $E$ occurs and wins with probability $1/2$ otherwise, which shows that $\varepsilon$ is negligible.

First, $\mathbb{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, \nu)$ be its inputs) and, for this instance, generates a fresh, second random credential
˜c. $\mathbb{B}$ plays the pair $(c, \nu)$, $(\tilde{c}, \nu)$ in the IND-PA0 game, where $c$ is the last credential in $\text{Cred}_x$. It gets back an encrypted ballot $b$, which it uses in the simulation as the output of $\mathcal{O}_{\text{vote}}$. Afterwards, $\mathbb{B}$ removes from $\mathbb{B}\mathbb{B}$ any ballot output by $\mathcal{O}_{\text{vote}}$ (including $b$) and plays $\mathbb{B}\mathbb{B}$ in the IND-PA0 game to get the decryption of the remaining ballots. If one uses the credential $c$ (resp. $\tilde{c}$), $\mathbb{B}$ states that the IND-PA0 encrypted $(c, \nu)$ (resp. $(\tilde{c}, \nu)$). If there is no such ballot or if there is a ballot which uses $c$ and a ballot which uses $\tilde{c}$, $\mathbb{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, \nu)$ (resp. $(\tilde{c}, \nu)$). Let $q_v$ be the number of (valid) calls to $\mathcal{O}_{\text{vote}}$ and $q_c$ be the number of ballots from $\mathbb{B}\mathbb{B}$ which are not an output of $\mathcal{O}_{\text{vote}}$. With probability $\varepsilon$, $\mathbb{A}_5$ managed to produce a ballot which uses the same credential as a ballot output by $\mathcal{O}_{\text{vote}}$. In this case, with probability at least $1/q_v$, one of the concerned ballot is $b$. Then, when $\mathbb{B}$ gets the decryption from the IND-PA0 game, there is a ballot of the form $(c, \gamma)$ (resp. $(\tilde{c}, \gamma)$). In addition, $\mathbb{A}_5$ has no information about $\tilde{c}$ (resp. $c$) so that with probability at least $1 - q_c/2^{\lambda}$, there is no ballot of the form $(\tilde{c}, \gamma)$ (resp. $(c, \gamma)$). Hence $\mathbb{B}$ wins with probability at least $1 - q_c/2^{\lambda+1}$. Otherwise, no ballot uses the credential $c$ (resp. $\tilde{c}$) and since the adversary has no information about $\tilde{c}$ (resp. $c$), the probability that a ballot uses the credential $\tilde{c}$ (resp. $c$) is at most $q_c/2^{\lambda}$. Therefore, the probability that $\mathbb{B}$ wins the IND-PA0 game is at least $(1 - q_c/2^{\lambda})/2$. Overall, $\mathbb{B}$'s probability to win is at least

$$ \frac{\varepsilon}{q_v}(1 - q_c/2^{\lambda+1}) + (1 - \frac{\varepsilon}{q_v})(1 - q_c/2^{\lambda})/2 = \frac{1}{2} + \frac{\varepsilon}{2q_v} - \frac{q_c}{2^{\lambda+1}}. $$

Therefore, we have

$$ \frac{\varepsilon}{2q_v} - \frac{q_c}{2^{\lambda+1}} \leq \text{Adv}_{\mathbb{B}}^{\text{IND-PA0}} \leq \varepsilon_{\text{PA0}}, $$

hence $|S_6 - S_5| = \varepsilon/2 \leq q_v \varepsilon_{\text{PA0}} + \frac{q_c q_v}{2^{\lambda+1}}$, where $q_v$ is the number of calls to $\mathcal{O}_{\text{vote}}$ and $q_c$ the number of ballots in $\mathbb{B}\mathbb{B}$ which are not an output of $\mathcal{O}_{\text{vote}}$.

**Conclusion.** Now, remark that due to the nature of $\mathcal{O}_{\text{vote}}$ which overwrite HV, it is clear that the adversary must call $\mathcal{O}_{\text{check}}(i)$ between each call of $\mathcal{O}_{\text{vote}}$ with the same voter $i$, otherwise $H_i < 1$ at line 6. Since $\mathcal{O}_{\text{check}}$ erases HV$_i$, it is also necessary for the adversary to call $\mathcal{O}_{\text{cast}}(b)$ before $\mathcal{O}_{\text{check}}(i)$, where $b$ is the output of $\mathcal{O}_{\text{vote}}(i, \nu)$. Note that due to the randomness involved in Vote, except with negligible probability $\mu$, the adversary cannot call $\mathcal{O}_{\text{cast}}(b)$ before $\mathcal{O}_{\text{vote}}(i, \nu)$ (at which point it has no information about $b$). Therefore, the order of the revotes of each voter is enforced in $\mathbb{B}\mathbb{B}$ 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. $\square$

# 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 $\text{Pr}(\mathbb{R}^g|\alpha)$ and $\text{Pr}(\mathbb{R}^g|\beta)$, given $\mathbb{R}^g$ with $g \in \{\text{Real}^{\text{CR}}, \text{Ideal}^{\text{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, $\mathbb{R}^{\text{ideal}}$ is the vector $\overrightarrow{res}$, and computing $\text{Pr}(\overrightarrow{res}|\alpha)$ for any $\alpha$ can be done thanks to a formula given in the following result from [29].

**Theorem 6** ([29]). Let $(\alpha, \beta)$ be two options, $n_H$ the number of honest voters and a pure result $\overrightarrow{res}$ such that $\sum_{i=0}^{C} \text{res}_i = n_H + 1$. Let $\overrightarrow{P}$ be the probability distribution for the honest voters. Assuming $P_\alpha P_\beta \neq 0$, we have $\text{Pr}(\overrightarrow{res}|\beta) \geq \text{Pr}(\overrightarrow{res}|\alpha)$ if and only if $\text{res}_\beta P_\alpha \geq \text{res}_\alpha P_\beta$.

In addition, we have

$$ \text{Pr}(\overrightarrow{res}|\alpha) = \frac{n_H!}{\prod_{k=0}^{C} \text{res}_k!} \left( \prod_{k=0}^{C} P_k^{\text{res}_k} \right) \frac{\text{res}_\alpha}{P_\alpha}. $$

Finally, with $M_{\alpha, \beta} = \{\overrightarrow{res} | \text{Pr}(\overrightarrow{res}|\beta) \geq \text{Pr}(\overrightarrow{res}|\alpha)\}$, the optimal value of $\delta_{\alpha, \beta}^{\text{ideal}}$ is

$$ \delta_{\alpha, \beta}^{\text{ideal}^{\text{CR}}} = \sum_{\overrightarrow{res} \in M_{\alpha, \beta}} (\text{Pr}(\overrightarrow{res}|\beta) - \text{Pr}(\overrightarrow{res}|\alpha)) = \sum_{\overrightarrow{res} \in M_{\alpha, \beta}} \frac{n_H!}{\prod_{k=0}^{C} \text{res}_k!} \left( \prod_{k=0}^{C} P_k^{\text{res}_k} \right) \left( \frac{\text{res}_\beta}{P_\beta} - \frac{\text{res}_\alpha}{P_\alpha} \right). $$

Thanks to this result, it appears that the adversary can compare $\text{Pr}(\mathbb{R}^{\text{ideal}}|\alpha)$ and $\text{Pr}(\mathbb{R}^{\text{ideal}}|\beta)$ in $\mathcal{O}(1)$ floating operations, as long as it has access to $P_\alpha$ and $P_\beta$ (note that it does not need the whole distribution), and where the asymptotic analysis is
˜c. $\mathbb{B}$ plays the pair $(c, \nu)$, $(\tilde{c}, \nu)$ in the IND-PA0 game, where $c$ is the last credential in $\text{Cred}_x$. It gets back an encrypted ballot $b$, which it uses in the simulation as the output of $\mathcal{O}_{\text{vote}}$. Afterwards, $\mathbb{B}$ removes from $\mathbb{B}\mathbb{B}$ any ballot output by $\mathcal{O}_{\text{vote}}$ (including $b$) and plays $\mathbb{B}\mathbb{B}$ in the IND-PA0 game to get the decryption of the remaining ballots. If one uses the credential $c$ (resp. $\tilde{c}$), $\mathbb{B}$ states that the IND-PA0 encrypted $(c, \nu)$ (resp. $(\tilde{c}, \nu)$). If there is no such ballot or if there is a ballot which uses $c$ and a ballot which uses $\tilde{c}$, $\mathbb{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, \nu)$ (resp. $(\tilde{c}, \nu)$). Let $q_v$ be the number of (valid) calls to $\mathcal{O}_{\text{vote}}$ and $q_c$ be the number of ballots from $\mathbb{B}\mathbb{B}$ which are not an output of $\mathcal{O}_{\text{vote}}$. With probability $\varepsilon$, $\mathbb{A}_5$ managed to produce a ballot which uses the same credential as a ballot output by $\mathcal{O}_{\text{vote}}$. In this case, with probability at least $1/q_v$, one of the concerned ballot is $b$. Then, when $\mathbb{B}$ gets the decryption from the IND-PA0 game, there is a ballot of the form $(c, \gamma)$ (resp. $(\tilde{c}, \gamma)$). In addition, $\mathbb{A}_5$ has no information about $\tilde{c}$ (resp. $c$) so that with probability at least $1 - q_c/2^{\lambda}$, there is no ballot of the form $(\tilde{c}, \gamma)$ (resp. $(c, \gamma)$). Hence $\mathbb{B}$ wins with probability at least $1 - q_c/2^{\lambda+1}$. Otherwise, no ballot uses the credential $c$ (resp. $\tilde{c}$) and since the adversary has no information about $\tilde{c}$ (resp. $c$), the probability that a ballot uses the credential $\tilde{c}$ (resp. $c$) is at most $q_c/2^{\lambda}$. Therefore, the probability that $\mathbb{B}$ wins the IND-PA0 game is at least $(1 - q_c/2^{\lambda})/2$. Overall, $\mathbb{B}$'s probability to win is at least

$$ \frac{\varepsilon}{q_v}(1 - q_c/2^{\lambda+1}) + (1 - \frac{\varepsilon}{q_v})(1 - q_c/2^{\lambda})/2 = \frac{1}{2} + \frac{\varepsilon}{2q_v} - \frac{q_c}{2^{\lambda+1}}. $$

Therefore, we have

$$ \frac{\varepsilon}{2q_v} - \frac{q_c}{2^{\lambda+1}} \leq \text{Adv}_{\mathbb{B}}^{\text{IND-PA0}} \leq \varepsilon_{\text{PA0}}, $$

hence $|S_6 - S_5| = \varepsilon/2 \leq q_v \varepsilon_{\text{PA0}} + \frac{q_c q_v}{2^{\lambda+1}}$, where $q_v$ is the number of calls to $\mathcal{O}_{\text{vote}}$ and $q_c$ the number of ballots in $\mathbb{B}\mathbb{B}$ which are not an output of $\mathcal{O}_{\text{vote}}$.

**Conclusion.** Now, remark that due to the nature of $\mathcal{O}_{\text{vote}}$ which overwrite HV, it is clear that the adversary must call $\mathcal{O}_{\text{check}}(i)$ between each call of $\mathcal{O}_{\text{vote}}$ with the same voter $i$, otherwise $H_i < 1$ at line 6. Since $\mathcal{O}_{\text{check}}$ erases HV$_i$, it is also necessary for the adversary to call $\mathcal{O}_{\text{cast}}(b)$ before $\mathcal{O}_{\text{check}}(i)$, where $b$ is the output of $\mathcal{O}_{\text{vote}}(i, \nu)$. Note that due to the randomness involved in Vote, except with negligible probability $\mu$, the adversary cannot call $\mathcal{O}_{\text{cast}}(b)$ before $\mathcal{O}_{\text{vote}}(i, \nu)$ (at which point it has no information about $b$). Therefore, the order of the revotes of each voter is enforced in $\mathbb{B}\mathbb{B}$ 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. $\square$

# 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 $\text{Pr}(\mathbb{R}^g|\alpha)$ and $\text{Pr}(\mathbb{R}^g|\beta)$, given $\mathbb{R}^g$ with $g \in \{\text{Real}^{\text{CR}}, \text{Ideal}^{\text{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, $\mathbb{R}^{\text{ideal}}$ is the vector $\overrightarrow{res}$, and computing $\text{Pr}(\overrightarrow{res}|\alpha)$ for any $\alpha$ can be done thanks to a formula given in the following result from [29].

**Theorem 6** ([29]). Let $(\alpha, \beta)$ be two options, $n_H$ the number of honest voters and a pure result $\overrightarrow{res}$ such that $\sum_{i=0}^{C} \text{res}_i = n_H + 1$. Let $\overrightarrow{P}$ be the probability distribution for the honest voters. Assuming $P_{\alpha}P_{\beta} \neq 0$, we have $\text{Pr}(\overrightarrow{res}|\beta) \geq \text{Pr}(\overrightarrow{res}|\alpha)$ if and only if $\text{res}_{\beta}P_{\alpha} \geq \text{res}_{\alpha}P_{\beta}$.

In addition, we have

$$ \text{Pr}(\overrightarrow{res}|\alpha) = \frac{n_H!}{\prod_{k=0}^{C} \text{res}_k!} \left( \prod_{k=0}^{C} P_k^{\text{res}_k} \right) \frac{\text{res}_\alpha}{P_\alpha}. $$

Finally, with $M_{\alpha, \beta} = \{\overrightarrow{res} | \text{Pr}(\overrightarrow{res}|\beta) \geq \text{Pr}(\overrightarrow{res}|\alpha)\}$, the optimal value of $\delta_{\alpha, \beta}^{\text{ideal}}$ is

$$ \delta_{\alpha, \beta}^{\text{ideal}^{\text{CR}}} = \sum_{\overrightarrow{res} \in M_{\alpha, \beta}} (\text{Pr}(\overrightarrow{res}|\beta) - \text{Pr}(\overrightarrow{res}|\alpha)) = \sum_{\overrightarrow{res} \in M_{\alpha, \beta}} \frac{n_H!}{\prod_{k=0}^{C} \text{res}_k!} \left( \prod_{k=0}^{C} P_k^{\text{res}_k} \right) \left( \frac{\text{res}_{\beta}}{P_{\beta}} - \frac{\text{res}_{\alpha}}{P_{\alpha}} \right). $$

Thanks to this result, it appears that the adversary can compare $\text{Pr}(\mathbb{R}^{\text{ideal}}|\alpha)$ and $\text{Pr}(\mathbb{R}^{\text{ideal}}|\beta)$ in $\mathcal{O}(1)$ floating operations, as long as it has access to $P_{\alpha}$ and $P_{\beta}$ (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 $\delta^{\text{ldeal}}$ in $O(n_H)$ floating operations.

**Lemma 1.** Let $(\alpha, \beta)$ be two options, $n_H$ the number of honest voters and a pure result $\overrightarrow{res}$ such that $\sum_{i=0}^{C} \text{res}_i = n_H + 1$. Let $\overrightarrow{P}$ be the probability distribution for the honest voters. Assuming $P_\alpha P_\beta \neq 0$, we have

$$ \delta_{\alpha, \beta}^{\text{ldeal}^{\text{CR}}} = n_H! \sum_{x=0}^{n_H} \frac{T_x P_{\beta}^{T_x-1} P_{\alpha}^{N_x-T_x}}{x! T_x! (N_x-T_x)!} (1-P_{\beta}-P_{\alpha})^x, \quad \text{where} \quad N_x = n_H - x + 1 \text{ and } T_x = \left[ \frac{P_{\beta}}{P_{\beta}+P_{\alpha}} N_x \right]. $$

*Proof.* First, we partition $M_{\alpha,\beta}$ into $\cup_{x=0}^{n_H} M_{\alpha,\beta}^x$, where $M_{\alpha,\beta}^x$ is the subset of all results in $M_{\alpha,\beta}$ where the options other than $\alpha$ and $\beta$ received exactly $x$ votes. Then, we further partition $M_{\alpha,\beta}^x$ into subsets where $\text{res}_\beta = y$ (and, thus, $\text{res}_\alpha = N_x - y$). Note that due to the condition from Theorem 6, $\text{res}_\beta P_\alpha \ge \text{res}_\alpha P_\beta$ hence $y$ ranges from $T_x$ to $N_x$. To express the formula from Theorem 6 using this partition, we assume that $\alpha$ and $\beta$ are the last two voting options (otherwise we reorder them) and denote $\tilde{M}^x = \{\overrightarrow{res} \in \mathbb{N}^{C-2} | \sum_{k=0}^{C-2} \text{res}_k = x\}$. With these notations, we have

$$ \begin{aligned} \delta_{\alpha, \beta}^{\text{ldeal}^{\text{CR}}} &= \sum_{x=0}^{n_H} \sum_{\overrightarrow{res} \in \tilde{M}^x} \sum_{y=T_x}^{N_x} \frac{n_H!}{\prod_{k=0}^{C-2} \text{res}_k!} \left( \prod_{k=0}^{C-2} P_k^{\text{res}_k} \right) \frac{P_{\beta}^y P_{\alpha}^{N_x-y}}{y!(N_x-y)!} \left( \frac{y}{P_{\beta}} - \frac{N_x-y}{P_{\alpha}} \right) \\ &= \sum_{x=0}^{n_H} \sum_{\overrightarrow{res} \in \tilde{M}^x} \frac{n_H!}{\prod_{k=0}^{C-2} \text{res}_k!} \left( \prod_{k=0}^{C-2} P_k^{\text{res}_k} \right) \sum_{y=T_x}^{N_x} \frac{P_{\beta}^y P_{\alpha}^{N_x-y}}{y!(N_x-y)!} \left( \frac{y}{P_{\beta}} - \frac{N_x-y}{P_{\alpha}} \right) \end{aligned} $$

Now, we show that, for all $0 \le T \le N$, $\sum_{y=T}^{N} \frac{P_{\beta}^y P_{\alpha}^{N-y}}{y!(N-y)!} \left( \frac{y}{P_{\beta}} - \frac{N-y}{P_{\alpha}} \right) = \frac{TP_{\beta}^{T-1} P_{\alpha}^{N-T}}{T!(N-T)!}$.

For this purpose, we first fix some $N \ge 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 \le N$; we show that it is also true for $T - 1$:

$$ \begin{aligned} \sum_{y=T-1}^{N} \frac{P_{\beta}^{y} P_{\alpha}^{N-y}}{y!(N-y)!} \left( \frac{y}{P_{\beta}} - \frac{N-y}{P_{\alpha}} \right) &= \frac{P_{\beta}^{T-1} P_{\alpha}^{N-T+1}}{(T-1)!(N-T+1)!} \left( \frac{T-1}{P_{\beta}} - \frac{N-T+1}{P_{\alpha}} \right) + \sum_{y=T}^{N} \frac{P_{\beta}^{y} P_{\alpha}^{N-y}}{y!(N-y)!} \left( \frac{y}{P_{\beta}} - \frac{N-y}{P_{\alpha}} \right) \\ &= \frac{P_{\beta}^{T-1} P_{\alpha}^{N-T+1}}{(T-1)!(N-T+1)!} \left( \frac{T-1}{P_{\beta}} - \frac{N-T+1}{P_{\alpha}} \right) + \frac{TP_{\beta}^{T-1} P_{\alpha}^{N-T}}{T!(N-T)!} \\ &= \frac{(T-1)P_{\beta}^{T-2} P_{\alpha}^{N-T+1}}{(T-1)!(N-T+1)!} \end{aligned} $$

Hence, with $T = T_x$ and $N = N_x$, we deduce that

$$ \begin{aligned} \delta_{\alpha, \beta}^{\text{ldeal}^{\text{CR}}} &= \sum_{x=0}^{n_H} \sum_{\overrightarrow{res} \in \tilde{M}^x} \frac{n_H!}{\prod_{k=0}^{C-2} \text{res}_k!} \left( \prod_{k=0}^{C-2} P_k^{\text{res}_k} \right) \frac{T_x P_{\beta}^{T_x-1} P_{\alpha}^{N_x-T_x}}{T_x!(N_x-T_x)!} \\ &= n_H! \sum_{x=0}^{n_H} \frac{T_x P_{\beta}^{T_x-1} P_{\alpha}^{N_x-T_x}}{x! T_x! (N_x-T_x)!} (1-P_{\beta}-P_{\alpha})^x \sum_{\overrightarrow{res} \in \tilde{M}^x} \frac{x!}{\prod_{k=0}^{C-2} \text{res}_k!} \prod_{k=0}^{C-2} \left( \frac{P_k}{1-P_{\beta}-P_{\alpha}} \right)^{\text{res}_k} \\ &= n_H! \sum_{x=0}^{n_H} \frac{T_x P_{\beta}^{T_x-1} P_{\alpha}^{N_x-T_x}}{x! T_x! (N_x-T_x)!} (1-P_{\beta}-P_{\alpha})^x. \end{aligned} $$

Indeed, the last summation is the sum over all possibilities of a multinomial distribution, which is 1. $\square$

## 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
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 $\delta^{\text{ldeal}}$ in $O(n_H)$ floating operations.

**Lemma 1.** Let $(\alpha, \beta)$ be two options, $n_H$ the number of honest voters and a pure result $\overrightarrow{res}$ such that $\sum_{i=0}^{C} \text{res}_i = n_H + 1$. Let $\overrightarrow{P}$ be the probability distribution for the honest voters. Assuming $P_\alpha P_\beta \neq 0$, we have

$$ \delta_{\alpha, \beta}^{\text{ldeal}^{\text{CR}}} = n_H! \sum_{x=0}^{n_H} \frac{T_x P_{\beta}^{T_x-1} P_{\alpha}^{N_x-T_x}}{x! T_x! (N_x-T_x)!} (1-P_{\beta}-P_{\alpha})^x, \quad \text{where } N_x = n_H - x + 1 \text{ and } T_x = \left[ \frac{P_{\beta}}{P_{\beta}+P_{\alpha}} N_x \right]. $$

*Proof.* First, we partition $M_{\alpha,\beta}$ into $\cup_{x=0}^{n_H} M_{\alpha,\beta}^x$, where $M_{\alpha,\beta}^x$ is the subset of all results in $M_{\alpha,\beta}$ where the options other than $\alpha$ and $\beta$ received exactly $x$ votes. Then, we further partition $M_{\alpha,\beta}^x$ into subsets where $\text{res}_\beta = y$ (and, thus, $\text{res}_\alpha = N_x - y$). Note that due to the condition from Theorem 6, $\text{res}_\beta P_\alpha \ge \text{res}_\alpha P_\beta$ hence $y$ ranges from $T_x$ to $N_x$. To express the formula from Theorem 6 using this partition, we assume that $\alpha$ and $\beta$ are the last two voting options (otherwise we reorder them) and denote $\tilde{M}^x = \{\overrightarrow{res} \in \mathbb{N}^{C-2} | \sum_{k=0}^{C-2} \text{res}_k = x\}$. With these notations, we have

$$ \begin{aligned} \delta_{\alpha, \beta}^{\text{ldeal}^{\text{CR}}} &= \sum_{x=0}^{n_H} \sum_{\overrightarrow{res} \in \tilde{M}^x} \sum_{y=T_x}^{N_x} \frac{n_H!}{\prod_{k=0}^{C-2} \text{res}_k!} \left( \prod_{k=0}^{C-2} P_k^{\text{res}_k} \right) \frac{P_{\beta}^y P_{\alpha}^{N_x-y}}{y!(N_x-y)!} \left( \frac{y}{P_{\beta}} - \frac{N_x-y}{P_{\alpha}} \right) \\ &= \sum_{x=0}^{n_H} \sum_{\overrightarrow{res} \in \tilde{M}^x} \frac{n_H!}{\prod_{k=0}^{C-2} \text{res}_k!} \left( \prod_{k=0}^{C-2} P_k^{\text{res}_k} \right) \sum_{y=T_x}^{N_x} \frac{P_{\beta}^y P_{\alpha}^{N_x-y}}{y!(N_x-y)!} \left( \frac{y}{P_{\beta}} - \frac{N_x-y}{P_{\alpha}} \right) \end{aligned} $$

Now, we show that, for all $0 \le T \le N$, $\sum_{y=T}^{N} \frac{P_{\beta}^y P_{\alpha}^{N-y}}{y!(N-y)!} \left( \frac{y}{P_{\beta}} - \frac{N-y}{P_{\alpha}} \right) = \frac{TP_{\beta}^{T-1} P_{\alpha}^{N-T}}{T!(N-T)!}$.

For this purpose, we first fix some $N \ge 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 \le N$; we show that it is also true for $T - 1$:

$$ \begin{aligned} \sum_{y=T-1}^{N} \frac{P_{\beta}^y P_{\alpha}^{N-y}}{y!(N-y)!} \left( \frac{y}{P_{\beta}} - \frac{N-y}{P_{\alpha}} \right) &= \frac{P_{\beta}^{T-1} P_{\alpha}^{N-T+1}}{(T-1)!(N-T+1)!} \left( \frac{T-1}{P_{\beta}} - \frac{N-T+1}{P_{\alpha}} \right) + \sum_{y=T}^{N} \frac{P_{\beta}^y P_{\alpha}^{N-y}}{y!(N-y)!} \left( \frac{y}{P_{\beta}} - \frac{N-y}{P_{\alpha}} \right) \\ &= \frac{P_{\beta}^{T-1} P_{\alpha}^{N-T+1}}{(T-1)!(N-T+1)!} \left( \frac{T-1}{P_{\beta}} - \frac{N-T+1}{P_{\alpha}} \right) + \frac{TP_{\beta}^{T-1} P_{\alpha}^{N-T}}{T!(N-T)!} \\ &= \frac{(T-1)P_{\beta}^{T-2} P_{\alpha}^{N-T+1}}{(T-1)!(N-T+1)!}. \end{aligned} $$

Hence, with $T = T_x$ and $N = N_x$, we deduce that

$$ \begin{aligned} \delta_{\alpha, \beta}^{\text{ldeal}^{\text{CR}}} &= \sum_{x=0}^{n_H} \sum_{\overrightarrow{res} \in \tilde{M}^x} \frac{n_H!}{\prod_{k=0}^{C-2} \text{res}_k!} \left( \prod_{k=0}^{C-2} P_k^{\text{res}_k} \right) \frac{T_x P_{\beta}^{T_x-1} P_{\alpha}^{N_x-T_x}}{T_x!(N_x-T_x)!} \\ &= n_H! \sum_{x=0}^{n_H} \frac{T_x P_{\beta}^{T_x-1} P_{\alpha}^{N_x-T_x}}{x! T_x! (N_x-T_x)!} (1-P_{\beta}-P_{\alpha})^x \sum_{\overrightarrow{res} \in \tilde{M}^x} \frac{x!}{\prod_{k=0}^{C-2} \text{res}_k!} \prod_{k=0}^{C-2} \left( \frac{P_k}{1-P_{\beta}-P_{\alpha}} \right)^{\text{res}_k} \\ &= n_H! \sum_{x=0}^{n_H} \frac{T_x P_{\beta}^{T_x-1} P_{\alpha}^{N_x-T_x}}{x! T_x! (N_x-T_x)!} (1-P_{\beta}-P_{\alpha})^x. \end{aligned} $$

Indeed, the last summation is the sum over all possibilities of a multinomial distribution, which is 1. $\square$

## 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
<figure><img src="image_10.png" /><figcaption>Fig. 11: Tree structure for two candidates.</figcaption></figure>

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₁,₂ is the probability to first vote for option 1 but to finally revote for option 2 while P₂,ϕ 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 $\overrightarrow{res} = (res_0, \dots, res_C)$ is the number of votes for each option and $n_r$ is the number of revotes, then $Pr(\overrightarrow{res}, n_r|\alpha)$ is the probability that the honest voters votes $res_k - 1_{k=\alpha}$ times for each candidate k and revote $n_r$ times. Given the above tree, for any possible outcome $(\overrightarrow{res}, n_r)$ with $n_H$ honest voters, we have

$$ \Pr(\overrightarrow{res}, n_r) = \sum_{H^{n_r}_{\overrightarrow{res}} \atop \overrightarrow{res}} \frac{n_H!}{res_0! \prod_{k=1}^{C} n_{k,\varnothing}! \prod_{l=1}^{C} n_{l,k}!} P_0^{res_0} \prod_{k=1}^{C} P_{k,\varnothing}^{n_{k,\varnothing}} \prod_{l=1}^{C} P_{l,k}^{n_{l,k}}, \quad (2) $$

where $H^{n_r}_{\overrightarrow{res}} = \{(n_k, \varnothing), (n_{l,k}) \mid \sum_{l,k} n_{l,k} = n_r, \forall k > 0, n_{k,\varnothing} + \sum_{k=1}^{C} n_{l,k} = res_k\}$ is the set of all possible atomic outcomes compatible with $\overrightarrow{res}$ and $n_r$.

### 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, $\delta^{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}|\alpha)$ and $Pr(R^{Real}|\beta)$, which takes $O(n_H)$ floating operations.
<figure><img src="image_9.png" /><figcaption>Fig. 11: Tree structure for two candidates.</figcaption></figure>

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₁,₂ is the probability to first vote for option 1 but to finally revote for option 2 while P₂,ϕ 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 $\overrightarrow{res} = (res_0, \dots, res_C)$ is the number of votes for each option and $n_r$ is the number of revotes, then $\Pr(\overrightarrow{res}, n_r|\alpha)$ is the probability that the honest voters votes $res_k - 1_{k=\alpha}$ times for each candidate k and revote $n_r$ times. Given the above tree, for any possible outcome $(\overrightarrow{res}, n_r)$ with $n_H$ honest voters, we have

$$ \Pr(\overrightarrow{res}, n_r) = \sum_{H^{n_r}_{\overrightarrow{res}} \atop n_r} \frac{n_H!}{res_0! \prod_{k=1}^{C} n_{k,\varnothing}! \prod_{l=1}^{C} n_{l,k}!} P_0^{res_0} \prod_{k=1}^{C} P_{k,\varnothing}^{n_{k,\varnothing}} \prod_{l=1}^{C} P_{l,k}^{n_{l,k}}, \quad (2) $$

where $H^{n_r}_{\overrightarrow{res}} = \{(n_k, \varnothing), (n_{l,k}) \mid \sum_{l,k} n_{l,k} = n_r, \forall k > 0, n_{k,\varnothing} + \sum_{k=1}^{C} n_{l,k} = res_k\}$ is the set of all possible atomic outcomes compatible with $\overrightarrow{res}$ and $n_r$.

### 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, $\delta^{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(\mathbb{R}^{Real}|\alpha)$ and $\Pr(\mathbb{R}^{Real}|\beta)$, which takes $O(n_H)$ floating operations.
**Lemma 2.** Let $n_H$ be the number of honest voters, $(\text{res}_0, \text{res}_1, \text{res}_2)$ such that $\text{res}_0+\text{res}_1+\text{res}_2 = n_H+1$ and $n_r \le n_H - \text{res}_0$. Let $\beta \in \{0, 1, 2\}$ be a voting option. Then the probability $\text{Pr}((\text{res}_0, \text{res}_1, \text{res}_2), n_r|\beta)$ that there are $\text{res}_0$ abstentions, $\text{res}_1$ votes for option 1, $\text{res}_2$ votes for option 2 and $n_r$ revotes when the coerced voter chooses the voting option $\beta$ is given by the following algorithm.

* First, set $\overrightarrow{res} = (\text{res}_0, \text{res}_1, \text{res}_2)$.

* If $\text{res}_\beta = 0$, return 0, otherwise, do $\text{res}_\beta \leftarrow \text{res}_\beta - 1$.

* Set $N = n_H - \text{res}_0 - n_r$, $P_{r1} = P_{1,1} + P_{2,1}$ and $P_{r2} = P_{1,2} + P_{2,2}$. Return

$$ \text{Pr}(\overrightarrow{res}, n_r) = \frac{n_H! P_0^{\text{res}_0}}{\text{res}_0!} \sum_{n_{1,\emptyset}} \frac{P_{1,\emptyset}^{n_{1,\emptyset}} P_{2,\emptyset}^{N-n_{1,\emptyset}}}{n_{1,\emptyset}!(N-n_{1,\emptyset})!} \frac{P_{r1}^{\text{res}_1-n_{1,\emptyset}}}{(\text{res}_1-n_{1,\emptyset})!(n_r+n_{1,\emptyset}-\text{res}_1)!} \frac{P_{r2}^{n_r+n_{1,\emptyset}-\text{res}_1}}{(n_r+n_{1,\emptyset}-\text{res}_1)!} $$

where $\max(0, \text{res}_1 - n_r) \le n_{1,\emptyset} \le \min(\text{res}_1, n_H - \text{res}_0 - n_r)$.

*Proof.* As shown in Section D-B, $\text{Pr}((\text{res}_0, \text{res}_1, \text{res}_2), n_r|\beta)$ is given by Eq. (2). We explicit the sum over $H_{\overrightarrow{res}}^{n_r}$. First, $0 \le n_{2,\emptyset} \le \text{res}_2$ and $n_{1,\emptyset} + n_{2,\emptyset} = n_H - \text{res}_0 - n_r$ and $\text{res}_0 + \text{res}_1 + \text{res}_2 = n_H$, therefore

$$ \begin{aligned} 0 &\le n_{1,\emptyset} \le \text{res}_1 \\ \text{res}_1 - n_r &\le n_{1,\emptyset} \le n_H - \text{res}_0 - n_r. \end{aligned} $$

In addition, $n_{1,\emptyset} + n_{1,1} + n_{2,1} = \text{res}_1$ and $0 \le n_{2,1} \le n_r$ so that

$$ \begin{aligned} 0 &\le n_{1,1} \le n_r \\ \text{res}_1 - n_{1,\emptyset} - n_r &\le n_{1,1} \le \text{res}_1 - n_{1,\emptyset}. \end{aligned} $$

Finally, $n_{1,2} + n_{2,2} = n_r - n_{1,1} - n_{2,1} = n_r + n_{1,\emptyset} - \text{res}_1$, thus

$$ 0 \le n_{1,2} \le \text{res}_2 - n_{2,\emptyset} = n_r + n_{1,\emptyset} - \text{res}_1 $$

Let $N = n_H - \text{res}_0 - n_r$, $N_{n_{1,\emptyset}} = \text{res}_1 - n_{1,\emptyset}$ and $N'_{n_{1,\emptyset}} = n_r + n_{1,\emptyset} - \text{res}_1$. Considering all these inequalities, we have

$$ \begin{aligned} \text{Pr}(\overrightarrow{res}, n_r) &= \frac{n_H! P_0^{\text{res}_0}}{\text{res}_0!} \sum_{n_{1,\emptyset}} \frac{P_{1,\emptyset}^{n_{1,\emptyset}} P_{2,\emptyset}^{N-n_{1,\emptyset}}}{n_{1,\emptyset}!(N-n_{1,\emptyset})!} \sum_{n_{1,1}} \frac{P_{1,1}^{n_{1,1}} P_{2,1}^{N_{n_{1,\emptyset}}-n_{1,1}}}{n_{1,1}!(N_{n_{1,\emptyset}}-n_{1,1})!} \sum_{n_{1,2}} \frac{P_{1,2}^{n_{1,2}} P_{2,2}^{N'_{n_{1,\emptyset}}-n_{1,2}}}{n_{1,2}!(N'_{n_{1,\emptyset}}-n_{1,2})!} \\ &= \frac{n_H! P_0^{\text{res}_0}}{\text{res}_0!} \sum_{n_{1,\emptyset}} \frac{P_{1,\emptyset}^{n_{1,\emptyset}} P_{2,\emptyset}^{N-n_{1,\emptyset}}}{n_{1,\emptyset}!(N-n_{1,\emptyset})!} \sum_{n_{1,1}} \frac{P_{1,1}^{n_{1,1}} P_{2,1}^{N_{n_{1,\emptyset}}-n_{1,1}}}{n_{1,1}!(N_{n_{1,\emptyset}}-n_{1,1})!} \frac{(P_{1,2} + P_{2,2})^{N'_{n_{1,\emptyset}}}}{N'_{n_{1,\emptyset}}!} \end{aligned} $$

Now, $\text{res}_1 - n_{1,\emptyset}$ is equal to the number of revotes for 1, so that $\text{res}_1 - n_{1,\emptyset} \le n_r$. Therefore, the innermost summation is also on the full domain for $n_{1,2}$. Hence,

$$ \begin{aligned} \text{Pr}(\overrightarrow{res}, n_r) &= \frac{n_H! P_0^{\text{res}_0}}{\text{res}_0!} \sum_{n_{1,\emptyset}} \frac{P_{1,\emptyset}^{n_{1,\emptyset}} P_{2,\emptyset}^{N-n_{1,\emptyset}}}{n_{1,\emptyset}!(N-n_{1,\emptyset})!} \frac{(P_{1,1} + P_{2,1})^{N_{n_{1,\emptyset}}}}{N_{n_{1,\emptyset}}!} \frac{(P_{1,2} + P_{2,2})^{N'_{n_{1,\emptyset}}}}{N'_{n_{1,\emptyset}}!} \\ &= \frac{n_H! P_0^{\text{res}_0}}{\text{res}_0!} \sum_{n_{1,\emptyset}} \frac{P_{1,\emptyset}^{n_{1,\emptyset}} P_{2,\emptyset}^{N-n_{1,\emptyset}}}{n_{1,\emptyset}!(N-n_{1,\emptyset})!} \frac{P_{r1}^{\text{res}_1-n_{1,\emptyset}}}{(\text{res}_1-n_{1,\emptyset})!(n_r+n_{1,\emptyset}-\text{res}_1)!} \frac{P_{r2}^{n_r+n_{1,\emptyset}-\text{res}_1}}{(n_r+n_{1,\emptyset}-\text{res}_1)!} \end{aligned} $$

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 $\text{res}_0, \text{res}_1, \text{res}_2, n_r$, the overall $\delta^{\text{Real}}$ can be computed in $O(n_H^4)$ floating operations. $\square$

In Section III, we used the formulas from Lemma 2 and 1 to evaluate the coercion level. The only exceptions are Figures 16 and 6, 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$.
**Lemma 2.** Let $n_H$ be the number of honest voters, $(\text{res}_0, \text{res}_1, \text{res}_2)$ such that $\text{res}_0 + \text{res}_1 + \text{res}_2 = n_H + 1$ and $n_r \le n_H - \text{res}_0$. Let $\beta \in \{0, 1, 2\}$ be a voting option. Then the probability $\text{Pr}((\text{res}_0, \text{res}_1, \text{res}_2), n_r|\beta)$ that there are $\text{res}_0$ abstentions, $\text{res}_1$ votes for option 1, $\text{res}_2$ votes for option 2 and $n_r$ revotes when the coerced voter chooses the voting option $\beta$ is given by the following algorithm.

* First, set $\overrightarrow{res} = (\text{res}_0, \text{res}_1, \text{res}_2)$.

* If $\text{res}_\beta = 0$, return 0, otherwise, do $\text{res}_\beta \leftarrow \text{res}_\beta - 1$.

* Set $N = n_H - \text{res}_0 - n_r$, $P_{r1} = P_{1,1} + P_{2,1}$ and $P_{r2} = P_{1,2} + P_{2,2}$. Return

$$ \text{Pr}(\overrightarrow{res}, n_r) = \frac{n_H! P_0^{\text{res}_0}}{\text{res}_0!} \sum_{n_{1,\emptyset}} \frac{P_{1,\emptyset}^{n_{1,\emptyset}} P_{2,\emptyset}^{N-n_{1,\emptyset}}}{n_{1,\emptyset}!(N-n_{1,\emptyset})!} \frac{P_{r1}^{\text{res}_1-n_{1,\emptyset}}}{(\text{res}_1-n_{1,\emptyset})!(n_r+n_{1,\emptyset}-\text{res}_1)!} \frac{P_{r2}^{n_r+n_{1,\emptyset}-\text{res}_1}}{(n_r+n_{1,\emptyset}-\text{res}_1)!} $$

where $\max(0, \text{res}_1 - n_r) \le n_{1,\emptyset} \le \min(\text{res}_1, n_H - \text{res}_0 - n_r)$.

*Proof.* As shown in Section D-B, $\text{Pr}((\text{res}_0, \text{res}_1, \text{res}_2), n_r|\beta)$ is given by Eq. (2). We explicit the sum over $H^{n_r}_{\overrightarrow{res}}$. First, $0 \le n_{2,\emptyset} \le \text{res}_2$ and $n_{1,\emptyset} + n_{2,\emptyset} = n_H - \text{res}_0 - n_r$ and $\text{res}_0 + \text{res}_1 + \text{res}_2 = n_H$, therefore

$$ \begin{aligned} 0 &\le n_{1,\emptyset} \le \text{res}_1 \\ \text{res}_1 - n_r &\le n_{1,\emptyset} \le n_H - \text{res}_0 - n_r. \end{aligned} $$

In addition, $n_{1,\emptyset} + n_{1,1} + n_{2,1} = \text{res}_1$ and $0 \le n_{2,1} \le n_r$ so that

$$ \begin{aligned} 0 &\le n_{1,1} \le n_r \\ \text{res}_1 - n_{1,\emptyset} - n_r &\le n_{1,1} \le \text{res}_1 - n_{1,\emptyset}. \end{aligned} $$

Finally, $n_{1,2} + n_{2,2} = n_r - n_{1,1} - n_{2,1} = n_r + n_{1,\emptyset} - \text{res}_1$, thus

$$ 0 \le n_{1,2} \le \text{res}_2 - n_{2,\emptyset} = n_r + n_{1,\emptyset} - \text{res}_1 $$

Let $N = n_H - \text{res}_0 - n_r$, $N_{n_{1,\emptyset}} = \text{res}_1 - n_{1,\emptyset}$ and $N'_{n_{1,\emptyset}} = n_r + n_{1,\emptyset} - \text{res}_1$. Considering all these inequalities, we have

$$ \begin{aligned} \text{Pr}(\overrightarrow{res}, n_r) &= \frac{n_H! P_0^{\text{res}_0}}{\text{res}_0!} \sum_{n_{1,\emptyset}} \frac{P_{1,\emptyset}^{n_{1,\emptyset}} P_{2,\emptyset}^{N-n_{1,\emptyset}}}{n_{1,\emptyset}!(N-n_{1,\emptyset})!} \sum_{n_{1,1}} \frac{P_{1,1}^{n_{1,1}} P_{2,1}^{N_{n_{1,\emptyset}}-n_{1,1}}}{n_{1,1}!(N_{n_{1,\emptyset}}-n_{1,1})!} \sum_{n_{1,2}} \frac{P_{1,2}^{n_{1,2}} P_{2,2}^{N'_{n_{1,\emptyset}}-n_{1,2}}}{n_{1,2}!(N'_{n_{1,\emptyset}}-n_{1,2})!} \\ &= \frac{n_H! P_0^{\text{res}_0}}{\text{res}_0!} \sum_{n_{1,\emptyset}} \frac{P_{1,\emptyset}^{n_{1,\emptyset}} P_{2,\emptyset}^{N-n_{1,\emptyset}}}{n_{1,\emptyset}!(N-n_{1,\emptyset})!} \sum_{n_{1,1}} \frac{P_{1,1}^{n_{1,1}} P_{2,1}^{N_{n_{1,\emptyset}}-n_{1,1}}}{n_{1,1}!(N_{n_{1,\emptyset}}-n_{1,1})!} \frac{(P_{1,2} + P_{2,2})^{N'_{n_{1,\emptyset}}}}{N'_{n_{1,\emptyset}}!} \end{aligned} $$

Now, $\text{res}_1 - n_{1,\emptyset}$ is equal to the number of revotes for 1, so that $\text{res}_1 - n_{1,\emptyset} \le n_r$. Therefore, the innermost summation is also on the full domain for $n_{1,2}$. Hence,

$$ \begin{aligned} \text{Pr}(\overrightarrow{res}, n_r) &= \frac{n_H! P_0^{\text{res}_0}}{\text{res}_0!} \sum_{n_{1,\emptyset}} \frac{P_{1,\emptyset}^{n_{1,\emptyset}} P_{2,\emptyset}^{N-n_{1,\emptyset}}}{n_{1,\emptyset}!(N-n_{1,\emptyset})!} \frac{(P_{1,1} + P_{2,1})^{N_{n_{1,\emptyset}}}}{N_{n_{1,\emptyset}}!} \frac{(P_{1,2} + P_{2,2})^{N'_{n_{1,\emptyset}}}}{N'_{n_{1,\emptyset}}!} \\ &= \frac{n_H! P_0^{\text{res}_0}}{\text{res}_0!} \sum_{n_{1,\emptyset}} \frac{P_{1,\emptyset}^{n_{1,\emptyset}} P_{2,\emptyset}^{N-n_{1,\emptyset}}}{n_{1,\emptyset}!(N-n_{1,\emptyset})!} \frac{P_{r1}^{\text{res}_1-n_{1,\emptyset}}}{(\text{res}_1-n_{1,\emptyset})!(n_r+n_{1,\emptyset}-\text{res}_1)!} \frac{P_{r2}^{n_r+n_{1,\emptyset}-\text{res}_1}}{(n_r+n_{1,\emptyset}-\text{res}_1)!} \end{aligned} $$

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 $\text{res}_0, \text{res}_1, \text{res}_2, n_r$, the overall $\delta^{\text{Real}}$ can be computed in $O(n_H^4)$ floating operations. $\square$

In Section III, we used the formulas from Lemma 2 and 1 to evaluate the coercion level. The only exceptions are Figures 16 and 6, 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$.
<figure><img src="image_11.png" /><figcaption>Fig. 12: Simplified tree structure for two candidates.</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>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.</figcaption></figure>

### D. The impact of the parameters

In Lemma 2, we saw that $\delta^{\text{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,\emptyset}$ (resp. $P_{2,\emptyset}$), 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,\emptyset} + P_{2,\emptyset}),$$

which is the probability to revote (after voting),

$$p_1 = P_{1,\emptyset}/(P_{1,\emptyset} + P_{2,\emptyset}) \text{ and } p_2 = P_{2,\emptyset}/(P_{1,\emptyset} + P_{2,\emptyset}),$$

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}) \text{ 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
<figure><img src="image_10.png" /><figcaption>Fig. 12: Simplified tree structure for two candidates.</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>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.</figcaption></figure>

### D. The impact of the parameters

In Lemma 2, we saw that $\delta^{\text{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,\emptyset}$ (resp. $P_{2,\emptyset}$), 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,\emptyset} + P_{2,\emptyset}),$$

which is the probability to revote (after voting),

$$p_1 = P_{1,\emptyset}/(P_{1,\emptyset} + P_{2,\emptyset}) \text{ and } p_2 = P_{2,\emptyset}/(P_{1,\emptyset} + P_{2,\emptyset}),$$

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}) \text{ 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
<figure><img src="image_13.png" /><figcaption>Fig. 14: Coercion levels as a function of the bias when revoting; with 20 voters, 2 candidates and 30% abstention.</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>Fig. 15: Coercion level as a function of the abstention rate; with 20 voters and 2 candidates.</figcaption></figure>

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.
<figure><img src="image_12.png" /><figcaption>Fig. 14: Coercion levels as a function of the bias when revoting; with 20 voters, 2 candidates and 30% abstention.</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>Fig. 15: Coercion level as a function of the abstention rate; with 20 voters and 2 candidates.</figcaption></figure>

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.
<figure><img src="image_15.png" /><figcaption>Fig. 16: Coercion level as a function of the number of voters; with 2 candidates and 30% abstention.</figcaption></figure>
<figure><img src="image_14.png" /><figcaption>Fig. 16: Coercion level as a function of the number of voters; with 2 candidates and 30% abstention.</figcaption></figure>