# Taming Delegations in Anonymous Signatures: k-Times Anonymity for Proxy and Sanitizable Signature

Xavier Bultel, Charles Olivier-Anclin

► To cite this version:

Xavier Bultel, Charles Olivier-Anclin. Taming Delegations in Anonymous Signatures: k-Times Anonymity for Proxy and Sanitizable Signature. CANS 2024 - 23rd International Conference on Cryptology and Network Security, Sep 2024, Cambridge, United Kingdom. hal-04644979

HAL Id: hal-04644979

https://hal.science/hal-04644979v1

Submitted on 11 Jul 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

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

Distributed under a Creative Commons Attribution 4.0 International License
# Taming Delegations in Anonymous Signatures: $k$-Times Anonymity for Proxy and Sanitizable Signature

Xavier Bultel¹[0000-0002-8309-8984] and Charles Olivier-Anclin¹,²,³[0000-0002-9365-3259]

¹ LIFO, Université d'Orléans, INSA Centre Val de Loire, Inria, Bourges, France

² Université Clermont Auvergne, LIMOS, CNRS, Clermont-Ferrand, France

³ be ys Pay

**Abstract.** Fully traceable $k$-times anonymity is a security property concerning anonymous signatures: if a user produces more than $k$ anonymous signatures, its identity is disclosed and all its previous signatures can be identified. In this paper, we show how this property can be achieved for delegation-supported signature schemes, especially proxy signatures, where the signer allows a delegate to sign on its behalf, and sanitizable signatures, where a signer allows a delegate to modify certain parts of the signed messages. In both cases, we formalize the primitive, give a suitable security model, provide a scheme and then prove its security under the DDH assumption. The size of the keys/signatures is logarithmic in $k$ in our two schemes, making them suitable for practical applications, even for large $k$.

# 1 Introduction

Proxy signature [25], which enables the signer to delegate the ability to sign messages on its behalf to a delegate, is a standard cryptographic primitive that has attracted a great deal of interest in recent decades. In some contexts, it is preferable to hide the delegate's identity from the signature verifier. Such a signature is called an *anonymous proxy signature* [18]. A trivial way of achieving this property is to give the delegate the signing key directly, however, this technique allows the delegate to impersonate the signer without any constraint, which is clearly not desirable. The signer therefore needs a way of tracing its delegates if one of them abuses their power. This leads to two inherent issues: the signer must be active to manage the trace, and must have access to the signatures.

The concept of traceable $k$-times anonymity offers an alternative way to delegate tracing. Signature schemes following this paradigm allow users to create $k$ signatures anonymously. If they exceed this limit, a verifier can then publicly link two signatures and trace the identity of the signer. This property has been defined for *ring signatures* [19], *group signatures* [2] and *anonymous authentication* [26]. Moreover, a $k$-times signature is said to be *fully traceable* when the verifier can retrieve all the signatures generated by the signer which has exceeded the $k$ limit a *posteriori*. To the best of our knowledge, this more powerful property has only been defined for *ring signatures* [7].

However, $k$-times anonymity has never been applied directly to proxy signatures, even though they seem naturally suited to this property. This would enable a verifier, which has access to all signatures, to publicly trace dishonest proxies on its own, while preserving the anonymity of honest proxies, without the intervention of the signer. In this paper, we close this gap by modeling and instantiating the first fully traceable $k$-times anonymous proxy signature.

On the other hand, sanitizable signatures [1] are conceptually close to proxy signatures: in this primitive, the delegate (called the sanitizer) can no longer produce signatures by itself, but can modify certain parts of a signed message. When considering a setting where the sanitizer must remain anonymous, the same problems arise as with proxy signatures. Applying a similar approach, we propose the first fully traceable $k$-times anonymous sanitizable signatures.

**Contributions and Technical Overview.** We give a formal definition, a security model, and an efficient scheme (in term of size of the keys/signatures) for fully traceable $k$-times anonymous proxy signatures and fully traceable $k$-times anonymous sanitizable signatures. We give security proofs for these schemes. From a technical point of view, we rely on the method proposed in [7]: the delegate has $k$ different public/secret
keys; if it reuses the same key twice, then it is possible to link the two signatures to the user and extract an element that links all its other signatures. However, this method requires a number of keys linear in $k$; our main technical contribution is a method for generating $k$ distinct and mutually unlinkable keys from $2 \log_2(k)$ keys only. The idea is to compose, at the $i^{th}$ signature, the keys corresponding to the bits of $i$ to obtain a new public/secret key pair. These keys must be certified by the delegator, but must be unlinkable. To achieve these two properties simultaneously, we use a signature on equivalence class [17], which allows the delegate to randomize the $2 \log_2(k)$ keys while maintaining the validity of their certificate. This method requires the creation of an ad-hoc zero-knowledge proof ensuring the verifier that the delegate has correctly generated its key. For the special case where $k$ is not a power of 2, we build another ad-hoc zero-knowledge proof to ensure that $i$ is indeed less than $k$. Both of these proofs have logarithmic complexity in size, enabling us to obtain logarithmic complexity in size for both our keys and our signatures. This method is fairly generic, so we think it could be of independent interest in other primitives requiring the generation of several certified keys. Our sanitizable signature scheme uses the same technique as the one proposed in [3] combined with the method described above to make it $k$-times anonymous. The main technical challenge here is to adapt the signature to enable the signer to simulate the use of the $2 \log_2(k)$ keys in the original signature, so that it is not possible to determine whether it has been sanitized or not.

For each signature primitive, we define the following properties in addition to unforgeability:

**Anonymity:** signatures are anonymous as long as the delegate does not exceed $k$ signatures. In particular, they cannot be linked to each other.

**Traceability:** if the delegate exceeds the $k$ signatures limit, it cannot prevent anyone from linking all its signatures and recovering its identity.

**Non-framability:** a delegate cannot produce a signature that can be traced back to someone else.

We also adapt the security properties of sanitizable signatures:

**Immutability:** it is not possible to modify parts of messages that are not intended to be modified.

**Transparency:** it is not possible to guess whether a signature has been sanitized or not. This property implies privacy: it is not possible to determine any information about the original message.

**Unlinkability:** it is not possible to link a sanitized signature to the original signature, or to link sanitized signatures from the same original signature. A few schemes such as [16] achieve this property. Note that unlinkability differs from anonymity, which ensures that it is not possible to link signatures from the same user. We provide more details about this on Section 6.

**Invisibility:** it is not possible to identify which part of the message is modifiable. Note that designing schemes that are both unlinkable and invisible is challenging, and there are only two schemes in the literature that combine these properties [8, 3].

**Motivations.** Anonymous proxy signatures are used wherever an entity wishes to delegate the ability to sign on its behalf to others, without making the delegation policy transparent to the recipient of the messages. Anonymity can also protect proxies when their identity must remain secret, for example in legal proceedings where retaliation is possible. Conversely, anonymity provides a high level of protection for proxies who might be tempted to abuse their power. The fully traceable $k$-times anonymity property can significantly limit this, even in the absence of the delegate. Sanitizable signatures extend proxy signatures by adding a degree of control over the messages sent by delegates. For example, they can be used to force the use of message templates.

For instance, consider a manager who delegates the ability to sign and send emails on their behalf from their email address to multiple entities. These could be employees or servers that automatically send emails that contain, depending on their role, specific messages, appointments, contracts, payments, invoices, reminders, summonses or other legal or commercial documents. If too many emails are being sent from the same entity on behalf of the manager, the company's mail server can use the $k$-times mechanism to locate the offending entity, block the emails it is sending, list all its signatures and alert the manager and anyone else who has received emails from this entity in the past. Note that in our case the server is honest but curious: we trust it to check signatures and detect anomalies (it cannot be fully corrupted by an active attacker),
but the information it processes does not allow it to learn anything about the identity of honest proxies
or the delegation policy (a passive attacker can observe everything that passes through the server without
compromising anonymity).

To control the content of messages, it is helpful to use sanitizable signatures that force delegates to use
templates. For example, by setting the metadata it is possible to allow emails to be sent only to certain
people, on certain dates, with certain subjects, or by forcing the addition of copy users who can check
the content of the email. In the case of automatic emails, such as invoices, it is possible to impose a very
precise template where only the customer's name, date and amount can be changed. Note that thanks to
the security properites of our sanitizable signatures (transparency, anonymity, unlinkability, and invisibility),
the company's delegation policy remains entirely private from the point of view of the verifiers and the mail
server as long as the *k* limit is not exceeded,

**Related works.** Anonymous proxy signatures have been introduced by Fuchsbauer and Pointcheval [18]. Since then, several other anonymous proxy signature schemes have been proposed [27, 28]. However, as mentioned above, they all consider active traceability management by the original signer or a dedicated semi-trusted proxy. Note that unlike our scheme, Fuchsbauer and Pointcheval's scheme allows hierarchical management of proxies (a delegate can allow a sub-delegate to sign in its place, etc.). This feature could naturally be achieved by extending our scheme, despite a linear growth in the number of delegations. This function is left outside of the scope of this work.

*k*-times anonymity has been introduced for authentication, group signature (where the group is managed by an authority that generates keys), and ring signature (where the group is chosen ad-hoc at the time of signing) in [26], [2], and [19] respectively. In some schemes, the identity of the signer leaks if it produces more than *k* signatures. Fully traceable *k*-times anonymity [7] extends this concept by making it possible to trace all signatures produced a priori by the user that exceed the *k* signatures (and not just a pair of signatures). To the best of our knowledge, the only scheme that matches this property is the ring signature described in [7], and this at the cost of a signature size in $O(nk)$ where *n* is the number of users, and a secret key size in $O(k)$.

In [18], Fuchsbauer and Pointcheval mention that anonymous proxy signatures can be seen as group signatures: the delegator becomes the group manager and each delegate (i.e., each group member) can sign anonymously on behalf of the manager (i.e., within the group). We can therefore see our fully traceable *k*-times proxy signature as the first fully traceable *k*-times group signature. Since our aim is also to design sanitizable signatures, which have some similarities with proxy signatures (in both cases a delegator gives a delegate the power to create new signatures on his behalf), we have chosen to present our scheme as an anonymous proxy signature rather than as a group signature. In comparison with the only *k*-times group signature scheme [2] in the literature, our scheme achieves full traceability, in return the key/signature size is in $O(\log(k))$ whereas [2] claims a constant key/signature size (note, however, that in this scheme, the delegator must produce and share a public key of size linear in *k*, moreover if the limit *k* is different for each delegate, then this key must be kept secret by each delegate, which significantly restrains its practicability for large *k*).

Sanitizable signatures were introduced by Ateniese et al. in [1], who identified several security properties (unforgeability, immutability, privacy, transparency, and accountability) later formally defined in [4]. They show that privacy (the original message does not leak from the sanitized signature) is implied by transparency. Invisibility was also introduced in [1] but received formal treatment much later in [9]. Last but not least, unlinkability has been introduced and formalized in [5] and studied in [6, 16]. Only two schemes guarantee all these properties at once [8, 3]. In this paper, we adapt and prove all these properties on our scheme, with the exception of accountability, which consists in allowing the signer to reveal the author (i.e., the original signer or the sanitizer) of a problematic signature, since this information leaks spontaneously if the sanitizer exceeds the limit of *k* sanitizations.

Traceable *k*-times anonymous proxy signatures should not be confused with the *k*-times (not anonymous) proxy signatures introduced by Liu et al. in [24], where if the (non-anonymous) proxy exceeds a limit of *k* signatures, then its secret key leaks. This primitive is close to ours, but differs in two crucial points: (i) the proxy is not anonymous, so there is no need to trace it or link signatures, thus full traceability makes no sense
in [24], and (ii) unlike [24] we do not want to leak the proxy's secret key for security reasons. Indeed, if a verifier recovers a proxy secret key, it can sign messages as a proxy without the original signer having chosen to give it this power. As a result, users which have not had access to the $k+1$ proxy signatures (including the original signer) are unaware that this verifier can impersonate the signer, which causes serious security problems in most applications. Similarly, one line of work, started in [22], aims to limit the sanitizer's power in various ways in sanitizable signatures [11]. In particular, in [22, 11] the authors propose a scheme where if the (non-anonymous) sanitizer exceeds a limit of $k$ signatures, then its secret key leaks, as in k-times (not anonymous) proxy signatures [24]. The differences between this primitive and ours are the same as those between k-times proxy signatures [24] and our k-times anonymous proxy signatures.

Finally, k-times anonymous sanitizable signatures should not be confused with $\gamma$-times sanitizable signatures [3], where $\gamma$ bounds the number of blocks that can be modified instead of the number of times the signature can be sanitized. In the primitive introduced in [3], the sanitizer is not anonymous, and cannot (in the computational sense) sanitize a signature by modifying more than $\gamma$ blocks. The mechanism is therefore very different, as there is no intention of triggering some secret information leak when the limit is exceeded.

## 2 Preliminaries

**Notations.** $r \leftarrow_S S$ means that $r$ is chosen uniformly at random over the set $S$ and $|S|$ is the cardinal of $S$. The operator $\xrightarrow{p}$ denotes the parsing of a tuple or a set of elements. We denote by $y \leftarrow A(x)$ the execution of an algorithm $A$ outputting $y$ on input $x$. When $A$ is probabilistic, $[A]$ denotes the set of all its possible outputs. Considering a second algorithm $O, A^O$ means that the algorithm $A$ has access to $O$ as a black-box oracle. PPT means *Probabilistic Polynomial Time*. $\llbracket n \rrbracket$ denotes the set $\{n\}$. For a vector $m = (m_1, \dots, m_n)$ and an integer $\mu, m^\mu$ denotes the vector $(m_1^\mu, \dots, m_n^\mu)$. $\sqcup$ operates as the union $\cup$ while preserving the repetition of elements, hence producing a multi-set. Finally, $\eta[i]$ refers to the $i^{th}$ bit of some integer $\eta$.

