## C SECURITY PROOFS OF Applause

We present the security proofs for Applause, with respect to the security model presented in Section 3. Through this section, we operate proofs divided into sequences of games. We refer to this games as $G_{\mathcal{A}}^i(1^{\lambda})$ for a given PPT algorithm $\mathcal{A}$ and a security parameter $1^{\lambda}$. Moreover, we characterise by $w_i$ the winning event where a PPT algorithm $\mathcal{A}$ makes $G_{\mathcal{A}}^i(1^{\lambda})$ outputs 1. At first we present the security proofs of the version of Applause presented in Section 5, which relies on the *Random Oracle Model* (ROM). Then we present the security proofs for the version of Applause in the standard model. Recall that both versions of Applause differ only in few points, as explained in Section 6.

### C.1 Security Proofs of Applause in Random Oracle Model

*PROOF OF UNFORGEABILITY.* Let $\mathcal{A}$ be a PPT adversary and assume for contradiction that the following probability $\text{Pr}[\text{Exp}_{\mathcal{A}}^{\text{UF}}(1^{\lambda}) \to 1]$ is non-negligible. This proof relies on the ROM, meaning that $\mathcal{A}$ has access to an oracle Ohash replacing the function $H$ and programmed by the challenger $C$, which on call on a message $m$, samples at random a value $h$ representing the hash associated to $m$. This process is repeated if the value is already associated to another message $m'$. Then the sampled value $h$ is returned to $\mathcal{A}$.

*Game* $G^0$. The initial game represents $\text{Exp}_{\mathcal{A}}^{\text{UF}}$ defined in Fig. 3, we observe that $\text{Pr}[W_0] = \text{Pr}[\text{Exp}_{\mathcal{A}}^{\text{UF}}(1^{\lambda}) \to 1]$.

*Game* $G^1$. In this game, we now reject tickets with valid signatures from $\mathcal{D}$ that where not produced by the challenger. To distinguish such signature from the originally produced ones, $C$ keeps updated a set $S_{\mathcal{D}} = \{m_i, \sigma_i\}$ containing all the signature produced by $\mathcal{D}$ during the protocol. A signature is deemed valid if the message-signature pair is contained in this set, otherwise invalid. This prevents $\mathcal{A}$ from forging a signature, which was previously possible with probability $\text{Adv}_{\mathcal{A}}^{\text{EUF-CMA}}$. Therefore, we obtain the following bound $|\text{Pr}[W_0] - \text{Pr}[W_1]| \le \text{Adv}_{\mathcal{A}}^{\text{EUF-CMA}}(1^{\lambda})$.

*Game* $G^2$. The same action as in $G^1$ is performed on the signature produced by $\mathcal{T}$. Hence $|\text{Pr}[W_1] - \text{Pr}[W_2]| \le \text{Adv}_{\mathcal{A}}^{\text{EUF-CMA}}(1^{\lambda})$.

In $G^2$, the adversary $\mathcal{A}$ is not able to produce a ticket containing a forged signature from $\mathcal{D}$ or $\mathcal{T}$. A valid ticket is requires to contain a signature either by $\mathcal{D}$ or $\mathcal{T}$ as prescribed by the CheckTk algorithm executed in Validate, Refund or Transfer. $\mathcal{A}$ can still reuse a signature produced by the Challenger. Under the ROM, this implies using the hash $c \leftarrow Ohash(ide, idp, r_c)$ corresponding to a random value, already signed by $C$. Either $\text{tk} \notin \text{TK}$ and $\mathcal{A}$ loses the game, otherwise $\text{tk} \in \text{TK}$ and in such case, $c$ appears in the state $\text{st}$ of the Challenger $C$ and the ticket will fail to verify in the last verification of the CheckTk algorithm. This can been seen by analyzing the inclusion of $c$ in $\text{st}$ through the processes. In both cases, a condition of CheckTk is not achieved and the protocol aborts for $C$. This shows that $\text{Pr}[W_2] = 0$, and then, we obtain $\text{Pr}[\text{Exp}_{\mathcal{A}}^{\text{UF}}(1^{\lambda}) \to 1] \le 2 \cdot \text{Adv}_{\mathcal{A}}^{\text{EUF-CMA}}(1^{\lambda})$.

By hypothesis on the EUF-CMA property of the signature $S$, we know that $\text{Adv}_{\mathcal{A}}^{\text{EUF-CMA}}$ is negligible, leading to a negligible quantity on the right hand side of the inequation, giving a direct contraction

with the initial hypothesis. Hence, $\text{Pr}[\text{Exp}_{\mathcal{A}}^{\text{UF}}(1^{\lambda}) \to 1]$ is negligible and Applause has Unforgeability. $\square$

*PROOF OF PSEUDONYMITY.* Assume a PPT algorithm $\mathcal{A}$, we show that it breaks at least one of the assumed properties of the used primitives, and that such an algorithm cannot exist under the given hypothesis. We start by considering an initial game $G^0$.

*Game* $G^0$. The initial game corresponds to experiment $\text{Exp}_{\mathcal{A}}^{\text{PSE}}$. Observe that $\text{Pr}[W_0] = \text{Pr}[\text{Exp}_{\mathcal{A}}^{\text{PSE}}(1^{\lambda}) \to 1]$.

*Game* $G^1$. We focus on the anonymous payment. At the beginning, the challenger generates a new key pair and uses this key $\text{sk}_{\text{new}}^{\text{P}}$ instead of using $\text{sk}_{\text{U}_b}^{\text{Pay}}$ in all payments of the experiment. By hypothesis, an adversary has a negligible advantage $\text{Adv}_{\mathcal{A}}^{\text{PayPse}}(1^{\lambda})$ of distinguishing between which one among the two key pairs used in a payment. This property is directly transferred into our case and leaves the two key pairs of $\text{sk}_{\text{U}_0}^{\text{Pay}}$ and $\text{sk}_{\text{U}_1}^{\text{Pay}}$ unused. Hence, we obtain the following bound $|\text{Pr}[W_0] - \text{Pr}[W_1]| \le \text{Adv}_{\mathcal{A}}^{\text{PayPse}}(1^{\lambda})$.

Now, we notice that the user's key is not used in Purchase and Refund. Only Transfer and Validate involve the user's key, excluding the payment key. Hence, a call to oracles OPurchase$_b$, ORefund$_b$ does not reveal any information on the key pair $(\text{sk}_{\text{U}_b}, \text{pk}_{\text{U}_b})$ in use, ignoring the payment key that we already modified we apply the following:

*Game* $G^2$. Instead of randomizing the key pair in Validate, when $\mathcal{A}$ calls OValidate$_b$, we generate a new signature and encryption key pairs. The resulting keys are unrelated to the key pair of the user. Provided with statistically randomizable key pairs, they where already unrelated after randomization, resulting in $\text{Pr}[W_2] = \text{Pr}[W_1]$.

*Game* $G^3$. On each call of $\mathcal{A}$ to OTransfer$_b$, the same modification is put in place in Transfer. As for the previous modification, games are therefore statistically indistinguishable. This is again a bridging step with $\text{Pr}[W_3] = \text{Pr}[W_2]$.

In this game $G^3$, none of $(\text{sk}_{\text{U}_0}, \text{pk}_{\text{U}_0})$ or $(\text{sk}_{\text{U}_1}, \text{pk}_{\text{U}_1})$ are used by the challenger during the experiment. Hence, the adversary has no mean to recover $b$ and then no advantage in breaking the pseudonymity. Hence, we obtain $\text{Pr}[W_3] = \frac{1}{2}$. Summing up, $\mathcal{A}$ is a PPT algorithm with non-negligible advantage of winning against $G^0$ i.e., a non-negligible advantage in breaking the anonymity of $\text{U}_b$. Hence, we observe that $|\text{Pr}[\text{Exp}_{\mathcal{A}}^{\text{PSE}}(1^{\lambda}) \to 1] - \frac{1}{2}| \le \text{Adv}_{\mathcal{A}}^{\text{PayPse}}(1^{\lambda})$.

By hypothesis on the anonymity property of considered anonymous payment, we know that $\text{Adv}_{\mathcal{A}}^{\text{Pay}}$ is negligible, implying that no such $\mathcal{A}$ could exist. Therefore, pseudonymity holds for our ETS protocol Applause. $\square$

*PROOF OF PRIVACY.* We prove secrecy of $r_c$ through this proof. Assume $\mathcal{A}$ has a PPT algorithm. If an adversary $\mathcal{A}$ is unable to recover $r_c$, then it is unable to win against $\text{Exp}_{\mathcal{A}}^{\text{PRIV}}(1^{\lambda})$, or at least with a negligible probability. Notice that $\mathcal{U}$, the user simulated by $C$ which has generated $\text{tk}$, cannot be corrupted, otherwise $\mathcal{A}$ would fail to the experiment under $\text{corr}_1 = 0$. The following modification applied to the oracles are assumed to append only when the ticket $\text{tk}$ is involved during the execution of the oracle.

*Game* $G^0$. The initial game corresponds to the experiment $\text{Exp}_{\mathcal{A}}^{\text{PRIV}}$, hence $\text{Pr}[W_0] = \text{Pr}[\text{Exp}_{\mathcal{A}}^{\text{PRIV}}(1^{\lambda}) \to 1]$.
Game $G^1$. First, we modify the Purchase algorithm happening in the experiment. When tk is purchased, the challenger sends a random element as the first message from $U_1$, thus replacing $\text{Enc}_{pk_E^D}$ (ide, idp, $r_c$, $c$) by a random sampled uniformly from $[\text{Enc}_{pk_E^D}]$. $D$ being also simulated by $C$ it still has access to ide, idp, $r_c$, $c$ and then is able to continue the Purchase protocol.

We observe that the difference between $G^0$ and $G^1$ occurs only in the encryption of this message. Under the IND-CPA hypothesis, a distinguisher would have negligible chances to distinguish between these two experiments. Hence $|\text{Pr}[W_0] - \text{Pr}[W_1]| \le \text{Adv}_{\mathcal{A},E}^{\text{IND-CPA}}(1^\lambda)$.

Game $G^2$. The second game replaces the encryption of tk under the key $pk_E^D$ during a call to ORefund by a random element sampled uniformly from $[\text{Enc}_{pk_E^D}]$. This is the same argument as before, we directly conclude to $|\text{Pr}[W_1] - \text{Pr}[W_2]| \le \text{Adv}_{\mathcal{A},E}^{\text{IND-CPA}}(1^\lambda)$.

Game $G^3$. The third game replaces the encryption of tk under the key $pk_E^T$ during a call to OTransfer by a random element sampled uniformly from $[\text{Enc}_{pk_E^T}]$. As seen in $G^1$ and in $G^2$, we have $|\text{Pr}[W_2] - \text{Pr}[W_3]| \le \text{Adv}_{\mathcal{A},E}^{\text{IND-CPA}}(1^\lambda)$.

Game $G^4$. In the last game, concluding this proof, we replace the encryption of $pk'_{q_U}$, $\text{tk}_U$, $\text{cert}'_U$ under $pk_E^V$ by a random element sampled uniformly from $[\text{Enc}_{pk_E^V}]$. Still using the indistinguishability argument we have $|\text{Pr}[W_3] - \text{Pr}[W_4]| \le \text{Adv}_{\mathcal{A},E}^{\text{IND-CPA}}(1^\lambda)$.