**Mathematical background.** Throughout this paper, we consider a bilinear group setting $(p, \mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_t, e)$ where $\mathbb{G}_1, \mathbb{G}_2$, and $\mathbb{G}_t$ are multiplicative groups of prime order $p, g_1 \in \mathbb{G}_1$ and $g_2 \in \mathbb{G}_2$, and $e$ is a type-3 bilinear pairing $e: \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_t$. We assume the *Decision Diffie-Hellman (DDH)* assumptions over these three groups: given $(g, g^a, g^b, g^z) \in \mathbb{G}^4$, there exists no PPT algorithm in $|p|$ able to decide whether $z = a \cdot b$ or not with non negligible probability$^4$. This assumption implies hardness of the *Discrete Logarithm (DL)* problem: given $(g, g^x) \in \mathbb{G}^2$, there exists no PPT algorithm in $|p|$ able to return $x$ with non-negligible probability. We also consider the relation $\mathcal{R}$ over $(p, \mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_t, e)$ defined by $\mathcal{R} = \{(m, m') \in \mathbb{G}^l \times \mathbb{G}^l \mid \exists \mu \in \mathbb{Z}_p, m' = m^\mu\}$ defining equivalence classes $[M]_\mathcal{R} \subset \mathbb{G}$ for an element $M \in \mathbb{G}^l$.

In what follows, we recall the definitions of structure-preserving signatures for equivalent class, zero-knowledge proofs, and encryption scheme.

**Definition 1 (Class-hiding).** Let $l > 1$ be an integer, and $\mathbb{G}$ be a group. $(\mathbb{G}^*)^l$ is class-hiding if for all PPT adversaries $A$, the following probability is negligible:

$$ \Pr \left[ \begin{array}{l} b \leftarrow_S \{0, 1\}, \quad M \leftarrow_S (\mathbb{G}^*)^l, \quad M^{(0)} \leftarrow_S (\mathbb{G}^*)^l, \quad M^{(1)} \leftarrow_S [M]_\mathcal{R}, \quad b^* \leftarrow A(M, M^{(b)}) \end{array} : b = b^* \right]. $$

**Lemma 1 (Fuchsbauer et al. [17]).** Let $l > 1$ be an integer, and $\mathbb{G}$ be a group of prime order $p$. Then $(\mathbb{G}^*)^l$ is a class hiding message space if and only if the DDH assumption holds in $\mathbb{G}$.

**Definition 2 (SPS-EQ [17]).** A Structure-Preserving Signatures for Equivalence Classes $\mathcal{R}$ SPS-EQ over a group $\mathbb{G}$ is a tuple of algorithms:

*KeyGen_{SPS-EQ}(1^\lambda, l; \mathcal{R})$: given an integer $l > 1$, return a key pair $(pk, sk)$.

*Sign_{SPS-EQ}(sk, m; \mathcal{R})$: given a secret sk and a message $m$, return a signature $\sigma$.

*ChgRep_{SPS-EQ}(m, \sigma, \mu, pk; \mathcal{R})$: given a representative $m$ of an equivalent class, a signature $\sigma$, a scalar $\mu$, and a public key $pk$, return an updated signature $\sigma'$ for the message $m^\mu$.

<footnote>$^4$ A function $\epsilon: \mathbb{N} \to \mathbb{R}^+$ is called negligible, if $\forall c > 0, \exists k_0 \in \mathbb{N}, \forall k > k_0, |\epsilon(k)| < \frac{1}{|k^c|}$.</footnote>
Verif<sub>SPS-EQ</sub>(m, σ, pk; R): given a public key pk, a message m, a signature σ, return 0 or 1 (meaning reject or accept).

We require that SPS-EQ meets Correctness, EUF-CMA, and Signature Adaptation (stating that Sign<sub>SPS-EQ</sub> and ChgRep<sub>SPS-EQ</sub> outputs are identically distributed). We further describe these properties in Appendix A. Since we always use the relation R defined above, we will no longer specify it in the input to the SPS-EQ algorithms.

**Definition 3 (NIZK [12] and SoK [21]).** A Non-Interactive Zero-Knowledge proof (NIZK) for a relation *R* is a pair of PPT algorithms:

ZK{w : (w, φ) ∈ R} : given a witness w and a statement φ, return a proof π,

ZK.Verif(φ, π): given a statement and a proof, return a bit 0 or 1.

A NIZK requires Completeness, Simulation-Extractability and Zero-Knowledge properties to be secure. We recall the definition of these properties in Appendix A.

A Signature of Knowledge (SoK) is similar to a NIZK except that the proof algorithm SoK<sub>m</sub>{w : (w, φ) ∈ R} takes m as an additional parameter. As a consequence, the Simulation-Extractability of a SoK, similar to soudness of NIZK proofs, implies that it can be used as an EUF-CMA signature scheme, where φ is the public key, w is the secret key, m is the signed message, and π is the signature. SoK also achieve Perfect Simulability which is defined similarly to zero-knowledge for NIZK proofs. A signature of knowledge can be constructed from a non-interactive zero knowledge proof based on the Fiat-Shamir heuristic [10].

**Definition 4 (Asymmetric Encryption [20]).** An asymmetric encryption scheme $\mathcal{E}$ is a triple of PPT algorithms:

KeyGen(1<sup>λ</sup>): return a key pair (pk, sk).

Enc(pk, p): given a public key pk and a message p, return a ciphertext c.

Dec(sk, c): given a secret key sk and a ciphertext c, return a message p.

An encryption scheme $\mathcal{E}$ has to achieve Correctness and Indistinguishability under Chosen Ciphertext Attack (IND-CCA). We recall this property in Appendix A.

## 3 k-Times Anonymous Proxy Signature

In this section we give a formal definition and security model for (fully traceable) k-times anonymous proxy signature. In this primitive, a signer can delegate to a proxy the authority to anonymously produce at most k signatures. To do this, the signer generates a delegation certificate (denoted del) via the algorithm Delegate, using the proxy's public key and the limit k as input. To produce a proxy signature, the proxy uses this delegation with an integer $\eta \in \{0, \dots, k-1\}$ that must be different for each k signature. Note that $\eta$ must not appear in the signature to preserve anonymity (we will describe the corresponding security model in more detail later in this section), so it is not given as input to the verification algorithm. If the proxy decides to produce more than k signatures, it will be forced to use the same index $\eta$ twice, triggering a mechanism that allows any user to link these two signatures using an algorithm Link, and to extract the identity of the proxy. The algorithm Link also returns a token w which, when used with a signature as input to the Trace algorithm, indicates whether or not the signature was generated by the same proxy, making it possible to find all signatures generated by the proxy in the past. Note that the signer can extend the limit by generating new delegations for the same proxy.

**Definition 5 (k-APS).** A k-times Anonymous Proxy Signature scheme (k-APS) is a tuple of algorithms:

Setup(1<sup>λ</sup>): given a security parameter, return a public parameter params. Note that params is considered as implicit input of all the following algorithms.

KeyGen(1<sup>λ</sup>, k): given a limit k ∈ N, return the signer secret/public keys (sk, pk).

PKeyGen(1<sup>λ</sup>): return the proxy secret/public keys (psk, ppk).

Delegate(sk, ppk, l): given the keys sk, ppk and l ≤ k, return a delegation certificate del.

Sign(pk, psk, m, del, η): given the keys pk, psk, a message m, a certificate del, and an index η, return a signature σ.
Verify(pk, m, σ): given the key pk, a message m, and a signature σ, return 0 or 1 (for reject or accept).

Link(pk, m, σ, m', σ') : given a public key pk and two message-signature pairs (m, σ), (m', σ'), return identity denoted by the public key ppk of ther signer and a witness w or ⊥ in case of failure.

Trace(w, σ) : given a witness w and a signature σ, return 0 or 1.

A k-APS is said to be correct if, using keys/certificates honestly generated by the algorithms KeyGen, PKeyGen, and Delegate, (i) any signature produced by the algorithm Sign is verified by the algorithm Verify using the signer public key, (ii) 2 signatures are linked by the algorithm Link which outputs the corresponding public key if and only if they were produced with the same delegation certificate and the same η, and (iii) the algorithm Trace returns 1 on the token outputted by Link and any of the signatures produced from this delegation certificate.

Our security model is inspired both by that of anonymous proxy signatures [18] and that of k-times
full traceability [7]. The security experiments and associated oracles are given in Figure 1, with Figure 2
providing a subroutine for the experiment associated to the traceability. For each oracle, the underlined
inputs correspond to those chosen by the opponent. Experiments use multisets (sets that may contain the
same element multiple times) that are considered to be global variables (and can therefore be accessed and
modified in oracles): $\mathcal{U}$ stores the registered users, $\mathcal{D}$ stores the delegations, $\mathcal{S}$ stores the produced signatures,
and $\mathcal{H}$ stores the signature indexes. The security properties required for k-APS are defined as follows:

**Unforgeability.** This property ensures that an adversary playing the role of proxies will not be able to produce a signature unless they have received a delegation certificate. For this property to hold, a PPT adversary $\mathcal{A}$ must forge a valid fresh message/signature pair $(m^*, \sigma^*)$ for a message that has never been queried to the signature oracle. The adversary can request delegation certificates generated for non-corrupted proxies whose secret keys it does not know. A k-APS is *Unforgeable* if for any probabilistic polynomial time algorithm $\mathcal{A}$, the probability $\text{Adv}_{\text{k-APS},\mathcal{A}}^{\text{unf}}(1^{\lambda}) = \text{Pr}[\text{Exp}_{\text{k-APS},\mathcal{A}}^{\text{unf}}(1^{\lambda}) = 1]$ is negligible.

**Anonymity.** The anonymity ensures that the signatures do not disclose the identity of the proxy signer (given by its public key) and that signatures generated by the same proxy signer remain unlinkable. Note that in our model, anonymity only concerns the signature verifiers, and not the delegator; indeed, in our application, there is no reason why the delegator should not know the identity of the proxy signing on its behalf, and it is even rather preferable that it should for accountability reasons. In the corresponding experiment, the adversary chooses a limit $t \le k$, then it tries to distinguish the origin of a challenge signature produced by one of two honest proxies. The adversary can request to the oracles a maximum of $t-1$ signatures for each of the proxies, and a single signature for one of the two proxies (the one chosen by the challenger), which guarantees that the adversary cannot obtain more than $t$ signatures for one of the two proxies (it would trivially link these signatures to the challenge, which is an inherent property of our primitive). For each of the two proxies, the signature oracle increments the index $\eta$ at each signature, which ensures that a $\eta$ is not used twice for the same proxy. Our model therefore considers adversaries trying to link two signatures from two different proxies with the same $\eta$, which would allow the adversary to infer that two signatures are not from the same proxy, and thus generally ensures that $\eta$ is not leaked from the signature.

A k-APS is anonymous if for any PPT $\mathcal{A}$, the probability $\text{Adv}_{\text{k-APS},\mathcal{A}}^{\text{Ano}}(1^{\lambda}) = |\text{Pr}[\text{Exp}_{\text{k-APS},\mathcal{A}}^{\text{Ano}}(1^{\lambda}) = 1]| - 1/2$
is negligible.

**Traceability.** This property guarantees that the Trace algorithm leaks the identity of any adversary over-
passing the delegation limit. In the corresponding experiment, the adversary's target is to produce more
signatures than allowed by the delegator, without the Link and Trace algorithms being able to correctly
link or trace the signatures. For that the adversary can obtain multiple delegation certificates for different
limits and different public keys ppk. Since each delegation certificate allows it to produce $k_i$ signatures, it is
required to produce strictly more than $\sum_{i=1}^{n} k_i$ valid signatures. The adversary wins the experiment if the
number of traced signatures is less than the number of signatures that would have been traced if they had
been generated honestly. This test, which is described in Figure 2, has to take account of all the delegations
that have been exceeded in any execution scenario. First, note that if the limit of a delegation certificate
for a public key is exceeded, then it must be possible to trace all signatures generated by the owner of
that public key, even if they were generated using a different delegation certificate. Thus, the number of
<figure><img src="image_2.png" /><figcaption>**Figure 1:** Experiments and Oracles modeling the Security of *k*-Times Anonymous Proxy Signatures. (Oracles inputs provided by the adversary are underlined, the other are provided by the challenger. The sets *U*, *D*, *S*, *H* are global parameters. Subroutine *CheckTrace* is defined in Figure 2.)</figcaption></figure>
CheckTrace(pk, $(m_i^*, \sigma_i^*)_{i=1}^{q_s}$)

1: if $\mathcal{D}$ is defined, $\mathcal{D} \xrightarrow{p} (\text{pk}_i, \text{del}_i, k_i)_{i=1}^n$ // For proxy signatures only.

2: if $\mathcal{S}$ is defined $\wedge \exists i \in \llbracket q_s \rrbracket$, $(m_i^*, \sigma_i^*, \dots, \sigma_i^*, \dots) \in \mathcal{S}$, return 0 // For sanitizable signatures only.

3: $T \leftarrow 0$, W, ID $\leftarrow \emptyset$, diff $\leftarrow q_s - \sum_{1 \le i \le n} k_i$ // diff is required to be strictly positive.

4: if $(\exists i \in \llbracket q_s \rrbracket, \text{Verify}(\text{pk}, m_i^*, \sigma_i^*) = 0) \lor (\exists i, j \in \llbracket q_s \rrbracket, j \ne i, (m_i^*, \sigma_i^*) = (m_j^*, \sigma_j^*)) \lor (\text{diff} \le 0)$,

5: return 0

6: for $1 \le i < j \le q_s$,

7: $(\text{ppk}_{i,j}, w_{i,j}) \leftarrow \text{Link}(\text{pk}, m_i^*, \sigma_i^*, m_j^*, \sigma_j^*)$ // Try linking any two signatures.

8: if $(\text{ppk}_{i,j}, w_{i,j}) \neq \perp \wedge \text{ppk}_{i,j} \notin \text{ID}$, // Identities for which signatures have been linked.

9: ID $\leftarrow$ ID $\cup \{\text{ppk}_{i,j}\}$, $W[\text{ppk}_{i,j}] \leftarrow W[\text{ppk}_{i,j}] \cup \{w_{i,j}\}$

10: $T \leftarrow \sum_{\text{ppk} \in \text{ID}} \left( \sum_{w \in W[\text{ppk}]} \left( \sum_{i=1}^{q_s} \text{Trace}(w, \sigma_i) \right) \right)$ // Sum up traced signatures and compare it to the number of allowed signatures for these entities.

11: if $T < \sum_{\text{pk}_i \in \text{ID}} k_i + \text{diff}$, return 1, else, return 0

<caption>**Figure 2:** CheckTrace Subroutine for the Traceability Experiment.</caption>

signatures traced $T$ should be at least the sum of the limits $k_i$ of each delegation produced for each public key traced (expressed as $\sum_{\text{pk}_i \in \text{ID}} k_i$ in Figure 2), to which we add the number of signatures that exceed the global sum of the limits for all delegation certificate used by the adversary (expressed as $\text{diff} = q_s - \sum_{i=1}^n k_i$ in Figure 2, where $q_s$ is the number of signatures outputted by the adversary). A k-APS is *traceable* if for any PPT algorithm $\mathcal{A}$, the probability $\text{Adv}_{k\text{APS},\mathcal{A}}^{\text{Trace}}(1^{\lambda}) = \text{Pr}[\text{Exp}_{k\text{APS},\mathcal{A}}^{\text{Trace}}(1^{\lambda}) = 1]$ is negligible.

**Non-Frameability.** This property prevents a PPT adversary from framing someone else by generating malformed yet valid signatures. More precisely, the goal of the adversary is to output two signatures traceable to a registered proxy who remains honest. To help it, the adversary has access to oracles that can be used to register users, obtain delegation certificates, and obtain signatures for honest users. The adversary must of course not have abused the signature oracle by producing more than $k$ signatures for the proxy it wishes to trace. Note that in our model we implicitly assume that the linking of two signatures and the tracing are performed by the same user (we do not consider the case where an adversary only generates a tracing token $w$ that traces an honest user without the linked signatures). In practice, this means that to delegate tracing, the delegate must be provided with the two linked signatures so that it can link them and produce its own token $w$. A k-APS is *Non-Frameable* if for any PPT algorithm $\mathcal{A}$, the probability $\text{Adv}_{k\text{APS},\mathcal{A}}^{\text{no-Frame}}(1^{\lambda}) = \text{Pr}[\text{Exp}_{k\text{APS},\mathcal{A}}^{\text{no-Frame}}(1^{\lambda}) = 1]$ is negligible.

## 4 Our $k$-Times Anonymous Proxy Signature Scheme

In this section, we present our $k$-times anonymous proxy signature (Setup, KeyGen, PKeyGen, Delegate, Sign, Verify, Link, Trace), which uses a bilinear group setting $(\mathcal{P}, \mathcal{G}_1, \mathcal{G}_2, \mathcal{G}_t, \mathcal{E})$ and a SPS-EQ scheme.

*Construction Intuition.* The setup (algorithm Setup) of our construction returns several group elements and the description of a hash function. In particular, the group element $g_1$ will be used as a basis for the proxy public key $\text{ppk} = g_1^{\text{psk}}$ (where $\text{psk}$ is the proxy secret key). The signer key pair (generated from based on KeyGen) is a SPS-EQ key pair supporting vectors of $4l + 1$ group elements in $\mathcal{G}_1$, where $l = \lceil \log_2(k) \rceil$.

To delegate (algorithm Delegate) the power to create $k$ anonymous signatures, the signer will create two sets of $l$ public/secret keys $(y_{i,0}, x_{i,0})_{i \in \llbracket l \rrbracket}$ and $(y_{i,1}, x_{i,1})_{i \in \llbracket l \rrbracket}$. The idea behind this technique is to be able to create $k$ public/secret keys by composing the previous $2\log_2(k)$ keys: given an integer $\eta < k$, the key corresponding to $\eta$ will be composed of the keys corresponding to each of the bits in $\eta$. For each $i$, the signer also produce a Diffie-Hellman key $\text{ppk}_{i,j} = g_1^{\text{psk} \cdot x_{i,j}}$ between $y_{i,j} = g_1^{x_{i,j}}$ and $\text{ppk} = g_1^{\text{psk}}$. This will enable
us to link the keys produced by these elements to the **ppk** owner later on. Finally, all these public keys are signed with an **SPS-EQ**, acting as a certificate, so that they can be randomized. All these elements are stored in the delegation **del**. Thanks to **del**, we have already shown that the proxy can produce **k** distinct pairs of certified ElGamal public/secret keys. The idea of our signature algorithm (**Sign**) is to use one of its keys for each signature. If the same key is used several times, however, it will be possible to find its owner thanks to the mechanism introduced in [7] (this point will be discussed further in this section). However, to preserve anonymity, these keys must not be linkable, so they must be randomized (note that the **SPS-EQ** properties preserve their certification by the signer).

Assume that the delegate is using the algorithm for the $\eta^{th}$ time. First, the delegate randomizes $g_1$ and all the elements $y_{i,j}$ and $\overline{\text{ppk}}_{i,j}$ using the same random $r$ as an exponent, and adapts the **SPS-EQ** accordingly. The randomized version of $g_1$ is denoted $\hat{g}_1$, and the keys are respectively denoted $\hat{y}_{i,j}$ and $\overline{\text{ppk}}_{i,j}$. This first step randomizes all the elements in the delegation $y_{i,j}$ and $\overline{\text{ppk}}_{i,j}$, so that it is not possible to make the link between the randomized delegation $\hat{y}_{i,j}$ and $\overline{\text{ppk}}_{i,j}$ and the original one. Then, the delegate chooses a new random $s$, randomize the basis $\hat{g}_1$ in $\tilde{g}_1$, and randomizes only the $\hat{y}_{i,\eta[i]}$ and $\overline{\text{ppk}}_{i,\eta[i]}$ corresponding to the bits of $\eta$ to obtain the keys $\tilde{y}_i$ and $\overline{\text{ppk}}_i$. The delegate uses a zero-knowledge proof to ensure that the randomization has been done correctly and with an integer $\eta$ actually lower than $k$ (the instantiation of this proof is rather technical and described in more details in the next section). In this way, it is possible to multiply the public keys $\tilde{y} = \prod_{i=1}^l \tilde{y}_i$ and add the corresponding secret keys $x = \sum_{i=1}^l x_{i,\eta[i]}$ to obtain a new public/secret key pair $(\tilde{y}, x)$ that verifies $\tilde{y} = \hat{g}_1^x$. This second step allows the proxy to hide its chosen $\eta$ in the elements $\tilde{y}_i$ and $\overline{\text{ppk}}_i$ (by randomizing the $\hat{y}_{i,\eta[i]}$ and $\overline{\text{ppk}}_{i,\eta[i]}$ again) while preserving the link between the randomized delegation $\hat{y}_{i,j}$ and $\overline{\text{ppk}}_{i,j}$ and the generated key pair $(\tilde{y}, x)$. Note that $\overline{\text{ppk}} = \prod_{i=1}^l \overline{\text{ppk}}_i$ is the Diffie-Hellman of $\tilde{y}$ and $\overline{\text{ppk}}$, which links $\tilde{y}$ to the owner of $\overline{\text{ppk}}$ in a hidden way. It allows the delegate to prove in zero-knowledge that the identity revealed by the mechanism of [7] is indeed the identity of the delegate. This proof, denoted $\pi_\sigma$, also proves that the mechanism of [7] triggers correctly if the delegate signs more than $k$ messages. The technical description of this proof is given in Appendix B.

The signature verification (algorithm **Verify**) consists of re-computing $\tilde{y}$ and $\overline{\text{ppk}}$ and checking that the proof $\pi_\sigma$ is valid. Finally, the **Link** and **Trace** algorithms work in the same way as in [7]: each signature contains $\alpha_1 = h_1^x, \alpha_2 = g_2^t, \alpha_3 = h_3^x \cdot g_1^{u \cdot \text{psk}}$, and $\alpha_4 = h_4^x \cdot h_4^{v \cdot \text{psk}}$. Thus, if the same key $x$ is used twice in signatures, they can be linked since they share the same $\alpha_1 = h_1^x$. Let's note $\alpha'_3 = h_3^x \cdot g_1^{u' \cdot \text{psk}}$ the element $\alpha_3$ of the second signature. It is possible to find the identity of the delegate by computing $(\alpha_3/\alpha'_3)^{1/(u-u')} = \overline{\text{ppk}}$. By a similar way, the token $\omega = h_4^{\text{psk}}$ leaks from $\alpha_4$ when two signatures are linked. Each signature has also the elements $\tau = e(\omega, \alpha_2)$. Without knowledge of $\omega$, $\tau$ is indistinguishable from a random element under the DDH assumption, but a user which knows the delegate's token $\omega$ can retrieve its signatures by recomputing $\tau$, thus achieving full traceability.

**Formal Description.** Below is the formal description of our scheme.

**Setup(1)$^{\lambda}$:** sample $g_1, h_1, h_2, h_3, h_4 \in \mathbb{G}_1$ and $g_2 \in \mathbb{G}_2$, choose a hash function $H: \{0, 1\}^* \to \mathbb{Z}_p^*$, and return them as the common parameters.

**KeyGen(1, k):** set $l = \lceil \log_2(k) \rceil$, and return $(\text{pk}, \text{sk}) \leftarrow \text{KeyGen}_{\text{SPS-EQ}}(1^{\lambda}, 4l + 1)$.

**PKeyGen(1)$^{\lambda}$:** sample $\text{psk} \leftarrow \$\mathbb{Z}_q$ and set $\overline{\text{ppk}} = g_1^{\text{psk}}$. Return the pair $(\text{psk}, \overline{\text{ppk}})$.

**Delegate(sk, ppk, k):** set $l = \lceil \log_2(k) \rceil$, abort if the SPS-EQ key sk does not support message of $4l + 1$ elements. For all $(i, j) \in [l] \times \{0, 1\}$, sample $x_{i,j} \leftarrow \$\mathbb{Z}_p^*$, set $y_{i,j} = g_1^{x_{i,j}}$, $\overline{\text{ppk}}_{i,j} = \overline{\text{ppk}}^{x_{i,j}}$ and produce $\hat{\sigma} \leftarrow \text{Sign}_{\text{SPS-EQ}}(\text{sk}, g_1, y_{1,0}, \dots, y_{l,1}, \overline{\text{ppk}}_{1,0}, \dots, \overline{\text{ppk}}_{l,1})$. Return $\text{del} = ((x_{i,j}, y_{i,j}, \overline{\text{ppk}}_{i,j})_{i \in [l]; j \in \{0,1\}}, \hat{\sigma})$.

**Sign(pk, psk, m, del, \eta):** set $l = \lceil \log_2(k) \rceil$. Sample $r, s \leftarrow \$\mathbb{Z}_p^*$, set $\hat{g}_1 = g_1^r$ and $\tilde{g}_1 = \hat{g}_1^s$. For all $i \in [l]$ and $j \in \{0, 1\}$, compute $\hat{y}_{i,j} = y_{i,j}^r$ and $\overline{\text{ppk}}_{i,j} = \overline{\text{ppk}}_{i,j}^r$, adapt the SPS-EQ signature $\hat{\sigma} \leftarrow \text{ChgRep}_{\text{SPS-EQ}}((g_1, y_{1,0}, \dots, y_{l,1}, \overline{\text{ppk}}_{1,0}, \dots, \overline{\text{ppk}}_{l,1}), \hat{\sigma}, r, \text{pk})$, compute $\tilde{y}_i = \hat{y}_{i,\eta[i]}^s$, and $\overline{\text{ppk}}_i = \overline{\text{ppk}}_{i,\eta[i]}^s$. Generate a zero-knowledge proof $\Pi_{<k}$ of knowledge of $s$ and $\eta$ which proves that (i) $\tilde{y}_i$ and $\overline{\text{ppk}}_i$ are well formed according to $s$ and some integer $\eta$ of $l$ bits and (ii) $\eta < k$. We defer the formalisation of this zero-knowledge proof to
Section 5. Set $x = \sum_{i=1}^{l} x_{i,\eta[i]}; \tilde{y} = \prod_{i=1}^{l} \tilde{y}_i, \tilde{\text{ppk}} = \prod_{i=1}^{l} \tilde{\text{ppk}}_i$, sample $t \leftarrow \mathbb{Z}_p^*$ and compute $\alpha_1 = h_1^x, \alpha_2 = g_2^t, u = H(m, 0, \alpha_2)$ and $v = H(m, 1, \alpha_2)$. Generate the matching elements $\alpha_3 = h_2^x \cdot g_1^{u \cdot \text{psk}}$ and $\alpha_4 = h_3^x \cdot h_4^{v \cdot \text{psk}}$, and the tracing element $\tau = e(h_4, \alpha_2)^{\text{psk}}$. Also generate:

$$ \pi_{\sigma} \leftarrow \text{ZK} \left\{ \text{psk}, x, t: \begin{array}{l} \tilde{y} = \tilde{g}_1^x \wedge \tilde{\text{ppk}} = \tilde{y}^{\text{psk}} \wedge \alpha_1 = h_1^x \wedge \alpha_2 = g_2^t \\ \wedge \alpha_3 = h_2^x \cdot g_1^{u \cdot \text{psk}} \wedge \alpha_4 = h_3^x \cdot h_4^{v \cdot \text{psk}} \wedge \tau = e(h_4, \alpha_2)^{\text{psk}} \end{array} \right\}. $$

Set $\sigma_{\text{del}} = (\tilde{g}_1, ((\tilde{y}_{i,b}, \tilde{\text{ppk}}_{i,b})_{b \in \{0,1\}}, \tilde{y}_i, \tilde{\text{ppk}}_i)_{i \in [l]}, \hat{\sigma}, \Pi_{<k})$ and return the signature $\sigma = (\tilde{g}_1, \alpha_1, \alpha_2, \alpha_3, \alpha_4, \tau, \pi_{\sigma}, \sigma_{\text{del}})$.

* **Verify(m, σ, pk):** parse $\sigma \xrightarrow{p} (\tilde{g}_1, \alpha_1, \alpha_2, \alpha_3, \alpha_4, \tau, \pi_{\sigma}, \sigma_{\text{del}})$ and $\sigma_{\text{del}} \xrightarrow{p} (\tilde{g}_1, ((\tilde{y}_{i,b}, \tilde{\text{ppk}}_{i,b})_{b \in \{0,1\}}, \tilde{y}_i, \tilde{\text{ppk}}_i)_{i \in [l]}, \hat{\sigma}, \Pi_{<k})$. Compute $u = H(m, 0, \alpha_2)$, $v = H(m, 1, \alpha_2)$, $\tilde{y}_n = \prod_{i=1}^{l} \tilde{y}_i$, and $\tilde{\text{ppk}} = \prod_{i=1}^{l} \tilde{\text{ppk}}_i$. Verify the signature $\hat{\sigma}$ and the proofs $\Pi_{<k}$ and $\pi_{\sigma}$. If all checks are correct, returns 1, otherwise 0

* **Link(pk, m, σ, m', σ'):** verify that $\text{Verify(pk}, m, \sigma) = \text{Verify(pk}, m', \sigma') = 1$ and return 0 if $\alpha_1 \neq \alpha'_1$ or if one of the verification failed. Compute $u = H(m, 0, \alpha_2)$, $v = H(m, 1, \alpha_2)$, $u' = H(m', 0, \alpha'_2)$, $v' = H(m', 1, \alpha'_2)$, $\text{ppk} = (\alpha_3/\alpha'_3)^{1/(u-u')}$ and $w = (\alpha_4/\alpha'_4)^{1/(v-v')}$. Return $(\text{ppk}, w)$.

* **Trace(w, σ):** return 1 if and only if $\tau = e(w, \alpha_2)$.

In the following, we informally explain why each of the security properties presented in Section 3 holds in our scheme.

**Unforgeability.** Zero-knowledge proofs produced during the signing process ensure that the delegate has used its certificate correctly. This means that a user who has not been delegated cannot produce a valid fresh signature under the assumption that the proof is sound.

**Anonymity.** Since the elements of the certificate are randomized for each new signature, and since the delegate is able to create public keys $\tilde{y}$ for $k$ different secret keys $x$, it is not possible to link two signatures from the elements $\tilde{y}_{i,j}$ and $\tilde{y}_i$ under the DDH assumption. Recall also that the $\text{ppk}_{i,j}$ and $\text{ppk}_i$ do not allow the signature to be linked to $\text{ppk}$ under the DDH assumption either. On the other hand, the element $h_2^x$ (resp. $h_3^x$) is the Diffie-Hellman of $h_2$ (resp. $h_3$) and $\tilde{y}$ (where $\tilde{y}$ varies with each of the $k$ signatures), and therefore hides the elements linked to the identity of the delegate composing $\alpha_3$ (resp. $\alpha_4$). Finally, $\tau$ hides the value of $\text{ppk}$ under the DDH assumption on the elements $h_4$ and $\text{ppk}$. Assuming that the proofs are indeed zero-knowledge, it is not possible to link two signatures from the same honest user.

**Traceability and Non-Frameability.** Zero-knowledge proofs ensure that the signature is correct and that the delegate knows the secret key corresponding to the public key used in the certificate. Thus, the delegate cannot bypass the mechanism for linking/tracing its signatures if it exceeds the limit, which ensures traceability, and the delegate can only use elements of its own delegation, which ensures non-frameability.

We therefore have the following theorem, the proofs are available in Appendix C.

**Theorem 1.** Instanciated by a signature on equivalent classes that is unforgeable, class-hiding, and signature adaptable, by NIZK proofs which are zero-knowledge and sound, and by a collision-resistante hash function, our k-APS scheme is unforgeable, anonymous, traceable and non-frameable under the DDH assumption in $\mathbb{G}_1$ and $\mathbb{G}_2$.

# 5 Zero-knowledge Proof Instantiation

The proof $\Pi_{<k}$ requires several building blocks. In [13], Chaum and Pedersen introduce a zero-knowledge proof of knowledge for discrete logarithm equality $\text{ZK}\{x : y_1 = g_1^x \wedge y_2 = g_2^x\}$ in a group of prime order $p$. This proof is a sigma protocol: the prover sends a commitment, the verifier sends a challenge (chosen in $\mathbb{Z}_p^*$), and the prover sends a response. This proof can be extended to prove the equality of more than two discret logarithms equalities, in this case the size of the resulted transcript is linear in the number of statements. In general, if two sigma protocols for two instances $\phi_1$ and $\phi_2$ and two relations $\mathcal{R}_1$ and $\mathcal{R}_2$ use the same
proxy signatures defined in Section 3 with the standard features of sanitizable signatures [4, 11, 23, 3]. In particular, each sanitization requires the use of a delegation that can only be used $k$ times, even if it is used for different signatures.

A k-SAN is composed by the algorithms Setup, KeyGen, SaKeyGen, Delegate, Sign, Sanitize, Verify, Link and Trace. With the exception of Sign and Sanitize, all these algorithms are defined in a similar way to k-APS (SaKeyGen correspond to PKeyGen and generate the sanitizer key pair (ssk, spk)). The algorithms Sign and Sanitize are defined as follows:

**Sign($m, \text{ADM}, \text{sk}, \text{spk}$):** given a signer secret key sk, a sanitizer public key spk, a message $m$, a admissible set ADM (which describes the set of all modifications MOD that can be applied to the message), return a signature $\sigma$.

**Sanitize($m, \sigma, \text{MOD}, \text{ssk}, \text{pk}, \text{del}, \eta$):** given the signer public key pk, the sanitizer secret key ssk, a message-signature pair ($m, \sigma$), a modification MOD, a delegation del, a signature index $\eta$, return a signature $\sigma'$ (for the modified message MOD($m$)).

A $k$-times Anonymous Sanitizable Signature scheme is required to achieve *Unforgeability*, *Immutability*, *Transparency*, *Invisibility*, *Unlinkability*, *Anonymity*, *Traceability* and *Non-Frameability*. After describing our scheme, we give some intuition on these requirement and set out how they are achieved.

Note that sanitizable signatures usually have two additional algorithms, Prove and Judge, which allow the delegating signer to reveal a posteriori that a given signature was produced by the sanitizer. In this case, an additional security property, accountability, is required to ensure that the signer cannot blame the sanitizer for a signature it did not produce, and that the sanitizer will not be able to produce a signature that cannot be traced by the signer. Since in this article we are considering a scenario where the tracing of dishonest users is not done by the signer, but by the verifier using the mechanism triggered when the sanitizer produces too many signatures, we have not provided our construction with these algorithms and have not adapted the accountability model.

Our $k$-times anonymous sanitizable signature combines the design of the sanitizable signatures in [8, 3] with the mechanism we introduced in our $k$-times anonymous proxy signature. The signature contains commitments that allows the sanitizer to show that only admissible blocks are modified. More precisely, the sanitizer gives a proof that for every block within the altered message, the commitment corresponds to the hash of the index or the hash of the index combined with its content. If any unauthorized block is altered, then the sanitizer is unable to generate the proof. In addition, the sanitizer produces elements that enable our tracing mechanism to work if it exceeds its sanitization limit. In order to achieve transparency, we show how the signer can simulate these elements in the original signature. This results in two computationally identically distributed signatures outputted by Sign and Sanitize. In what follows, we describe our k-SAN scheme. The Setup algorithm is the same as in Section 4.

**KeyGen($1^{\lambda}, k, n$):** if $n > 1$, set $l = \lceil \log_2(k) \rceil$, and generate two SPS-EQ keys pairs ($pk_{\text{SPS-EQ}}^{\text{del}}, sk_{\text{SPS-EQ}}^{\text{del}}$) $\leftarrow$ KeyGen$_{\text{SPS-EQ}}(1^{\lambda}, 4l+1)$ and ($pk_S^{\text{MOD}}, sk_S^{\text{MOD}}$) $\leftarrow$ KeyGen$_{\text{SPS-EQ}}(1^{\lambda}, 2n)$. Sample $sk_{\text{log}} \leftarrow \$ Z_p^*$ and set $pk_{\text{log}} = g_1^{sk_{\text{log}}}$.$\quad$ Return $pk = (pk_{\text{SPS-EQ}}^{\text{del}}, pk_{\text{SPS-EQ}}^{\text{MOD}})$ and $sk = (sk_{\text{SPS-EQ}}^{\text{del}}, sk_{\text{SPS-EQ}}^{\text{MOD}})$.

**SaKeyGen($1^{\lambda}$):** sample $ssk_{\text{log}} \leftarrow \$ Z_q$, set $spk_{\text{log}} = g_1^{ssk_{\text{log}}}$, run ($ssk_e, spk_e$) $\leftarrow$ KeyGen$_{\mathcal{E}}(1^{\lambda})$ and return $ssk = (ssk_{\text{log}}, ssk_e)$ as the secret key and $spk = (spk_{\text{log}}, spk_e)$ as the public key.

**Delegate($sk, spk, k$):** set $l = \lceil \log_2(k) \rceil$, abort if the SPS-EQ key $sk_{\text{SPS-EQ}}^{\text{del}}$ does not support messages of $4l+1$ group elements. For all $(i, j) \in [l] \times \{0, 1\}$, sample $x_{i,j} \leftarrow \$ Z_p^*$, set $y_{i,j} = g_1^{x_{i,j}}$, $spk_{i,j} = sk_{\text{log}}^{x_{i,j}}$ and produce the SPS signature $\hat{\sigma} \leftarrow \text{Sign}_{\text{SPS-EQ}}(sk_{\text{SPS-EQ}}^{\text{del}}, g_1, y_{1,0}, \dots, spk_{l,1})$. Return $\text{del} = ((x_{i,j}, y_{i,j}, spk_{i,j})_{i \in [l]; j \in \{0,1\}}, \hat{\sigma})$.

Below, we describe the Sign and Sanitize algorithms, drawing parallels between their similarities and specifying their respective executions when they differ.

Both $\text{Sign}(m, \text{ADM}, \text{sk}, \text{spk})$ and $\text{Sanitize}(m, \sigma, \text{MOD}, \text{ssk}, \text{pk}, \text{del}, \eta)$ set $l = \lceil \log_2(k) \rceil$. Then:

**Sign:** Parse $m \xrightarrow{p} m_1 \| \dots \| m_n$, sample $\eta \leftarrow \llbracket 0, k-1 \rrbracket$, $s \leftarrow \$ Z_p^*$, and $\hat{g}_1, \hat{y}_{i,j}, \widehat{\text{spk}}_{i,j} \leftarrow \$ \mathbb{G}_1$ for all $(i, j) \in [l] \times \{0, 1\}$. Simulate a delegation by singing $\hat{\sigma} \leftarrow \text{Sign}_{\text{SPS-EQ}}(sk_{\text{SPS-EQ}}^{\text{del}}, \hat{g}_1, \hat{y}_{1,0}, \dots, \widehat{\text{spk}}_{l,1})$. For all $i \in [l]$ and $j \in \{0, 1\}$, set $\tilde{y}_i = \hat{y}_{i,\eta[i]}$, and $\widehat{\text{spk}}_i = \widehat{\text{spk}}_{i,\eta[i]}$.
**Sanitize:** Parse MOD($m$) $\xrightarrow{p}$ $m_1 \| \cdots \| m_n$, $\sigma \xrightarrow{p}$ (del$_\sigma$, tra, $\pi_\sigma$), $\text{del}_\sigma \xrightarrow{p}$ $(\hat{g}_1, \tilde{g}_1, ((\hat{y}_{i,b}, \widehat{\text{spk}}_{i,b})_{b \in \{0,1\}}, \tilde{y}_i, \widehat{\text{spk}}_i)_{i \in [l]}, \hat{\sigma}$, $\Pi_{<k}$) and tra $\xrightarrow{p}$ $((u_i, v_i)_i^n, \tilde{y}, \alpha_1, \alpha_2, \alpha_3, \alpha_4, \tau, \pi_{\text{MOD}}, \sigma_{\text{MOD}}, e)$ (Note that the values of most of these variables will be updated by reallocation during the algorithm). Then proceeds similarly to the initial steps of the Sign algorithm of the k-APS signature scheme, halting before the execution of the proof $\Pi_{<k}$.

Both algorithms generate the proof $\Pi_{<k}$ of knowledge of $s$ and $\eta$ which proves that $(i) \tilde{y}_i$ and $\widehat{\text{spk}}_i$ are well formed according to $s$ and some integer $\eta$ of $l$ bits and $(ii) \eta < k$. This proof follows the same instantiation as before. To conclude this first part, set $\text{del}_\sigma = (\hat{g}_1, \tilde{g}_1, ((\hat{y}_{i,b}, \widehat{\text{spk}}_{i,b})_{b \in \{0,1\}}, \tilde{y}_i, \widehat{\text{spk}}_i)_{i \in [l]}, \hat{\sigma}, \Pi_{<k})$.

Both algorithms start the second phase by setting the message blocks:

**Sign:** To mandate the sanitizer for a set of modifiable blocks: sample $a \leftarrow \mathbb{Z}_p^*$. For all $i \in \text{ADM}$ let $u_i = H(m_i, i, 0)^a$ and $v_i = H(m_i, i, 1)^a$, otherwise let $u_i = H(i, 0)^a$ and $v_i = H(i, 1)^a$. Encrypt $e \leftarrow \text{Enc}(\text{spk}_e, a)$

**Sanitize:** Sample $b \leftarrow \mathbb{Z}_p^*$, decrypt $a \leftarrow \text{Dec}(\text{ssk}_e, e)$ and update $e \leftarrow \text{Enc}(\text{spk}_e, a \cdot b)$. Set $\text{ADM} = \emptyset$ and $\forall i \in [n]$, let $u_i = H(m_i, i, 0)^{a \cdot b}$ and $v_i = H(m_i, i, 1)^{a \cdot b}$ when the signature contains $H(m_i, i, 0)^a$ and $H(m_i, i, 1)^a$, otherwise let $u_i = H(i, 0)^{a \cdot b}$ and $v_i = H(i, 1)^{a \cdot b}$. Check $\text{MOD} \subset \text{ADM}$ and set $a = a \cdot b$.

Both algorithms prove:

$$ \pi_{\text{MOD}} \leftarrow \text{SoK}_e \left\{ a: \bigwedge_{1 \le i \le n} (u_i = H(m_i, i, 0)^a \wedge v_i = H(m_i, i, 1)^a) \vee (u_i = H(i, 0)^a \wedge v_i = H(i, 1)^a) \right\}. $$

**Sign:** execute $\sigma_{\text{MOD}} \leftarrow \text{Sign}_{\text{SPS-EQ}}(\text{sk}_{\text{SPS-EQ}}^{\text{MOD}}, u_1, v_1, \dots, u_n, v_n)$. Set $\tilde{y} = \prod_{i=1}^l \tilde{y}_i$, $\widehat{\text{spk}} = \prod_{i=1}^l \widehat{\text{spk}}_i$, $u = \sum_{i=1}^n u_i$, $v = \sum_{i=1}^n v_i$ and sample the elements $\alpha_1, \alpha_3, \alpha_4 \leftarrow \mathbb{G}_1, \alpha_2 \leftarrow \mathbb{G}_2$ and a tracing element $\tau \leftarrow \mathbb{G}_t$.

**Sanitize:** Adapt $\sigma_{\text{MOD}}$ according to the randomness $b$: $\sigma_{\text{MOD}} \leftarrow \text{ChgRep}_{\text{SPS-EQ}}((u_1, v_1, \dots, u_n, v_n), \sigma_{\text{MOD}}, b, \text{pk}_{\text{SPS-EQ}}^{\text{MOD}})$. Set $x = \sum_{i=1}^l x_{i, \eta[i]}$, $\tilde{y} = \prod_{i=1}^l \tilde{y}_i$, $\widehat{\text{spk}} = \tilde{y}^{\text{ssk}_{\text{log}}}$, and compute $\alpha_1 = h_1^x$. Let $u = \sum_{i=1}^n u_i$, $v = \sum_{i=1}^n v_i$ and sample $t \leftarrow \mathbb{Z}_p^*$. Compute $\alpha_2 = g_2^t$, the matching elements $\alpha_3 = h_2^x \cdot g_1^{u \cdot \text{ssk}_{\text{log}}}$, $\alpha_4 = h_3^x \cdot h_4^{v \cdot \text{ssk}_{\text{log}}}$ and a tracing element $\tau = e(h_4, \alpha_2)^{\text{ssk}_{\text{log}}}$. Compute $\alpha_3 = h_3^x \cdot g_1^{u \cdot \text{ssk}_{\text{log}}} \wedge \alpha_4 = h_4^x \cdot h_4^{v \cdot \text{ssk}_{\text{log}}} \wedge \tau = e(h_4, \alpha_2)^{\text{ssk}_{\text{log}}} \vee (\text{pk}_{\text{log}} = g_1^{\text{sk}_{\text{log}}})$.

The vector of elements tra = $((u_i, v_i)_i^n, \tilde{y}, \alpha_1, \alpha_2, \alpha_3, \alpha_4, \tau, \pi_{\text{MOD}}, \sigma_{\text{MOD}}, e)$ is set by both entities and embed in a signature of knowledge where the sanitizer proves the first part of the or statement and the signer the second part:

$$ \begin{aligned} \pi_{\sigma} \leftarrow \text{SoK}_{(\text{del}, \text{tra})} \{ & \text{sk}_{\text{log}} : (\tilde{y} = \hat{g}_1^{x \cdot s} \wedge \widehat{\text{spk}} = \tilde{y}^{\text{ssk}_{\text{log}}} \wedge \alpha_1 = h_1^x \wedge \alpha_2 = g_2^t \wedge \\ & \alpha_3 = h_2^x \cdot g_1^{u \cdot \text{ssk}_{\text{log}}} \wedge \alpha_4 = h_3^x \cdot h_4^{v \cdot \text{ssk}_{\text{log}}} \wedge \tau = e(h_4, \alpha_2)^{\text{ssk}_{\text{log}}} \vee (\text{pk}_{\text{log}} = g_1^{\text{sk}_{\text{log}}}) \}. \end{aligned} $$

Finally Sign and Sanitize return the signature $\sigma = (\text{del}_\sigma, \text{tra}, \pi_\sigma)$.

The signature verification consists of re-computing the elements that are necessary for the verification of every SPS-EQ and signature of knowledge.

We will now informally describe the security properties of k-SAN (we recall that the formal definition can be found in Appendix E) and explain why they hold on our scheme, except for anonymity, traceability and non-frameability that are reached in a similar way to our k-APS (Section 4).

**Unforgeability.** The users cannot generate a valid signature without knowing a secret key which has obtained a delegation. This property relies on the hardness of recovering the secret key of the signer or one of the sanitizers, which is ensured by the DDH assumption. Once this have been ruled out, we can reduce the ability of an adversary to forge a signature to its ability to forge SPS signatures.

**Immutability.** A sanitizable signature is immutable when no adversary is able to sanitize with unauthorized modification. This property relies on the collision resistance of the hash function, as well as the soundness and zero-knowledge properties of the signature of knowledge $\pi_{\text{MOD}}$ (as they link the message to the signature). Moreover, the EUF-CMA security of the SPS-EQ and the DDH assumption prevent impersonation of the signer.
**Transparency.** The verifier cannot decide whether a given signature has been sanitized or not, which means that the outputs of Sign and Sanitize should be computationally indistinguishable. The randomised delegation encompassed in the signature is identically distributed to a newly produced one. All SoK can be produced by both the signer and the sanitizer, while the other elements are shown to computationally indistinguishable based on the DDH problem.

**Invisibility.** The invisibility property prevents an adversary which is not the signer nor the sanitizer of a signature from determining any information on the modifiable blocks. The difference between a modifiable block and a non-modifiable block is the input of the hash function serving as a commitment. The obtained hash is then elevated to a secret random power. Therefore, invisibility mainly relies on the class hiding property (Definition 1).

**Unlinkability.** Considering a fixed sanitizer assigned with two signatures, the verifier cannot link a sanitized signature with its original version. In the proposed signature scheme, all elements undergo randomization during sanitization or are entirely new, which ensures this property.

**Anonymity versus unlinkability.** We highlight the fact that, although conceptually close, the properties of unlinkability and anonymity capture independent attack scenarios. In unlinkability, the adversary tries to link signatures modified for a single known sanitizer, while in anonymity, the adversary has to guess the identity of an unknown sanitizer for a given message and can control the modifications this sanitizer makes to these signatures. Since in anonymity the adversary chooses for itself how and by whom signatures are modified via oracles, knowing how to link a sanitized signatures to its original gives it no advantage. Note that for signatures sanitized by the unknown sanitizer that the adversary has to determine, the sanitization oracle will always use the key of the unknown sanitizer, thus avoiding trivial attacks where the adversary tests whether the sanitization of its signature by a chosen sanitizer fails or not.

On the other hand, in unlinkability, the adversary receives a signature sanitized by a given user, and must determine the original signature used. As the original signature can only be sanitized by one sanitizer chosen a *priori* by the signer, guessing the identity of this sanitizer by attacking anonymity gives the adversary no advantage. So there is no implication between unlinkability and anonymity.

Note that when the $k$ limit is exceeded, it is the identity of the sanitizer and the link between their signatures that are leaked, but it is still not possible to link the sanitized signatures to the original signatures; we link the signatures of a sanitizer, but the unlinkability property still holds for these signatures.

We therefore have the following theorem, the proofs are available in Appendix F.

**Theorem 2.** *Instanciated by a signature on equivalent classes that is unforgeable, class-hiding, and signature adaptable, by NIZK proofs which are zero-knowledge and sound, by a collision-resistante hash function, by a SoK that is perfectly-simulability and simulation-extractability, and by an IND-CCA public key encryption, our k-SAN is unforgeable, immutable, transparent, unlinkable, anonymity, invisible, k-traceable and non-frameable under the DDH assumption in $G_1$ and $G_2$ in the random oracle model.*

# 7 Conclusion

In this paper, we mitigate for practical purposes the delegations carried out through some signatures with anonymity. To this end, we define full traceable $k$-times anonymity for proxy signatures and sanitizable signatures. In both cases, we define a security model, give an efficient scheme (in the sense that the size of keys and signatures is logarithmic in $k$), and prove its security. In the future, we would like to address two problems that we leave open: the construction of $k$-times proxy/sanitizable signature schemes that produce signatures of constant size, and the construction of schemes that do not require the generic group model (required for equivalence class signatures).

**Acknowledgments.** This article is an extended version of a paper published at the CANS 24 conference. The authors would like to thank Jan Bobolz and the anonymous reviewers of CANS 2024 conference for their valuable
and insightful comments. Xavier Bultel's research was supported by the ANR project PRIV-SIQ (ANR-23-CE39-0008). Charles Olivier-Anclin's research was partially supported by the ANR projet MobiS5 (ARN-18-CE39-0019).

## References

1. Ateniese, G., Chou, D.H., De Medeiros, B., Tsudik, G.: Sanitizable signatures. In: Computer Security-ESORICS 2005: 10th European Symposium on Research in Computer Security (2005)

2. Au, M.H., Susilo, W., Yiu, S.M.: Event-oriented k-times revocable-iff-linked group signatures. In: ACISP 2006 (2006)

3. Bossuat, A., Bultel, X.: Unlinkable and invisible $\gamma$-sanitizable signatures. In: International Conference on Applied Cryptography and Network Security (2021)

4. Brzuska, C., Fischlin, M., Freudenreich, T., Lehmann, A., Page, M., Schelbert, J., Schröder, D., Volk, F.: Security of sanitizable signatures revisited. In: Public Key Cryptography-PKC 2009: 12th International Conference on Practice and Theory in Public Key Cryptography (2009)

5. Brzuska, C., Fischlin, M., Lehmann, A., Schröder, D.: Unlinkability of sanitizable signatures. In: PKC 2010 (2010)

6. Brzuska, C., Pöhls, H.C., Samelin, K.: Efficient and perfectly unlinkable sanitizable signatures without group signatures. In: Public Key Infrastructures, Services and Applications: 10th European Workshop (2014)

7. Bultel, X., Lafourcade, P.: k-times full traceable ring signature. In: 2016 11th International Conference on Availability, Reliability and Security (2016)

8. Bultel, X., Lafourcade, P., Lai, R.W., Malavolta, G., Schröder, D., Thyagarajan, S.A.K.: Efficient invisible and unlinkable sanitizable signatures. In: 22nd IACR International Conference on Practice and Theory of Public-Key Cryptography (2019)

9. Camenisch, J., Derler, D., Krenn, S., Pöhls, H.C., Samelin, K., Slamanig, D.: Chameleon-hashes with ephemeral trapdoors. In: PKC 2017 (2017)

10. Camenisch, J., Stadler, M.: Efficient group signature schemes for large groups. In: Advances in Cryptology — CRYPTO '97 (1997)

11. Canard, S., Jambert, A.: On extended sanitizable signature schemes. In: Cryptographers' Track at the RSA Conference (2010)

12. Chase, M., Lysyanskaya, A.: On signatures of knowledge. In: Advances in Cryptology-CRYPTO: 26th Annual International Cryptology Conference (2006)

13. Chaum, D., Pedersen, T.P.: Wallet databases with observers. In: Advances in Cryptology — CRYPTO' 92 (1993)

14. Cramer, R., Damgård, I., Schoenmakers, B.: Proofs of partial knowledge and simplified design of witness hiding protocols. In: CRYPTO '94 (1994)

15. Fiat, A., Shamir, A.: How to prove yourself: Practical solutions to identification and signature problems. In: CRYPTO' 86 (1987)

16. Fleischhacker, N., Krupp, J., Malavolta, G., Schneider, J., Schröder, D., Simkin, M.: Efficient unlinkable sanitizable signatures from signatures with re-randomizable keys. In: 19th IACR International Conference on Practice and Theory in Public-Key Cryptography (2016)

17. Fuchsbauer, G., Hanser, C., Slamanig, D.: Structure-preserving signatures on equivalence classes and constant-size anonymous credentials. Journal of Cryptology (2019)

18. Fuchsbauer, G., Pointcheval, D.: Anonymous proxy signatures. In: Security and Cryptography for Networks: 6th International Conference (2008)

19. Fujisaki, E., Suzuki, K.: Traceable ring signature. In: Public Key Cryptography - PKC 2007 (2007)

20. Goldwasser, S., Micali, S.: Probabilistic encryption. Journal of Computer and System Sciences (1984)

21. Groth, J., Maller, M.: Snarky signatures: Minimal signatures of knowledge from simulation-extractable snarks. In: Annual International Cryptology Conference (2017)

22. Klonowski, M., Lauks, A.: Extended sanitizable signatures. In: Proceedings of the 9th International Conference on Information Security and Cryptology. ICISC'06 (2006)

23. Krenn, S., Samelin, K., Sommer, D.: Stronger security for sanitizable signatures. In: International Workshop on Data Privacy Management (2015)

24. Liu, W., Yang, G., Mu, Y., Wei, J.: k-time proxy signature: Formal definition and efficient construction. In: Provable Security: 7th International Conference, ProvSec 2013, Melaka, Malaysia, October 23-25, 2013. Proceedings 7 (2013)

25. Mambo, M., Usuda, K., Okamoto, E.: Proxy signatures for delegating signing operation. In: Proceedings of the 3rd ACM Conference on Computer and Communications Security. CCS '96 (1996). https://doi.org/10.1145/238168.238185
26. Teranishi, I., Furukawa, J., Sako, K.: k-times anonymous authentication (extended abstract). In: ASIACRYPT 2004 (2004)

27. Wei, J., Yang, G., Mu, Y.: Anonymous proxy signature with restricted traceability. In: 2014 IEEE 13th International Conference on Trust, Security and Privacy in Computing and Communications (2014)

28. Wei, J., Yang, G., Mu, Y., Liang, K.: Anonymous Proxy Signature with Hierarchical Traceability. The Computer Journal (2015)

# Auxiliary Supporting Material

## A Security Properties of our Building Blocks

*Security of SPS-EQ Schemes* We require that SPS-EQ meets the following requirements:

**Correctness:** for all $l \in \mathbb{N}$, $(pk, sk)$, $m \in \mathbb{G}^l$, and $\mu \in \mathbb{Z}_p^*$, the following equations should be true : $\text{Verif}_{\text{SPS-EQ}}(m, \text{Sign}_{\text{SPS-EQ}}(sk, m; \mathcal{R}), pk; \mathcal{R}) = 1$ and $\text{Verif}_{\text{SPS-EQ}}(\mu m, \text{ChgRep}_{\text{SPS-EQ}}(m, \text{Sign}(sk, m; \mathcal{R})), \mu, pk; \mathcal{R}), pk; \mathcal{R}) = 1$.

**EUF-CMA** (existential unforgeability under adaptive chosen-message attacks): let $l > 1$ and $1^\lambda$ a given security parameter;

$$ \Pr \left[ \begin{array}{l} (pk, sk) \in [\text{KeyGen}_{\text{SPS-EQ}}(1^\lambda, l; \mathcal{R})], \\ (m^*, \sigma^*) \leftarrow \mathcal{A}^{\text{Sign}_{\text{SPS-EQ}}(\cdot, sk; \mathcal{R})}(pk, l) \end{array} \middle| \begin{array}{l} \forall m \in \mathcal{S}, m^* \notin [m]_{\mathcal{R}} \land \\ \text{Verif}_{\text{SPS-EQ}}(m, \sigma, pk; \mathcal{R}) \end{array} \right], $$

is negligible for every PPT adversary $\mathcal{A}$ where $\mathcal{S}$ is the set of queries that $\mathcal{A}$ has issued to the signing oracle.

**Signature Adaptation:** let $l > 1$ and $1^\lambda$ a given security parameter, $(pk, sk) \in [\text{KeyGen}(1^\lambda, l; \mathcal{R})]$, $\mu \in \mathbb{Z}_p^*$ and $m \in \mathbb{G}^l$. For all tuples $(sk, pk, m, \sigma, \mu)$ the distributions of $\text{Sign}(sk, m; \mathcal{R})$ and $\text{ChgRep}(m, \sigma, \mu, pk; \mathcal{R})$ are identical.

*Security of NIZK proofs* A NIZK requires the following properties:

**Completeness:** For any $(w, \phi) \in \mathcal{R}$, ZK. Verif($\phi$, ZK{$w : (w, \phi) \in \mathcal{R}$}) = 1.

**Simulation-Extractability:** For all PPT adversary $\mathcal{A}$ returning a valid proof on the statement $\phi^*$ with non-negligible probability, there exists a PPT extractor $\text{Ext}_{\mathcal{A}}$ returning $w^*$ such that $(w^*, \phi^*) \in \mathcal{R}$ with overwhelming probability. This implies that no PPT algorithm can output a valid proof on a false statement with non-negligible probability.

**Zero-Knowledge:** For any $(w, \phi) \in \mathcal{R}$, there exists a PPT algorithm $\text{Sim}(\phi)$ that follows the same probability distribution as ZK{$w : (w, \phi) \in \mathcal{R}$}.

*Security for Asymmetric Encryption Schemes* An encryption scheme $\mathcal{E}$ has to achieve Correctness and Indistinguishability under Chosen Ciphertext Attack. (IND-CCA) Formally, for all PPT adversary $\mathcal{A}$, given a decryption oracle $\text{Dec}(sk, \cdot)$ (which rejects the challenge $c$), has at most a negligible probability

$$ \left| \Pr \left[ \begin{array}{l} (sk, pk) \leftarrow \mathcal{S} \text{ KeyGen}(1^{\lambda}), (m_0, m_1) \leftarrow \mathcal{A}^{\text{Dec}(sk, \cdot)}(pk) \\ b \leftarrow \mathcal{S} \{0, 1\}, c \leftarrow \text{Enc}(pk, m_b), b^* \leftarrow \mathcal{A}^{\text{Dec}(sk, \cdot)}(c) \end{array} : b = b^* \right] - \frac{1}{2} \right| $$

## B Instantiation of the Proof $\Pi_\sigma$

In this section, we show how to instantiate the proof $\pi_\sigma$ used in Section 4. For the sake of clarity, we rewrite this proof with more generic notations (where for any integer $i$, each $g_i$, $\gamma_i$, and $h_i$ is an element of a group $\mathbb{G}_i$ of the same prime order $p$):

$$ \pi_{\sigma} \leftarrow \text{ZK} \left\{ x, y, z: \begin{array}{l} h_1 = g_1^x \wedge h_2 = g_2^y \wedge h_3 = g_3^x \wedge h_4 = g_4^z \\ h_5 = g_5^x \cdot \gamma_5^y \wedge h_6 = g_6^x \cdot \gamma_6^y \wedge h_7 = g_7^y \end{array} \right\}. $$

Our construction follows the Schnorr protocol structure:
- The prover picks $(r, s, t) \stackrel{\$}{\leftarrow} \mathbb{Z}_p^3$ and sets $R_1 = g_1^r; S_2 = g_2^s; R_3 = g_3^r; T_4 = g_4^t; R_5 = g_5^r; S_5 = g_5^s; R_6 = g_6^s; S_5 = g_6^s$; and $S_7 = g_7^s$. The prover sends $(R_1, S_2, R_3, T_4, R_5, S_5, R_6, S_5, S_7)$ to the verifier.

- The verifier picks a challenge $c \stackrel{\$}{\leftarrow} \mathbb{Z}_p$ and sends it to the prover.

- The prover computes $\alpha = r + x \cdot c, \beta = s + y \cdot c$, and $\delta = t + z \cdot c$, then sends $(\alpha, \beta, \gamma)$ to the verifier.

- If the following equations holds, then the verifier accepts the proof, else the verifier rejects: $g_1^\alpha = R_1 \cdot h_1^c$; $g_2^\beta = S_2 \cdot h_2^c$; $g_3^\alpha = R_3 \cdot h_3^c$; $g_4^\delta = T_4 \cdot h_4^c$; $g_5^\alpha \cdot \gamma_5^\beta = R_5 \cdot S_5 \cdot h_5^c$; $g_6^\alpha \cdot \gamma_6^\beta = R_6 \cdot S_6 \cdot h_6^c$; and $g_7^\beta = S_7 \cdot h_7^c$.

This proof is **complete** by construction.

To show that this proof is **sound**, we show that knowing two valid transcripts $\tau_0 = ((R_1, S_2, R_3, T_4, R_5, S_5, R_6, S_5, S_7), c_0, (\alpha_0, \beta_0, \gamma_0))$ and $\tau_1 = ((R_1, S_2, R_3, T_4, R_5, S_5, R_6, S_5, S_7), c_1, (\alpha_1, \beta_1, \gamma_1))$ using both the same commitment $(R_1, S_2, R_3, T_4, R_5, S_5, R_6, S_5, S_7)$ but different challenges $c_0$ and $c_1$, it is possible to deduce $(x, y, z)$ in polynomial time (special soundness). Since the two transcripts are valid, we have: $g_1^{\alpha_0} = R_1 \cdot h_1^{c_0}$; $g_2^{\beta_0} = S_2 \cdot h_2^{c_0}$; $g_3^{\alpha_0} = R_3 \cdot h_3^{c_0}$; $g_4^{\delta_0} = T_4 \cdot h_4^{c_0}$; $g_5^{\alpha_0} \cdot \gamma_5^{\beta_0} = R_5 \cdot S_5 \cdot h_5^{c_0}$; $g_6^{\alpha_0} \cdot \gamma_6^{\beta_0} = R_6 \cdot S_6 \cdot h_6^{c_0}$; $g_7^{\beta_0} = S_7 \cdot h_7^{c_0}$; $g_1^{\alpha_1} = R_1 \cdot h_1^{c_1}$; $g_2^{\beta_1} = S_2 \cdot h_2^{c_1}$; $g_3^{\alpha_1} = R_3 \cdot h_3^{c_1}$; $g_4^{\delta_1} = T_4 \cdot h_4^{c_1}$; $g_5^{\alpha_1} \cdot \gamma_5^{\beta_1} = R_5 \cdot S_5 \cdot h_5^{c_1}$; $g_6^{\alpha_1} \cdot \gamma_6^{\beta_1} = R_6 \cdot S_6 \cdot h_6^{c_1}$; and $g_7^{\beta_1} = S_7 \cdot h_7^{c_1}$. Setting $x = (\alpha_1 - \alpha_0)/(c_1 - c_0)$; $y = (\beta_1 - \beta_0)/(c_1 - c_0)$; and $z = (\delta_1 - \delta_0)/(c_1 - c_0)$ and using the equations above, we find that: $h_1 = g_1^x$; $h_2 = g_2^y$; $h_3 = g_3^x$; $h_4 = g_4^z$; $h_5 = g_5^x \cdot \gamma_5^y$; $h_6 = g_6^x \cdot \gamma_6^y$; and $h_7 = g_7^y$, which concludes the proof of soundness.

We show that this proof is **zero-knowledge** by giving a polynomial-time simulator that outputs transcripts indistinguishable from the transcripts of the real protocol without using the secret value $(x, y, z)$. The simulator picks $(c, \alpha, \beta, \delta) \stackrel{\$}{\leftarrow} \mathbb{Z}_p^4; R_5 \stackrel{\$}{\leftarrow} \mathbb{G}_5$; and $R_6 \stackrel{\$}{\leftarrow} \mathbb{G}_6$. Then the simulator computes: $R_1 = g_1^\alpha/h_1^c$; $S_2 = g_2^\beta/h_2^c$; $R_3 = g_3^\alpha/h_3^c$; $T_4 = g_4^\delta/h_4^c$; $S_5 = (g_5^\alpha \cdot \gamma_5^\beta)/(R_5 \cdot h_5^c)$; $S_6 = (g_6^\alpha \cdot \gamma_6^\beta)/(R_6 \cdot c d o t h_c^6)$; and $S_7 = g_7^\beta/h_7^c$. The simulator returns $((R_1, S_2, R_3, T_4, R_5, S_5, R_6, S_5, S_7), c, (\alpha, \beta, \gamma))$.

Finally, as this proof is a sigma protocol, it can be made **non-interactive** using the Fiat-Shamir transformation [15].

## C Proof of Theorem 1

*Proof.* Let $\mathcal{A}$ be a PPT adversary against each of the experiments. $\text{Adv}_{G_i, G_{i+1}}^{\text{diff}}(\mathcal{A})$ denotes the probability $|\text{Pr}[G_i(\mathcal{A}) = 1] - \text{Pr}[G_{i+1}(\mathcal{A}) = 1]|$. We investigate each of the properties independently.

**Correctness.** It is verified by investigation.

**Unforgeability.** Let $\text{Game}_0^{\text{unf}}$ denote the experiment $\text{Exp}_{k-\text{APS}, \mathcal{A}}(1^{\lambda})$ instantiated by the Log Size k-APS.

**Game**$_1^{\text{unf}}$: is similar to $\text{Game}_0^{\text{unf}}$ but we abort if there is a collision for the responses of the hash function in the elements that the challenger sees.

*Claim.* We claim that the adversary's $\mathcal{A}$ advantage in hybrids $\text{Game}_0^{\text{unf}}$ and $\text{Game}_1^{\text{unf}}$ only differs by a negligible factor, i.e., $\text{Adv}_{G_0, G_1}^{\text{diff}}(\mathcal{A}) \le \text{Adv}_H^{\text{col-resist}}$.

The reduction is straightforwardly achieved based on a record of the hashes. The reduction returns the collisions it sees.

**Game**$_2^{\text{unf}}$: is similar to $\text{Game}_1^{\text{unf}}$ but the witness $(\text{psk}^*, \text{psk}_i^*, r^*)$ is extracted from the proof NIZK proof $\pi_\sigma^*$ and matched with the signature's elements.

*Claim.* We claim that the adversary's advantage in hybrids $\text{Game}_1^{\text{unf}}$ and $\text{Game}_2^{\text{unf}}$ only differs by a negligible factor, i.e., $\text{Adv}_{G_1, G_2}^{\text{diff}}(\mathcal{A}) \le \text{Adv}_{\text{NIZK}}^{\text{sound}}$.

The reduction is direct to the soundness of the NIZK proof.

$\text{Game}_3^{\text{unf}}$ (enabling step): is similar to $\text{Game}_2^{\text{unf}}$ but the proof $\pi_\sigma$ is simulated on calls to the signing oracle. The reduction directly follows from the zero-knowledge property of the NIZK proof. Hence, the adversary's advantage only differs by a negligible factor, i.e., $\text{Adv}_{G_2, G_3}^{\text{diff}}(\mathcal{A}) \le q_{\text{Sign}} \cdot \text{Adv}_{\text{NIZK}}^{\text{ZK}}$, where $q_{\text{Sign}}$ represent the number of calls to the signing oracle.
**Game**<sub>4</sub><sup>unf</sup> (enabling step): is similar to **Game**<sub>3</sub><sup>unf</sup> but we define $h_4 = g_1^{r_4}$ based on a random value $r_4 \leftarrow \$ \mathbb{Z}_p^*$. This elements keeps the same distribution, thus, the adversary has indistinguishable viewing of these two experiments.

**Game**<sub>5</sub><sup>unf</sup>: is similar to **Game**<sub>4</sub><sup>unf</sup> but we abort if the signature $\sigma^*$ has been produced for a registered user. This is check by verifying if $(g_1^{\text{psk}^*}, \text{psk}^*) \in \mathcal{U}$.

*Claim.* We claim that the adversary's advantage in hybrids $\text{Game}_4^{\text{unf}}$ and $\text{Game}_5^{\text{unf}}$ only differs by a negligible factor, i.e., $\text{Adv}_{\text{G}_4, \text{G}_5}^{\text{diff}}(\mathcal{A}) \le q_{\mathcal{U}} \cdot \text{Adv}_{\text{G}_1}^{\text{DL}}$.

*Reduction.* Consider a sequence of hybrids $H_1, \dots, H_{q_{\mathcal{U}}}$, where we expect the difference in between two consecutive experiments to be at most $\text{Adv}_{\text{G}_1}^{\text{DL}}$. Define $H_i$ as $\text{Game}_4^{\text{unf}}$ where the game is aborted if $(g_1^{\text{psk}^*}, \text{psk}^*) \in \mathcal{U}$ was produced during the $i$-first calls to $\mathcal{O}_{\text{Register}}^{\text{unf}}$. It follows that $H_0 = \text{Game}_4^{\text{unf}}$ and $H_{q_{\mathcal{U}}} = \text{Game}_5^{\text{unf}}$. Consider $\mathcal{R}_i$ the reduction simulating $H_i$ and additionally receiving a challenge $X = g_1^x \in \mathbb{G}_1$ to the DL problem. On the $i$-th call to $\mathcal{O}_{\text{Register}}^{\text{unf}}$, $\mathcal{R}_i$ sets the key of the user generated on as $\text{ppk} = X$. From the previous bridging, we can compute the elements involving the key $\text{psk}: \alpha_3 = h_2^x \cdot \text{ppk}^u; \alpha_4 = h_3^x \cdot \text{ppk}^{v \cdot r_4}; \tau = e(\text{ppk}^{r_4}, \alpha_2)$ an output $\pi_{\sigma}$ based on the simulator, which allows us to output valid signatures. Receiving a response from $\mathcal{A}$, we can transfer the extracted value $\text{psk}^*$ as an answer to the challenger of the DL problem. An adversary winning against $H_i$ and not against $H_{i+1}$ would have output a valid answer, as this is only possible with negligible probability $\text{Adv}_{\text{G}_1}^{\text{DL}}$, we have proven our claim.

*Analysis.* Forgery of the NIZK proof $\pi_{\sigma}$ or adversarial produced NIZK proofs for registered users leads to an abort in $\text{Game}_5^{\text{unf}}$. Hence, the adversary $\mathcal{A}$ can only output signatures for unregistered users.

*Claim.* The adversary's $\mathcal{A}$ advantage in hybrid $\text{Game}_5^{\text{unf}}$ is negligible, given that the SPS-EQ scheme is existentially unforgeable under adaptive chosen-message attacks, i.e., $\text{Adv}_{\text{G}_5}^{\text{unf}}(\mathcal{A}) \le \text{Adv}_{\text{SPS-EQ}}^{\text{EUF-CMA}}$.

*Reduction.* Consider an adversary $\mathcal{A}$ winning against $\text{Game}_5^{\text{unf}}$. Let $\mathcal{R}$ be a reduction emulating between the answers of $\mathcal{A}$ and $\text{Exp}_{\text{SPS-EQ}}^{\text{EUF-CMA}}$. We implement $\mathcal{R}$ straightforwardly setting $\text{pk}$ as the public key received from the challenger against $\text{Exp}_{\text{SPS-EQ}}^{\text{EUF-CMA}}$. To issue $\hat{\sigma}$ on a call to $\mathcal{O}_{\text{Delegated}}^{\text{unf}}$, $\mathcal{R}$ calls the signing oracle for the message $(g_1, y_{1,0}, \dots, \text{ppk}_{l,1})$. For a winning adversary outputting a pair $(m^*, \sigma^*)$, it holds that $\text{Verif}_{\text{SPS-EQ}}(\text{pk}, (\hat{g}_1^*, \hat{y}_{1,0}, \dots, \widehat{\text{ppk}}_{l,1}), \hat{\sigma}^*) = 1$. The message-signature pair is transfer to the challenger of the EUF-CMA experiment and a bit $b$ is returned. As previously established, a successful adversary $\mathcal{A}$ must generate a new delegation to win in $\text{Game}_5^{\text{unf}}$. This implies that $\mathcal{R}$ would produce a valid forgery for the SPS-EQ signature, which contradicts the EUF-CMA property of the SPS-EQ signature.

**Anonymity.** Let $\text{Game}_0^{\text{Ano}}$ denote the experiment $\text{Exp}_{\text{k-APS},\mathcal{A}}^{\text{Ano}}(1^{\lambda})$ instantiated by our k-APS. What we then call *challenge* is the output of the oracle $\mathcal{O}_{\text{chall}}^{\text{Ano}}$ which is generated when the adversary calls this oracle. We modify the *challenge* sent to the adversary to decorrelate it from the identity of the proxy signer who issued it. In this game hope, we modify the *challenge* to decorrelate it from the identity of the proxy signer making it.

**Game**<sub>1</sub><sup>\text{Ano}\</sup>: is similar to $\text{Game}_0^{\text{Ano}}$ but generates new SPS-EQ signatures $\hat{\sigma}$ for the randomised messages base on the secret $\text{sk}$ instead of randomising the certificate.

*Claim.* We claim that adversary's advantage is left unchanged under this modification, i.e., $\text{Adv}_{\text{G}_0, \text{G}_1}^{\text{diff}}(\mathcal{A}) = 0$.

*Reduction.* Randomised signatures and newly generated ones follow identical distributions, hence $\mathcal{A}$ has indistinguishable viewing of these two experiments.

**Game**<sub>2</sub><sup>\text{Ano}\</sup>: is similar to $\text{Game}_1^{\text{Ano}}$ but the NIZK proofs $\Pi_{<k}$ and $\pi_{\sigma}$ in the challenge $\sigma$ are simulated. As argued previously, this results in a negligible difference in the adversary's advantage, i.e., $\text{Adv}_{\text{G}_1, \text{G}_2}^{\text{diff}}(\mathcal{A}) \le 2 \cdot \text{Adv}_{\text{NIZK}}^{\text{ZK}}$.
**Game**<sub>3</sub><sup>Ano</sup> (enabling step): is similar to Game<sub>2</sub><sup>Ano</sup> but sets $h_1 = g_1^{r_1}$, $h_2 = g_1^{r_2}$, $h_3 = g_1^{r_3}$ and $h_4 = g_1^{r_4}$ from sampled values $r_1, r_2, r_3, r_4 \leftarrow \mathbb{Z}_p^*$. The distribution of these elements remains unchanged, hence $\mathcal{A}$ has indistinguishable viewing of these experiments, i.e., $\text{Adv}_{\mathbb{G}_2, \mathbb{G}_3}^{\text{diff}}(\mathcal{A}) = 0$.

**Game**<sub>4</sub><sup>Ano</sup>: is similar to Game<sub>3</sub><sup>Ano</sup> but for all $k \in \{0,1\}$, $i \in [l]$, $j \in \{0,1\}$ elements $\text{ppk}_{i,j}^k$, are sampled at random within $\mathbb{G}_1$.

*Claim.* We claim that the adversary's advantage in hybrids Game<sub>3</sub><sup>Ano</sup> and Game<sub>4</sub><sup>Ano</sup> only differs by a negligible factor, i.e., $\text{Adv}_{\mathbb{G}_3, \mathbb{G}_4}^{\text{diff}}(\mathcal{A}) \le 4l \cdot \text{Adv}_{\mathbb{G}_1}^{\text{DDH}}$.

*Reduction.* Consider a sequence of hybrids $H_0, \cdots, H_{2l}$, such that for all $i \in [l]$, $j \in \{0,1\}$ in $H_{2i+j}$, the first $2i+j$ elements of the vector $(\text{ppk}_{1,0}, \cdots, \text{ppk}_{l,1})$ are sampled randomly at uniform, the remaining ones are generated similarly to Game<sub>3</sub><sup>Ano</sup>. We see that $H_0 = \text{Game}_3^{\text{Ano}}$ and $H_{2l} = \text{Game}_4^{\text{Ano}}$. Now consider the reduction $\mathcal{R}_{2i+j}$ in between $H_{2i+j}$ and $H_{2i+j+1}$ receiving a DDH challenge $(X, Y, Z)$. The reduction sets $\text{ppk} = X$, and $y_{2i,1} = Y$, if $j=0$ or $y_{2(i+1),0} = Y$, when $j=1$. Based on the simulator of the proof $\pi_\sigma$ is simulated, and the following equalities: $\alpha_3 = \tilde{y}^{r_2} \cdot \text{ppk}^u; \alpha_4 = \tilde{y}^{r_3} \cdot \text{ppk}^{v \cdot r_4}; \tau = e(\text{ppk}^{r_4}, \alpha_2)$, and $\alpha_1 = Y^{\sum_{k=1; k \neq i}^l x_{k, \eta[k]}}$, then, $\mathcal{R}$ can perfectly simulate the remaining of the actions prescribed by the experiments. Given a distinguisher between hybrids $H_{2i+j}$ and $H_{2i+j+1}$ emulated by the reduction $\mathcal{R}_{2i+j}$, the latter returns the obtained decisions bit $b$ to the challenger of the DDH problem. $\mathcal{R}_{2i+j}$ succeeds to the DDH problem with the same probability that the distinguisher has to differentiate in between the two hybrids. The same reduction is now applied for the elements generated to proxy of index 1, which leads to the proof of the claim.

**Game**<sub>5</sub><sup>Ano</sup>: is similar to Game<sub>4</sub><sup>Ano</sup> but elements $(\hat{g}_1, \hat{y}_{1,0}, \cdots, \widehat{\text{ppk}}_{l,1})$ used to produce $\sigma$ are sample uniformly at random in $\mathbb{G}_1^{4l+1}$.

*Claim.* We claim that the adversary's advantage in hybrids Game<sub>4</sub><sup>Ano</sup> and Game<sub>5</sub><sup>Ano</sup> only differs by a negligible factor, i.e., $\text{Adv}_{\mathbb{G}_4, \mathbb{G}_5}^{\text{diff}}(\mathcal{A}) \le \text{Adv}_{\mathbb{G}_1}^{\text{class-hid}}$.

*Reduction.* Let $\mathcal{R}$ be a reduction based on a challenge from the class-hiding experiment in $\mathbb{G}_1$. The reduction $\mathcal{R}$ receives two elements $M, M' \in \mathbb{G}_1^{4l+1}$. During the setup it defines $g_1 \leftarrow M_1$ (the first element of vector $M$), then executing Delegate(sk, $\text{ppk}^b, t$), it signs $M$ as $\hat{\sigma}$. During the execution of Sign(pk, psk<sup>b</sup>, $m^*$, $\text{del}_b, i^*$), it inputs $M'$ into the SPS-EQ signature scheme, thus obtaining $\hat{\sigma} \leftarrow \text{Sign}_{\text{SPS-EQ}}(\text{sk}, M')$ embedded in the signature $\sigma$ with $M'$. The rest of the experiment is executed normally. Based on the challenge $M'$, we either emulate Game<sub>4</sub><sup>Ano</sup> when $M'$ has been picked in the equivalent class of $M$, or Game<sub>5</sub><sup>Ano</sup> when $M'$ has been picked at random. As a result, a distinguisher between Game<sub>4</sub><sup>Ano</sup> and Game<sub>5</sub><sup>Ano</sup>, has a negligible probability of success.

**Game**<sub>6</sub><sup>Ano</sup>: is similar to Game<sub>5</sub><sup>Ano</sup> but $\alpha_3$ is sampled uniformly at random in $\mathbb{G}_1$, when producing the signature $\sigma$.

*Claim.* We claim that the adversary's advantage in hybrids Game<sub>5</sub><sup>Ano</sup> and Game<sub>6</sub><sup>Ano</sup> only differs by a negligible factor, i.e., $\text{Adv}_{\mathbb{G}_5, \mathbb{G}_6}^{\text{diff}}(\mathcal{A}) \le \text{Adv}_{\mathbb{G}_1}^{\text{DDH}}$.

*Reduction.* Based on a DDH challenge $(X = g_1^x, Y = g_1^y, Z)$, a reduction $\mathcal{R}$ set $h_2 = X$ during the setup, $\tilde{y} = Y$ to produce the signature $\sigma$ and generates the $\tilde{y}_i$ in order to preserve $\tilde{y} = \prod_{i=1}^l \tilde{y}_i$. Among $(\tilde{y}_i)_{i \in [l]}$, $l-1$ elements are generated normally and the remaining element is set to $\tilde{y}_l = \tilde{y} \cdot (\prod_{i=1}^{l-1} \tilde{y}_i)^{-1}$, thus ensuring the same distribution as before. Then set $\alpha_3 = Z \cdot g_1^{u \cdot \text{psk}}$. Knowing the discrete logarithm of $h_3$, $\mathcal{R}$ we can compute $\alpha_4 = Y^{r_3} \cdot h_4^{v \cdot \text{psk}}$ and it simulates the NIZK proofs $\Pi_{<k}$ and $\pi_\sigma$ as prescribed by the experiment. When $Z = g_1^{xy}$ we have perfectly simulated Game<sub>5</sub><sup>Ano</sup> and when $Z \leftarrow \mathbb{G}_1$, we have perfectly simulated Game<sub>6</sub><sup>Ano</sup>. Hence, distinguishing between these two experiments implies distinguishing between the two event of the DDH problem.

**Game**<sub>7</sub><sup>Ano</sup>: is similar to Game<sub>6</sub><sup>Ano</sup> but we sample $\alpha_4$ at random $\alpha_4 \leftarrow \mathbb{G}_1$ when producing the signature $\sigma$.

*Claim.* We claim that the adversary's advantage in hybrids Game<sub>6</sub><sup>Ano</sup> and Game<sub>7</sub><sup>Ano</sup> only differs by a negligible factor, i.e., $\text{Adv}_{\mathbb{G}_6, \mathbb{G}_7}^{\text{diff}}(\mathcal{A}) \le \text{Adv}_{\mathbb{G}_1}^{\text{DDH}}$.
**Reduction.** The reduction is analogous to the previous one: consider a reduction $\mathcal{R}$ basing itself on a DDH challenge $(X = g_1^x, Y = g_1^y, Z)$ and emulating either $\mathcal{Game}_6^{\text{Ano}}$ or $\mathcal{Game}_7^{\text{Ano}}$ based on the value of $Z$. The reduction sets $h_3 = X$ during the setup, it sets $\tilde{y} = Y$ and the generates elements $\tilde{y}_i$ for $i \in [l]$, preserving $\tilde{y} = \prod_{i=1}^l \tilde{y}_i$. Then it sets $\alpha_4 = Z \cdot h_4^{v \cdot \text{psk}}$ based on the challenge and compute $\alpha_1 = Y \sum_{k=1; k \neq i}^l x_{k, \eta[k]}$, and $\alpha_3 = \tilde{y}^{r_2} \cdot g_1^{\text{psk} \cdot u}$. The rest of the experiment is executed as it should have been in both game. Distinguishing between these two experiments implies distinguishing between the two event of the DDH problem as these two games only differs by a DDH challenge.

$\mathcal{Game}_8^{\text{Ano}}$: is similar to $\mathcal{Game}_7^{\text{Ano}}$ but we sample an element $Z \leftarrow_S G_1$ at the beginning of the game and let $\tau = e(Z, \alpha_2)$ to produce a signature with $\text{psk}_0$.

*Claim.* We claim that the adversary's advantage in hybrids $\mathcal{Game}_7^{\text{Ano}}$ and $\mathcal{Game}_8^{\text{Ano}}$ only differs by a negligible factor, i.e., $\text{Adv}_{G_7, G_8}^{\text{diff}}(\mathcal{A}) \le \text{Adv}_{G_1}^{\text{DDH}}$.

**Reduction.** Consider a reduction $\mathcal{R}$ taking as input a DDH challenge $(X, Y, Z) \in \mathbb{G}_1^3$. $\mathcal{R}$ defines $h_4 = X$ during the setup and $\text{ppk}_0 = Y$ during the key generation of the proxy associated to index 0. The element $\tau$ is meant to be computed as $\tau = e(h_4, \alpha_2)^{\text{psk}_b} = e(h_4^{\text{psk}_b}, \alpha_2)$. Based on the DDH challenger we set $\tau = e(Z, \alpha_2)$. The remaining computation are conducted as follow: $\alpha_3 = h_2^x \cdot Y^u \alpha_4 = h_3^x \cdot Z^v$ and algorithms Setup, KeyGen; PKeyGen, Delegate and Sign for $\text{psk}_1$ remain unchanged. It is important to ensure that the threshold of $k$ signature is not overpasses as no tracing could be possible for the produced signature as it is done in $\mathcal{O}_{\text{Sign}}^{\text{Ano}}$. The bit returned by the adversary $\mathcal{A}$ is then transferred as the decision against the DDH challenge. When $Z = g^{xy}$ we perfectly emulate $\mathcal{Game}_7^{\text{Ano}}$ otherwise $\mathcal{Game}_8^{\text{Ano}}$, our claim follows.

$\mathcal{Game}_9^{\text{Ano}}$: is similar to $\mathcal{Game}_8^{\text{Ano}}$ but we sample a new $Z$ for each signature request to the signer of index 0 and set $\tau = e(Z, \alpha_2)$.

*Claim.* We claim that the adversary's advantage in hybrids $\mathcal{Game}_8^{\text{Ano}}$ and $\mathcal{Game}_9^{\text{Ano}}$ only differs by a negligible factor, i.e., $\text{Adv}_{G_8, G_9}^{\text{diff}}(\mathcal{A}) \le \text{Adv}_{G_2}^{\text{class-hid}}$.

**Reduction.** This reduction rely on the fact that $\tau = e(Z, \alpha_2) = e(g_1, \alpha_2^{\log_{g_1}(Z)})$. Consider a reduction $\mathcal{R}$ based on a challenge from the class hiding experiment in $\mathbb{G}_2$ receiving two elements $M, M' \in \mathbb{G}_2^{q_S}$. We refer to $\alpha_2$ (resp. $\tau$) on the $i^{th}$ call from $\mathcal{A}$ to the $\mathcal{O}_{\text{Sign}}^{\text{Ano}}$ as $\alpha_{2,i}$ (resp. $\tau_i$). Let $\alpha_{2,i} = M_i$ and $\tau_i = e(g_1, M_i')$ for all $i \in [q_S]$. Based on the challenge, we have either $\tau_i = e(g_1, M_i')$, for all $i$ and an integer $r$ fixed for all sanitization of index 0, or either $\tau_i = e(g_1, M_i')$, for a new random element $M_i'$ changed for each sanitization of index 0. As a result, we emulate perfectly one or other of the games. We can forward the adversary's response to the challenger of the class hiding experiment and we win against this game with equal probability. This prove the claim.

$\mathcal{Game}_{10}^{\text{Ano}}$: is similar to $\mathcal{Game}_9^{\text{Ano}}$ but we apply the last two modifications to the actions of the proxy using the key $\text{psk}_1$. This leads the same modifications of the adversary's advantage.

In Experiment $\mathcal{Game}_{10}^{\text{Ano}}$, the elements provided to $\mathcal{A}$ are entirely independent of the value $b$. Any guessing strategy employed by $\mathcal{A}$ would result in a zero advantage because the distribution of the outputs produced by the adversary $\mathcal{A}$ is unrelated to the uniformly distributed value $b \leftarrow \$\{0, 1\}$. This concludes our proof for this property.

**Traceability.** Let $\text{Game}_0^{\text{Trace}}$ be the experiment $\text{Exp}_{k-\text{APS}, \mathcal{A}}(1^{\lambda})$ instantiate with the k-APS signature of Section 4.

$\text{Game}_1^{\text{Trace}}$: is similar to $\text{Game}_0^{\text{Trace}}$ but we abort if there is a collision for the responses of the hash function. As argued in $\text{Game}_1^{\text{unf}}$ the adversary's $\mathcal{A}$ advantage differs by a negligible factor, i.e., $\text{Adv}_{G_0, G_1}^{\text{diff}}(\mathcal{A}) \le \text{Adv}_{H}^{\text{col-resist}}$.

$\text{Game}_2^{\text{Trace}}$: is similar to $\text{Game}_1^{\text{Trace}}$ but for all $\mathcal{A}$'s responses, the NIZK proofs $\pi_{\sigma,j}^*$ and $\Pi_{<k}^j$ are extracted. The experiment is aborted if any of the extractions fails or if a valid proof for an invalid statement has
been produced. The reduction to the soundness of the proofs is direct through an hybrid sequence. We can conclude that: $\text{Adv}_{G_1, G_2}^{\text{diff}}(\mathcal{A}) \le 2q_s \cdot \text{Adv}_{\text{NIZK}}^{\text{sound}}$.

**Game**<sub>3</sub><sup>Trace</sup>: is similar to Game<sub>2</sub><sup>Trace</sup> but the indices $\eta_j$ extracted from the proofs $\Pi_{<k}^j$, for $j \in [q_S]$ are used to verify if the adversary overpasses the signature limitations. If there exist $\eta$ such that the public key **ppk** did not receive at least $\eta$ delegation or if there exist a second occurrence of $\eta$ for the same public key, we abort the experiment. The adversary's $\mathcal{A}$ advantage is left unmodified under this change: $\text{Adv}_{G_2, G_3}^{\text{diff}}(\mathcal{A}) = 0$.

*Analysis.* It is now ensured that $\mathcal{A}$ has produced valid proofs of knowledge, in particular from all the $\pi_\sigma^*$, the elements $\alpha_3 = h_2^x \cdot g_1^{u \cdot \text{psk}}$, $\alpha_4 = h_3^x \cdot h_4^{v \cdot \text{psk}}$, $\tau = e(h_4, \alpha_2)^{\text{psk}}$ are well formed and correspond to certified keys. Based on the correctness, we can always recover **ppk** = $(\alpha_3/\alpha'_3)^{1/(u-u')}$ and $w = (\alpha_4/\alpha'_4)^{1/(v-v')}$ when the number of signature has overpass the number obtained in the delegations for one user. Hence, it cannot win this game unless it forges a SPS-EQ signature for the original signer's key.

*Claim.* The adversary's $\mathcal{A}$ advantage in hybrid Game<sub>3</sub><sup>Trace</sup> is negligible, given the SPS-EQ scheme is existentially unforgeable under adaptive chosen-message attacks, i.e., $\text{Adv}_{G_2, G_3}^{\text{diff}}(\mathcal{A}) \le \text{Adv}_{\text{SPS-EQ}}^{\text{EUF-CMA}}$.

*Reduction.* Similar to the conclusion of the proof of unforgeability.

**Non-Frameability.** Let $\text{Game}_0^{\text{no-Frame}}$ be the experiment of Non-Frameability instantiated with our k-APS scheme of Section 4.

**Game**<sub>1</sub><sup>no-Frame</sup>: is similar to Game<sub>0</sub><sup>no-Frame</sup> but we abort if there is a collision for the responses of the hash function in the elements that the challenger sees. Once more the adversary's $\mathcal{A}$ advantage differs by $\text{Adv}_{G_0, G_1}^{\text{diff}}(\mathcal{A}) \le \text{Adv}_H^{\text{col-resist}}$.

*Analysis.* This prevent from an adversary outputting $u^1 = H(m^1, 0, \alpha_2^1) = H(m^2, 0, \alpha_2^2) = u_2$ such that **ppk** would be set to 0 in the Trace algorithm.

**Game**<sub>2</sub><sup>no-Frame</sup>: is similar to Game<sub>1</sub><sup>no-Frame</sup> but we abort the experiment if two proxy public keys produced by the challenger are the same.

*Claim.* We claim that the adversary's advantage in hybrids $\text{Game}_1^{\text{no-Frame}}$ and $\text{Game}_2^{\text{no-Frame}}$ only differs by a negligible factor, i.e., $\text{Adv}_{G_1, G_2}^{\text{diff}}(\mathcal{A}) \le |\mathcal{U}|/|G_1|$.

Secret keys psk are sampled uniformly within the group $\mathbb{Z}_p^*$, which has the same order as $\mathbb{G}_1$. The probability to draw to equal keys based on $|\mathcal{U}|$ independent and identically distributed draw is $|\mathcal{U}|/|G_1|$.

**Game**<sub>3</sub><sup>no-Frame</sup>: is similar to Game<sub>2</sub><sup>no-Frame</sup> but the NIZK proofs $\pi_\sigma$ in the signatures returned by $\mathcal{A}$ are extracted. The soundness of the proof is verified and the experiment is aborted if valid proof for invalid statements are provided. As argued before we obtain the following difference in the advantages: $\text{Adv}_{G_2, G_3}^{\text{diff}}(\mathcal{A}) \le 2 \cdot \text{Adv}_{\text{NIZK}}^{\text{sound}}$.

*Analysis.* Soundness of the NIZK proof ensures that $\mathcal{A}$ holds the witness $(\text{psk}^i, x^i, r^i)$ associated to $\pi_\sigma^i$ for $i \in \{1, 2\}$ and that $(\alpha_3^1, \alpha_4^1)$ and $(\alpha_3^2, \alpha_4^2)$ are correctly computed. If $\mathcal{A}$ wins, then we want to show that we have extracted the discrete logarithm of the public keys of one of the users.

**Game**<sub>4</sub><sup>no-Frame</sup> (enabling step): is similar to Game<sub>3</sub><sup>no-Frame</sup> but the challenger defines $h_4 = g_1^{r_4}$ for $r_4 \leftarrow \mathbb{Z}_p^*$. The adversary has indistinguishable viewing of these experiments as the distribution of $h_4$ is left unchanged.

**Game**<sub>5</sub><sup>no-Frame</sup> (enabling step): is similar to Game<sub>4</sub><sup>no-Frame</sup> but the NIZK proofs $\pi_\sigma$ are simulated. This leads to a negligible difference of the adversary's advantage, i.e., $\text{Adv}_{G_4, G_5}^{\text{diff}}(\mathcal{A}) \le q_{\text{Sign}} \cdot \text{Adv}_{\text{NIZK}}^{\text{ZK}}$.

*Claim.* The adversary's $\mathcal{A}$ advantage in hybrid Game<sub>5</sub><sup>no-Frame</sup> is negligible, given that the discrete logarithm problem is hard, i.e., $\text{Adv}_{G_5}^{\text{no-Frame}}(\mathcal{A}) \le \text{Adv}_{\mathbb{G}_1}^{\text{DL}}$.

*Reduction.* Consider a reduction $\mathcal{R}$ emulating Game<sub>5</sub><sup>no-Frame</sup> based on a challenge $X$ for the DL problem. For a registration request from $\mathcal{A}$, it sets $\text{set } \text{ppk} = X^{s_i}$ for $s_i \leftarrow \mathbb{Z}_p$. On signing requests, the elements involving the public key **ppk** are computed as follows: $\alpha_3 = h_2^x \cdot \text{ppk}^u$, $\alpha_4 = h_3^x \cdot \text{ppk}^{r_4 \cdot v}$ and $\tau = e(\text{ppk}^{r_4}, \alpha_2)$. All
these elements follows the same distribution as before, hence, Game<sup>no-Frame</sup><sub>5</sub> is perfectly simulated. On A's success, sk<sup>1</sup> and sk<sup>2</sup> are extracted consistently from both proofs. The value sk = sk<sup>1</sup> · s<sub>i</sub><sup>-1</sup> for the according index i is returned to R's challenger. The reduction R has the same probability as A to win against the DL problem. □

## D An Example for the Proof $\Pi_{<k}$

In this section, we give more details about the structure of the second part of the proof $\Pi_{<k}$, then we show an example that illustrates how the proof works and why it is linear in $l$. We first recall some facts about sigma protocols and or-proofs. A Sigma protocol is made up of three interactions, enabling the exchange of a commitment $R$, a challenge $c$, and a response $z$. Usually, the simulator of such a protocol for some discrete logarithm relation in a group of prime order $p$ randomly picks a challenge $c \in \mathbb{Z}_p^*$ and a response $z \in \mathbb{Z}_p^*$, then computes the commitment $R$ from $(c, z)$ to complete the simulated transcript $(R, c, z)$.

The Cramer et al. or-proof transformation [14] transforms $n$ sigma protocols sharing the same challenge space for the respective statements/relations $(\phi_i)_{i \in [n]}$ and $(\mathcal{R}_i)_{i \in [n]}$ denoted ZK $\{w : (w, \phi_i) \in \mathcal{R}_i\}$ into a or-proof sigma protocol ZK $\{w : \bigvee_{i \in [n]} (w, \phi_i) \in \mathcal{R}_i\}$. This transformation works as follows: assume that the prover knows the witness $w_j$ for the statement/relation $\phi_j$ and $\mathcal{R}_j$. It first produces the commitment $R_j$ for $\phi_j$ as in the proof ZK $\{w : (w, \phi_j) \in \mathcal{R}_j\}$, then simulates the transcripts $(R_i, c_i, z_i)$ for the other statements $\phi_i$ where $i \neq j$. It sends the commitments $(R_i)_{i \in [n]}$ to the verifier and receives the challenge $c$. The prover then computes $c_j = c \oplus \bigoplus_{i \in [n]: i \neq j} c_i$, computes the response $z_j$ from $w_j$, $R_j$ and $c_j$ as in ZK $\{w : (w, \phi_j) \in \mathcal{R}_j\}$, and returns $(c_i, z_i)_{i \in [n]}$ to the verifier. The verifier checks that $c = \bigoplus_{i \in [n]} c_i$, and checks that each transcript $(R_i, c_i, z_i)$ is valid according to $\phi_i$ and $\mathcal{R}_i$ for $i \in [n]$.

On the other hand, the and-proof transformation we use to build the zero-knowledge proofs

$$ \text{ZK} \left\{ (w_i)_{i \in [n]} : \bigwedge_{i \in [n]} (w, \phi_i) \in \mathcal{R}_i \right\} $$

consists in running the proofs ZK $\{w_i : (w_i, \phi_i) \in \mathcal{R}_i\}$ in parallel by using a unique challenge $c$: the prover sends the commitments $(R_i)_{i \in [n]}$, receives a challenge $c$, and outputs the responses $(z_i)_{i \in [n]}$ such that each $(R_i, c, z_i)$ is a valid transcript for the statement/relation $(\phi_i, \mathcal{R}_i)$.

In what follows, we will show how the second part of the proof $\Pi_{<k}$ works for the example $k = 1001101$ given in Section 4:

$$ \text{ZK} \left\{ s : \begin{array}{l} (\tilde{g}_1 = \hat{g}_1^s \wedge \tilde{y}_0 = \hat{y}_{0,0}^s) \vee ((\tilde{g}_1 = \hat{g}_1^s \wedge \tilde{y}_1 = \hat{y}_{1,0}^s) \\ \wedge (\tilde{g}_1 = \hat{g}_1^s \wedge \tilde{y}_2 = \hat{y}_{2,0}^s) \wedge ((\tilde{g}_1 = \hat{g}_1^s \wedge \tilde{y}_3 = \hat{y}_{3,0}^s) \\ \vee ((\tilde{g}_1 = \hat{g}_1^s \wedge \tilde{y}_4 = \hat{y}_{4,0}^s) \vee ((\tilde{g}_1 = \hat{g}_1^s \wedge \tilde{y}_5 = \hat{y}_{5,0}^s) \\ \wedge (\tilde{g}_1 = \hat{g}_1^s \wedge \tilde{y}_6 = \hat{y}_{6,0}^s)))) \end{array} \right\} $$

Throughout this section:

- $\mathcal{R}$ denotes the relation:

$$ \begin{aligned} & (\tilde{g}_1 = \hat{g}_1^s \wedge \tilde{y}_0 = \hat{y}_{0,0}^s) \vee ((\tilde{g}_1 = \hat{g}_1^s \wedge \tilde{y}_1 = \hat{y}_{1,0}^s) \wedge (\tilde{g}_1 = \hat{g}_1^s \wedge \tilde{y}_2 = \hat{y}_{2,0}^s) \\ & \wedge ((\tilde{g}_1 = \hat{g}_1^s \wedge \tilde{y}_3 = \hat{y}_{3,0}^s) \vee ((\tilde{g}_1 = \hat{g}_1^s \wedge \tilde{y}_4 = \hat{y}_{4,0}^s) \vee ((\tilde{g}_1 = \hat{g}_1^s \wedge \tilde{y}_5 = \hat{y}_{5,0}^s) \\ & \wedge (\tilde{g}_1 = \hat{g}_1^s \wedge \tilde{y}_6 = \hat{y}_{6,0}^s)))) \\ & \end{aligned} $$

- $\mathcal{R}_0$ denotes the relation $(\tilde{g}_1 = \hat{g}_1^s \wedge \tilde{y}_0 = \hat{y}_{0,0}^s)$.

- $\mathcal{R}_{1,2-}$ denotes the relation:

$$ \begin{aligned} & (\tilde{g}_1 = \hat{g}_1^s \wedge \tilde{y}_1 = \hat{y}_{1,0}^s) \wedge (\tilde{g}_1 = \hat{g}_1^s \wedge \tilde{y}_2 = \hat{y}_{2,0}^s) \wedge ((\tilde{g}_1 = \hat{g}_1^s \wedge \tilde{y}_3 = \hat{y}_{3,0}^s) \\ & \vee ((\tilde{g}_1 = \hat{g}_1^s \wedge \tilde{y}_4 = \hat{y}_{4,0}^s) \vee ((\tilde{g}_1 = \hat{g}_1^s \wedge \tilde{y}_5 = \hat{y}_{5,0}^s) \wedge (\tilde{g}_1 = \hat{g}_1^s \wedge \tilde{y}_6 = \hat{y}_{6,0}^s)))) \\ & \end{aligned} $$

- $\mathcal{R}_3$ denotes the relation $(\tilde{g}_1 = \hat{g}_1^s \wedge \tilde{y}_3 = \hat{y}_{3,0}^s)$.
- $\mathcal{R}_4$ denotes the relation $(\tilde{g}_1 = \hat{g}_1^s \wedge \tilde{y}_4 = \hat{y}_{4,0})$.

- $\mathcal{R}_{5,6}$ denotes the relation $(\tilde{g}_1 = \hat{g}_1^s \wedge \tilde{y}_5 = \hat{y}_{5,0}) \wedge (\tilde{g}_1 = \hat{g}_1^s \wedge \tilde{y}_6 = \hat{y}_{6,0})$.

Moreover, $(R_x, c_x, z_x)$ will denote the transcript for the relation $\mathcal{R}_x$ in the proof. According to the boolean structure of the relation $\mathcal{R}$, the challenges $c$ chosen by the verifier and the challenges $c_0, c_{1,2-}, c_3, c_4$ and $c_{5,6}$ sent by the verifier must to verify the following equations:

$$c = c_0 \oplus c_{1,2-} ; \\ c_{1,2-} = c_3 \oplus c_4 \oplus c_{5,6} .$$

If the prover is honest (i.e., $\mathcal{R}$ holds), then we have the following cases:

**Case $\eta = 1001100$:** the relations $\mathcal{R}_{1,2-}$ and $\mathcal{R}_{5,6}$ hold, but the relations $\mathcal{R}_0, \mathcal{R}_3$ and $\mathcal{R}_4$ are not verified. The prover chooses $(c_0, z_0), (c_3, z_3)$ and $(c_4, z_4)$, then simulates the transcripts for these relations. It then receives $c$ from the verifier, which fixes the values of $c_{1,2-}$ and $c_{5,6}$:

$$c_{1,2-} = c_0 \oplus c ; \\ c_{5,6} = c_3 \oplus c_4 \oplus c_{1,2-} .$$

Since $\mathcal{R}_{1,2-}$ and $\mathcal{R}_{5,6}$ hold, the prover is able to compute the responses $z_{1,2-}$ and $z_{5,6}$ from $c_{1,2-}$ and $c_{5,6}$.

**Case $\eta = 10010xx$ (where each $x$ can be replaced by any bit):** the relations $\mathcal{R}_{1,2-}$ and $\mathcal{R}_4$ hold, but the relations $\mathcal{R}_0, \mathcal{R}_3$ and $\mathcal{R}_{5,6}$ may be not verified. The prover chooses $(c_0, z_0), (c_3, z_3)$ and $(c_{5,6}, z_{5,6})$, then simulates the transcripts for these relations. It then receives $c$ from the verifier, which fixes the values of $c_{1,2-}$ and $c_4$:

$$c_{1,2-} = c_0 \oplus c ; \\ c_4 = c_3 \oplus c_{5,6} \oplus c_{1,2-} .$$

Since $\mathcal{R}_{1,2-}$ and $\mathcal{R}_4$ hold, the prover is able to compute the responses $z_{1,2-}$ and $z_4$ from $c_{1,2-}$ and $c_4$.

**Case $\eta = 1000xxx$ (where each $x$ can be replaced by any bit):** the relations $\mathcal{R}_{1,2-}$ and $\mathcal{R}_3$ hold, but the relations $\mathcal{R}_0, \mathcal{R}_4$ and $\mathcal{R}_{5,6}$ may be not verified. The prover chooses $(c_0, z_0), (c_4, z_4)$ and $(c_{5,6}, z_{5,6})$, then simulates the transcripts for these relations. It then receives $c$ from the verifier, which fixes the values of $c_{1,2-}$ and $c_3$:

$$c_{1,2-} = c_0 \oplus c ; \\ c_3 = c_4 \oplus c_{5,6} \oplus c_{1,2-} .$$

Since $\mathcal{R}_{1,2-}$ and $\mathcal{R}_3$ hold, the prover is able to compute the responses $z_{1,2-}$ and $z_3$ from $c_{1,2-}$ and $c_3$.

**Case $\eta = 0xxxxxx$ (where each $x$ can be replaced by any bit):** the relation $\mathcal{R}_0$ holds, but the relations $\mathcal{R}_{1,2-}, \mathcal{R}_3, \mathcal{R}_4$ and $\mathcal{R}_{5,6}$ may be not verified. The prover chooses $z_{1,2-}, (c_3, z_3), (c_4, z_4)$ and $(c_{5,6}, z_{5,6})$, which fixes the value $c_{1,2-}$:

$$c_{1,2-} = c_3 \oplus c_4 \oplus c_{5,6} .$$

The prover then simulates the transcripts for these relations and receives $c$ from the verifier, which fixes the values of $c_0$:

$$c = c_0 \oplus c_{1,2-} .$$

Since $\mathcal{R}_0$ holds, the prover is able to compute the responses $z_0$ from $c_0$.

On the other hand, if the prover is dishonest (i.e., $\mathcal{R}$ does not hold), then we have the following cases:

**Case $\eta = 1001101$:** the relations $\mathcal{R}_0, \mathcal{R}_3, \mathcal{R}_4$, and $\mathcal{R}_{5,6}$ are not verified. The prover chooses $(c_0, z_0), (c_3, z_3), (c_4, z_4)$, and $(c_{5,6}, z_{5,6})$ then simulates the transcripts for these relations. It then receives $c$ from the verifier, which fixes the value of $c_{1,2-}$ in order that the equation $c_{1,2-} = c_0 \oplus c$ holds. However, since $c_{1,2-}, c_3, c_4$, and $c_{5,6}$ are fixed, the probability that the equation $c_{1,2-} = c_3 \oplus c_4 \oplus c_{5,6}$ holds is $1/p$ (each challenge is chosen in $\mathbb{Z}_p^*$), which is negligible.
**Case η = 100111x (where x can be replaced by any bit):** this case is similar to the previous one.

**Case η = 101xxxx (where each x can be replaced by any bit):** the relations $\mathcal{R}_0$ and $\mathcal{R}_{1,2-}$ are not verified. The prover chooses $(c_0, z_0)$ and $(c_{1,2-}, z_{1,2-})$ then simulates the transcripts for these relations. It then receives $c$ from the verifier, however the probability that the equation $c_{1,2-} = c_0 \oplus c$ holds is $1/p$, which is negligible.

**Case η = 11xxxxx (where each x can be replaced by any bit):** this case is similar to the previous one.
This example covers all cases in the structure of the binary word $k$, and can easily be generalized. Note that the size of the transcript of this proof is linear in $l$. As the prover/verifier needs to check the equations on the challenges that follow a tree structure, the time complexity is quadratic in $l$, however, we note that the number of exponentiations remains linear in $l$, making this proof efficient.

## E Security Model for k-Times Anonymous Sanitizable Signatures

In this section we propose a fully detail model for k-times Anonymous Sanitizable Signature schemes.

**Definition 6 (k-SAN).** A k-times Anonymous Sanitizable Signature scheme (k-SAN) is a tuple of polynomial time algorithms:

**Setup(1^λ):** given a security parameter, returns public parameters params.

**KeyGen(1^λ, k, n):** given a security parameter and two integers $k$ and $n$, return a pair of key (sk, pk).

**SaKeyGen(1^λ):** given the public parameters, a security parameter, return a pair of key (ssk, spk).

**Delegate(sk, spk, k):** given the keys sk and spk and an integer $k$, return a delegation del.

**Sign(m, ADM, sk, spk):** given the keys sk, spk, a message $m$ and a admissible set $\text{ADM} \subset [[n]]$, return a signature $\sigma$.

**Sanitize(m, σ, MOD, ssk, pk, del, η):** given the keys pk, ssk, a message-signature pair $(m, \sigma)$, a modification MOD, a delegation del and a signature index $η$, return a signature $\sigma'$.

**Verify(pk, m, σ):** given a key pk, a message $m$ and a signature $\sigma$, returns 0 or 1.

**Link(pk, m, σ, m', σ'):** given a key pk, two message-signature pair $m, \sigma$ and $m', \sigma'$, return an identity ppk and a witness $w$ or $\perp$.

**Trace(w, σ):** given a witness $w$ and a signature $\sigma$, return 0 or 1.

The security properties of sanitizable signatures have already been investigated in numerous previous works [1, 4, 10, 12]. We have adapted the existing security properties to the newly introduced model. We also add the properties related to the k-times mechanism: anonymity, traceability and non-frameability. These properties stay consistent with what has been defined for proxy signatures (Section 3) as both notions share conceptual similarities but diverge in practical usages. Security experiments are provided in Figure 3, with associated oracles detailed in Figure 4 and 5.

**Unforgeability.** The users cannot generate a valid signature without knowing a secret key which has obtained a delegation. A k-times anonymous sanitizable signature is *unforgeable* when for any PPT adversary $\mathcal{A}$, the probability that $\mathcal{A}$ wins the SUF experiment is negligible for every $n \in \mathbb{N}$.

**Immutability.** A sanitizable signature is *immutable* when no adversary is able to sanitize with unauthorized modification. A k-times anonymous sanitizable signature is *immutable* when for any PPT time adversary $\mathcal{A}$, the probability that $\mathcal{A}$ wins the *Immut* experiment is negligible for every $n \in \mathbb{N}$. The adversary has access to a delegation and a signature oracle.

**Transparency.** The verifier cannot decide whether a given signature has been sanitized or not. A k-times anonymous sanitizable signature is *transparent* when for any PPT adversary $\mathcal{A}$, the probability that $\mathcal{A}$ wins the $\{O_{\text{Sa/Si}}^{\text{tran}}, O_{\text{del}}, O_{\text{Sign}}, O_{\text{San}}^{\text{tran}}\}$-Sanitize experiment is negligible for every $n \in \mathbb{N}$.

**Invisibility.** The invisibility property prevents an adversary which is not the signer nor the sanitizer of a signature from determining any information on the modifiable blocks. A k-times anonymous sanitizable signature is *invisible* when for any PPT adversary $\mathcal{A}$, the probability that $\mathcal{A}$ wins the $\{O_{\text{LRADM}}^{\text{Invis}}, O_{\text{del}}, O_{\text{Sign}}, O_{\text{San}}^{\text{Invis}}\}$-Sanitize experiment is negligible for every $n \in \mathbb{N}$.
<figure><img src="image_3.png" /><figcaption>**Figure 3:** Experiments and Oracles for k-Times Anonymous Sanitizable Signatures. (Additional Oracles are Provided in Figure 4 and 5. Oracles inputs provided by the adversary are underlined, the other are provided by the challenger. Sets *U*, *D*, *S*, *H* are global parameters.)</figcaption></figure>
<figure><img src="image_4.png" /><figcaption>**Figure 4:** Oracles for k-Times Anonymous Sanitizable Signatures. (Oracles inputs provided by the adversary are underlined, the other are provided by the challenger. Sets *U*, *D*, *S*, *H* are global parameters.)</figcaption></figure>
Anonymity Oracle

$\mathcal{O}_{\text{San}}^{\text{Ano}}(\text{pk}, (\text{ssk}_i, \text{del}_i)_{i \in \{0,1\}}, j, m, \sigma, \text{MOD})$

1: if $\not\exists \text{ADM}, (m, \sigma, \text{ADM}, \text{spk}_j) \in S$, s.t. $(\text{ADM}(\text{MOD}) = 1)$:

2: return $\perp$

3: $\sigma \leftarrow \text{Sanitize}(m, \sigma, \text{MOD}, \text{ssk}_j, \text{pk}, \text{del}_j, \eta_j)$

4: $S \leftarrow S \cup \{(\text{MOD}(m), \sigma, \text{ADM}, \text{spk}_j)\}$

5: $\eta_j \leftarrow \eta_j + 1$

6: return $\sigma$

$\mathcal{O}_{\text{chal-Sign}}^{\text{Ano}}(\text{sk}, (\text{ssk}_i, \text{del}_i)_{i \in \{0,1\}}, \underline{m}, \text{ADM})$

1: $\sigma \leftarrow \text{Sign}(m, \text{ADM}, \text{sk}, \text{spk}_b)$

2: $S_{\text{chal}} \leftarrow S_{\text{chal}} \cup \{(\text{MOD}(m), \sigma, \text{ADM})\}$

3: return $\sigma$

$\mathcal{O}_{\text{chal-San}}^{\text{Ano}}(\text{sk}, (\text{ssk}_i, \text{del}_i)_{i \in \{0,1\}}, \underline{m}, \sigma, \text{MOD})$

1: if $\not\exists \text{ADM}, (m, \sigma, \text{ADM}) \in S_{\text{chal}}, \text{s.t. } (\text{ADM}(\text{MOD}) = 1)$:

2: return $\perp$

3: $\sigma \leftarrow \text{Sanitize}(m, \sigma, \text{MOD}, \text{ssk}_b, \text{pk}, \text{del}_b, \eta_b)$

4: $S_{\text{chal}} \leftarrow S_{\text{chal}} \cup \{(\text{MOD}(m), \sigma, \text{ADM})\}$

5: $\eta_b \leftarrow \eta_b + 1, \gamma \leftarrow \gamma + 1$

6: return $\sigma$

**Figure 5:** Oracles for k-Times Anonymous Sanitizable Signatures. (Oracles inputs provided by the adversary are underlined, the other are provided by the challenger. Sets $S$ are global parameters.)

**Unlinkability.** Considering a fixed sanitizer assigned with two signature, the verifier cannot link a sanitized signature with its original version. A k-times anonymous sanitizable signature is *unlinkable* when for any PPT adversary $\mathcal{A}$, the probability that $\mathcal{A}$ wins the $\{\mathcal{O}_{\text{LRSan}}^{\text{unlink}}, \mathcal{O}_{\text{del}}, \mathcal{O}_{\text{Sign}}^{\text{SUF/unlink}}, \mathcal{O}_{\text{San}}^{\text{unlink}}\}$-Sanitize experiment is negligible for every $n \in \mathbb{N}$.

## F Proof of Theorem 2

*Proof.* Each of the 8 properties are proven individually to establish the security of the k-SAN. It's important to note that properties of *unforgeability*, *immutability*, *k-traceability*, and *non-frameability* only necessitate collision-resistance in the hash function, whereas *invisibility* requires programming the random oracle in the proof. *Transparency*, *unlinkability*, and *anonymity* proofs, on the other hand, are not dependent on the specific hash function employed. These reductions are applicable for any value of $n \in \mathbb{N}$. Denote by $\text{Adv}_{G_i, G_{i+1}}^{\text{diff}}(\mathcal{A})$, the probability $|\text{Pr}[G_i(\mathcal{A}) = 1] - \text{Pr}[G_{i+1}(\mathcal{A}) = 1]|$.

**Correctness.** It is verified by investigation.

**Unforgeability.** Let $\text{Game}_0^{\text{SUF}}$ denote the experiment $\text{Exp}_{\text{k-SAN},\mathcal{A}}^{\text{SUF}}(1^{\lambda})$ instantiated by the k-Times Anonymous Sanitizable Signature of Section E.

Based on the condition $(m^*, \sigma^*, \cdot, \cdot) \notin S$, we are ensured that $\mathcal{A}$ outputted a signature that was not outputted by the challenger. The SoK proof $\pi_\sigma$ signs all elements in the signature, hence, any modification of the signature implies modifying $\pi_\sigma$. We elaborate our reduction based on this fact.

$\text{Game}_1^{\text{SUF}}$: we abort if there is a collision for the responses of the hash function. As argued in the proof of Theorem 1, the adversary's $\mathcal{A}$ advantage differs by a negligible factor, i.e.,

$$ \text{Adv}_{G_0, G_1}^{\text{diff}}(\mathcal{A}) \le \text{Adv}_H^{\text{col}-\text{resist}}. $$
Game<sub>2</sub><sup>SUF</sup>: the SoK π<sub>MOD</sub> and π<sub>σ</sub>, and the NIZK proof Π<sub><i>k</i></sub> are simulated based on their respective simulator for each request to the oracles O<sub>Sign</sub> and O<sub>San</sub>. This reduction is achieved straightforwardly for each of the proofs independently leading to

$$
\mathrm{Adv}_{G_1, G_2}^{\mathrm{diff}}(\mathcal{A}) \le (q_{\mathrm{Sign}} + q_{\mathrm{San}}) \cdot (2 \cdot \mathrm{Adv}_{\mathrm{SoK}}^{\mathrm{Sim}} + \mathrm{Adv}_{\mathrm{NIZK}}^{\mathrm{ZK}}).
$$

Game<sub>3</sub><sup>SUF</sup> (enabling step): instead of sampling h<sub>4</sub> ←$_{S}$ G<sub>1</sub>, we sample a random value r<sub>4</sub> ←$_{S}$ Z<sub>p</sub><sup>*</sup> and define h<sub>4</sub> = g<sub>1</sub><sup>r<sub>4</sub></sup>. This elements keeps the same distribution, no modification of the advantages is needed.

Game<sub>4</sub><sup>SUF</sup>: based on the extraction of ssk<sub>log</sub><sup>*</sup>, we abort if the adversary A has produced a signature passing all other conditions and such that spk = g<sub>1</sub><sup>ssk<sub>log</sub><sup>*</sup></sup>. A similar reduction for multiple users has been given in the experiment Game<sub>5</sub><sup>unf</sup> of the proof of Theorem 1. This leads

$$
\mathrm{Adv}_{G_3, G_4}^{\mathrm{diff}}(\mathcal{A}) \leq \mathrm{Adv}_{G_1}^{\mathrm{DL}}.
$$

Game<sub>5</sub><sup>SUF</sup>: based on the extraction of sk<sub>log</sub><sup>*</sup>, we abort if the adversary A has produced a signature passing all other conditions such that pk = g<sub>1</sub><sup>sk<sub>log</sub><sup>*</sup></sup>. Based on similar arguments this leads to:

$$
\mathrm{Adv}_{G_4, G_5}^{\mathrm{diff}}(\mathcal{A}) \leq \mathrm{Adv}_{G_1}^{\mathrm{DL}}.
$$

Analysis. The challenger reject any forged NIZK or SoK without knowledge of the witnesses. Moreover any valid NIZK or SoK based on the secret keys of the signer or a sanitizer make the challenger returns failure. It is still required that A has outputted a valid SoK proof π<sub>σ</sub> otherwise failing the verification. Hence, it must be for a different key, thus, the adversary has obtained a valid delegation for another public sanitization key. Claim. The adversary’s A advantage in hybrid Game<sub>5</sub><sup>SUF</sup> is negligible, given the SPS-EQ scheme is existentially unforgeable under adaptive chosen-message attacks, i.e.,

$$
\mathrm{Adv}_{G_5}^{\mathrm{SUF}}(\mathcal{A}) \leq \mathrm{Adv}_{\mathrm{SPS-EQ}}^{\mathrm{EUF-CMA}}.
$$

Reduction. This reduction is similar to the one provided to conclude to unforgeability of the k-APS signature in Theorem 1.

**Immutability.** Let game **Game**<sub>0</sub><sup>Immut</sup> represent experiment Exp<sub>k-SAN,<i>A</i></sub>(λ) instantiated with our *k*-Times Anonymous Sanitizable Signature.

Game<sub>1</sub><sup>Immut</sup>: we abort if there is a collision for the responses of the hash function in the elements that the challenger sees during the experiment. As argued before, the adversary's A advantage in hybrids Game<sub>0</sub><sup>Immut</sup> and Game<sub>1</sub><sup>Immut</sup> only differs by a negligible factor, i.e.,

$$
\mathrm{Adv}_{G_0, G_1}^{\mathrm{diff}}(\mathcal{A}) \leq \mathrm{Adv}_H^{\mathrm{col}-\mathrm{resist}}.
$$

Game<sub>2</sub><sup>Immut</sup>: we extract the SoK π<sub>MOD</sub> recovering a witness c such that, for all i ∈ ⌊n⌋, any of the these two statement: u<sub>i</sub> = H(m<sub>i</sub>, i, 0)<sup>c</sup> ∧ v<sub>i</sub> = H(m<sub>i</sub>, i, 1)<sup>c</sup> or u<sub>i</sub> = H(i, 0)<sup>c</sup> ∧ v<sub>i</sub> = H(i, 1)<sup>c</sup>, should hold true. If the above does not hold the challenger aborts the experiment. The reduction is similar to the previous ones involving the simulation-extractability of a SoK. We conclude that the adversary's A advantage differs by a negligible factor, i.e.,

$$
\mathrm{Adv}_{G_1, G_2}^{\mathrm{diff}}(\mathcal{A}) \leq \mathrm{Adv}_{\mathrm{SoK}}^{\mathrm{Sim}}.
$$

Claim. The adversary's A advantage in hybrid Game<sub>2</sub><sup>Immut</sup> is negligible, given the SPS-EQ scheme is existen-
tially unforgeable under adaptive chosen-message attacks, i.e.,

$$
\mathrm{Adv}_{G_2}^{\mathrm{Immut}}(\mathcal{A}) \leq \mathrm{Adv}_{\mathrm{SPS-EQ}}^{\mathrm{EUF-CMA}}.
$$
**Reduction.** Once again, this reduction is similar to the one provided to conclude to unforgeability of our k-APS signature in Theorem 1.

**Transparency.** Let $Game_0^{\text{tran}}$ represent $\text{Exp}_{\text{K-SAN},\mathcal{A}}^{\{\mathcal{O}_{\text{San}}^{\text{tran}}, \mathcal{O}_{\text{del}}, \mathcal{O}_{\text{Sign}}, \mathcal{O}_{\text{San}}^{\text{tran}}\}-\text{Sanitize}}(\lambda)$ instantiated with our k-SAN signature.

**Game**$_1^{\text{tran}}$: on a call to $\mathcal{O}_{\text{San}}$, we output new SPS-EQ signatures $\hat{\sigma}$ instead of randomised ones. **Claim.** We claim that hybrids $Game_0^{\text{tran}}$ and $Game_1^{\text{tran}}$ are identically distributed, i.e.,

$$ \text{Adv}_{\mathcal{G}_0, \mathcal{G}_1}^{\text{diff}}(\mathcal{A}) = 0. $$

**Reduction.** The reduction $\mathcal{R}$ is straightforward and has been provided in a similar context for $Game_1^{\text{Ano}}$ in the proof of Theorem 1.

**Game**$_2^{\text{tran}}$: the same change as in hybrid $Game_1^{\text{tran}}$ is applied for the signature $\sigma_{\text{MOD}}$. The reduction is analogous, hence,

$$ \text{Adv}_{\mathcal{G}_1, \mathcal{G}_2}^{\text{diff}}(\mathcal{A}) = 0. $$

**Game**$_3^{\text{tran}}$: the signature of knowledge $\pi_{\sigma}$ produced during signature or sanitization on calls from $\mathcal{A}$ to oracles $\mathcal{O}_{\text{Sign}}$, $\mathcal{O}_{\text{San}}$ or $\mathcal{O}_{\text{Sa/Si}}$ are now simulated. This reduction is achieved straightforwardly for each of the proofs independently. The adversary's $\mathcal{A}$ advantage differs by,

$$ \text{Adv}_{\mathcal{G}_2, \mathcal{G}_3}^{\text{diff}}(\mathcal{A}) \le (q_{\text{Sign}} + q_{\text{San}} + q_{\text{Sa/Si}}) \cdot \text{Adv}_{\text{SoK}}^{\text{Sim}}. $$

**Game**$_4^{\text{tran}}$: instead of computing $\alpha_3 = h_2^x \cdot g_1^{u \cdot \text{ssk}_{\text{log}}}$, we sample it at random $\alpha_3 \leftarrow \mathbb{S} \mathbb{G}_1$, when producing the signature $\sigma$.

**Claim.** We claim that the adversary's $\mathcal{A}$ advantage in hybrids $Game_3^{\text{tran}}$ and $Game_4^{\text{tran}}$ only differs by a negligible factor, i.e.,

$$ \text{Adv}_{\mathcal{G}_3, \mathcal{G}_4}^{\text{diff}}(\mathcal{A}) \le q_{\text{Sa/Si}} \cdot \text{Adv}_{\mathcal{G}_1}^{\text{DDH}}. $$

**Reduction.** Based on a DDH challenge ($X = g_1^x, Y = g_1^y, Z$), we highlight the reduction to prove our claim. Let $h_2 = X$ during the setup, $\tilde{y} = Y$, while producing the signature $\sigma$ and generating all $\tilde{y}_i$ in order to preserve $\tilde{y} = \prod_{i=1}^l \tilde{y}_i$. Among the $l$ elements $\tilde{y}_i$, $l-1$ are generated and the remaining element is defined as $\tilde{y}_l = \tilde{y} \cdot (\prod_{i=1}^{l-1} \tilde{y}_i)^{-1}$. Here all elements follow a uniform distribution. Note that we are simulating the NIZK proof $\Pi_{<k}$ and the SoK $\pi_{\sigma}$, hence allowing us to be unaware of the witness. Then set $\alpha_3 = Z \cdot g_1^{u \cdot \text{ssk}_{\text{log}}}$. Knowing the discrete logarithm of $h_3$, we can compute $\alpha_4 = Y^{r_3} \cdot h_4^{u \cdot \text{ssk}_{\text{log}}}$. In order to simulate the signing oracle, we execute it as usual. The values defined in the setup are used, i.e., $h_2 = X$. Note that the game is aborted if the adversary tries to query a signature for the same index a second time, hence no other signature for index $i^*$ could be computed nor leak information to the adversary. When $Z = g_1^{xy}$ we have perfectly simulated $Game_3^{\text{tran}}$ and when $Z \leftarrow \mathbb{S} \mathbb{G}_1$, we have perfectly simulated $Game_4^{\text{tran}}$. Hence distinguishing between these two experiments implies distinguishing between the two event of the DDH problem.

**Game**$_5^{\text{tran}}$: instead of computing $\alpha_4 = h_3^x \cdot h_4^{u \cdot \text{ssk}_{\text{log}}}$, we sample it at random $\alpha_4 \leftarrow \mathbb{S} \mathbb{G}_1$ when producing the signature $\sigma$. The reduction to show indistinguishability of these two problems is analogous to the previous one, we directly conclude that

$$ \text{Adv}_{\mathcal{G}_4, \mathcal{G}_5}^{\text{diff}}(\mathcal{A}) \le q_{\text{Sa/Si}} \cdot \text{Adv}_{\mathcal{G}_1}^{\text{DDH}}. $$

**Game**$_6^{\text{tran}}$: instead of computing $\tau = e(h_4, \alpha_2)^{\text{ssk}_{\text{log}}}$, we sample $Z \leftarrow \mathbb{S} \mathbb{G}_1$ and define $\tau = e(Z, \alpha_2)$ for any sanitized signature.
*Claim.* We claim that the adversary's $\mathcal{A}$ advantage in hybrids $\text{Game}_5^{\text{tran}}$ and $\text{Game}_6^{\text{tran}}$ only differs by a negligible factor, i.e.,

$$ \text{Adv}_{\mathbb{G}_5, \mathbb{G}_6}^{\text{diff}}(\mathcal{A}) \le \text{Adv}_{\mathbb{G}_1}^{\text{DDH}}. $$

*Reduction.* We consider a reduction $\mathcal{R}$ emulating experiments $\text{Game}_5^{\text{tran}}$ and $\text{Game}_6^{\text{tran}}$ against a distinguisher $\mathcal{A}$. This reduction takes as input a DDH challenge $(X, Y, Z) \in \mathbb{G}_1^3$. It defines $h_4 = X$ during the setup and $\text{spk}_{\text{log}} = Y$ during the key generation of the sanitizer. The remaining actions of algorithms Setup and SaKeyGen stay unchanged. The algorithms KeyGen and Delegate are not affected by this change and can still be execute as they should be in $\text{Game}_5^{\text{tran}}$ and $\text{Game}_6^{\text{tran}}$. In contrary, sanitizations require slight changes at the end of the algorithms. First, relying on the previously produced signature $\sigma$ and the delegation del, we can execute sanitization up to the signature $\sigma_{\text{MOD}}$ and produce $x, \tilde{y}, \tilde{\text{spk}}, \alpha_1, u, v$ and $\alpha_2$ just like they used to be in description of the scheme in Section 6. Since the previous games, $\alpha_3$ and $\alpha_4$ are sampled at uniform in $\mathbb{G}_1$. Our concern is now on $\tau$ supposed to be computed as $\tau = e(h_4, \alpha_2)^{\text{ssk}_{\text{log}}} = e(h_4^{\text{ssk}_{\text{log}}}, \alpha_2)$. Based on the DDH challenger define $\tau = e(Z, \alpha_2)$. When $Z = g^{xy}$ we perfectly emulate $\text{Game}_5^{\text{tran}}$, otherwise $\text{Game}_6^{\text{tran}}$. At last the signature of knowledge is emulated which produce valid signatures. It is important to ensure that the threshold of $k$ signature is not overpasses as no tracing could be possible for the produced signature. A condition checks the limit of $k$ signatures in both $\mathcal{O}_{\text{Sa/Si}}$ and $\mathcal{O}_{\text{San}}^{\text{tran}}$. The bit returned by the adversary $\mathcal{A}$ is then transferred as the decision against the DDH challenge. $\mathcal{R}$ has a probability of success similar to the success of the distinguisher $\mathcal{A}$. This conclude to our claim.

*Game*$_7^{\text{tran}}$: instead of sampling $Z \leftarrow \mathbb{G}_1$ and computing $\tau = e(Z, \alpha_2)$ for all signatures produced by the sanitizer, we sample a new $Z \leftarrow \mathbb{G}_2$ for each of the signatures and define $\tau = e(g_1, Z)$.

*Claim.* We claim that the adversary's $\mathcal{A}$ advantage in hybrids $\text{Game}_6^{\text{tran}}$ and $\text{Game}_7^{\text{tran}}$ only differs by a negligible factor, i.e.,

$$ \text{Adv}_{\mathbb{G}_6, \mathbb{G}_7}^{\text{diff}}(\mathcal{A}) \le \text{Adv}_{\mathbb{G}_2}^{\text{class-hid}}. $$

*Reduction.* Consider a reduction $\mathcal{R}$ based on a challenge from the class hiding experiment in $\mathbb{G}_2$ playing against a distinguisher $\mathcal{A}$. The reduction $\mathcal{R}$ receives two elements $M$ and $M^{(b)}$ both in $\mathbb{G}_2^{(q_{\text{San}}+q_{\text{Sa/Si}})}$. We only modify how $\alpha_2$ and $\tau$ are computed, the rest remains similar to both $\text{Game}_6^{\text{tran}}$ and $\text{Game}_7^{\text{tran}}$. We refer to $\alpha_2$ (resp. $\tau$) on the $i^{th}$ call from $\mathcal{A}$ to the oracle $\mathcal{O}_{\text{Sa/Si}}$ or $\mathcal{O}_{\text{San}}^{\text{tran}}$ as $\alpha_{2,i}$ (resp. $\tau_i$). Let $\alpha_{2,i} = M_i$ and $\tau_i = e(g_1, M_i^{(b)})$ for all $i \in [q_{\text{San}} + q_{\text{Sa/Si}}]$. Based on the value of $b$, we have $\tau_i = e(g_1, M_i^r)$, for all $i$ and a integer $r$ fixed for all sanitizations, otherwise, $\tau_i = e(g_1, M_i^r)$, for a random element $M_i^r$. As a result, we emulate perfectly one or other of the games. We can forward the adversary $\mathcal{A}$'s response to the challenger of the class hiding experiment and we win against this game with equal probability. This prove the claim.

*Game*$_8^{\text{tran}}$: on execution of the sanitization algorithm on calls to $\mathcal{O}_{\text{Sa/Si}}$, we sample $\tilde{y}_{i,j} \leftarrow \mathbb{G}_1$ instead of defining them as a power of the $\tilde{y}_{i,j} = y_{i,j}^r$. We have replaced the randomisation of these elements by newly produced, one which are then signed since $\text{Game}_1^{\text{tran}}$. Hence the signature $\hat{\sigma}$ remains valid under this modification.

*Claim.* We claim that the adversary's $\mathcal{A}$ advantage in hybrids $\text{Game}_7^{\text{tran}}$ and $\text{Game}_8^{\text{tran}}$ only differs by a negligible factor, i.e.,

$$ \text{Adv}_{\mathbb{G}_7, \mathbb{G}_8}^{\text{diff}}(\mathcal{A}) \le 2 \cdot q_{\text{Sa/Si}} \cdot l \cdot \text{Adv}_{\mathbb{G}_1}^{\text{DDH}}. $$

*Reduction.* We consider a sequence of hybrids $H_{2i+j}$ with associated reduction $\mathcal{R}_{i,j}$ for $i \in [q_{\text{Sa/Si}} \cdot l]$ and $j \in \{0, 1\}$. All reductions take as input the decision Diffie-Hellman instance $(X, Y, X)$ in $\mathbb{G}_1$ and instead of defining $\hat{g}_1 = g_1^r$ and $\hat{y}_{i,j} = y_{i,j}^r$ after having defined $y_{i,j} = g_1^{x_{i,j}}$ in the delegation process, it sets $\hat{g}_1 = X$, $y_{i,j} = Y$ and $\hat{y}_{i,j} = Z$. To compute $\hat{y}_{i',j'}$, for $i' > i$ and $j' > j$, its set $\hat{y}_{i',j'} = X^{x_{i',j'}}$. In order to compute $\text{spk}_{i,j} = \text{spk}_{\text{log}}^{x_{i,j}} = y_{i,j}^{\text{ssk}_{\text{log}}}$, we take advantage of the knowledge of $\text{ssk}_{\text{log}}$ and proceed as before for the other parts of the algorithms. $\mathcal{R}_{i,j}$ simulate the rest of the experiment straightforwardly and on obtaining the answer of a distinguisher between experiments $\text{Game}_7^{\text{tran}}$ and $\text{Game}_8^{\text{tran}}$, forward it to the DDH challenger. Clearly, if the tuple $(X = g_1^x, Y = g_1^y, X = g_1^{xy})$ is a decisional Diffie-Hellman tuple, then $\mathcal{R}_{i,j}$ perfectly
simulates $H_{2i+j}$. On the other hand, if the tuple is not a strong decisional Diffie-Hellman tuple, then $\mathcal{R}_{i,j}$ simulates $H_{2i+j+1}$ perfectly. It is easy to see that $H_1$ correspond to $\text{Game}_7^{\text{tran}}$ and that $H_{2 \cdot q_{Sa/Si} \cdot l+2}$ correspond to $\text{Game}_8^{\text{tran}}$. The claim follows since we proceeded to a sequence of $2 \cdot q_{Sa/Si} \cdot l$ reductions to the DDH problem.

**Game**<sub>9</sub><sup>tran</sup>: on calls to $\mathcal{O}_{Sa/Si}$, while executing the sanitization algorithm, we sample all elements $\widehat{\text{spk}}_{k,l} \leftarrow_{\mathbb{G}_1}$ instead of defining them as a power of the $\widehat{\text{spk}}_{k,l}$.

**Claim.** We claim that the adversary's $\mathcal{A}$ advantage in hybrids $\text{Game}_8^{\text{tran}}$ and $\text{Game}_9^{\text{tran}}$ only differs by a negligible factor, i.e.,

$$ \text{Adv}_{\mathbb{G}_8, \mathbb{G}_9}^{\text{diff}}(\mathcal{A}) \leq q_{Sa/Si} \cdot \text{Adv}_{\mathbb{G}_1}^{\text{class-hid}}. $$

**Reduction.** We consider a sequence of hybrids $H_i$ with associated reduction $\mathcal{R}_i$ for $i \in [q_{Sa/Si}]$. Where in $H_i$, the elements $\widehat{\text{spk}}_{k,l}$ are sampled as $\widehat{\text{spk}}_{k,l} \leftarrow_{\mathbb{G}_1}$ during the first $i$ calls to sanitization of the $q_{Sa/Si}$ oracle instead of being computed as they used to be.

Consider a reduction $\mathcal{R}_i$ in between each of the hybrids $H_i$ and $H_{i+1}$. The reduction $\mathcal{R}_i$ simulating either of $H_i$ or $H_{i+1}$ with similar probability for an adversary $\mathcal{A}$ trying to distinguish in between those two hybrids. The reduction $\mathcal{R}_i$ takes as input a challenge $(m, m') \in (\mathbb{G}_1^{2l})^2$ from the challenger of the class-hiding experiment in $\mathbb{G}_1$. The vector $m'$ is either a randomisation of $m$ or a completely new message sampled uniformly at random. $\mathcal{R}_i$ simulate the identical parts of the experiments $H_i$ or $H_{i+1}$ except that it sets $(\widehat{\text{spk}}_{1,0}, \dots, \widehat{\text{spk}}_{k,l}) = m$ and based on $\widehat{\text{ssk}}_{\text{log}}$ sets $y_{k,l} = \widehat{\text{spk}}_{k,l}^{-\widehat{\text{ssk}}_{\text{log}}}$, for all $k \in [l]$ and $l \in \{0, 1\}$. As the elements of $m$ are randomly sampled at uniform, the distribution of the $y_{k,l}$ is unchanged. Based on the received message $m' = (m'_1, \dots, m'_{2l})$, it defines $(\widehat{\text{spk}}_{1,0}, \dots, \widehat{\text{spk}}_{k,l}) = m'$. Note that as we are only generating new SPS-EQ signatures since the change introduced in experiment $\text{Game}_1^{\text{tran}}$, hence the signature $\widehat{\sigma}$ remains valid under the proposed change. Moreover the elements $\alpha_3, \alpha_4$ and $\tau$ are sampled at random during sanitization in $\mathcal{O}_{Sa/Si}$, hence they are independent of the values of the $\widehat{\text{spk}}_j$ and we can simulate either $H_i$ or $H_{i+1}$ based on the received challenge $m'$. Trying to distinguish between both experiments, $\mathcal{A}$ returns a bit $b$, the latter is forwarded to the challenger of the class-hiding experiment. $\mathcal{R}$ wins with the same probability that $\mathcal{A}$ has to win against this experiment.

**Claim.** An adversary $\mathcal{A}$ against $\text{Game}_9^{\text{tran}}$ has no advantage, i.e., $\text{Adv}_{\mathbb{G}_9}^{\text{tran}}(\mathcal{A}) = 0$.

In $\text{Game}_9^{\text{tran}}$ we reached the point where algorithmsx Sign($m$, ADM, sk, spk) and Sanitize($m$, $\sigma$, MOD, ssk, pk, del, $\eta$) leads to executing the same algorithm. Indeed, in the Sanitize algorithms all elements included in the signature follow the same distribution as in Sign. Hence, an adversary is unable to distinguish a signature $\sigma \leftarrow$ Sign($m$, ADM, sk, spk) outputted by the $\mathcal{O}_{Sa/Si}$ oracle from a signature produced by $\sigma \leftarrow$ Sanitize($m$, $\sigma$, MOD, ssk, pk, del, $\eta$) as the latest correspond to a second execution of $\sigma \leftarrow$ Sign($m$, ADM, sk, spk).

**Invisibility.** Let $\text{Game}_0^{\text{Invis}}$ represent $\text{Exp}_{\text{k-SAN}, \mathcal{A}}^{\{\mathcal{O}_{\text{LRADM}}, \mathcal{O}_{\text{del}}, \mathcal{O}_{\text{Sign}}, \mathcal{O}_{\text{San}}\} - \text{Sanitize}}(\lambda)$ instantiated with our k-Times Anonymous Sanitizable Signature in the ROM.

**Game**<sub>1</sub><sup>Invis</sup>: we abort the experiment if a signature given to one of the oracle by $\mathcal{A}$ is valid and has not been produced by one of the oracles.

**Claim.** We claim that the adversary's $\mathcal{A}$ advantage in hybrids $\text{Game}_0^{\text{Invis}}$ and $\text{Game}_1^{\text{Invis}}$ only differs by a negligible factor, i.e.,

$$ \text{Adv}_{\mathbb{G}_0, \mathbb{G}_1}^{\text{diff}}(\mathcal{A}) \leq \text{Adv}_{\text{k-SAN}}^{\text{SUF}}. $$

**Reduction.** The reduction is straightforward based on a record of the produced signatures kept by the challenger.

**Game**<sub>2</sub><sup>Invis</sup>: we abort the game if there is a collision in the responses of the random oracle.

**Claim.** We claim that the adversary's $\mathcal{A}$ advantage in hybrids $\text{Game}_1^{\text{Invis}}$ and $\text{Game}_2^{\text{Invis}}$ only differs by a negligible factor, i.e.,

$$ \text{Adv}_{\mathbb{G}_1, \mathbb{G}_2}^{\text{diff}}(\mathcal{A}) \leq \frac{q_H}{2^\lambda}. $$

We can apply a union bound over all $q_h$ queries to the random oracle, and the claim follows.
Game<sub>3</sub><sup>Invis</sup>: we rely on the perfect simulatability of the signature of knowledge π<sub>MOD</sub> to make them independent of the witness a used to compute values u<sub>i</sub> and v<sub>i</sub> for i ∈ ⌊n⌋ while signing or sanitizing a signature on calls to the oracles O<sub>LRADM</sub> and O<sub>San</sub><sup>Invis</sup>. The same reduction has already been provided, hence we directly conclude that the adversary's A advantage in hybrids Game<sub>2</sub><sup>Invis</sup> and Game<sub>3</sub><sup>Invis</sup> only differs by a negligible factor, i.e.,

$$ \mathrm{Adv}_{G_2, G_3}^{\mathrm{diff}}(\mathcal{A}) \le (q_{\mathrm{LRADM}} + q_{\mathrm{San}}) \cdot \mathrm{Adv}_{\mathrm{SoK}}^{\mathrm{Sim}}. $$

*Analysis.* The SoK being simulated, π<sub>MOD</sub> does not allow to recover the witnesses. Thus, the value a could only leak through the ciphertext e.

Game<sub>4</sub><sup>Invis</sup>: on calls to O<sub>LRADM</sub>, the ciphertext e is sampled at random during the signature. A record A of the random value e, a is kept. On calls to O<sub>San</sub><sup>Invis</sup> for messages signed within O<sub>LRADM</sub>, instead of decrypting e the value a is recovered from the record.

*Claim.* We claim that the adversary's A advantage in hybrids Game<sub>3</sub><sup>Invis</sup> and Game<sub>4</sub><sup>Invis</sup> only differs by a negligible factor, i.e.,

$$ \mathrm{Adv}_{G_3, G_4}^{\mathrm{diff}}(\mathcal{A}) \le q_{\mathrm{LRADM}} \cdot \mathrm{Adv}_{\mathcal{E}}^{\mathrm{IND-CCA}}. $$

*Reduction.* The reduction is direct based on the IND-CCA property of the encryption scheme E. It is achieved through a sequence of hybrids experiment H<sub>0</sub>, ..., H<sub>q<sub>LRADM</sub></sub>. Experiment H<sub>0</sub> is defined as Game<sub>3</sub><sup>Invis</sup>. For all i ∈ ⌊q<sub>LRADM</sub>⌋, H<sub>i</sub> execute the same action as H<sub>i-1</sub> except that on the i<sup>th</sup> call to O<sub>LRADM</sub>, it generate the value e by sampling it at random in the encryption space.

To obtain a reduction R<sub>i</sub> in between H<sub>i-1</sub> and H<sub>i</sub>, for all i ∈ ⌊q<sub>LRADM</sub>⌋. The reduction R<sub>i</sub> simulate either H<sub>i-1</sub> or H<sub>i</sub> to an adversary A trying to distinguish between the two games. R<sub>i</sub> obtains the sanitizer public encryption key pk<sub>e</sub> from the challenger of the IND-CCA encryption scheme. On the i-1 first calls (except for i = 1 as there exist no call 0) to O<sub>LRADM</sub>, samples the values e at random during signature. On call i to O<sub>LRADM</sub>, sends a random value a<sub>0</sub> and a to the IND-CCA challenger and obtain a response c, set e = c and include it in the signature. On obtaining the decision bit from A, R<sub>i</sub> sends the same answer to IND-CCA challenger. As this encrypted value is the only difference between all the H<sub>i-1</sub> and H<sub>i</sub>, it is as hard to distinguish both hybrids as to win against the IND-CCA challenge.

Game<sub>5</sub><sup>Invis</sup>: on a call to O<sub>San</sub>, we output new SPS-EQ signatures ̂σ instead of randomised ones.
*Claim.* We claim that hybrids Game<sub>4</sub><sup>Invis</sup> and Game<sub>5</sub><sup>Invis</sup> are identically distributed, i.e.,

$$ \mathrm{Adv}_{G_4, G_5}^{\mathrm{diff}}(\mathcal{A}) = 0. $$

*Reduction.* The reduction R is straightforward. Consider “maliciously” generated keys, outputted by R executing (pk<sub>SPS-EQ</sub><sup>del</sup>, sk<sub>SPS-EQ</sub><sup>del</sup>) ← KeyGen<sub>SPS-EQ</sub>(1<sup>λ</sup>, l). Hence, passing any potential key verification as honestly generated. Answer every signature and sanitization request as usual. All request to O<sub>San</sub>/Si are answered by producing a new signature ̂σ of the randomised u<sub>i</sub>, v<sub>i</sub> when sanitization is required instead of randomizing the existing one. From the Signature Adaptation property, ChgRep and Sign outputs identically distributed signatures when executed based on the same key and messages randomised by the same random value.

Game<sub>6</sub><sup>Invis</sup>: this game is the same as the previous one, except that the values u<sub>i</sub> and v<sub>i</sub> computed during one of the signature of the O<sub>LRADM</sub> oracle are generated randomly. The signature of knowledge π<sub>MOD</sub> is already simulated, hence can be computed even for these random elements.

*Claim.* We claim that the adversary's A advantage in hybrids Game<sub>5</sub><sup>Invis</sup> and Game<sub>6</sub><sup>Invis</sup> only differs by a negligible factor, i.e.,

$$ \mathrm{Adv}_{G_5, G_6}^{\mathrm{diff}}(\mathcal{A}) \le q_{\mathrm{LRADM}} \cdot \mathrm{Adv}_{\mathrm{SPS-EQ}}^{\mathrm{class-hid}}. $$

*Reduction.* We use a sequence of hybrids to demonstrate this claim. For all i ∈ ⌊0, q<sub>LRADM</sub>⌋, consider the sequence of hybrids H<sub>i</sub> where for all j ≤ i, the values u<sub>j</sub> and v<sub>j</sub> are chosen at random while executing O<sub>LRADM</sub> and the remaining ones are defined as originally prescribed in experiment Game<sub>5</sub><sup>Invis</sup>. Now we show
through a reduction that the difference between two consecutive hybrids are negligible: the reduction obtains the setup for the SPS-EQ signature from the challenger of the class hiding experiment, based on these setup it generates its own keys. The remaining of the setup and the set definitions are executed as usual. The classe-hiding experiment is executed for messages in $\mathbb{G}_1^{2n}$. We obtain two messages $m$ and $m_b$. The element $m$ is used to program the random oracle: for $i \in \text{ADM} H(m_i, i, 0) \leftarrow m_i$, $H(m_i, i, 1) \leftarrow m_{2i}$ and for $i \notin \text{ADM}, H(i, 0) \leftarrow m_i$, $H(m_i, i, 1) \leftarrow m_{2i}$. The second message $m_b$ is used as $(u_1, \dots, u_n, v_1, \dots, v_n)$. The remaining of the algorithms are executed as it is done in both hybrids $H_i$ and $H_{i+1}$. Once an answer $b \in \{0, 1\}$ is received from $\mathcal{A}$, it is forwarded to the DDH challenger as the reduction's response.

*Claim.* An adversary $\mathcal{A}$ against $\text{Game}_0^{\text{Invis}}$ has no advantage, i.e., $\text{Adv}_{\mathcal{A}}^{\text{Invis}, G_6} = 0$.

The adversary's $\mathcal{A}$ response is a decisional bit $b$ that should reflect if the signature outputted by $\mathcal{O}_{\text{LRADM}}$ can be modified based on $\text{ADM}_0$ or $\text{ADM}_1$. Considering that all signatures outputted by $\mathcal{O}_{\text{LRADM}}$ are now independent of $\text{ADM}_0$ and $\text{ADM}_1$. We conclude that the adversary's bit distribution is independent of the uniform distribution of $b$. As a direct consequence the distribution of $b = b^*$ is uniform within $\{0, 1\}$ and then $\text{Adv}_{G_6}^{\text{Invis}}(\mathcal{A}) = 0$.

**Unlinkability.** Let $\text{Game}_0^{\text{unlink}}$ represent $\text{Exp}_{\text{k-SAN}, \mathcal{A}}^{\{\mathcal{O}_{\text{LRSan}}, \mathcal{O}_{\text{del}}, \mathcal{O}_{\text{Sign}}^{\text{SUF/unlink}}, \mathcal{O}_{\text{San}}^{\text{unlink}}\}-\text{Sanitize}(\lambda)$ instantiated with our $k$-Times Anonymous Sanitizable Signature.

Starting from $\text{Game}_0^{\text{unlink}}$ and executing Sanitize($m_b, \sigma_b, \text{MOD}_b, \text{ssk}, \text{pk}, \text{del}, \eta$) on calls to $\mathcal{O}_{\text{LRSan}}$, we introduce independent changes leading to an execution which is independent of the bit $b$. As these steps only implies negligible changes to the adversary's advantage this is sufficient to show unlinkability. We highlight that the delegation del, the sanitizer's key and the signature index $\eta$ remains unchanged through this process. As the tuple del returned in the signature only depends on these value, both values will lead to identically distributed elements.

$\text{Game}_1^{\text{unlink}}$: on a call to $\mathcal{O}_{\text{LRSan}}$, we output new SPS-EQ signatures $\sigma_{\text{MOD}}$ instead of randomised ones.
*Claim.* We claim that hybrids $\text{Game}_0^{\text{unlink}}$ and $\text{Game}_1^{\text{Invis}}$ are identically distributed, i.e.,

$$ \text{Adv}_{G_0, G_1}^{\text{diff}}(\mathcal{A}) = 0. $$

*Reduction.* The reduction $\mathcal{R}$ is straightforward. Consider “maliciously” generated keys, outputted by $\mathcal{R}$ executing $(\text{pk}_{\text{SPS-EQ}}, \text{sk}_{\text{SPS-EQ}}) \leftarrow \text{KeyGen}_{\text{SPS-EQ}}(1^{\lambda}, n)$, hence, passing any potential key verification as honestly generated. Answer every signature and sanitization request as usual. All request to $\mathcal{O}_{\text{LRSan}}$ are answered by producing a new signature $\sigma_{\text{MOD}}$ of the randomised $u_i, v_i$ when sanitization is required instead of randomizing the existing one. From the Signature Adaptation property, $\text{ChgRep}_{\text{SPS-EQ}}$ and $\text{Sign}_{\text{SPS-EQ}}$ outputs identically distributed signatures when executed based on the same key and messages randomised by the same random value.

Under this change, the signature has been totally randomised during the sanitization, all element being newly produced at sanitization. The NIZK proof $\Pi_{<k}$ is new and only depends on witness $\eta$ and del. While the mandatory equality $\text{ADM}_0 = \text{ADM}_1$, implies that the immutable base of both message is the same. Hence the $u_{i,j}$ and the $v_{i,j}$ are the same for all $i \in [l]$ and $j \in \{0, 1\}$ and still randomised by a value $b$, stored in a new ciphertext. Finally the last part of the signature is only dependent of the randomised values and does not leak any information on the previously used message. Under these considerations, we conclude to our proof.

**Anonymity.** Let game $\text{Game}_0^{\text{Ano}}$ represent experiment $\text{Exp}_{\pi, \mathcal{A}}^{\text{Ano}}(\lambda)$ instantiated with our $k$-Times Anonymous Sanitizable Signature.

In contrary to the unlinkability where the message and the modifications under sanitization change for a fixed sanitizer, in the anonymity experiment the delegation del$_b$ and the sanitizer's identity i.e., $\text{spk}_b$ are changing based on the challenge bit $b$ while the message and the modification is fixed. If we shown that there are only negligible steps between an execution of $\text{Sign}(m, \text{ADM}, \text{sk}, \text{spk}_b)$ and $\text{Sanitize}(m, \sigma, \text{MOD}, \text{ssk}_b)$,
pk, del<sub>b</sub>, η) and their respective execution that does not rely on b, then, we can conclude that the identity of the sanitizer remains hidden.

Game<sub>1</sub><sup>Ano</sup>: during the sanitization executed on call to oracle O<sup>Ano</sup><sub>chal-San</sub> of the experiment Exp<sup>Ano</sup><sub>π,A</sub>(λ), we output new SPS-EQ signatures ̂σ instead of randomising it from ̂σ of del<sub>b</sub>.

*Claim.* We claim that hybrids Game<sub>0</sub><sup>Ano</sup> and Game<sub>1</sub><sup>Ano</sup> are identically distributed, i.e.,

$$ \mathrm{Adv}_{G_0, G_1}^{\mathrm{diff}}(\mathcal{A}) = 0. $$

*Reduction.* The reduction $\mathcal{R}$ is straightforward by an hybrid over the $\eta \le t \le k$ signatures randomised by the challenge sanitization oracle. Consider the keys outputted by $\mathcal{R}$ executing $(pk_{\mathrm{SPS-EQ}}^{\mathrm{del}}, sk_{\mathrm{SPS-EQ}}^{\mathrm{del}}) \leftarrow \mathrm{KeyGen}_{\mathrm{SPS-EQ}}(1^{\lambda}, 4l + 1)$. Answer every signature and sanitization request as usual. The sanitization request $\sigma \leftarrow \mathrm{Sanitize}(m, \sigma, \mathrm{MOD}, \mathrm{ssk}_b, \mathrm{pk}, \mathrm{del}_b, \eta)$ and answeres it by producing a new signature $\hat{\sigma}$ of $(\hat{g}_1, \hat{y}_{1,0}, \dots, \widehat{pk}_{l,1})$ instead on the randomised vector $\hat{\sigma}$ of del<sub>b</sub>. From the signature adaptation property, $\mathrm{ChgRep}_{\mathrm{SPS-EQ}}$ and $\mathrm{Sign}_{\mathrm{SPS-EQ}}$ outputs identically distributed signatures when executed based on the same key and messages randomised by the same random value.

Game<sub>2</sub><sup>Ano</sup>: instead of producing the proof $\pi_\sigma$ on calls to the sanitization oracle, the proof is simulated based on its simulator.

*Claim.* We claim that the adversary's $\mathcal{A}$ advantage in hybrids Game<sub>1</sub><sup>Ano</sup> and Game<sub>2</sub><sup>Ano</sup> only differs by a negligible factor, i.e.,

$$ \mathrm{Adv}_{G_1, G_2}^{\mathrm{diff}}(\mathcal{A}) \le k \cdot \mathrm{Adv}_{\mathrm{SoK}}^{\mathrm{Sim}}. $$

The reduction is direct based on the zero-knowledge property of the SoK.

Game<sub>3</sub><sup>Ano</sup> (enabling step): instead of directly sampling $h_1, h_2, h_3, h_4 \leftarrow \mathbb{G}_1$, we sample a random value $r_1, r_2, r_3, r_4 \leftarrow \mathbb{Z}_p^*$ and define $h_i = g_1^{r_i}$, for $i \in [4]$.

*Claim.* We claim that it is a bridging step, meaning that the adversary's $\mathcal{A}$ advantage is not modified under this change:

$$ \mathrm{Adv}_{G_2, G_3}^{\mathrm{diff}}(\mathcal{A}) = 0. $$

As this elements keeps the same distribution in the group, the adversary has indistinguishable viewing of these experiments.

Game<sub>4</sub><sup>Ano</sup>: instead of encrypting $a \cdot b$ into $e$ during the sanitization of $\sigma$, the sanitizer sampled the ciphertext $e$ at random and $a \cdot b$ is kept in a record to be used in further sanitization.

*Claim.* We claim that the adversary's $\mathcal{A}$ advantage in hybrids Game<sub>3</sub><sup>Ano</sup> and Game<sub>4</sub><sup>Ano</sup> only differs by a negligible factor, i.e.,

$$ \mathrm{Adv}_{G_3, G_4}^{\mathrm{diff}}(\mathcal{A}) \le \mathrm{Adv}_{\mathcal{E}}^{\mathrm{IND-CCA}}. $$

This is a direct reduction to the IND-CCA experiment.

Game<sub>5</sub><sup>Ano</sup>: instead of encrypting $a$ into $e$ during the signature and the sanitizations of $\sigma$, the challenger sample the ciphertext $e$ at random and $a$ is kept in a record to be used in further sanitization. Let $q_s^{\mathrm{chal}}$ be the number of calls to the oracle O<sup>Ano</sup><sub>chal-San</sub>.

*Claim.* We claim that the adversary's $\mathcal{A}$ advantage in hybrids Game<sub>4</sub><sup>Ano</sup> and Game<sub>5</sub><sup>Ano</sup> only differs by a negligible factor, i.e.,

$$ \mathrm{Adv}_{G_4, G_5}^{\mathrm{diff}}(\mathcal{A}) \le (q_s^{\mathrm{chal}} + k) \cdot \mathrm{Adv}_{\mathcal{E}}^{\mathrm{IND-CCA}}. $$

This is a direct reduction to the IND-CCA experiment.

Step 5 directly leads a signature totaly decorrelated of the sanitizer's identity. All elements are either sampled at random or independent of the sanitizer's identity by construction.

Game<sub>6</sub><sup>Ano</sup>: instead of computing $\alpha_3 = h_2^x \cdot g_1^{u \cdot \mathrm{ssk}_{1 \to g_2}}$, we sample it at random $\alpha_3 \leftarrow \mathbb{G}_1$, when producing the a sanitization $\sigma$ when requested to the oracle O<sup>Ano</sup><sub>chal-San</sub>.
*Claim.* We claim that the adversary's $\mathcal{A}$ advantage in hybrids $\text{Game}_5^{\text{Ano}}$ and $\text{Game}_6^{\text{Ano}}$ only differs by a negligible factor, i.e.,

$$ \text{Adv}_{\text{G}_5, \text{G}_6}^{\text{diff}}(\mathcal{A}) \le k \cdot \text{Adv}_{\text{G}_1}^{\text{DDH}}. $$

*Reduction.* The same reduction is provided in proof of Theorem 1. We apply an hybrid argument over it for a constant number of executions.

*Game*<sub>7</sub><sup>Ano</sup>: instead of computing $\alpha_4 = h_3^x \cdot h_4^{v \cdot \text{ssk}_{\text{log}_b}}$, we sample it at random $\alpha_4 \leftarrow \mathbb{G}_1$ when producing a signature $\sigma$ requested to the oracle $\mathcal{O}_{\text{chal-San}}^{\text{Ano}}$.

*Claim.* We claim that the adversary's $\mathcal{A}$ advantage in hybrids $\text{Game}_6^{\text{Ano}}$ and $\text{Game}_7^{\text{Ano}}$ only differs by a negligible factor, i.e.,

$$ \text{Adv}_{\text{G}_6, \text{G}_7}^{\text{diff}}(\mathcal{A}) \le k \cdot \text{Adv}_{\text{G}_1}^{\text{DDH}}. $$

*Reduction.* The same reduction has been provided in the proof of Theorem 1. We apply an hybrid argument over it for a constant number of executions.

*Game*<sub>8</sub><sup>Ano</sup>: instead of computing $\tau = e(h_4, \alpha_2)^{\text{ssk}_{\text{log}_0}}$ on sanitization of a signature, the challenger samples a fixed $Z_0 \leftarrow \mathbb{G}_1$ at the beginning of the experiment and define $\tau = e(Z_0, \alpha_2)$ for any signature sanitized with the oracle $\mathcal{O}_{\text{chal-San}}^{\text{Ano}}$.

*Claim.* We claim that the adversary's $\mathcal{A}$ advantage in hybrids $\text{Game}_7^{\text{Ano}}$ and $\text{Game}_8^{\text{Ano}}$ only differs by a negligible factor, i.e.,

$$ \text{Adv}_{\text{G}_7, \text{G}_8}^{\text{diff}}(\mathcal{A}) \le k \cdot \text{Adv}_{\text{G}_1}^{\text{DDH}}. $$

*Reduction.* We consider a reduction $\mathcal{R}$ emulating experiments $\text{Game}_7^{\text{Ano}}$ and the same experiment with the first sanitization by $\mathcal{O}_{\text{chal-San}}^{\text{Ano}}$ encompassing this modification. $\mathcal{R}$ is against a distinguisher $\mathcal{A}$. This reduction takes as input a DDH challenge $(X, Y, Z) \in \mathbb{G}_1^3$. It defines $h_4 = X$ during the setup and $\text{spk}_{\text{log}_0} = Y$ during the key generation of the sanitizer associated to index 0. The remaining actions of algorithms Setup and SaKeyGen stay unchanged. The algorithms KeyGen and Delegate are not affected by this change and can still be execute as they should be in $\text{Game}_7^{\text{Ano}}$ and its modification. In contrary, sanitizations require slight changes when executed with the unknown key $\text{ssk}_{\text{log}_0}$. First, relying on the previously produced signature $\sigma$ and the delegation del, we can execute the algorithm normally up to the signature $\sigma_{\text{MOD}}$ and produce $x$, $\tilde{y}$, spk, $\alpha_1$, u, v and $\alpha_2$. Since the previous games, $\alpha_3$ and $\alpha_4$ are sampled at uniform in $\mathbb{G}_1$. The element $\tau$ is supposed to be computed as $\tau = e(h_4, \alpha_2)^{\text{ssk}_{\text{log}_0}} = e(h_4^{\text{ssk}_{\text{log}_0}}, \alpha_2)$. Based on the DDH challenger define $\tau = e(Z, \alpha_2)$. When $Z = g^{xy}$ we perfectly emulate $\text{Game}_7^{\text{Ano}}$ otherwise the modified game where the first sanitization is made based of $Z = g^z$. At last the signature of knowledge is emulated which produce valid signatures. It is important to ensure that the threshold of $k$ signature is not overpasses as no tracing could be possible for the produced signature as it is done in $\mathcal{O}_{\text{San}}^{\text{Ano}}$. Indeed, the outputted $\tau$ is random and does not allow tracing. The bit returned by the adversary $\mathcal{A}$ is then transferred as the decision against the DDH challenge. $\mathcal{R}$ has a probability of success similar to the success of the distinguisher $\mathcal{A}$. This conclude to our claim. Now based on an hybrid argument we can conclude the reduction between experiments $\text{Game}_7^{\text{Ano}}$ and $\text{Game}_8^{\text{Ano}}$.

*Game*<sub>9</sub><sup>Ano</sup>: instead of computing $\tau = e(h_4, \alpha_2)^{\text{ssk}_{\text{log}_1}}$ on sanitization of a signature, the challenger samples a fixed $Z_1 \leftarrow \mathbb{G}_1$ at the beginning of the experiment and define $\tau = e(Z_1, \alpha_2)$ for any signature sanitized with the oracle $\mathcal{O}_{\text{chal-San}}^{\text{Ano}}$.

*Claim.* We claim that the adversary's $\mathcal{A}$ advantage in hybrids $\text{Game}_8^{\text{Ano}}$ and $\text{Game}_9^{\text{Ano}}$ only differs by a negligible factor, i.e.,

$$ \text{Adv}_{\text{G}_8, \text{G}_9}^{\text{diff}}(\mathcal{A}) \le \text{Adv}_{\text{G}_1}^{\text{DDH}}. $$

*Reduction.* This reduction is the identical to the previous reduction with the bit 0 flipped to 1.
**Game**<sub>10</sub><sup>Ano</sup>: instead of sampling $Z_0 \leftarrow_S G_1$ and computing $\tau = e(Z_0, \alpha_2)$ for all signatures produced by the
sanitizer associated to index 0, for each new sanitization a new $Z_0 \leftarrow_S G_2$ is sampled to define $\tau = e(g_1, Z_0)$.
**Claim.** We claim that the adversary's $\mathcal{A}$ advantage in hybrids $Game_9^{Ano}$ and $Game_{10}^{Ano}$ only differs by a negligible
factor, i.e.,

$$
\mathrm{Adv}_{G_9, G_{10}}^{\mathrm{diff}}(\mathcal{A}) \leq k \cdot \mathrm{Adv}_{G_2}^{\mathrm{class}-\mathrm{hid}}.
$$

*Reduction.* Consider a reduction $\mathcal{R}$ based on a challenge from the class hiding experiment in $\mathbb{G}_2$ playing against a distinguisher $\mathcal{A}$. The reduction $\mathcal{R}$ receives two elements $M, M' \in \mathbb{G}_2^{q_{\text{San}}}$. The only modification needed is on how $\alpha_2$ and $\tau$ are computed, the rest remains similar to both $\text{Game}_9^{\text{Ano}}$ and $\text{Game}_{10}^{\text{Ano}}$. We refer to $\alpha_2$ (resp. $\tau$) on the $i^{\text{th}}$ call from $\mathcal{A}$ to the oracle $\mathcal{O}_{\text{San}}^{\text{Ano}}$ as $\alpha_{2,i}$ (resp. $\tau_i$). Let $\alpha_{2,i} = M_i$ and $\tau_i = e(g_1, M'_i)$ for all $i \in [q_{\text{San}}]$. Based on the challenge, we have either $\tau_i = e(g_1, M_i^r)$, for all $i$ and an integer $r$ fixed for all sanitization of index 0, or either $\tau_i = e(g_1, M_i')$, for a new random element $M_i'$ changed for each sanitization of index 0. As a result, we emulate perfectly one or other of the games. We can forward the adversary $\mathcal{A}$'s response to the challenger of the class hiding experiment and we win against this game with equal probability. This prove the claim.

**Game**<sub>11</sub><sup>Ano</sup>: instead of sampling $Z_1 \leftarrow_S G_1$ and computing $\tau = e(Z_1, \alpha_2)$ for all signatures produced by the
sanitizer associated to index 1, for each new sanitization a new $Z_1 \leftarrow_S G_2$ is sampled to define $\tau = e(g_1, Z_1)$.
**Claim.** We claim that the adversary's $\mathcal{A}$ advantage in hybrids $Game_{10}^{Ano}$ and $Game_{11}^{Ano}$ only differs by a negligible
factor, i.e.,

$$
\mathrm{Adv}_{G_{10}, G_{11}}^{\mathrm{diff}}(\mathcal{A}) \leq k \cdot \mathrm{Adv}_{G_2}^{\mathrm{class}-\mathrm{hid}}.
$$

*Reduction.* This reduction is the identical to the previous reduction with the bit 0 flipped to 1.

**Game**<sub>12</sub><sup>Ano</sup>: while the challenger produces the delegation for the proxy signer, instead of generating $\text{spk}_{i,j} = \text{spk}^{x_{i,j}}$ for all $i \in [l]$, $j \in \{0, 1\}$, they are sampled uniformly at random within $G_1$.
**Claim.** We claim that the adversary's $\mathcal{A}$ advantage in hybrids $\text{Game}_{11}^{\text{Ano}}$ and $\text{Game}_{12}^{\text{Ano}}$ only differs by a negligible factor, i.e.,

$$
\mathrm{Adv}_{G_{11}, G_{12}}^{\mathrm{diff}}(\mathcal{A}) \leq 2l \cdot \mathrm{Adv}_{G_1}^{\mathrm{DDH}}.
$$

*Reduction.* The same reduction is provided in proof of Theorem 1.

**Game**<sub>12</sub><sup>Ano</sup>: since $\text{Game}_{11}^{\text{Ano}}$ the vector $(g_1, y_{1,0}, \dots, \text{spk}_{l,1})$ is sampled at random during the delegations of both sanitizers. Instead of randomising one of them to obtain $(\hat{g}_1, \hat{y}_{1,0}, \dots, \widehat{\text{spk}}_{l,1})$ embedded in the sanitized signature $\sigma$ returned to the adversary, we sample these elements randomly for all the signatures sanitized with the oracle $\mathcal{O}_{\text{chal-San}}^{\text{Ano}}$.

*Claim.* We claim that the adversary's $\mathcal{A}$ advantage in hybrids $\text{Game}_{11}^{\text{Ano}}$ and $\text{Game}_{12}^{\text{Ano}}$ only differs by a negligible factor, i.e.,

$$
\mathrm{Adv}_{G_{11}, G_{12}}^{\mathrm{diff}}(\mathcal{A}) \leq k \cdot \mathrm{Adv}_{G_1}^{\mathrm{class}-\mathrm{hid}}.
$$

*Reduction.* Let $\mathcal{R}$ be a reduction based on a challenge from the class hiding experiment in $G_1$ playing against a distinguisher $\mathcal{A}$ against one modification in one of the answer of the oracle. The reduction $\mathcal{R}$ receives two elements $M, M' \in G_1^{4l+1}$. During the setup it defines $g_1 \leftarrow M_1$ (the first element of vector $M$), then while executing *Delegate(sk, spk<sup>b</sup>, k)*, it signs $M$ in $\hat{\sigma}$. Based on the challenge $M'$, during the execution of *Sanitize(m, σ, MOD, ssk<sub>b</sub>, pk, del<sub>b</sub>, η)*, it inputs $M'$ into the *SPS-EQ* signature, thus obtaining $\hat{\sigma} \leftarrow \text{Sign}_{\text{SPS-EQ}}(\text{sk}_{\text{SPS-EQ}}^{\text{del}}, M')$ embedded in the signature with $M'$. The rest of the experiment is executed normally. Based on the value of $M'$, we either emulate $\text{Game}_{11}^{\text{Ano}}$ when $M'$ has been picked in the equivalent class of $M$, or its modified version, when $M'$ has been picked at random. As a result it is hard to distinguish between both experiments. Based on an hybrid argument we conclude this reduction between $\text{Game}_{11}^{\text{Ano}}$ and $\text{Game}_{12}^{\text{Ano}}$.

In experiment $Game_{12}^{Ano}$, the elements that $\mathcal{A}$ sees are completely independent of the value $b$ which is supposed to be guessed by $\mathcal{A}$. Any strategy of guess would then inevitably lead to a null advantage as the
distribution of the adversary's $\mathcal{A}$ outputs are independent of the uniformly distributed value $b \leftarrow \{0, 1\}$. This conclude to our proof for this property.

**Traceability.** Let game $Game_0^{\text{Trace}}$ represent experiment $\text{Exp}_{k-\text{SAN},\mathcal{A}}(\lambda)$ instantiated with our $k$-Times Anonymous Sanitizable Signature.

$Game_1^{\text{Trace}}$: we abort if there is a collision for the responses of the hash function in the elements that the challenger sees during the experiment. As argued before, the adversary's $\mathcal{A}$ advantage in hybrids $Game_0^{\text{Trace}}$ and $Game_1^{\text{Trace}}$ only differs by a negligible factor, i.e.,

$$ \text{Adv}_{G_0, G_1}^{\text{diff}}(\mathcal{A}) \le \text{Adv}_{H}^{\text{col-resist}}. $$

$Game_2^{\text{Trace}}$: each of the SoK $\pi_{\sigma,i}^*$ contained in the signatures $(\sigma_i^*)_{i=1}^{q_s}$ outputted by the adversary are extracted. The witnesses $\text{ssk}_{\log_i}$, $x_i^*$, $s_i^*$, $t_i^*$, $\text{sk}_{\log,i}^*$ are recovered and based on the publicly known elements and the ones inside the signatures, we can check soundness of the proofs. On failure of the extraction or proof of invalid statements, the experiment is aborted. This leads to the following difference based on a straightforward sequence of reductions:

$$ \text{Adv}_{G_1, G_2}^{\text{diff}}(\mathcal{A}) \le q_S \cdot \text{Adv}_{\text{SoK}}^{\text{ZK}}. $$

*Analysis.* Under simulation-extractability of the SoK $\pi_\sigma$, it is ensured that $\mathcal{A}$ has sanitized the signature produced by the signer if CheckTrace returned 1. Unless it knows the DL of $\text{pk}_{\log}$, $\mathcal{A}$ has correctly computed the elements $\tilde{y}, \text{spk}, \alpha_1, \alpha_2, \alpha_3, \alpha_4$ and $\tau$. Based on the correctness of the sanitizable signature we are ensured that no delegation where forged, we can always recover $\text{ppk} = (\alpha_3/\alpha'_3)^{1/(u-u')}$ and $w = (\alpha_4/\alpha'_4)^{1/(v-v')}$ when the same combination of keys $\text{spk}_i$ was used twice. This does not implies that $\mathcal{A}$ has not overpasses the limitation $k \le 2^l$. We now ensure this through another reduction.

$Game_3^{\text{Trace}}$: witnesses $s$ are extracted from $\Pi_{<k}$. Based on the extracted witness we verify the soundness of the proof. The experiment is aborted and returns 0 if the extracted values $s$ are not consistent with the elements in the signatures. The probability that an adversary has outputted a valid proof for an invalid statement is negligible:

$$ \text{Adv}_{G_2, G_3}^{\text{diff}}(\mathcal{A}) \le q_S \cdot \text{Adv}_{\text{NIZK}}^{\text{sound}}. $$

*Analysis.* The previous reduction guarantees that no key index greater than $k$ can be used to sanitize a signature. Hence, on receiving a delegation del for $k$, $\mathcal{A}$ has not been able to use more than the $k$ first combination of keys. The last line of attacks that remains is to produce a valid delegation that remains unknown to the signer i.e., forging a signature for its key or based on a forged delegation. We proceeds in three steps, one enabeling step and two steps to conclude:

$Game_4^{\text{Trace}}$ (enabling step): instead of producing the SoK $\pi_\sigma$ on calls to the signing oracle, the signature of knowledge is simulating with its simulator.

*Claim.* We claim that the adversary's $\mathcal{A}$ advantage in hybrids $Game_3^{\text{Trace}}$ and $Game_4^{\text{Trace}}$ only differs by a negligible factor, i.e.,

$$ \text{Adv}_{G_3, G_4}^{\text{diff}}(\mathcal{A}) \le q_S \cdot \text{Adv}_{\text{SoK}}^{\text{ZK}}. $$

The reduction is direct based on the perfect simulatability of the SoK.

$Game_5^{\text{Trace}}$: we abort if one of the recovered element $\text{sk}_{\log}^*$ extracted from the proofs $\pi_\sigma$ verify $\text{sk}_{\log}^* = \text{sk}_{\log}$. *Claim.* We claim that the adversary's $\mathcal{A}$ advantage in hybrids $Game_5^{\text{Trace}}$ is negligible, i.e.,

$$ \text{Adv}_{G_5}^{\text{Trace}}(\mathcal{A}) \le q_S \cdot \text{Adv}_{G_1}^{\text{DL}}. $$

*Reduction.* The reduction $\mathcal{R}$ is straight forward. $\mathcal{R}$ receive a challenge $(g_1, X)$ for the DL problem, uses $g_1$ as the base element and set $\text{pk} = X$. It simulates the $\mathcal{O}_{\text{del}}$ as usually after having generate the necessary keys
for the SPS-EQ signatures. On calls from $\mathcal{A}$ to the $\mathcal{O}_{\text{Sign}}$, $\mathcal{R}$ execute it normally and simulate the proof $\pi_{\sigma}$ as prescribed by the latest experiment. On receiving an answer $(m_i^*, \sigma_i^*)_{i=1}^{q_s}$ from $\mathcal{A}$, if the experiment succeeds for the given values, we return a random $sk_{\text{log}}^*$ to the challenger of the DL problem.

**Game**<sub>6</sub><sup>Trace</sup>: unforgeability of SPS-EQ signature $\hat{\sigma}$ implies that it is not possible to produce dishonest delegation. We claim that:

$$ \mathrm{Adv}_{G_5, G_6}^{\mathrm{diff}}(\mathcal{A}) \le q_S \cdot \mathrm{Adv}_{\mathrm{SPS-EQ}}^{\mathrm{EUF-CMA}}. $$

**Reduction.** Consider an adversary $\mathcal{A}$ winning against Game<sub>6</sub><sup>Trace</sup>. Let $\mathcal{R}$ be a reduction emulating between the answers of $\mathcal{A}$ and $\mathrm{Exp}_{\mathrm{SPS-EQ}}^{\mathrm{EUF-CMA}}$. We implement the reduction $\mathcal{R}$ straightforwardly. Instead of using $\mathrm{KeyGen}_{\mathrm{SPS-EQ}}(1^{\lambda}, 4l + 1)$ to generate the keys $(pk_{\mathrm{SPS-EQ}}^{\mathrm{del}}, sk_{\mathrm{SPS-EQ}}^{\mathrm{del}})$, set $pk_{\mathrm{SPS-EQ}}^{\mathrm{del}}$ as the public key received from the challenger against $\mathrm{Exp}_{\mathrm{SPS-EQ}}^{\mathrm{EUF-CMA}}$. Moreover, to issue elements $\hat{\sigma}$ on a call from $\mathcal{A}$ to $\mathcal{O}_{\text{Sign}}$, $\mathcal{R}$ uses the provided signing oracle obtaining $\hat{\sigma}$. Finally, for a winning adversary outputting a triple $(\mathrm{spk}^*, m^*, \sigma^*)$ for which we have $\mathrm{Ver}(m^*, \sigma^*, pk) = 1$, it holds that $\mathrm{Verif}_{\mathrm{SPS-EQ}}(pk_{\mathrm{SPS-EQ}}^{\mathrm{MOD}}, (\hat{g}_1, \hat{y}_{1,0}, \dots, \hat{pk}_{l,1}), \sigma_{\mathrm{MOD}}) = 1$ from the passing verification. For a winning adversary we can then, transfer one of the message-signature pair $(u_1, v_1, \dots, u_n, v_n)$, $\sigma_{\mathrm{MOD}}$ to the challenger of the EUF-CMA experiment of the SPS-EQ signature. The response given by the challenger of the EUF-CMA experiment, is outputted by the challenger simulating Game<sub>6</sub><sup>Trace</sup> instead of a winning bit. The claim follows as for any adversary there are only negligible chances to forge a SPS-EQ signature and there must be at least one tuple that the returned message-signature pair is a forge.

With this reduction we prevent from an adversary forging a new delegation. This allows us to conclude the proof.

**Non-Frameability.** The proof of Non-Frameability is the same as for our k-APS signature. Let Game<sub>0</sub><sup>no-Frame</sup> be the original experiment of Non-Frameability instantiated with our k-SAN scheme of Section 6.

**Game**<sub>1</sub><sup>no-Frame</sup>: we abort if there is a collision in the responses of the random oracle $\mathcal{O}_H$. This prevent from an adversary outputting two values $u^1 = H(m^1, 0, \alpha_2^1) = H(m^2, 0, \alpha_2^2) = u_2$ such that $\mathrm{ppk}$ would be set to 0 during the computation in the Trace algorithm.

**Claim.** We claim that the adversary's $\mathcal{A}$ advantage in hybrids Game<sub>0</sub><sup>no-Frame</sup> and Game<sub>1</sub><sup>no-Frame</sup> only differs by a negligible factor, i.e.,

$$ \mathrm{Adv}_{G_0, G_1}^{\mathrm{diff}}(\mathcal{A}) \le \frac{q_H}{2^\lambda}. $$

We can apply a union bound over all $q_h$ queries to the random oracle, and the claim follows.

**Game**<sub>2</sub><sup>no-Frame</sup>: we abort the experiment if two public keys $\mathrm{spk}_{\mathrm{log}}$ produced by the challenger for the proxies are the same

**Claim.** We claim that the adversary's $\mathcal{A}$ advantage in hybrids Game<sub>1</sub><sup>no-Frame</sup> and Game<sub>2</sub><sup>no-Frame</sup> only differs by a negligible factor, i.e.,

$$ \mathrm{Adv}_{G_1, G_2}^{\mathrm{diff}}(\mathcal{A}) \le |\mathcal{U}|/|G_1|. $$

Secret keys $\mathrm{ssk}_{\mathrm{log}}$ are sampled uniformly within the group $\mathbb{Z}_p^*$, which is of the order of the group $\mathbb{G}_1$. Each $\mathrm{ssk}_{\mathrm{log}}$ leads to a unique public key $\mathrm{spk}_{\mathrm{log}}$. Hence, the probability to draw to equal keys based on $|\mathcal{U}|$ independent and identically distributed draw is $|\mathcal{U}|/|\mathbb{G}_1|$.

**Game**<sub>3</sub><sup>no-Frame</sup>: the SoK proofs $\pi_{\sigma}$ in the signature returned by $\mathcal{A}$ are extracted. Based on the extracted values $(\mathrm{ssk}_{\mathrm{log}}^{\mathrm{Ext},i}, x^{\mathrm{Ext},i}, s^{\mathrm{Ext},i}, t^{\mathrm{Ext},i}, sk_{\mathrm{log}}^{\mathrm{Ext},i})_{i=1,2}$, we verify the soundness of the proofs by checking if it belong to the language. As argued before we obtain the following difference in the advantages:

$$ \mathrm{Adv}_{G_2, G_3}^{\mathrm{diff}}(\mathcal{A}) \le 2 \cdot \mathrm{Adv}_{\mathrm{SoK}}^{\mathrm{sound}}. $$

**Analysis.** From this point, it is ensured that $\mathcal{A}$ holds a witness for the proofs $\pi_{\sigma}^1$ and $\pi_{\sigma}^2$ and has computed $(\alpha_3^1, \alpha_4^1)$ and $(\alpha_3^2, \alpha_4^2)$ based on these values or knows the discrete logarithm of the signer's key $sk_{\mathrm{log}}$.
Game<sub>4</sub><sup>no-Frame</sup>: we abort if one of the recovered element sk<sub>log</sub><sup>Ext,i</sup> extracted from the proofs π<sub>σ</sub> verify sk<sub>log</sub><sup>Ext,i</sup> = sk<sub>log</sub> for any of i ∈ {1, 2}.

*Claim.* We claim that the adversary's $\mathcal{A}$ advantage in hybrids Game<sub>3</sub><sup>no-Frame</sup> and Game<sub>4</sub><sup>no-Frame</sup> only differs by a negligible factor, i.e.,

$$ \mathrm{Adv}_{G_3, G_4}^{\mathrm{diff}}(\mathcal{A}) \le \mathrm{Adv}_{G_1}^{\mathrm{DL}}. $$

*Reduction.* Consider a reduction $\mathcal{R}$ emulating Game<sub>5</sub><sup>no-Frame</sup> based on a challenge $X$ for the discrete logarithm problem. For each registration request from $\mathcal{A}$, it sets $\mathrm{spk}_{\mathrm{log}} = X^{s_i}$ for a random $s_i \leftarrow \mathbb{Z}_p$. As $\mathcal{A}$ is not provided with a sanitization oracle, their is no need to simulate any action for the sanitizers. On $\mathcal{A}$'s success, $\mathrm{ssk}_{\mathrm{log}}^{\mathrm{Ext},i}$ and $\mathrm{ssk}_{\mathrm{log}}^{\mathrm{Ext},i}$ where extracted consistently from both proofs. The value $\mathrm{ssk}_{\mathrm{log}} = \mathrm{ssk}_{\mathrm{log}}^{-1} \cdot s_i^{-1}$ for the correct $i$ is returned as the answer to the DL problem. The witness has the same probability as $\mathcal{A}$ to be right. Hence, $\mathrm{Adv}_{\mathcal{A}}^{\mathrm{no-Frame},G_3-G_4} \le \mathrm{Adv}_{G_1}^{\mathrm{DL}}$.

Game<sub>5</sub><sup>no-Frame</sup>: the signature of knowledge π<sub>σ</sub> is simulated based on its simulator for each request to the oracles $\mathcal{O}_{\mathrm{Sign}}^{\mathrm{no-Frame}}$. The adversary's $\mathcal{A}$ advantage in hybrids Game<sub>4</sub><sup>no-Frame</sup> and Game<sub>5</sub><sup>no-Frame</sup> only differs by a negligible factor, i.e.,

$$ \mathrm{Adv}_{G_4, G_5}^{\mathrm{diff}}(\mathcal{A}) \le q_{\mathrm{Sign}} \cdot \mathrm{Adv}_{\mathrm{SoK}}^{\mathrm{Sim}}. $$

*Claim.* The adversary's $\mathcal{A}$ advantage in hybrid Game<sub>5</sub><sup>no-Frame</sup> is negligible, given that the discrete logarithm problem is hard, i.e.,

$$ \mathrm{Adv}_{G_5}^{\mathrm{no-Frame}}(\mathcal{A}) \le \mathrm{Adv}_{G_1}^{\mathrm{DL}}. $$

*Reduction.* Consider a challenge $X$ for the discrete logarithm problem. During the signer's key generation KeyGen, we define $\mathrm{pk}_{\mathrm{log}} = X$. The others keys for the SPS-EQ signature are produced normally, hence delegation request $\mathcal{O}_{\mathrm{del}}$ can executed as usual as they do not depend on the key $\mathrm{pk}_{\mathrm{log}}$ or the associated secret key. The same holds for request to $\mathcal{O}_{\mathrm{Register}}^{\mathrm{no-Frame}}$. It remains to produced coherent answer for the signature request. As the proof π<sub>σ</sub> is simulated, this is straightforwardly achieved by the challenger. Once $\mathcal{A}$ returns $(m_i^*, \sigma_i^*)_{i=1,2}$ both $\mathrm{sk}_{\mathrm{log}}^{\mathrm{Ext},1}$ and $\mathrm{sk}_{\mathrm{log}}^{\mathrm{Ext},2}$ are extracted. At the end of both hybrids, if the proof does not holds for a valid statement or holds under the witnesses associated to one of the registered sanitizer, the experiment is aborted. Thus, the proof must holds true for a

The value $\mathrm{sk} = \mathrm{sk}^1 \cdot s_i^{-1}$ for the correct $i$ is returned as the answer to the DL problem. The witness has the same probability as $\mathcal{A}$ to be right.

Based on the two previous reductions, $\mathcal{A}$ has not produced a proof π<sub>σ</sub> for any of the keys produced by the challenger. Hence, if the signatures σ<sub>1</sub><sup>*</sup> and σ<sub>2</sub><sup>*</sup> verifies, the proof π<sub>σ</sub> holds true for some keys generated by the adversary. Moreover the elements α<sub>3</sub>, α<sub>4</sub> and τ are well formed and tracing an adversary's registered user. The condition $(\mathrm{ppk}, \cdot, \cdot, 1) \in \mathcal{U}$ implies that $\mathcal{A}$ has probability 0 to win this experiment. □