Since $\mathcal{A}$ has no more advantage, and since $r_c$ is randomly picked at uniformly in $\{0, 1\}^\lambda$, $\mathcal{A}$ has probability $2^{-\lambda}$ to guess correctly, hence $\text{Pr}[W_4] = 2^{-\lambda}$. Finally, we observe that: $\text{Adv}_{\mathcal{A}}^{\text{PRIV}}(1^\lambda) = \text{Pr}[\text{Exp}_{\mathcal{A}}^{\text{PRIV}}(1^\lambda) \to 1] \le 4 \cdot \text{Adv}_{\mathcal{A},E}^{\text{IND-CPA}} + 2^{-\lambda}$. $\square$

### PROOF OF NO-DOUBLE-SPENDING.
Let $\mathcal{A}$ be a PPT adversary. We show that the probability $\text{Pr}[\text{Exp}_{\mathcal{A}}^{\text{DS}}(1^\lambda) \to 1]$ is negligible. In the game $\text{Exp}_{\mathcal{A}}^{\text{DS}}$, $\mathcal{A}$ is free to take advantage of any sequence of execution it has chosen. We show that under any chosen sequence, it is impossible for $\mathcal{A}$ to success to the same algorithm twice with the same ticket tk. The proof relies on the consistency of the state $\text{st}$, updated by the challenger $C$ during the protocol. We argue that this state prevent any double spending, indeed acting as a blacklist containing every ticket tk used in any of the protocols. We proceed by analyzing the update of the state through the algorithms: In the Refund protocol, on the reception of tk, $\mathcal{D}$ executes the CheckTk algorithm which checks that $\sigma_c$ is signed either by $\mathcal{D}$ or by $\mathcal{T}$, but also that $c$ is not contained in $\text{st}$. If not, $c$ is inserted in $\text{st}$. Suppose now that $\mathcal{A}$ replays the refund protocol again, then the signature still verifies, but since tk is now contained in $\text{st}$, then the refund fails. The ticket transfer holds on the same principle. When transferring tk, algorithm CheckTk is executed, ensuring that tk is not already contained in $\text{st}$. Exactly as the previous protocols, on the reception of ticket tk, the validation executes the CheckTk checking that tk is not contained in $\text{st}$. When the algorithm successfully ends, then tk is required to be contained in $\text{st}$ to notify that the ticket is now considered as invalid.

All algorithms taking a ticket tk as an input ends with a state $\text{st}$ containing tk. Since the state $\text{st}$ is fully controlled by $C$ and cannot be modified by $\mathcal{A}$, we can directly conclude that for every PPT adversary, $\text{Pr}[\text{Exp}_{\mathcal{A}}^{\text{DS}}(1^\lambda) \to 1]$ is zero, meaning that the double-spending, in any sequence, is prevented. $\square$

Recall that in our construction, a ticket tk is defined by a place (ide, idp), the random $r_c$ and the signature $\sigma_c$. From an information theory perspective, tk is completely unrelated from any user $\mathcal{U}$. Then, our proof simply consists to show that at any moment, the identity of $\mathcal{U}$ (e.g., the public key $pk_{q_U}$, a signature using $\text{sk}_{q_U}$) is used during the communication.

### PROOF OF UNLINKABILITY.
Our proof is designed as a sequence of five games $G^i$ for $i$ ranging from 0 to 4, where the initial game $G^0$ corresponds the game $\text{Exp}_{\mathcal{A}}^{\text{UNL}}$ for a bit $b$, and our last game $G^4$ corresponds to the game $\text{Exp}_{\mathcal{A}}^{\text{UNL}}$ with $C$ using $1-b$. We show that both game are indistinguishable through a sequence of negligible modifications. We only need to apply the modifications where the third ticket $\text{tk}_3$ (purchased by $\mathcal{U}_b$) is involved. Let $\mathcal{A}$ be a PPT adversary, we show that it has negligible probability to succeed to $\text{Exp}_{\mathcal{A}}^{\text{UNL}}$ for a probability non-negligible close to $1/2$. For more clarity, let $\text{Exp}_{\mathcal{A},b}^{\text{UNL}}$ be the game $\text{Exp}_{\mathcal{A}}^{\text{UNL}}$ except that we set the bit $b$ as a parameter instead of being chosen randomly by the challenger.

Game $G^0$. The initial game corresponds to the experiment $\text{Exp}_{\mathcal{A},b}^{\text{UNL}}$ with the bit $b$ (still chosen randomly outside of the game) provided as a parameter. Hence, for every adversary $\mathcal{A}$, we have $\text{Pr}[W_0] = \text{Pr}[\text{Exp}_{\mathcal{A},b}^{\text{UNL}}(1^\lambda) \to 1]$.

Game $G^1$. We focus on the Validate protocol, where we have $pk'_{\mathcal{U}_b}$ and $\text{tk}_b$ sent from $\mathcal{U}_b$ to $\mathcal{V}$. Since tk is not related to $\mathcal{U}_b$, then using the statistical indistinguishability of the randomised keys, we replace $pk'_{\mathcal{U}_b}$ by $pk'_{\mathcal{U}_{1-b}}$. This modification implies that in the subsequent modification, we have $\text{Enc}_{pk_E^T}$ (s) which does not help $\mathcal{A}$ using the statistical indistinguishability of the randomised keys. Therefore, we have $\text{Pr}[W_0] = \text{Pr}[W_1]$.

Game $G^2$. We focus on Refund, which contains only a payment interaction between $\mathcal{U}_b$ and $\mathcal{D}$. Again, we replace the secret payment key $\text{sk}_b^P$ of $\mathcal{U}_b$ with the secret payment key of $\text{sk}_{1-b}^P$. The difference from the point of view of $\mathcal{A}$ relies on the capacity to link a payment either to $\mathcal{U}_b$ or to $\mathcal{U}_{1-b}$, which we quantify as the advantage $\text{Adv}_{\mathcal{A}}^{\text{PayUnl}}$. Then, we have $|\text{Pr}[W_1] - \text{Pr}[W_2]| \le \text{Adv}_{\mathcal{A}}^{\text{PayUnl}}$.

Game $G^3$. We focus on Transfer, where $\mathcal{A}$ is expected to have as an input the randomised public key $pk'_{\mathcal{U}_b}$. Using the same strategy of the game $G^1$, we replace $pk'_{\mathcal{U}_b}$ with $pk'_{\mathcal{U}_{1-b}}$. This modification of the input implies that $\sigma_{T,1}$ is now produces with the signature key $\text{sk}_{\mathcal{U}_{1-b}}^S$, which is verifiable using $pk'_{\mathcal{U}_{1-b}}$. Again, using the statistical indistinguishability of the randomised keys, $\mathcal{A}$ cannot notice the difference. However, Latter in the protocol, we have a call to the Refund protocol as a subroutine. As shown, Refund involves an anonymous payment. Since we replace the key $\mathcal{U}_b$ with key of $\mathcal{U}_{1-b}$, the secret payment key is replaced as well, which can be distinguished by $\mathcal{A}$ with the advantage of breaking the unlinkability of the anonymous payment. Hence $|\text{Pr}[W_2] - \text{Pr}[W_3]| \le \text{Adv}_{\mathcal{A}}^{\text{PayUnl}}$.

Game $G^4$. In the last game, we focus on Purchase, on which the two first interactions does not involve the public key $pk_{q_U}$. The third interaction, however, is the anonymous payment. As in game $G^2$ and $G^3$, we replace $\text{sk}_b^P$ by $\text{sk}_{1-b}^P$. The probability for $\mathcal{A}$ to distinguish between $G^3$ and $G^4$ is based on the advantage to break the unlinkability of the anonymous payment. Hence, we have $|\text{Pr}[W_3] - \text{Pr}[W_4]| \le \text{Adv}_{\mathcal{A}}^{\text{PayUnl}}$.
Game $G^1$. First, we modify the Purchase algorithm happening in the experiment. When tk is purchased, the challenger sends a random element as the first message from $U_1$, thus replacing $\text{Enc}_{pk_E^D}$ (ide, idp, $r_c$, $c$) by a random sampled uniformly from $[\text{Enc}_{pk_E^D}]$. $D$ being also simulated by $C$ it still has access to ide, idp, $r_c$, $c$ and then is able to continue the Purchase protocol.

We observe that the difference between $G^0$ and $G^1$ occurs only in the encryption of this message. Under the IND-CPA hypothesis, a distinguisher would have negligible chances to distinguish between these two experiments. Hence $|\text{Pr}[W_0] - \text{Pr}[W_1]| \le \text{Adv}_{\mathcal{A},E}^{\text{IND-CPA}}(1^\lambda)$.

Game $G^2$. The second game replaces the encryption of tk under the key $pk_E^D$ during a call to ORefund by a random element sampled uniformly from $[\text{Enc}_{pk_E^D}]$. This is the same argument as before, we directly conclude to $|\text{Pr}[W_1] - \text{Pr}[W_2]| \le \text{Adv}_{\mathcal{A},E}^{\text{IND-CPA}}(1^\lambda)$.

Game $G^3$. The third game replaces the encryption of tk under the key $pk_E^T$ during a call to OTransfer by a random element sampled uniformly from $[\text{Enc}_{pk_E^T}]$. As seen in $G^1$ and in $G^2$, we have $|\text{Pr}[W_2] - \text{Pr}[W_3]| \le \text{Adv}_{\mathcal{A},E}^{\text{IND-CPA}}(1^\lambda)$.

Game $G^4$. In the last game, concluding this proof, we replace the encryption of $pk'_{q_U}$, tk, $cert'_{q_U}$ under $pk_E^V$ by a random element sampled uniformly from $[\text{Enc}_{pk_E^V}]$. Still using the indistinguishability argument we have $|\text{Pr}[W_3] - \text{Pr}[W_4]| \le \text{Adv}_{\mathcal{A},E}^{\text{IND-CPA}}(1^\lambda)$.

Since $\mathcal{A}$ has no more advantage, and since $r_c$ is randomly picked at uniformly in $\{0, 1\}^\lambda$, $\mathcal{A}$ has probability $2^{-\lambda}$ to guess correctly, hence $\text{Pr}[W_4] = 2^{-\lambda}$. Finally, we observe that: $\text{Adv}_{\mathcal{A}}^{\text{PRIV}}(1^\lambda) = \text{Pr}[\text{Exp}_{\mathcal{A}}^{\text{PRIV}}(1^\lambda) \to 1] \le 4 \cdot \text{Adv}_{\mathcal{A},E}^{\text{IND-CPA}} + 2^{-\lambda}$. $\square$

### PROOF OF NO-DOUBLE-SPENDING.
Let $\mathcal{A}$ be a PPT adversary. We show that the probability $\text{Pr}[\text{Exp}_{\mathcal{A}}^{\text{DS}}(1^\lambda) \to 1]$ is negligible. In the game $\text{Exp}_{\mathcal{A}}^{\text{DS}}$, $\mathcal{A}$ is free to take advantage of any sequence of execution it has chosen. We show that under any chosen sequence, it is impossible for $\mathcal{A}$ to success to the same algorithm twice with the same ticket tk. The proof relies on the consistency of the state $st$, updated by the challenger $C$ during the protocol. We argue that this state prevent any double spending, indeed acting as a blacklist containing every ticket tk used in any of the protocols. We proceed by analyzing the update of the state through the algorithms: In the Refund protocol, on the reception of tk, $\mathcal{D}$ executes the CheckTk algorithm which checks that $\sigma_c$ is signed either by $\mathcal{D}$ or by $\mathcal{T}$, but also that $c$ is not contained in $st$. If not, $c$ is inserted in $st$. Suppose now that $\mathcal{A}$ replays the refund protocol again, then the signature still verifies, but since tk is now contained in $st$, then the refund fails. The ticket transfer holds on the same principle. When transferring tk, algorithm CheckTk is executed, ensuring that tk is not already contained in $st$. Exactly as the previous protocols, on the reception of ticket tk, the validation executes the CheckTk checking that tk is not contained in $st$. When the algorithm successfully ends, then tk is required to be contained in $st$ to notify that the ticket is now considered as invalid.

All algorithms taking a ticket tk as an input ends with a state $st$ containing tk. Since the state $st$ is fully controlled by $C$ and cannot be modified by $\mathcal{A}$, we can directly conclude that for every PPT adversary, $\text{Pr}[\text{Exp}_{\mathcal{A}}^{\text{DS}}(1^\lambda) \to 1]$ is zero, meaning that the double-spending, in any sequence, is prevented. $\square$

Recall that in our construction, a ticket tk is defined by a place (ide, idp), the random $r_c$ and the signature $\sigma_c$. From an information theory perspective, tk is completely unrelated from any user $\mathcal{U}$. Then, our proof simply consists to show that at any moment, the identity of $\mathcal{U}$ (e.g., the public key $pk_{q_U}$, a signature using $sk_{q_U}$) is used during the communication.

### PROOF OF UNLINKABILITY.
Our proof is designed as a sequence of five games $G^i$ for $i$ ranging from 0 to 4, where the initial game $G^0$ corresponds the game $\text{Exp}_{\mathcal{A}}^{\text{UNL}}$ for a bit $b$, and our last game $G^4$ corresponds to the game $\text{Exp}_{\mathcal{A}}^{\text{UNL}}$ with $C$ using $1-b$. We show that both game are indistinguishable through a sequence of negligible modifications. We only need to apply the modifications where the third ticket $tk_3$ (purchased by $\mathcal{U}_b$) is involved. Let $\mathcal{A}$ be a PPT adversary, we show that it has negligible probability to succeed to $\text{Exp}_{\mathcal{A}}^{\text{UNL}}$ for a probability non-negligible close to $1/2$. For more clarity, let $\text{Exp}_{\mathcal{A},b}^{\text{UNL}}$ be the game $\text{Exp}_{\mathcal{A}}^{\text{UNL}}$ except that we set the bit $b$ as a parameter instead of being chosen randomly by the challenger.

Game $G^0$. The initial game corresponds to the experiment $\text{Exp}_{\mathcal{A},b}^{\text{UNL}}$ with the bit $b$ (still chosen randomly outside of the game) provided as a parameter. Hence, for every adversary $\mathcal{A}$, we have $\text{Pr}[W_0] = \text{Pr}[\text{Exp}_{\mathcal{A},b}^{\text{UNL}}(1^\lambda) \to 1]$.

Game $G^1$. We focus on the Validate protocol, where we have $pk'_{q_U}$ and tk sent from $\mathcal{U}_b$ to $\mathcal{V}$. Since tk is not related to $\mathcal{U}_b$, then using the statistical indistinguishability of the randomised keys, we replace $pk'_{q_U}$ by $pk'_{q_{1-b}}$. This modification implies that in the subsequent modification, we have $\text{Enc}_{pk_E^T}$ (s) which does not help $\mathcal{A}$ using the statistical indistinguishability of the randomised keys. Therefore, we have $\text{Pr}[W_0] = \text{Pr}[W_1]$.

Game $G^2$. We focus on Refund, which contains only a payment interaction between $\mathcal{U}_b$ and $\mathcal{D}$. Again, we replace the secret payment key $sk_b^P$ of $\mathcal{U}_b$ with the secret payment key of $sk_{1-b}^P$. The difference from the point of view of $\mathcal{A}$ relies on the capacity to link a payment either to $\mathcal{U}_b$ or to $\mathcal{U}_{1-b}$, which we quantify as the advantage $\text{Adv}_{\mathcal{A}}^{\text{PayUnl}}$. Then, we have $|\text{Pr}[W_1] - \text{Pr}[W_2]| \le \text{Adv}_{\mathcal{A}}^{\text{PayUnl}}$.

Game $G^3$. We focus on Transfer, where $\mathcal{A}$ is expected to have as an input the randomised public key $pk'_{q_U}$. Using the same strategy of the game $G^1$, we replace $pk'_{q_U}$ with $pk'_{q_{1-b}}$. This modification of the input implies that $\sigma_{T,1}$ is now produces with the signature key $sk_{q_{1-b}}^{S'}$, which is verifiable using $pk'_{q_{1-b}}$. Again, using the statistical indistinguishability of the randomised keys, $\mathcal{A}$ cannot notice the difference. However, Latter in the protocol, we have a call to the Refund protocol as a subroutine. As shown, Refund involves an anonymous payment. Since we replace the key $\mathcal{U}_b$ with key of $\mathcal{U}_{1-b}$, the secret payment key is replaced as well, which can be distinguished by $\mathcal{A}$ with the advantage of breaking the unlinkability of the anonymous payment. Hence $|\text{Pr}[W_2] - \text{Pr}[W_3]| \le \text{Adv}_{\mathcal{A}}^{\text{PayUnl}}$.

Game $G^4$. In the last game, we focus on Purchase, on which the two first interactions does not involve the public key $pk_{q_U}$. The third interaction, however, is the anonymous payment. As in game $G^2$ and $G^3$, we replace $sk_b^P$ by $sk_{1-b}^P$. The probability for $\mathcal{A}$ to distinguish between $G^3$ and $G^4$ is based on the advantage to break the unlinkability of the anonymous payment. Hence, we have $|\text{Pr}[W_3] - \text{Pr}[W_4]| \le \text{Adv}_{\mathcal{A}}^{\text{PayUnl}}$.
Remark that in $G^4$, we have replaced the key pair $(sk_{q_b}, pk_{q_b})$ with $(sk_{q_{1-b}}, pk_{q_{1-b}})$, when $tk_3$ is used. This demonstrate that $\mathcal{A}$ is unable to distinguish the experiment $\text{Exp}_{\mathcal{A},b'}^{\text{UNL}}$ when $b'$ equals $b$ or $1-b$. We can conclude that

$$ \begin{aligned} & |\Pr[\text{Exp}_{\mathcal{A},b}^{\text{UNL}}(1^{\lambda}) \to 1] - \Pr[\text{Exp}_{\mathcal{A},b}^{\text{UNL}}(1^{\lambda}) \to 1]| \le 3 \cdot \text{Adv}_{\mathcal{A}}^{\text{PayUnl}} \\ & |\Pr[\text{Exp}_{\mathcal{A}}^{\text{UNL}}(1^{\lambda}) \to 1] - \frac{1}{2}| \le \frac{3}{2} \cdot \text{Adv}_{\mathcal{A}}^{\text{PayUnl}} \end{aligned} \quad \square $$

## C.2 Security Proofs of Applause in the Standard Model

We present the security proofs of Applause in the standard model, for which we replace the hash $c \leftarrow H(\text{ide}, \text{idp}, r_c)$ for a place $(\text{ide}, \text{idp})$ and a random $r_c$, by a commitment $c \leftarrow h^{r_c} g_1^{\text{ide}} g_2^{\text{idp}}$ where $h, g_1$ and $g_2$ are three generators of a group $\mathbb{G}$, assumed secure under the Discrete Logarithm (DL) problem.

Pseudonymity, Double-spending and Unlinkability have already been shown under standard assumption as the previous proof does not involve any argument based on the random oracle. We need no further consideration to guarantee these properties for the standard model version of Applause, the proof being the same as before. We only have to modify the proofs for Unforgeability and Privacy.

**PROOF OF UNFORGEABILITY.** We start with the same sequence of games as for the proof of Theorem 5.2. We consider $G^2$, where the challenger keeps record of the signatures produced by $\mathcal{D}$ and $\mathcal{T}$, and refuses any forged valid signature under $pk_{\mathcal{D}}^S$ or $pk_{\mathcal{T}}^S$.

During the execution of the algorithm Alg chosen by $\mathcal{A}$ the CheckTk is always executed, hence $\mathcal{A}$ must have transmitted a signature $\sigma_c$ for $c$ taken from tk returned by $\mathcal{A}$. We recall that in the current case $c = h^{r_c} g_1^{\text{ide}} g_2^{\text{idp}}$. As a forged signature would be refused by $\mathcal{C}$, $\mathcal{A}$ needs to output a signature generated for another ticket. It has been produced for this ticket, then $tk \in \text{TK}_i$ holds true and the game is lost. Hence $\mathcal{A}$ must used a previously made signature and need to find a triple $r_c$, ide, idp such that $c = h^{r_c} g_1^{\text{ide}} g_2^{\text{idp}}$ holds true for one of the signature produced for another ticket $tk'$. Equivalently, $c = h^{r_c} g_1^{\text{ide}} g_2^{\text{idp}} = h^{r_c'} g_1^{\text{ide}'} g_2^{\text{idp}'}$. Based on such an answer, we can recover the discrete logarithm of one of the generator based on the two others. For example, we can obtain $h = g_1^{\frac{\text{idc}-\text{idc}'}{r_c-r_c}} g_2^{\frac{\text{idp}-\text{idp}'}{r_c-r_c}}$.

Now assuming a challenger for the discrete logarithm problem sending $g, g^x$ as a challenge, we can sample a random $s \stackrel{s}{\leftarrow} \mathbb{Z}_p^*$ and set $h = g^x, g_1 = g$ and $g_2 = g^s$, all three are known to be generators of the prime order group if $g^x \neq 1$. Based on a correct answer from an adversary winning against game $G^2$, we recover $g^x = g_1^{\frac{\text{idc}-\text{idc}'}{r_c-r_c}} g_2^{\frac{\text{idp}-\text{idp}'}{r_c-r_c}} = g_1^{\frac{\text{idc}-\text{idc}'}{r_c-r_c}} + s \cdot \frac{\text{idp}-\text{idp}'}{r_c-r_c}$. Hence, recovering the discrete logarithm of $g^x$. This allows us to conclude that $\text{Pr}[W_2] \le \text{Adv}_{\mathcal{A}}^{\text{DL}}(1^{\lambda})$. And based on the previous reduction, we observe that: $\text{Pr}[\text{Exp}_{\mathcal{A}}^{\text{UF}}(1^{\lambda}) \to 1] \le 2 \cdot \text{Adv}_{\mathcal{A}}^{\text{EUF-CMA}}(1^{\lambda}) + \text{Adv}_{\mathcal{A}}^{\text{DL}}(1^{\lambda})$. $\square$

**PROOF OF PRIVACY.** The same sequence of game as in the proof of Theorem 5.4 can be applied. We follow up on the previous reduction. In $G^4$, among other things, $\mathcal{A}$ has to return the value $r_c$. This element is only involved in the computation of $c$, as in this

version of the protocol $c = h^{r_c} g_1^{\text{ide}} g_2^{\text{idp}}$. Using the state leakage, $\mathcal{A}$ can have access to $c$ during the game, similarly, ide and idp are both accessible to $\mathcal{A}$. In order to recover $r_c$ from the latest, $\mathcal{A}$ is expected to compute a discrete logarithm on $c \cdot g_1^{\text{ide}} g_2^{\text{idp}} = h^{r_c}$. Hence, given a challenger for the discrete logarithm problem sending $X = g^x$, during the purchase of (ide, idp), the challenger $\mathcal{C}$ replace $h^{r_c}$ by $X$. Receiving the answer from an adversary $\mathcal{A}$, we can return the value returned for $r_c$ to the challenger for the discrete logarithm problem. If $\mathcal{A}$ has non-negligible chances to break the privacy of the ticket, it would either break the discrete logarithm problem or the IND-CPA property of the encryption. A random guess can still be possible, leading to the following advantage: $\text{Pr}[\text{Exp}_{\mathcal{A}}^{\text{PRIV}}(1^{\lambda}) \to 1] \le \frac{1}{q} + 4 \cdot \text{Adv}_{\mathcal{A}}^{\text{IND-CPA}}(1^{\lambda}) + \text{Adv}_{\mathcal{A}}^{\text{DL}}(1^{\lambda})$. $\square$

## D SECURITY PROOFS OF Spotlight

The unforgeability of the ticket, its privacy and prevention of double spending property remains unaffected by the additional authentication information on this new version of the protocol. The proposed changes in Section 7, at a high level, adds a certificate that must to be sent by a user at the beginning of the protocols' execution. Since we only add authentication material to the protocol, it is fairly straightforward to see that the same proof strategies for unforgeability, privacy and no-double spending are valid in this latest version of the protocol. Note that the Judge $\mathcal{J}$ does not take part to the game in this case. The challenger is simulating it instead.

**PROOF OF PSEUDONYMITY.** Based on the above described modifications in the game (the judge is added and controlled by the challenger), we follow the same sequence of game as in proof of unforgeability. Let us denote it as Game $G^1$.

We have assumed statistical randomization of the certificates of $U_0$ with key pair $(sk_{q_0}, pk_{q_0})$ and $U_1$ with key pair $(sk_{q_1}, pk_{q_1})$ through the RandID algorithm. Hence, there is no link between the keys and the identity. Now, let us assume a distinguisher between $G^1$ with bit $b$ and $\text{Exp}_{\mathcal{A}}^{\text{PSE}}$ with bit $1-b$. Assuming existence of such a distinguisher, we can directly distinguish two randomised certificates. Hence, under the above hypothesis, we can conclude that pseudonymity holds for the auditable version of Applause. We precise an upper bound: $|\Pr[\text{Exp}_{\mathcal{A}}^{\text{PSE}}(1^{\lambda}) \to 1] - \frac{1}{2}| \le \text{Adv}_{\mathcal{A}}^{\text{PayPse}}(1^{\lambda})$. $\square$

**PROOF OF UNLINKABILITY.** The challenger executes the actions of the judge, hence, the adversary cannot recover the user's identity based on the judge's keys $(sk_{\mathcal{J}}, pk_{\mathcal{J}})$. Only an additional certificate is shared with the adversary during Purchase, Refund or Transfer. Even so, this is linked to the user's public key, that we have assumed statistically indistinguishable randomization, leading to impossibility of the recovery of the original identity of the user. Then, $|\Pr[\text{Exp}_{\mathcal{A}}^{\text{UNL}}(1^{\lambda}) \to 1] - \frac{1}{2}| \le 3 \cdot \text{Adv}_{\mathcal{A}}^{\text{PayUnl}}(1^{\lambda})$. $\square$

For the auditable version of Applause in the standard model, the same changes presented in Section C.2 can be applied to the above proof to show its security.
Remark that in $G^4$, we have replaced the key pair $(sk_{q_b}, pk_{q_b})$ with $(sk_{q_{1-b}}, pk_{q_{1-b}})$, when $tk_3$ is used. This demonstrate that $\mathcal{A}$ is unable to distinguish the experiment $\text{Exp}_{\mathcal{A},b'}^{\text{UNL}}$ when $b'$ equals $b$ or $1-b$. We can conclude that

$$ \begin{aligned} & |\Pr[\text{Exp}_{\mathcal{A},b}^{\text{UNL}}(1^{\lambda}) \to 1] - \Pr[\text{Exp}_{\mathcal{A},b}^{\text{UNL}}(1^{\lambda}) \to 1]| \le 3 \cdot \text{Adv}_{\mathcal{A}}^{\text{PayUnl}} \\ & |\Pr[\text{Exp}_{\mathcal{A}}^{\text{UNL}}(1^{\lambda}) \to 1] - \frac{1}{2}| \le \frac{3}{2} \cdot \text{Adv}_{\mathcal{A}}^{\text{PayUnl}} \end{aligned} \quad \square $$

## C.2 Security Proofs of Applause in the Standard Model

We present the security proofs of Applause in the standard model, for which we replace the hash $c \leftarrow H(ide, idp, r_c)$ for a place $(ide, idp)$ and a random $r_c$, by a commitment $c \leftarrow h^{r_c} g_1^{ide} g_2^{idp}$ where $h, g_1$ and $g_2$ are three generators of a group $\mathbb{G}$, assumed secure under the Discrete Logarithm (DL) problem.

Pseudonymity, Double-spending and Unlinkability have already been shown under standard assumption as the previous proof does not involve any argument based on the random oracle. We need no further consideration to guarantee these properties for the standard model version of Applause, the proof being the same as before. We only have to modify the proofs for Unforgeability and Privacy.

**PROOF OF UNFORGEABILITY.** We start with the same sequence of games as for the proof of Theorem 5.2. We consider $G^2$, where the challenger keeps record of the signatures produced by $\mathcal{D}$ and $\mathcal{T}$, and refuses any forged valid signature under $pk_{\mathcal{D}}^S$ or $pk_{\mathcal{T}}^S$.

During the execution of the algorithm Alg chosen by $\mathcal{A}$ the CheckTk is always executed, hence $\mathcal{A}$ must have transmitted a signature $\sigma_c$ for $c$ taken from tk returned by $\mathcal{A}$. We recall that in the current case $c = h^{r_c} g_1^{ide} g_2^{idp}$. As a forged signature would be refused by $\mathcal{C}$, $\mathcal{A}$ needs to output a signature generated for another ticket. It has been produced for this ticket, then $tk \in \text{TK}_i$ holds true and the game is lost. Hence $\mathcal{A}$ must used a previously made signature and need to find a triple $r_c$, ide, idp such that $c = h^{r_c} g_1^{ide} g_2^{idp}$ holds true for one of the signature produced for another ticket $tk'$. Equivalently, $c = h^{r_c} g_1^{ide} g_2^{idp} = h^{r_c'} g_1^{ide'} g_2^{idp'}$. Based on such an answer, we can recover the discrete logarithm of one of the generator based on the two others. For example, we can obtain $h = g_1^{\frac{ide-idc'}{r_c-r_c}} g_2^{\frac{idp-idp'}{r_c-r_c}}$.

Now assuming a challenger for the discrete logarithm problem sending $g, g^x$ as a challenge, we can sample a random $s \stackrel{s}{\leftarrow} \mathbb{Z}_p^*$ and set $h = g^x, g_1 = g$ and $g_2 = g^s$, all three are known to be generators of the prime order group if $g^x \neq 1$. Based on a correct answer from an adversary winning against game $G^2$, we recover $g^x = g_1^{\frac{ide-idc'}{r_c-r_c}} g_2^{\frac{idp-idp'}{r_c-r_c}} = g_1^{\frac{ide-idc'}{r_c-r_c}} + s \cdot \frac{idp-idp'}{r_c-r_c}$. Hence, recovering the discrete logarithm of $g^x$. This allows us to conclude that $\text{Pr}[W_2] \le \text{Adv}_{\mathcal{A}}^{\text{DL}}(1^{\lambda})$. And based on the previous reduction, we observe that: $\text{Pr}[\text{Exp}_{\mathcal{A}}^{\text{UF}}(1^{\lambda}) \to 1] \le 2 \cdot \text{Adv}_{\mathcal{A}}^{\text{EUF-CMA}}(1^{\lambda}) + \text{Adv}_{\mathcal{A}}^{\text{DL}}(1^{\lambda})$. $\square$

**PROOF OF PRIVACY.** The same sequence of game as in the proof of Theorem 5.4 can be applied. We follow up on the previous reduction. In $G^4$, among other things, $\mathcal{A}$ has to return the value $r_c$. This element is only involved in the computation of $c$, as in this

version of the protocol $c = h^{r_c} g_1^{ide} g_2^{idp}$. Using the state leakage, $\mathcal{A}$ can have access to $c$ during the game, similarly, ide and idp are both accessible to $\mathcal{A}$. In order to recover $r_c$ from the latest, $\mathcal{A}$ is expected to compute a discrete logarithm on $c \cdot g_1^{ide} g_2^{idp} = h^{r_c}$. Hence, given a challenger for the discrete logarithm problem sending $X = g^x$, during the purchase of $(ide, idp)$, the challenger $\mathcal{C}$ replace $h^{r_c}$ by $X$. Receiving the answer from an adversary $\mathcal{A}$, we can return the value returned for $r_c$ to the challenger for the discrete logarithm problem. If $\mathcal{A}$ has non-negligible chances to break the privacy of the ticket, it would either break the discrete logarithm problem or the IND-CPA property of the encryption. A random guess can still be possible, leading to the following advantage: $\text{Pr}[\text{Exp}_{\mathcal{A}}^{\text{PRIV}}(1^{\lambda}) \to 1] \le \frac{1}{q} + 4 \cdot \text{Adv}_{\mathcal{A}}^{\text{IND-CPA}}(1^{\lambda}) + \text{Adv}_{\mathcal{A}}^{\text{DL}}(1^{\lambda})$. $\square$

## D SECURITY PROOFS OF Spotlight

The unforgeability of the ticket, its privacy and prevention of double spending property remains unaffected by the additional authentication information on this new version of the protocol. The proposed changes in Section 7, at a high level, adds a certificate that must to be sent by a user at the beginning of the protocols' execution. Since we only add authentication material to the protocol, it is fairly straightforward to see that the same proof strategies for unforgeability, privacy and no-double spending are valid in this latest version of the protocol. Note that the Judge $\mathcal{J}$ does not take part to the game in this case. The challenger is simulating it instead.

**PROOF OF PSEUDONYMITY.** Based on the above described modifications in the game (the judge is added and controlled by the challenger), we follow the same sequence of game as in proof of unforgeability. Let us denote it as Game $G^1$.

We have assumed statistical randomization of the certificates of $U_0$ with key pair $(sk_{q_0}, pk_{q_0})$ and $U_1$ with key pair $(sk_{q_1}, pk_{q_1})$ through the RandID algorithm. Hence, there is no link between the keys and the identity. Now, let us assume a distinguisher between $G^1$ with bit $b$ and $\text{Exp}_{\mathcal{A}}^{\text{PSE}}$ with bit $1-b$. Assuming existence of such a distinguisher, we can directly distinguish two randomised certificates. Hence, under the above hypothesis, we can conclude that pseudonymity holds for the auditable version of Applause. We precise an upper bound: $|\text{Pr}[\text{Exp}_{\mathcal{A}}^{\text{PSE}}(1^{\lambda}) \to 1] - \frac{1}{2}| \le \text{Adv}_{\mathcal{A}}^{\text{PayPse}}(1^{\lambda})$. $\square$

**PROOF OF UNLINKABILITY.** The challenger executes the actions of the judge, hence, the adversary cannot recover the user's identity based on the judge's keys $(sk_{\mathcal{J}}, pk_{\mathcal{J}})$. Only an additional certificate is shared with the adversary during Purchase, Refund or Transfer. Even so, this is linked to the user's public key, that we have assumed statistically indistinguishable randomization, leading to impossibility of the recovery of the original identity of the user. Then, $|\text{Pr}[\text{Exp}_{\mathcal{A}}^{\text{UNL}}(1^{\lambda}) \to 1] - \frac{1}{2}| \le 3 \cdot \text{Adv}_{\mathcal{A}}^{\text{PayUnl}}(1^{\lambda})$. $\square$

For the auditable version of Applause in the standard model, the same changes presented in Section C.2 can be applied to the above proof to show its security.