Angèle Bossuat

Xavier Bultel

Unlinkable and Invisible γ-Sanitizable Signatures

come

Introduction

One of the main properties of digital signatures is integrity -indeed, it is important that any modification made to a message after it was signed would invalidate said signature. However, one might wish to modify a signed message without altering its core meaning, for example to anonymize a document, while not wanting (or not being able) to take the time necessary to get the original signer to sign again.

Sanitizable signatures, as introduced in [START_REF] Ateniese | Sanitizable signatures[END_REF] can serve such a purpose by allowing a form of controlled malleability, where a signer will sign a message along with a list of admissible modifications with respect to a second entity called the sanitizer. That sanitizer will be allowed to re-sign a message, producing a valid signature as long as the message was only modified within the limits defined by the list.

The relationship between the signer and the sanitizer will depend on the use case (e.g. they can be a boss and their employee, or a service provider and their client) and for this reason the means and content of any communication between those two entities (including credentials used to sign/sanitize) is out of scope of this paper.

A frequent usage example for such a signature scheme would be the anonymization of medical data destined to be analyzed: the name of the patients is -with a high probability -not relevant for the analysis, neither is their email address or phone number; Our scheme. Our aim when creating ULISS was to build a signature that is originally issued by a signer and that can be modified by the sanitizer, who has to prove that it was done within the authorized limits (i.e., the blocks that were modified are admissible and the number of blocks that were modified is below the limit). We also want the resulting signatures to not leak whether they come from the signer or the sanitizer. We focused on the idea that the sanitizer must prove that the sanitization was done properly, as allowed, and for this we base our scheme on the use of (non-interactive) zero-knowledge proofs.

The signer first computes commitments pertaining to the authorized modifications and the limit, and signs them, then encrypts some necessary information for the sanitizer. To edit the signature, the sanitizer will retrieve the encrypted data and use it to build some new proofs related to the original commitments, and sign everything (along with the modified message, of course) using the ring signature. Since the information about the modifications and the limit is committed, it cannot be deduced from the signature, which makes ULISS invisible.

Reaching both invisibility and unlinkability is a difficult task; to the best of our knowledge, the scheme presented in Bultel et al. [START_REF] Bultel | Efficient invisible and unlinkable sanitizable signatures[END_REF] is the only one that achieves these two properties together, thanks to class-equivalence signatures. We use a similar trick for ULISS: a sanitized signature uses the same signed commitments as the original signature. This could be used by an adversary to link these two signatures, however, we use a class-equivalence signature to sign the commitments, which allows the sanitizer to randomize the commitments and the signature in such a way that the messages in the signed commitments are not modified.

Related Work. Sanitizable signatures were, as cited above, first introduced by Ateniese et al. [START_REF] Ateniese | Sanitizable signatures[END_REF], proposing applications, among others, in the medical field. This primitive is related to (but should not be confused with) redactable signatures [START_REF] Brzuska | Redactable signatures for tree-structured data: Definitions and constructions[END_REF], where a sanitizer can erase some parts of the message but not modify it. The security properties were originally presented in [START_REF] Ateniese | Sanitizable signatures[END_REF], but formalized later on by Brzuska et al. in [START_REF] Brzuska | Security of sanitizable signatures revisited[END_REF] and [START_REF] Brzuska | Unlinkability of sanitizable signatures[END_REF], the latter adding the idea of unlinkability. Invisibility was formalized in [START_REF] Camenisch | Chameleon-hashes with ephemeral trapdoors -and applications to invisible sanitizable signatures[END_REF], and invisible constructions are proposed in [START_REF] Camenisch | Chameleon-hashes with ephemeral trapdoors -and applications to invisible sanitizable signatures[END_REF] and [START_REF] Beck | Practical strongly invisible and strongly accountable sanitizable signatures[END_REF]. In [START_REF] Bultel | Efficient invisible and unlinkable sanitizable signatures[END_REF], the authors propose a scheme that is both unlinkable and invisible, using class-equivalent signatures. To the best our knowledge, this scheme is the only one that achieves these two properties together. They also provide a generic way to add accountability on any sanitizable signature scheme, using verifiable ring signatures [START_REF] Bultel | Unlinkable and strongly accountable sanitizable signatures from verifiable ring signatures[END_REF]. Note that these schemes allow the sanitizer modify parts of the message in an unlimited way.

On the other hand, related primitives with a more general application can be used to achieve γ-Sanitizable Signatures, including functional signatures [START_REF] Boyle | Functional signatures and pseudorandom functions[END_REF] and delegatable functional signatures [START_REF] Backes | Delegatable functional signatures[END_REF], which allows a user to sign messages that verify some functions or predicate, policy-based signatures [START_REF] Bellare | Policy-based signatures[END_REF], where signers are authorized to sign a message if it satisfies some policy, and homomorphic signatures [START_REF] Johnson | Homomorphic Signature Schemes[END_REF]. All of these offer much more variety on what (the equivalent of) the sanitizer can do compared to traditional sanitizable signatures, while being generally much less efficient specifically because of their fine-grained possibilities, using heavy generic primitives (e.g., generic zero-knowledge proofs for garbled boolean circuits or homomorphic encryption). We believe our work lies somewhere in between, offering more control on the sanitizations while remaining practical.

The γ-sanitizable signature schemes were introduced in [START_REF] Klonowski | Extended sanitizable signatures[END_REF] and revisited by Canard and Jambert in [START_REF] Canard | On extended sanitizable signature schemes[END_REF], the latter proposing the first security model for γ-sanitizable signatures. To the best of our knowledge, there is no other such scheme in the literature -moreover, these two works are neither invisible nor unlinkable. Adding unlinkability to these schemes is not straightforward, as they use chameleon hashes [START_REF] Krawczyk | Chameleon hashing and signatures[END_REF] on modifiable parts of the signatures, which implies that these hashes are the same for both the sanitized signature and the original one. Moreover, adding invisibility does not seem trivial either, as the size of the public parameters of the sanitizer is linear in the limit γ (which must be secret in invisible schemes). Furthermore, the design of the schemes in [START_REF] Canard | On extended sanitizable signature schemes[END_REF][START_REF] Klonowski | Extended sanitizable signatures[END_REF] has inherent limitations making them unsuitable for practical applications:

-The signer must use a new public key (of size linear in γ) generated by the sanitizer at each new signature, implying that the signature algorithm is interactive and requires the presence of the sanitizer. -If the same signature is sanitized several times such that the total number of modified parts is greater than γ, then the key of the sanitizer is leaked to anybody, even if the sanitized signatures considered separately are within the limit γ, which drastically restricts the number of sanitizations of a signature. -To verify that the limit γ is respected on a sanitized signature, the verifier must also have the original signature. However, if the verifier knows the original signature and the original message, sanitizable signatures are useless by design. For these reasons, we believe that security notions and constructions of γ-Sanitizable Signatures must be revisited, to produce a more practical and more secure scheme. As explained above, this cannot be achieved by modifying the proposed schemes: we must instead get our inspiration from a regular sanitizable signature scheme that satisfies both unlinkability and invisibility -i.e., [START_REF] Bultel | Efficient invisible and unlinkable sanitizable signatures[END_REF]. We will show that the cost of introducing a new feature to sanitizable signatures is acceptable, especially since compared to Canard and Jambert's scheme, we obtain a much more practical scheme, and satisfy more security properties.

Outline. This work is organized as follows: in Section 2, we present the different cryptographic tools that we use, along with the security definitions, then in Section 3 we describe our security model. Our scheme is explained and analysed in Section 4. Some applications are presented in Section 5. The complete proofs are given in Appendix A.

Cryptographic Tools

In this section, we give or recall the definitions of various cryptographic tools that will be used when building our scheme, or when proving its security properties.

Definition 1 (DDH).

Let G be a multiplicative group of order p generated from a security parameter λ (with log(p) = λ) with generator g, the Decisional Diffie-Hellman (DDH) assumption states that for a, b and c randomly chosen in Z * p , it is difficult for a polynomial-time adversary A to decide whether he has been given (g a , g b , g a•b ) or (g a , g b , g c ), i.e., the following function is negligible:

Adv DDH G (λ) = | Pr[1 ← A(g a , g b , g c )] -Pr[1 ← A(g a , g b , g a•b )]|.
Definition 2 (NIZKP [START_REF] De Santis | Non-interactive zero-knowledge proof systems[END_REF]). A non-interactive zero-knowledge proof (NIZKP) for a language L is a pair of algorithms (Prove, Verify) such that: Prove(s, w): It outputs a proof π that s ∈ L using witness w, Verify(s, π): It checks whether π is a valid proof that s ∈ L.

A NIZKP must satisfy the following properties: Soundness No adversary A (possibly unbounded in time) is such that A(L) can, with non-negligible probability, output (x, π) where Verify(x, π) = 1 and x / ∈ L. Completeness For any statement s ∈ L and its witness w, Verify(s, Prove(s, w)) = 1.

(Perfect) Zero-Knowledge The proof π does not leak any information, in other words, there exists a probabilistic polynomial-time (PPT) simulator Sim (which has the ability to program the outputs of the random oracle in the random oracle model) such that Sim(s) follows the same probability distribution as Prove(s, w).

Definition 3 (2-Ring Signature (2RS) [START_REF] Bender | Ring signatures: Stronger definitions, and constructions without random oracles[END_REF]). A 2-Ring Signature scheme R is a tuple of 4 PPT algorithms defined as follows: R.ini(1 λ ): It returns a setup value set. R.gen(set): It returns a pair of public/private keys (pk, sk). R.sig(sk, {pk 0 , pk 1 }, m): This algorithm computes a signature σ from the message m using the secret key sk and two public keys (pk 0 , pk 1 ) (such that sk is the private key corresponding to one of them). R.ver({pk 0 , pk 1 }, m, σ): This algorithm returns a bit d. A 2RS scheme R is said to be correct if for all (pk 0 , sk 0 ), (pk 1 , sk 1 ) output by the algorithm R.gen(set) where set was output by R.ini(1 λ ), for any message m, and for b ∈ {0, 1}:

R.ver({pk 0 , pk 1 }, m, R.sig(sk b , {pk 0 , pk 1 }, m)) = 1.
We use two security notions for 2-Ring Signatures: strong unforgeability, and anonimity, formally defined below.

Definition 4 (Strong Unforgeability). Let P be a 2-ring signature, then P is strongly unforgeable if for any polynomial-time adversary A, the probability Pr[Exp SUF P,A (λ) = 1] that A wins the experiment in Figure 1 is negligible. Definition 5 (Anonymity). Let P be a 2-ring signature, then P is (perfectly) anonymous if for any polynomial-time adversary A, the probability Pr[Exp anon P,A (λ) = 1] that A wins the experiment in Figure 1 is negligibly close to 1/2. Definition 6 (Equivalence-Class Signature (EQS) [START_REF] Hanser | Structure-preserving signatures on equivalence classes and their application to anonymous credentials[END_REF]). An Equivalence-Class Signature scheme S on a bilinear group of prime order p generated from a security parameter λ (described as BG = (G 1 , G 2 , G t , g 1 , g 2 , g T , e, q)) is a tuple of 5 algorithms defined as follows: S.ini(1 λ ): It returns a setup value set which contains the bilinear group BG. S.gen(set): It returns a public/private key pair (pk, sk). of message m t . An EQS scheme is said to be correct if for all (pk, sk) output by S.gen(set) where set was output by S.ini(1 λ ), for any message m, any scalar t ∈ Z * p :

S.ver(pk, S.sig(sk, m), m) = 1, and S.ver(pk, S.ChRep(pk, S.sig(sk, m), m, t), m t ) = 1

Exp SUF P,A (λ): set ← R.ini(1 λ ); (pk 0 , sk0) ← R.gen(set); (pk 1 , sk1) ← R.gen(set); S ← { }; (m, σ) ← A R.sig(•,{pk 0 ,pk 1 },•) (pk 0 , pk 1 ); if (m, σ) / ∈ S then return R.ver({pk 0 , pk 1 }, m, σ), else 0; Oracle R.sig(i, {pk 0 , pk 1 }, m): σ ← R.sig(ski, {pk 0 , pk 1 }, m); S ← S ∪ (m, σ); return σ; Exp anon P,A (λ): b $ ← {0, 1}; set ← R.ini(1 λ ); (pk 0 , sk0) ← R.gen(set); (pk 1 , sk1) ← R.gen(set); b * ← A R.sig(sk b ,{pk 0 ,pk 1 },•) (pk 0 , pk 1 ); return b = b * ; Oracle R.sig(sk b , {pk 0 , pk 1 }, m): return R.sig(sk b , {pk 0 , pk 1 }, m); Exp EUF-CMA P,A (λ): set ← S.ini(1 λ ); (pk, sk) ← S.gen(set); S ← { }; (m, σ) ← A S.sig(sk,•) ; if (m, σ) /
∈ S then return S.ver(pk, m, σ); else return 0;

Oracle S.sig(sk, m): σ ← S.sig(sk, m); S ← S ∪ (m, σ); return σ;

Exp adapt P,A (λ): set ← S.ini(1 λ ); (pk, sk) ← S.gen(set); b * ← A S.Ch/Sig(b,•,•,•,•) (pk, sk); if b * = b then return 1; else return 0; Oracle S.Ch/Sig(b, (sk, pk), s, t, m): if b = 0 then return S.sig(sk, m t ); return S.ChRep(pk, s, m, t); Exp class-hid M,A (λ): b $ ← {0, 1}; set ← S.ini(1 λ ); m, m0 $ ← M 2 ; m1 $ ← [m]; b * ← A(set, m, m b ); return b * = b; Exp IND$-CCA E,A (λ): set ← E.ini(1 λ ); b $ ← {0, 1}; (pk, sk) ← E.gen(set); b * ← A RREnc(pk,b,•),Dec(sk,•) (pk); return b = b * ; Oracle RREnc(pk, b, m): if b = 1 then return E.enc(pk, m); m $ ← {0, 1} |m| ; return E.enc(pk, m );
Oracle Dec(sk, c): if c was output by RRenc then return ⊥; return Dec(sk, c); Fig. 1: Security experiments and oracles of our cryptographic tools.

Definition 7 (EUF-CMA

). An equivalence-class signature scheme P is said to be existentially unforgeable under chosen message attacks (EUF-CMA) if for any polynomialtime adversary A, the probability Pr[Exp EUF-CMA P,A (λ) = 1] that A wins the EUF-CMA experiment given in Figure 1 is negligible. Definition 8 ((Perfect) Signature Adaptation). An equivalence-class signature scheme P is said to (perfectly) adapt signatures if, for all tuples (pk, sk, σ, m, t) such that (pk, sk) is a public/private key pair and S.ver(pk, σ, m) = 1, it holds that S.sig(sk, m t ) and S.ChRep(pk, σ, m, t) are identically distributed. Formally, this translates into the fact that for any polynomial-time adversary A, the probability Pr[Exp adapt P,A (λ) = 1] of winning the adapt experiment given in Figure 1 is negligibly close to 1/2. Definition 9 (Class-Hiding). A message space M = G (with > 1) of an equivalenceclass signature scheme is said to be class-hiding if for all polynomial-time adversary A, the probability Pr[Exp class-hid M,A (λ) = 1] of winning the class-hid experiment given in Figure 1, in which [m] is the equivalence class of m, is negligibly close to 1/2.

Lemma 1. [22]

A message space M = G is class-hiding if and only if the DDH assumption holds in G.

Definition 10 (IND$-CCA

). An encryption scheme E=(E.ini, E.gen, E.enc, E.dec) with security parameter λ is said to be indistinguishable from random under adaptive chosen ciphertext attack (IND$-CCA) if for any polynomial-time adversary A, the probability Pr[Exp IND$-CCA E,A (λ) = 1] that A wins the experiment in Figure 1 is negligibly close to 1/2. Note that this notion is equivalent to its more classic version, IND-CCA, in which the adversary must guess which of the two messages sent to the challenger was encrypted.

Security Model

In this section, we define our notion of γ-Sanitizable Signature, as well as the various security properties of our model. Definition 11 (γ-Sanitizable Signature (γSaS)). A γ-Sanitizable Signature scheme is a tuple of 6 algorithms defined as follows: Init(1 λ ): It returns a setup value set. SiGen(set): It returns a pair of signer public/private keys (pk, sk). SaGen(set): It returns a pair of sanitizer public/private keys (spk, ssk). Sig(m, sk, spk, ADM, γ): This algorithm computes a signature σ from the message m using the secret key sk, the sanitizer public key spk, the admissible function ADM and the limit γ. Note that we assume that ADM can be efficiently recovered from any signature as in the definition of Fleischhacker et al. [START_REF] Fleischhacker | Efficient unlinkable sanitizable signatures from signatures with re-randomizable keys[END_REF]. Moreover, for a modification MOD we write that ADM(MOD) = 1 to signify that the modification is allowed, and for a block number i, we write i ∈ ADM to say that the ith block can be modified. San(m, MOD, σ, pk, ssk, spk): Let ADM be the admissible function according to the signature σ. If ADM(MOD) = 1 and Ver(m, σ, pk, spk) = 1 then this algorithm returns a signature σ of the message m = MOD(m) using the signature σ, the signer public key pk and the sanitizer public/private key pair (ssk, spk). Else it returns ⊥. Ver(m, σ, pk, spk): It returns a bit b: if the signature σ of m is valid for the two public keys pk and spk then b = 1, else b = 0. This algorithm is deterministic. A γ-SaS is said to be correct if for all set output by Init(1 λ ), all Sig and San key pairs (pk, sk), (spk, ssk) output by SiGen(set) and SaGen(set), respectively, all admissible functions ADM, limits γ, modifications MOD, messages m, we have: Ver(m, Sig(m, sk, spk, ADM, γ), pk, spk) = 1, and for all σ such that Ver(m, σ, pk, spk) = 1, and for all σ output by San(m, MOD, σ, pk, ssk, spk) such that σ =⊥:

Ver(MOD(m), σ , pk, spk) = 1.
We now adapt the security properties of sanitizable signatures to fit our notion. In most cases, the limit must be treated in a similar way as the admissible function -however, it is important to consider this additional feature carefully, as it does of course introduce new trivial attacks. The detailed meaning and formal definition of each adapted property is given below.

Strong Unforgeability: The (strong) unforgeability property ensures that an adversary cannot create a valid message-signature pair without knowing the corresponding private key (i.e., sk for the signer and ssk for the sanitizer). The adversary has access to the signing oracle and the sanitizing oracle, and must provide a message-signature pair. Of course, the adversary cannot be allowed to trivially win the experiment by sending a pair produced by either of the oracles to the challenger -but can, however, produce a pair containing a message that had been signed by either of the oracles.

Definition 12 (Strong Unforgeability). Let P be a γSaS of security parameter λ, then P is strongly unforgeable if for any polynomial-time adversary A, the probability Pr[Exp SUF ULISS,A (λ) = 1] that A wins the SUF experiment given in Figure 2 is negligible. Immutability: A γSaS is immutable when no adversary is able to sanitize a signature without the corresponding sanitizer secret key or to sanitize a signature using a modification function that is not admissible (i.e., ADM(MOD) = 0 or the number of modifications is higher that the limit γ). The adversary has access to a signature oracle.

Definition 13 (Immutability [START_REF] Brzuska | Security of sanitizable signatures revisited[END_REF]). Let P be a γSaS. P is Immut-secure (or immutable) when for any polynomial time adversary A, the probability Pr[Exp immut ULISS,A (λ) = 1] that A wins the immut experiment given in Figure 2 is negligible, where q Sig is the number of calls to the oracle Sig(•, sk, •, •, •), (m i , ADM i , γ i , spk i ) is the i th query to the oracle Sig(•, sk, •, •, •) and σ i is the corresponding response.

Transparency: The transparency property guarantees that no adversary is able to distinguish whether a signature is sanitized. In addition to the signature oracle, the adversary has access to a sanitize oracle San(•, •, •, •, ssk). Moreover, the adversary has access to a challenge oracle Sa/Si(b, pk, spk, sk, ssk, •, •, •, •) that depends on a randomly chosen bit b: this oracle signs a given message and sanitizes it, if b = 0 then it outputs the original signature, otherwise it outputs the sanitized signature. To succeed in winning the experiment, the adversary must guess b. In order to exclude trivial attacks, we must keep track of the outputs of the challenge oracle. Indeed, the adversary can easily determine whether the Sa/Si called Sig or San by sanitizing the output signature and figuring out how many modifications are allowed. The limit does indeed introduce some new and somewhat tricky trivial attacks for the transparency property. For example, let us consider a message m of length 2, with both blocks being admissible for modifications, and a limit of γ = 1. The adversary can query Sa/Si with a modification MOD 1 on the first block, then query San on the output with a modification MOD 2 on the second block. If Sa/Si queried Sig, i.e., if the ouput is an original signature on MOD 1 (m), then the modification would be allowed, as MOD 1 (m) and MOD 2 (MOD 1 (m)) only have one difference, but if Sa/Si queried San, i.e., if the ouput is a sanitized signature of m on MOD 1 (m), then the sanitization is not allowed, since m and MOD 2 (MOD 1 (m)) have two differences. Definition 14 (Transparency). Let P be a γSaS. P is Trans-secure (or transparent) when for any polynomial time adversary A, the probability Pr[Exp trans ULISS,A (λ) = 1] that A wins the trans experiment given in Figure 2 is negligible.

Unlinkability: The unlinkability property ensures that a sanitized signature cannot be linked with the original one. We consider an adversary that has access to the signature and the sanitize oracles. Moreover, the adversary has access to a challenge oracle LRSan(b, pk, ssk, spk, •, •) that depends on a bit b: this oracle takes as input two signatures σ 0 and σ 1 , the two corresponding messages m 0 and m 1 and two modification functions MOD 0 and MOD 1 chosen by the adversary. If the two signatures have the same admissible function ADM, if MOD 0 and MOD 1 are admissible according to ADM and if MOD 0 (m 0 ) = MOD 1 (m 1 ) then the challenge oracle sanitizes σ b using MOD b and returns it. The goal of the adversary is to guess the bit b. The adversary is allowed to query LRSan on two signatures with different limits, thus to prevent trivial attacks the resulting output will artificially be limited to the smaller of the two. This means that the challenger must keep track of the outputs of all three oracles. Definition 15 (Unlinkability). Let P be a γSaS of security parameter λ. P is Unlinksecure (or unlinkable) when for any polynomial time adversary A, the probability Pr[Exp unlink ULISS,A (λ) = 1] that A wins the unlink experiment given in Figure 2 is negligibly close to 1/2.

Invisibility:

The invisibility property ensures that an adversary who does not know any private key can neither decide whether a block is admissible for modification or not, nor how many blocks can be modified. The adversary we consider has access to the sign oracle, the sanitize oracle, and a left-or-right admissible oracle LRADM that depends on the bit b chosen by the challenger. The adversary will give a message m along with two ADM functions ADM 0 , ADM 1 and two γ values γ 0 , γ 1 as input to this oracle, which will output a signature with ADM b as its admissible function, and γ b as a limit. The adversary will try to guess the value of b. To exclude trivial attacks, we must artificially limit the number of modified blocks to min(γ 0 , γ 1 ) on any signature created by LRADM no matter the value of b, and we must also prevent the adversary from querying a sanitization with a MOD function that is admissible by ADM 0 but not by ADM 1 or vice-versa.

Definition 16 (Invisibility). Let P be a γSaS of security parameter λ, then P is said to be Invis-secure (or invisible) if for any polynomial-time adversary A, the probability Pr[Exp invis ULISS,A (λ) = 1] that A wins the invis experiment given in Figure 2 is negligibly close to 1/2.

Scheme

We now present our scheme, ULISS, and detail the role of each of its building blocks. We first give an idea of the aim of the centerpiece of our scheme, i.e., the zero-knowledge proofs, and more specifically, their commitments, before giving the formal definition of our scheme, after which we detail the goal of each primitive.

Recall that whoever signs a message must be able to prove that it was done within the authorized bounds. When a message is signed, the signer also computes some commitments that will be used in the zero-knowledge proofs. Each commitment is a hash of some value concatenated with the public parameters. All commitments are initially elevated to an identical, random exponent x, and signed by the signer. To avoid traceability, the sanitizer will present them elevated to another, random exponent t in each sanitization. This resulting exponent is used as a witness in the zero-knowledge proof. The implications of this (change of) exponent are detailed after the definition of our scheme, at the end of this subsection. For simplicity, we omit both the exponent and the public parameters in the following explanation.

Commitments are divided in two categories: those meant to show that only admissible blocks are modified, and those meant to show that the number of modifications is

Exp immut P,A (λ): set ← Init(1 λ ); (pk, sk) ← SiGen(set); (spk * , m * , σ * ) ← A Sig(•,sk,•,•,•) (pk); if (Ver(m * , σ * , pk, spk * ) = 1) and (∀ i ∈ 1, q Sig , (spk * = spk i ) or (∀ MOD such that ADMi(MOD) = 1, m * = MOD(mi)) or D(mi, m * ) > γi) (where D(mi, mj
) is the number of different blocks) then return 1, else return 0;

Exp SUF P,A (λ): set ← Init(1 λ ); (pk, sk) ← SiGen(set); (spk, ssk) ← SaGen(set); S ← {}; O ← {Sig(•, sk, •, •, •), San(•, •, •, •, ssk)}; (m, σ) ← A O (pk, spk); if (m, σ) /
∈ S then return Ver(m, σ, pk, spk), else return 0;

Exp trans P,A (λ): set ← Init(1 λ ); (pk, sk) ← SiGen(set); (spk, ssk) ← SaGen(set); b $ ← {0, 1}; L ← [ ]; O ← Sa/Si(b, pk, spk, sk, ssk, •, •, •) Sig(•, sk, •, •, •), San(•, •, •, •, ssk, •) ; b ← A O (pk, spk); if (b = b ) then return 1, else return 0; Exp invis P,A (λ): set ← Init(1 λ ); (pk, sk) ← SiGen(set); (spk, ssk) ← SaGen(set); b $ ← {0, 1}; L ← [ ]; O ← Sig(•, sk, •, •, •), San(•, •, •, •, ssk), LRADM(b, sk, spk, •, •, •) ; b ← A O (pk, spk); if (b = b ) then return 1, else return 0; Exp unlink P,A (λ): set ← Init(1 λ ); (pk, sk) ← SiGen(set); (spk, ssk) ← SaGen(set); b $ ← {0, 1}; L ← [ ]; O ← Sig(•, sk, •, •, •), San(•, •, •, •, ssk, •), LRSan(b, pk, ssk, spk, •, •) ; b ← A O (pk, spk); if (b = b ) then return 1, else return 0; immut oracles: Sig(m, sk, ADM, spk, γ): return Sig(m, sk, spk, ADM, γ); SUF oracles: Sig(m, sk, ADM, spk, γ): σ ← Sig(m, sk, ADM, spk, γ); S = S ∪ (m, σ); return σ; San(m, MOD, σ, pk, ssk): σ ← San(m, MOD, σ, pk, ssk); S = S ∪ (m, σ); return σ ; invis oracles: Sig(m, sk, ADM, spk, γ): return Sig(m, sk, spk, ADM, γ); LRADM(b, sk, spk, m, (ADM0, γ0), (ADM1, γ1)): σ ← Sig(m, sk, spk, ADM b , γ b ); L[σ] ← (m, min(γ0, γ1), ADM0 ∩ ADM1); return σ; San(m, MOD, σ, pk, ssk): if L[σ] =⊥ then return San(m, MOD, σ, pk, ssk, spk); ( m, γ, ADM) ← L[σ]; if D(MOD(m), m) ≤ γ and ADM(MOD) = 1 then σ = San(m, MOD, σ, pk, ssk); L[σ ] = L[σ]; return σ ; else return ⊥; trans oracles: Sig(m, sk, ADM, spk, γ): σ ← Sig(m, sk, spk, ADM, γ); L[σ] ← (m, γ) return σ; San(m, MOD, σ, pk, ssk): if L[σ] =⊥ then return San(m, MOD, σ, pk, ssk, spk); ( m, γ) ← L[σ]; if D( m, MOD(m)) > γ then return ⊥; σ ← San(m, MOD, σ, pk, ssk, spk); L[σ ] ← L[σ]; returns σ ; Sa/Si(b, pk, spk, sk, ssk, m, ADM, MOD, γ): if ADM(MOD) = 0 then return ⊥; If b = 0 then σ ← Sig(MOD(m), sk, spk, ADM, γ); else σ ← Sig(m, sk, spk, ADM); σ ← San(m, MOD, σ, pk, ssk, spk); L[σ] ← (m, γ); returns σ; unlink oracles: Sig(m, sk, ADM, spk, γ): σ ← Sig(m, sk, spk, ADM, γ); L[σ] ← (m, γ); return σ; San(m, MOD, σ, pk, ssk): if L[σ] =⊥ then return San(m, MOD, σ, pk, ssk, spk); ( m, γ) ← L[σ]; if D(MOD(m), m) > γ then return ⊥; σ ← San(m, MOD, σ, pk, ssk, spk); L[σ ] ← L[σ]; returns σ ; LRSan(b, pk, ssk, spk, (m0, MOD0, σ0)(m1, MOD1, σ1)): for i ∈ {0, 1}, if Ver(mi, σi, pk, spk) = 1 or ADM0 = ADM1 or ADM0(MOD0) = ADM1(MOD1) or MOD0(m0) = MOD1(m1) or L[σi] =⊥ then return 0; ( mi, γi) ← L[σi]; for i ∈ {0, 1}, if D(MOD0(m0), m0) ≤ γ0 and D(MOD1(m1), m1) ≤ γ1 then σ ← San(m b , MOD b , σ b , pk, ssk, spk); L[σ ] ← ( mb , min(γ0, γ1
)); return σ ; else return ⊥; Fig. 2: Security experiments and oracles for γSaS properties. below the limit. For the first kind, they are as follows: if a block i can be modified, then its corresponding commitment is a hash of its index, otherwise it is a hash of its index concatenated with its content. The sanitizer will thus have to show that for each block of the modified message, the commitment is either equal to the hash of the index or the hash of the index concatenated with its content -if at least one unauthorized block was modified, then the sanitizer cannot produce a valid proof. We also add to this batch a commitment of the public parameters, to authenticate them.

The second kind is slightly more intricate: one commitment is the hash of the limit γ, then for each block, the commitment is the concatenation of the index and the content of that block. The sanitizer will have to show that there exists a value v such that the hash of v is equal to the first commitment, and, considering there are n message blocks, at least n -i blocks of the modified message are such that the hash of their index and their content is equal to their corresponding commitment.

Scheme 1 (ULISS) Let G be a group of prime order p, and g be a generator of G. Let E be a public key encryption scheme such that E = (E.ini, E.gen, E.enc, E.dec), S be an Equivalence-Class Signature such that S = (S.ini, S.gen, S.sig, S.ver, S.ChRep), R be a 2-Ring Signature scheme such that R = (R.ini, R.gen, R.sig, R.ver), and F and H be two hash functions (of domain {0, 1} * and codomain G). Our scheme instantiated with (G, E, S, F, H) is a γ-sanitizable signature scheme defined by the following algorithms: -

Init(1 λ ): It runs set E ← E.ini(1 λ ), set R ← R.ini(1 λ ) and set S ← S.ini(1 λ ), then it returns the setup set = (set E , set R , set S ). SiGen(set): It parses set = (set E , set R , set S ), runs (pk S , sk S ) ← S.gen(set S ), (pk R , sk R ) ← R.gen(set R ),
It computes A i ← H(i m i pp) x . -If i ∈ ADM, it computes B i ← F (i pp) x , else it computes B i ← F (i m i pp)
x . It then computes the two following proofs:

π 1 ← NIZK x : n i=1 (Bi = F (i pp) x ∧ V = F (pp) x ) ∨ (Bi = F (i mi pp) x ∧ V = F (pp) x ) π 2 ← NIZK x : n i=1 ∃ J ⊆ [n], (|J| = n -i) ∧ (∀ j ∈ J, (Aj = H(j mj pp) x ) ∧ (C = H(i pp) x ))
Finally, it generates the following values:

-s ← S.sig(sk S , (A 1 , B 1 , . . . , A n , B n ), C, V ), -e ← E.enc(spk E , (x, (A i , B i ) i∈[n] , C, V, s)), -r ← R.sig(sk R , {pk R , spk R }, (m, (A i , B i ) i∈[n] , C, V, π 1 , π 2 , s, e)), and returns σ = ((A i , B i ) i∈[n] , C, V, π 1 , π 2 , s, e, r). San(m, MOD, σ, pk, ssk, spk): This algorithm computes m 1 . . . m n ← MOD(m),
sets pp = pk spk, parses pk as (pk S , pk R ) and ssk as (ssk E , ssk R ), parses σ as

((A i , B i ) i∈[n] , C, V, π 1 , π 2 , s, e, r), picks t $ ← Z * p , runs (x, ( Ãi , Bi ) i∈[n] , C, Ṽ , s) ← E.dec(ssk E , e), sets x = x • t, V = F (pp) x and C = H(γ pp) x , and runs e ← E.enc(spk E , (x, ( Ãi , Bi ) i∈[n] , C, Ṽ , s)).
The algorithm verifies that the signatures (s and r) are valid, and verifies that ADM(MOD) = 1, else it aborts. For all i in [n], it sets A i = Ãt i , B i = Bt i , then it computes the signature s ← S.ChRep(pk S , s, ( Ã1 , B1 , . . . , Ãn , Bn , C, Ṽ ), t). It then computes the two following proofs:

π 1 ← NIZK x : n i=1 B i = F (i pp) x ∧ V = F (pp) x ∨ B i = F (i m i pp) x ∧ V = F (pp) x π 2 ← NIZK x : n i=1 ∃ J ⊆ [n], (|J| = n -i) ∧ (∀ j ∈ J, A j = H(j m j pp) x ∧ C = H(i pp) x Finally, it computes r ← R.sig(ssk R , {pk R , spk R }, (MOD(m), (A i , B i ) i∈[n] , C , V , π 1 , π 2 , s , e )) and returns σ = ((A i , B i ) i∈[n] , C , V , π 1 , π 2 , s , e , r ). Ver(m, σ, pk, spk): It parses σ as ((A i , B i ) i∈[n] , C, V, π 1 , π 2 , s, e, r), pk as (pk S , pk R )
and spk as (spk E , spk R ), then if π 1 and π 2 are valid, and:

-S.ver((A 1 , B 1 . . . , A n , B n , C, V ), pk S , s) = 1, -R.ver((m, (A i , B i ) i∈[n] , C, V, π 1 , π 2 , s, e), {pk R , spk R }, r) = 1, then it returns 1, else 0.
From the definition of the Verify algorithm, we see that the correctness of our scheme relies on the correctness of the NIZKP, as well as the correctness of the 2-Ring Signature and the Equivalence-Class Signature.

Having now introduced all notations, we can give a more in-depth description.

Non-Interactive ZKPs. The commitments denoted as V and {B i } i∈[n] are linked to the admissible function, with B i being the ith block's commitment, and V being the public parameter's commitment. We see that it serves its purpose: the prover must show that for each block (denoted by n i=1 ) in the (modified) message, the corresponding commitment is either equal to the hash of the index, or (denoted by ∨) the hash of the index and the content.

The C and {A j } j∈[n] commitments are linked to the limit γ, with C committing the limit and A j committing the original content of block j. Again, they follow the idea described at the beginning of the section: the prover must show that there is a value i ∈ [n] (denoted by n i=1 ), for which there exists a subset J ⊆ [n] such that [n] \ J has a size i, such that i is committed in C, and such that for all indices j ∈ J, the hash of j and the content of block j is equal to A j . The soundness of these proofs implies the immutability.

Recall that, to compute a sanitization, the sanitizer will generate its own random value t and elevate all commitments to the power of t in order to produce a signature with different commitments, using x = x • t as its witness in the proofs.

All information about the admissibility or the limits are hidden by the commitments. Since the proofs are zero-knowledge, they do not leak this information to the verifier, which ensures that ULISS is invisible. Moreover, since all the other parts of the signature are computed in the same way by the signer and the sanitizer, ULISS is transparent.

Class-Equivalence Signature. The signer first signs the commitments using a classequivalence signature. Indeed, as mentioned above, the sanitizer will modify the commitments by elevating them all to the same power, i.e., using different elements from the same equivalence class. Thus, using class-equivalence signature allows the sanitizer to authenticate this change by changing the representative. Thanks to the adaptability, the sanitizer can randomize all the commitments and update the class-equivalence signature accordingly. Since the other parts of the sanitizable signature are re-generated by the sanitizer (the ciphertext, the 2-ring signature, and the proofs), the verifier cannot link the sanitized signature to the original one, making our scheme unlinkable.

Encryption Scheme. Each sanitization will be done on the original commitments and not on the (potentially) sanitized ones. Thus, the signer must include an encryption of the commitments along with the exponent x in the signature. In order for the signatures to remain unlinkable, the sanitizer will re-encrypt the commitments and their exponent when it sanitizes a signature instead of simply keeping the same ciphertext.

2-Ring Signature. The actual signature of the message itself is done with a 2-Ring Signature, which has the interesting property of taking one secret key and two public keys as input, and does not give the information of which public key verifies the signature when it is checked. This allows us to verify the transparency property, as the signer and the sanitizer will input both of their public keys when signing the message, and everything else that was computed, i.e., commitments, proofs, the equivalence-class signature, and the encryption.

Instantiation of the Zero-Knowledge Proofs. ULISS uses two NIZKP for discrete logarithm relations, as detailed above.

Prover P Verifier V x (g 1 , g 2 , h 1 , h 2 ) r $ ← Z * p R 1 = g r 1 R 2 = g r 2 (R1,R2) -----→ c $ ← Z * p z = r + x • c c ← ----- z -----→ If g z 1 = R 1 • h c 1 and g z 2 = R 2 • h c 2 then return 1, else 0 Fig. 3: LogEq protocols.
Even if the languages of these proofs seem nontrival, we show how to efficiently instantiate them without heavy generic zero-knowledge proofs by using specific Schnorr-like protocols only, which guarantees that our signature is practical. We use the interactive proof of two discrete logarithms equality given in [START_REF] Chaum | Wallet databases with observers[END_REF] by Chaum and Pederson as a building block, which we recall in Figure 3. We use the technique given in [START_REF] Cramer | Proofs of partial knowledge and simplified design of witness hiding protocols[END_REF] to transform a proof that an instance belongs to some language into a proof that k-out-of-n instances belong to some languages. This transformation works on sigma protocols, like the Chaum and Pederson proof. The proof π 1 is an AND-proof of n 1-out-of-2 discrete logarithm equality proofs: we can obtain such a proof by performing n 1-out-of-2 discrete logarithm equality proofs separately. Since each discrete logarithm equality uses the same pair of basis/element of the group (V = F (pp) x in our protocol), the proof that each discrete logarithm is the same x is implicit.

The proof π 2 is a 1-out-of-n proof, where each of the n instances is actually i-outof-n discrete logarithm equality proof instances, for each i such that 1 ≤ i ≤ n. This proof can be obtained by using the transformation of [START_REF] Cramer | Proofs of partial knowledge and simplified design of witness hiding protocols[END_REF] on the Chaum and Pederson proof twice. We applied the Fiat-Shamir transformation [START_REF] Fiat | How to prove yourself: Practical solutions to identification and signature problems[END_REF], in order to obtain noninteractive versions of these proofs, by using the commitments hash as a challenge.

Performance. We now look at the complexity of π 1 and π 2 . More precisely, we study the number of exponentiations performed by the prover and by the verifier, and we deduce the size of the proof by counting the number of group elements. The size of a k-out-of-n proof is n times the size of the original proof, and the verification algorithm requires n times the computation time of the original proof verification. The proof algorithm uses a simulator of the original proof: since the Chaum and Pederson proof is zero-knowledge, there exists at least one simulator that perfectly simulates the proof. We can use the simulator

Sim(g 1 , g 2 , h 1 , h 2 ) that picks (c, z) $ ← (Z * p ) 2 , com- putes R 1 = g z 1 /h c 1 and R 2 = g z 2 /h c 2 , and return (R 1 , R 2 , c, z).
The proof algorithm of a k-out-of-n proof requires k times the computation time of the original proof algorithm, and n -k times the computation time of the simulator. We recap the performances of our zero-knowledge proofs in Table 1.

Prove Verify Size Chaum Pederson [14] 2 4 3 k-out-of-n on [14] 4 • n -2 • k 4 • n 3 • n π1 6 • n 8 • n 6 • n π2 3 • n 2 -n 4 • n 2 3 • n 2 Table 1: NIZKP Performance
Scheme complexity. We use the NIZKPs previously given, the class-equivalence signature presented in Fuchsbauer et al. [START_REF] Fuchsbauer | Structure-preserving signatures on equivalence classes and constant-size anonymous credentials[END_REF], the Fujisaki-Okamoto CCA-transformation [START_REF] Fujisaki | Secure integration of asymmetric and symmetric encryption schemes[END_REF] on El Gamal [START_REF] Elgamal | A public key cryptosystem and a signature scheme based on discrete logarithms[END_REF] as a Public-Key Encryption, and the Ring-Signature presented in Bultel and Lafourcade [START_REF] Bultel | Unlinkable and strongly accountable sanitizable signatures from verifiable ring signatures[END_REF]. Note that this ring-signature is not the most efficient one, however this scheme is verifiable, meaning it makes our scheme accountable according to the generic transformation given in [START_REF] Bultel | Efficient invisible and unlinkable sanitizable signatures[END_REF]. We provide the size of our parameters with these choices in Table 2, as well as the number of exponentiations and pairings in Table 3. For the sake of simplicity, we don't differentiate elements of group G of prime order p where DDH holds, and elements of Z * p . The number of message blocks is denoted by n. In average, the computational and size cost of having the limit is a factor n in comparison with [START_REF] Bultel | Efficient invisible and unlinkable sanitizable signatures[END_REF]. Security proofs. In this section, we list the conditions under which our scheme verifies the security properties defined in Section 3. We give brief sketches of the proofs of each theorem, for which complete versions can be found in Appendix A .

Theorem 1 (Strong Unforgeability). For any underlying strongly unforgeable 2-Ring Signature scheme R, our scheme ULISS is strongly unforgeable. Proof. The complete proof is given in Appendix A. [START_REF] Ateniese | Sanitizable signatures[END_REF].

We show that if ULISS is not unforgeable, then neither is the 2-Ring Signature Scheme R. This is done by building an adversary B against the SUF property of R who simulates the experiment for A by computing everything but signatures from R. B can simply forward A's forgery to its challenger.

Theorem 2 (Immutability). If the underlying class-equivalence signature scheme S is existentially unforgeable under chosen-message attack, and proofs π 1 and π 2 are sound, then our scheme ULISS is immutable.

Proof. The complete proof is given in Appendix A.2.

We show that ULISS is immutable by first listing how A could win the experiment and then show how (un)likely these events are to occur. In order to produce a sanitized signature that either (1) uses a previously unseen public key spk * , (2) has modifications on inadmissible blocks, or (3) has too many modifications, the adversary A must: exploit a collision in the commitments that would match two signatures, if there are none, it must fake the zero-knowledge proofs, and if that is not possible, then it must forge the equivalence-class signature. We thus show how the advantage of A against the immutability of ULISS is related to these three events. Theorem 3 (Unlinkability). If our scheme is strongly unforgeable, and for any IND$-CCA underlying encryption scheme, any class-hiding and adaptable underlying classequivalence signature, any zero-knowledge NIZKP, and under the DDH assumption, our scheme ULISS is unlinkable in the random-oracle model.

Proof. The complete proof is given in Appendix A. [START_REF] Beck | Practical strongly invisible and strongly accountable sanitizable signatures[END_REF].

The general idea of this proof is to follow a classical game-hops strategy where we replace some elements with random, progressively, to show that the adversary A cannot distinguish which signature was sanitized if the final result is indistinguishable from random. In the beginning, we ensure the signatures input by A using the challenger's signer and sanitizer keys are not forgeries, i.e., were computed by the challenger. We then use the IND$-CCA property of the encryption to replace its input with random, then we use the adaptability of the class-equivalence signature to replace every change of representative (from m to m t ) to a signature (of m t ), breaking that link between a sanitization and its original signature, then we use the zero-knowledge property of the NIZKP to replace them with simulations, in order to afterwards replace the original commitments with random (using DDH), so that we can finally use the class-hiding property of the message space used in the class-equivalence signature to replace the commitments with random in the sanitizations, thus breaking the final relevant link with the original signature.

Theorem 4 (Transparency). If our scheme ULISS is strongly unforgeable, then for any underlying class-equivalence signature scheme with perfect signature adaptation S, any zero-knowledge NIZKP, any underlying anonymous 2-Ring Signature scheme R, any IND$-CCA underlying encryption scheme, and under the DDH assumption, ULISS is transparent in the random oracle model.

Proof. The complete proof is given in Appendix A. [START_REF] Bellare | Policy-based signatures[END_REF].

The idea of this proof is that an adversary A can either distinguish who signed via the equivalence-class signature S ("is it a signature on m t , or a change of representative on a signature of m?"), via the commitments ("are these hashes of m or MOD(m) ?"), or via the 2-Ring Signature R ("was it signed by pk R or spk R ?"), or by replacing the signature with a forgery whose properties are the same but whose γ is not artificially controlled by the challenger. If our scheme is strongly unforgeable, if S has perfect signature adaptation, if DDH holds, the proofs are zero-knowledge, if the encryption is IND$-CCA, and if R is anonymous, then A cannot answer any of these questions.

The proof first ensures no forgery can happen, then replaces the commitments with random (also replacing the input to the encryption and the NIZKP), then the proof uses a hybrid argument, with experiment 1 (E 1 ) being the b = 1 experiment, then hybrid experiment H which is like E 1 except the 2-Ring signatures are all signed with the signer's key, and experiment 0 (E 0 ) is the b = 0 experiment. Differentiating E 1 from H implies breaking the anonymity of the 2RS, and differentiating H from E 0 implies breaking the perfect adaptation of the class-equivalent signature.

Theorem 5 (Invisibility). If our scheme ULISS is strongly unforgeable, for any IND$-CCA underlying encryption scheme, any zero-knowledge NIZKP, and under the DDH assumption, ULISS is invisible in the random oracle model.

Proof. The complete proof is given in Appendix A. [START_REF] Bender | Ring signatures: Stronger definitions, and constructions without random oracles[END_REF].

Using the same logic as for the unlinkability, we first ensure that the adversary does not produce and use forgeries, then we progressively replace elements with random and show that the resulting signature is indistinguishable from the real one. The only commitments linked to the limit and the admissible function are C and {B i } i∈[n] , thus we first use the IND$-CCA property of the encryption to replace its input with random, then we replace the zero-knowledge proofs with simulated ones, so that we can ultimately use the DDH property to replace the C and {B i } i∈[n] commitments with random instead of generating them honestly.

Application

In this Section, we detail several examples of how γ-Sanitizable Signatures could be used in practice. All scenarios below follow the same basic idea: someone (the signer) wishes to allow another person (the sanitizer) to modify pre-specified blocks of some authenticated data without losing the authentication, but not all of these pre-specified blocks at once. Recall that this limit (the "not all allowed blocks at once") is not present in regular SaS, hence the need for γSaS in the following examples.

Medical data. To keep the usual application on medical data, we believe that it is both important to anonymize -hiding personal information and perhaps uncommon diseases -and censor whatever is irrelevant to the data analysis, while also preventing a too large modification that would allow dishonest results, e.g., linking two unrelated medical conditions. In this example, the signer would be anyone from the medical staff, while someone who is more on the administrative side would be a sanitizer.

In [START_REF] Bultel | Efficient invisible and unlinkable sanitizable signatures[END_REF], the authors highlight the importance of having both invisibility and unlinkability in sanitizable signature using the following example: a physician signs the medical record of a patient in such a way that the sanitizer can (1) remove the personal information and send the anonymized record for analysis, and (2) remove everything except for the personal information, for financing purposes. Unlinkability ensures that the two sanitized signatures cannot be linked, which would mean reconstructing the full medical record. Invisibility maintains secrecy about what has been modified or not, preventing the verifier from assuming anything about the patient's possible pathology. However, without limitation, the sanitizer can modify both medical and personal data in the record, and can therefore create just about any false record. Our primitive corrects this flaw: by preventing the sanitizer from modifying more than half of the modifiable parts, we strongly reduce its capacities of generating false records.

Identity theft. Another (completely different) angle could be usurpation-resistance on websites, mostly social media: some information about a user may change (name, address, phone number, etc) but usually not all of them at once... unless the user was pretending to be someone else.

Thus, a website moderator could sign a profile with γSaS, allowing a user to modify γ elements at once. After some time has passed since the last modification, the moderator will re-sign the current profile state, allowing the user to change "new" things. This ensures that the profile will remain close to the original even when changes are made.

A similar control is done on Facebook, where you can only change your birthday or the name of your page4 every once in a while.

Figure 4 explains how our scheme could be used, in a simple case where a user can edit their name and their birthday, but only one of them each time, with the moderator re-signing every time t days pass without a modification. In this case, we use a 1SaS scheme (more generally, a γSaS scheme where the user is allowed to modify γ pieces of information). Assume that the information of the user is info 0 = "name : Alice; bday : 01/01/01". The social media generates the signature

σ 0 ← Sig(info 0 , sk, spk, ADM, 1)
to validate Alice's information, where ADM accepts the messages of the form "name : * ; bday : * " where * can be replaced by any word. If Alice want to change her name to Bob, she can sanitize σ by computing:

σ 0 ← San(info 0 , MOD, σ 0 , pk, ssk, spk),
where MOD(info 0 ) = "name : Bob; bday : 01/01/01". The sanitized signature still authenticates the social network, and thanks to the transparency and the unlinkability properties, no user can guess what information has been modified to obtain σ 0 , even when having access to σ 0 . After t days, the social network generates a new signature on info 1 = "name : Alice; bday : 01/01/01":

σ 1 ← Sig(info 1 , sk, spk, ADM, 1).
Alice can then modify the parameters to further change her profile. Contracts. Yet another angle is that of contracts, with a focus on employment contracts. Regulations may differ within a company from branch to branch, compared to what the country's law dictates and what the company's headquarters decide (e.g., in France, trade unions may negotiate with management to obtain better deals, for example on paid leave) and : the director (the signer) could issue and sign a basic contract that can be edited afterwards by the branches (sanitizers), within specified bounds. In this case, we only wish to allow modifications to cover exceptions to the contract while staying as close as possible to the original: SaS are not fine-grained enough to obtain this, which is why we need γSaS.

Takeaway. Ultimately, we simply wish to trust the sanitizer as little as possible: in a broader consideration, we can argue that this limit allows the sanitizer to correct potential mistakes made on a signed document while not being able to act dishonestly, i.e., the signer could write something incorrect at n potential places, but will probably not be wrong more than γ different times.

Conclusion

In this work, we looked at an interesting feature for Sanitizable Signatures that we call γ-Sanitizable Signatures, which allows to not only control which blocks of a message a sanitizer can modify, but how many of them can be changed at once. We extended the security properties of unlinkability, invisibility, transparency, (strong) unforgeability, and immutability to these γ-Sanitizable Signatures. We proposed our scheme, ULISS, (which stands for Unlinkable Limited Invisible Sanitizable Signature), whose basic building blocks are class-equivalence signatures, 2-ring signatures, and zero-knowledge proofs, and showed that it verifies all of the properties listed above. In the future, we aim to design a scheme as efficient as the ones without limits, i.e., with linear complexity and signature size. We also intend to work on designing unlinkable and invisible schemes for other restrictions, such as limiting the set of possible messages for each modifiable parts, in a hidden way.

A Complete Proofs

A.1 Proof of Theorem 1 Proof. Let A be an adversary that wins the strong unforgeability game for ULISS and let B be an adversary against the strong unforgeability of the underlying 2-Ring Signature R. Let C be B's challenger. We show how B can perfectly simulate the experiment for A to win its own experiment.

Indeed, to simulate A's experiment, B can compute everything on its own (the encryption, the class-equivalence signatures) except for the 2-ring signature.

At the beginning of the experiment, B generates the necessary key pairs (pk E , sk E ) and (pk S , sk S ) to simulate the encryption and the equivalence-class signatures. B also creates an empty set S ← {}. C sends (pk 0 , pk 1 ) to B, who can set pk ← (pk S , pk 0 ) and spk ← (pk E , pk 1 ) and send that to A.

Upon receiving a query for a signature (or sanitization) of a message m (or a modified message MOD(m)), B acts as follows:

Sig(•, sk, •, •, •) A sends (m, ADM, spk, γ), B parses m into n blocks, generates x $ ← Z *
p , sets pp = pk spk, then computes V ← F (pp) x and C ← H(γ||pp) x as well as the (A i , B i ) i∈[n] and the two proofs π 1 and π 2 as described in Def. 1. B then computes s ← S.sig(sk S , Bi ) [n] , C, Ṽ , s and computes x = x • t, before re-encrypting it as e . B then sets pp = pk spk, computes V = F (pp) x , C = H(γ||pp) x , then all A i and B i as described in 1, and computes the signature s as S.ChRep(pk S , s, ( Ãi , Bi ) i∈[n] , C, Ṽ , t). B can then compute the proofs π 1 and π 2 as described in Def. 1. B then queries C for a signature r as an answer to (1, (MOD(m), (A i , B i ) i∈[n] , C , V , π 1 , π 2 , s , e )), and finally answers A with σ ← ((A i , B i ) i∈[n] , C , V , π 1 , π 2 , s , e , r ), adding (MOD(m), σ ) to S.

(A i , B i ) i∈[n] , C, V ) and e ← E.enc(spk E , x, (A i , B i ) i∈[n] , C, V, s), and queries C for (0, (m, (A i , B i ) i∈[n] , C, V, π 1 , π 2 , s, e)), receiving s as an answer. B finally outputs σ ← ((A i , B i ) [n] , C, V, π 1 , π 2 , s, e,
At the end of the experiment, A will produce a pair (m, σ). If this pair is in S, then B returns 0, as this is considered a trivial win and thus excluded. Otherwise, B parses σ as s,e)) and sends ( m, r) as its answer to C.

((A i , B i ) [n] , C, V, π 1 , π 2 , s, e, r), sets m = (m, (A i , B i ) [n] , C, V, π 1 , π 2 ,
Note that the winning conditions for B and for A actually coincide: if (m, ( , r)) is in S, then C has the pair ((m, ), r) in its own set, and vice-versa. There is a direct correspondence between the sets.

To be thorough, let (m, σ) = (m, ((A i , B i ) [n] , C, V, π 1 , π 2 , s, e, r)) be A's answer. If there exists (m, σ ) = (m, ((A i , B i ) [n] , C , V , π 1 , π 2 , s , e , r )) with σ = σ in S (and the corresponding ( m0 , r ) = ((m, (A i , B i ) [n] , C , V , π 1 , π 2 , s , e ), r ) in C's set), then the pair ( m1 , r) = ((m, (A i , B i ) [n] , C, V, π 1 , π 2 , s, e), r) that B forwards to C can be such that r = r or m0 = m1 , but not both, since σ and σ differ by at least one variable, and thus ( m0 , r ) is not in C's set.

For the other way around, we apply the same logic to the case where the pair (m , σ) such that m = m is in S to see that ( m0 , r ) is not in C's set in this case either. Thus:

Adv SUF ULISS,A (λ) ≤ Adv SUF R,B (λ).

A.2 Proof of Theorem 2

We show the conditions under which our scheme is immutable.

Proof. An adversary A can win the immutability experiment in three different ways: either by ( 1) producing a sanitized signature that uses a sanitizer secret key whose corresponding public key was not sent as an input to the Sig oracle, by ( 2) producing a sanitized signature on an inadmissible message modification, or by ( 3) producing a sanitized signature on a message with more modified blocks than the accepted limit. We will first analyze each case separately then give a general game-based proof.

A new spk * = spk i . If A is using a key that wasn't input to the oracle, then A did not receive a signature "meant" to be sanitized with this key. Using the generic notations for a signature σ * = ((A i , B i ) i∈[n] , C, V, π 1 , π 2 , s, e, r), A can always produce a valid r, and e is not used in the verification, so these two elements are not interesting here.

A needs ((A i , B i ) i∈[n] , C, V, π 1 , π 2 ,
s) such that s is a valid signature, and such that π 1 , π 2 are valid proofs. We will refer to

((A i , B i ) i∈[n] , C, V ) as the commitments.
If there exists a collision on the commitments such that one tuple of commitments would work for two pairs of message-public key (m, spk) and (m , spk ), then A can query the oracle for a signature on the first and reuse the commitments and the s signature, while making new proofs π 1 , π 2 for the correct discrete log.

If there are no collisions, then either A wants to reuse a commitments-s signature pair even though it does not match the message, in which case it must forge the NIZKPs, or A does not want to forge the proofs, in which all that is left is to forge the s signature.

If A cannot forge anything -i.e., neither the proofs nor the signature -then there is no option left and A cannot use a new public key spk * .

Inadmissible blocks. Now, to fit the second condition in the immutability experiment, the message m * submitted by A as an answer must not correspond to any acceptable modification of any message queried to the oracle. As mentioned above, elements e and r in the signature are of no interest here.

For the same reasons as above, if there exists a collision on the commitments for two message-signature pairs, then A can reuse the corresponding s signature (and submit what queries it needs to make the answered message inadmissible). Note that, if m * has modifications on inadmissible blocks for a previously submitted message m, but the number of modifications is within the admissible limit, then commitments A i and C for m could be valid for m * (and thus proof π 2 also works). The "important" collision to find here would be a collision on F .

Once again, if there are no collisions (on F ), then A can try to forge s. If A cannot forge s, then all that is left to forge is the NIZKPs -or at least the first one, involving C and the A i values.

If π 1 cannot be forged, then A has no possibility left for a valid signature on a message with modifications on inadmissible blocks.

Over the limit. Finally, to fit the third and last condition, we fall into a very similar situation as the previous paragraph. A must submit a message m * which has more different blocks than allowed when compared to any previously submitted messages. We set r and e aside again and focus on the rest.

As above, collisions on commitments would allow A to reuse them along with their signature s. Once again, if the message m * has too many modifications compared to previously-submitted message m but only on admissible blocks, then the B i and V of m are valid (and so is its π 1 proof). The really important collision thus concerns the H function for the A i values, and C.

Using the same logic as above, if no collision exists, A can only win by forging s or by forging the NIZKPs.

General proof. We show that:

Adv immut ULISS (λ) ≤ 2q 3 H p + 2q 3 F p + Adv EUF-CMA S (λ)
In the following sequence, we write as S i the event that A is wins in Game i. Let abort i be the event that the challenger aborts at Game i.

Game 0. This is the original Exp immut ULISS,A (λ) experiment.

Adv immut ULISS,A (λ) = Pr[S 0 ] Game 1. This is the same as Game 0 except that the challenger aborts if the random oracle for hash function H returned values h 1 , h 2 , h 3 , h 4 as answers to the respective distinct queries q 1 , q 2 , q 3 , q 4 such that log h1 (h 2 ) = log h3 (h 4 ). For a given set of pairs {(h 1 , h 2 ), (h 3 , h 4 )}, there's a 1/p probability that the logs are equal (as the group G is of prime order p). If we denote with q H the number of queries, then there are q H (q H -1) pairs of distinct queries, and for a given pair (h i , h j ) there are 4q H -2 pairs (h k , h l ) with h k = h i , h j and h l = h i , h j , and thus there are q H (q H -1)(4q H -2)/2 sets of 2 pairs with distinct elements, each of them having a probability 1/p of verifying the log relation, thus Pr[abort 1 ] = q H (q H -1)(2q H -1)/p, and

| Pr[S 1 ] -Pr[S 0 ]| ≤ q H (q H -1)(2q H -1)/p.
After this game there are no possible collisions on commitments that use hash function H, i.e., let V, {B i } i∈[n] be the commitments for the signature of m, ADM with public parameters γ (the limit γ does not matter here), there exists no tuple (m , ADM , pp ) distinct from (m, ADM, pp) for which there exists

t ∈ Z * p such that V t , {B t i } i∈[n] are valid commitments.
Game 2. This is the same as Game 1 except that the challenger aborts if the random oracle for hash function F returned values h 1 , h 2 , h 3 , h 4 as answers to the respective distinct queries q 1 , q 2 , q 3 , q 4 such that log h1 (h 2 ) = log h3 (h 4 ). Following the same logic as above, and if we denote with q F the number of queries, we have:

| Pr[S 2 ] -Pr[S 1 ]| ≤ q F (q F -1)(2q F -1)/p.
After this game, there are no possible collisions on commitments that use hash function F , and due to the previous game, there are no possible collisions on commitments at all. A can thus not "re-use" them.

Game 3. This is the same as Game 2 except that the challenger aborts if A returns a signature σ * containing a valid NIZKP π 1 or π 2 on a statement that is not in the language. The probability of this event is bound by the soundness of the proofs, thus:

| Pr[S 3 ] -Pr[S 2 ]| ≤ Adv sound π1,π2 (λ).
Indeed, if there exists an adversary A such that the challenger aborts at game 3 (event denoted abort 3 , and we have | Pr[S 3 ] -Pr[S 2 ] |≤ Pr[abort 3 ), then we show how to build an adversary B against the soundness of π 1 and π 2 .

Let C be B's challenger, to whom B must output π 1 and π 2 such that one or both proofs are valid and on a statement that is not in the language.

At the beginning of the experiment, B generates a signer key pair (pk, sk) = ((pk R , pk S ), (sk R , sk R )) and sends pk to A.

B answers A's queries as follows: Sig(•, sk, •, •, •): on input (m, ADM, spk, γ), B parses m as n blocks, parses spk as

(pk E , spk R ) sets pp = pk spk, picks x $ ← Z * p and computes the {A i , B i } i∈[n]
, C and V commitments and the π 1 , π 2 proofs as described in 1. B computes the classequivalence signature on ({A i , B i } i∈[n] , C, V ) to obtain s. To complete the signature, B computes the ciphertext e ← E.enc(pk E , x,

(A i , B i ) i∈[n] , C, V, s, d)) and the 2-Ring Signature r ← R.sig(sk R , {pk R , spk R }, (m, (A i , B i ) i∈[n] , C, V, π 1 , π 2 , s, e)), sets σ ← ((A i , B i ) i∈[n] , C, V, π 1 , π 2 , s, e,

(λ).

Let C be B's challenger. At the beginning of the experiment, C generates a signing key pair (pk S , sk S ) and sends pk S to B. B generates a signing key pair (pk R , sk R ), sets (pk, sk) = ((pk S , pk R ), (sk S , sk R )) and sends it to A. B also creates an empty set S to keep track of A's public keys. B will answer A's queries as follows:

Sig(•, sk, •, •, •): on input (m, ADM, spk, γ), B parses m as n blocks, sets pp = pk spk, picks x $ ← Z * p and computes the {A i , B i } i∈[n] ,
C and V commitments and the π 1 , π 2 proofs as described in 1. B queries C for a class-equivalence signature on ({A i , B i } i∈[n] , C, V ) and receives s as an answer. B computes the ciphertext e ← E.enc(pk E , x,

(A i , B i ) i∈[n] , C, V, s, d)) and the 2-Ring Signature r ← R.sig(sk R , {pk R , spk R }, (m, (A i , B i ) i∈[n] , C, V, π 1 , π 2 , s, e)), sets σ ← ((A i , B i ) i∈[n] , C, V, π 1 , π 2 ,
s, e, r), adds spk to S, and returns σ.

In the end, A submits (m * , spk * , σ * ) as its answer. If σ * is not valid or if spk * is in S, then B returns 0, else it parses σ * as ((

A * i , B * i ) i∈[n] , C * , V * , π * 1 , π * 2 , s * , e * , r * ) and sends (((A * i , B * i ) i∈[n] , C * , V * ), s *
) as its answer to C. The winning conditions of A and B coincide -if spk * was not in S, then, because it is included in the A * i , B * i , C * and V * commitments, the signature s * on these commitments cannot have been output by C already.Conversely, B will not reject an answer that C would have accepted, simply because of how S is built, i.e., with C's outputs. Thus, if C returns 1, and B wins, it is because A successfully produced a valid sanitized signature using a sanitizer key whose public key was not given as an input to the signer.

By the changes in the previous games, following the arguments given before the games, A is unable to produce a valid answer, thus Pr[S 4 ] = 0.

A.3 Proof of Theorem 3

Proof. An adversary A wins the unlinkability experiment by distinguishing which of two signatures σ 0 or σ 1 was sanitized. We exclude trivial ways of winning by asking for valid signatures with the same admissible function ADM 0 = ADM 1 , identically admissible modification functions (ADM 0 (MOD 0 ) = ADM 1 (MOD 1 )), sanitized such that the signed message is identical (MOD 0 (m 0 ) = MOD 1 (m 1 )). Note that all calls to H and F are implicitly simulated by a random oracle.

We show that

Adv unlink U LISS,A (λ) ≤q Sig q LRSan Adv class-hid S (λ) + Adv adapt S (λ) + Adv IND$-CCA E (λ) + q Sig (q H + q F ) • Adv DDH G (λ) + Adv SUF U LISS (λ).
In the following sequence of games, let S i be the event that A wins at Game i. Game 0. This is the original Exp unlink ULISS,A (λ) experiment, hence:

Adv unlink ULISS,A (λ) = Pr[S 0 ] -1/2 Game 1.
This game is the same as Game 1 except the challenger aborts and returns a random bit if A queries LRSan on a forgery. Denoting with abort 1 the event that the challenger aborts in this game, we have that

Pr[abort 1 ] ≤ Adv SUF U LISS (λ), and since | Pr[S 1 ] -Pr[S 0 ]| = Pr[abort 1 ], | Pr[S 1 ] -Pr[S 0 ]| ≤ Adv SUF
U LISS (λ). After this game, the adversary can only query LRSan on signatures output by the challenger.

Game 2. This game is identical to Game 1 except the input to the encryption scheme is replaced with random. We claim that :

| Pr[S 2 ] -Pr[S 1 ]| = Adv IND$-CCA E (λ)
Proof. We show that if there exists a PPT adversary A capable of distinguishing between Games 2 and 1 then we can build an adversary B against the IND$-CCA security of the encryption scheme.

Let C be B's challenger, we show how B can simulate A's challenges. At the beginning, C generates the encryption key pair (pk E , sk E ), picks a bit b, forwards pk E to B and whenever B sends a message m, C answers with the encryption of a random message if b = 0, and with the encryption of m if b = 1. B will embed its challenges into A's challenges.

B picks a random bit b . B generates key pairs (pk S , sk S ) for the equivalence-class signature S, then two key pairs (pk R , sk R ),(spk R , ssk R ) for the 2-Ring Signature, then sets (pk, sk) ← ((pk S , pk R ), (sk S , sk R ) and (spk, ssk) ← ((pk E , spk R ), ssk R ). B then forwards (pk, spk), to A, sets L ← [ ] to keep track of the limits, Q ← [ ] to keep track of the commitments (indeed, B won't be able to query C for decryptions on the challenges), and answers A's queries as follows:

Sig(•, sk, •, •, •): A sends (m, ADM, s pk, γ), B computes the signature as described in Scheme 1, except if s pk = spk, instead of encrypting c = (x, (A i , B i ) i∈[n]
, C, V ) itself, it sends c to C and receives e in exchange, sets Q[e] = c, then continues normally to obtain a signature σ, then sets L[σ] = (m, γ), and returns σ. LRSan(b , pk, ssk, spk, •, •): on input ((m 0 , MOD 0 , σ 0 )(m 1 , MOD 1 , σ 1 )), this oracle returns ⊥ if for i ∈ {0, 1}, any of the following conditions do not hold: ( 1)

Ver(m i , σ i , pk, spk) = 1, (2) ADM 0 = ADM 1 , (3) ADM 0 (MOD 0 ) = ADM 1 (MOD 1 ) and (4) MOD 0 (m 0 ) = MOD 1 (m 1 ), else it gets ( mi , γ i ) ← L[σ i ] for i ∈ {0, 1}, then if D(MOD 0 (m 0 ), m0 ) ≤ γ 0 and D(MOD 1 (m 1 ), m1 ) ≤ γ 1 ,
Pr[B → 1|b = 1] = Pr[b * = b |b = 1] = Pr[A wins|b = 1] = Pr[S 1 ] and Pr[B → 1|b = 0] = Pr[b * = b |b = 0] = Pr[A wins|b = 0] = Pr[S 2 ] so | Pr[S 1 ] -Pr[S 2 ]| = | Pr[B → 1|b = 1] -Pr[B → 1|b = 0]| = Adv IND$-CCA E (λ)
After this game, the content of the encryption cannot be used to link the sanitization with the signature.

Game 3. This game is the same as the previous one, except every occurrence of S.ChRep(pk S , s, m, t) is replaced with S.sig(pk S , m t ). We argue that

| Pr[S 3 ] -Pr[S 2 ]| = Adv adapt S (λ).
Proof. Indeed, we show that if there exists a PPT adversary A capable of distinguishing between Games 3 and 2, then we can build a PPT adversary B against the adaptability of the underlying equivalence-class signature, S.

Let C be B's challenger. At the beginning of the experiment, C picks a random bit b and generates a signing key pair (pk S , sk S ), which is sent to B. B generates the remaining key pairs to complete (pk, sk) and (spk, ssk) (i.e., the pairs for the 2-Ring Signature, and the pair for the encryption scheme), and forwards pk and spk to A. B also picks a random bit b .

B answers A's queries as follows: Sig(•, sk, •, •, •): A sends (m, ADM, s pk, γ), B computes the signature as described in Scheme 1 and returns it, except if This game "unlinks" the class-equivalence signature in the sanitization from the one in the original signature.

s pk = spk, instead of encrypting c = (x, (A i , B i ) i∈[n] , C, V ),
Game 4. This game is the same as the previous one except that the NIZKPs are faked by the simulator Sim. As the simulator is "perfect", we argue that:

Pr[S 4 ] = Pr[S 3 ].
Proof. Indeed, if there exists a PPT adversary A capable of distinguishing between Games 4 and 3, then we can build an adversary B against the zero-knowledge property of the NIZKP π 1 , π 2 .

Let C be B's challenger, we show how B can simulate A's challenges. At the beginning, C picks a random bit b, and C will answer queries with a fake NIZKP if b = 0, and a real one if b = 1.

B generates all key pairs for the encryption E, the 2-Ring Signature scheme R, and the class-equivalence signature scheme S, and forwards the public keys to A. B picks a random bit b and embeds its challenges into A's challenges by answering the queries as follows: After this game, the commitments and the proofs are not linked.

Sig(•, sk, •, •, •): A sends (m, ADM, s pk, γ), if s pk = spk,
Game 5. This game is the same as the previous one except we replace the commitments with random elements when computing a signature (i.e., when generating them).

We argue that :

| Pr[S 5 ] -Pr[S 4 ] ≤ (q H + q F ) • Adv DDH G (λ)
, where q H (resp. q F ) is the number of queries made to the random oracle for hash function H (resp. F ).

Proof. First, we propose the definition of fixed n-DDH, based on the n-DDH: Definition 17 (fixed n-DDH). Let G be a multiplicative group of prime order q, with g a generator. For an instance {(g a , g bi , g c b,i )} 1≤i≤n such that for i ∈

[n], b i $ ← Z * p ,
Adv f n-DDH G (λ) ≤ n • Adv DDH G (λ).
Proof. We use a hybrid argument. Consider the following problem: Definition 18 (fixed (j, n)-DDH:). let G be a multiplicative group of prime order p with generator g, let j ∈

[n]. Given an instance {(g a , g bi , g c b,i )} i∈[n] , with a $ ← Z * p , b i $ ← Z * p for i ∈ [n] and b $ ← {0, 1} such that if i ≤ j c 0,i $ ← Z * p and c 1,i = a • b i , else c 0,i = a • b i and c 1,i $ ← Z * p .
The fixed (j, n)-Decisional Diffie-Hellman problem, or fixed (j, n)-DDH, is to guess the value of b.

Let j, n be integers such that 1 ≤ j ≤ n -1, for any adversary A solving the fixed (j, n)-DDH problem with advantage Adv f(j, n)-DDH G,A (λ), we show how to build an adversary B against DDH.

Let C be B's challenger. C begins by picking a random bit b, then sends B an instance (A, B, C) = (g a , g b , g c ) of DDH. B will embed this challenge in A's challenges by picking a random bit b $ ← {0, 1} and sending the following instance of fixed (j, n)-DDH: for all i ∈ [n]\{j +1}, B picks b i $ ← Z * p and sets g i = g bi , and if i ≤ j h i,0

$ ← G and h i,1 = A bi , else h i,0 = A bi and h i,1 $ ← G. B then sets g i,2 = B, h i,0 = h i,1 = C. B sends {(A, g i,2 , h i,b )} i∈[n]
to A, who answers with a bit b * that B forwards to C. Analysis: if b = b then B perfectly simulates (j, n), otherwise it simulates (j+1, n). Let Exp prob T ,β be the experiment for problem prob conducted with bit β with adversary T , e.g., Exp

f(j, n)-DDH A,0
is the experiment of fixed (j, n)-DDH with bit 0, and adversary A. We thus have that:

Adv f(j, n)-DDH A,G (λ) =| Pr[Exp f(j, n)-DDH A,1 → 1] -Pr[Exp f(j, n)-DDH A,0 → 1]| =| Pr[(Exp DDH B,1 → 1) ∩ b = 1] -Pr[(Exp DDH B,0 → 1) ∩ b = 0]| Adv f(j + 1, n)-DDH A,G (λ) =| Pr[Exp f(j + 1, n)-DDH A,1 → 1] -Pr[Exp f(j + 1, n)-DDH A,0 → 1]| =| Pr[(Exp DDH B,0 → 1) ∩ b = 1] -Pr[(Exp DDH B,1 → 1) ∩ b = 0]| if D(MOD 0 (m 0 ),
| Pr[H i+1 ] -Pr[H i ]| = Adv f(q H + q F )-DDH G (λ) ≤ (q H + q F ) • Adv DDH G (λ)
Moreover, in H q Sig the commitments are done honestly, meaning H 0 is identical to Game 4, and in H 0 all commitments are random, meaning H q Sig is identical to Game 5.

Summing the hybrids yields the following inequality :

| Pr[S 5 ] -Pr[S 4 ]| = | Pr[H 0 ] -Pr[H q Sig ]| ≤ q Sig (q H + q F ) • Adv DDH G (λ)
After this game, the commitments are not linked to each other. This step is a necessary setup for the next game. Game 6. This game is the same as the previous one except the commitments are replaced with random elements when sanitizing a signature.

We argue that :

| Pr[S 6 ] -Pr[S 5 ]| ≤ q LRSan q Sig • Adv class-hid S (λ),
where q Sig is the number of calls to the Sig oracle and q LRSan is the number of calls to the LRSan oracle.

Proof. We show the indistinguishability of Games 6 and 5 using a hybrid argument.

Let H i be the experiment such that the first i queries to LRSan have honestly computed commitments, while the q LRSan -i last queries are computed using random commitments.

We show that if there exists a PPT adversary A capable of distinguishing H i+1 from H i , for 0 ≤ i < q LRSan , then we can build an adversary B against the classhiding property of the message space of S. Let C be B's challenger, we now show how B simulates A's challenges. C starts by picking a random bit b. C will send B pairs of the form (C, C ) ∈ (G ) 2 such that C is in the equivalence class of C if b = 1, and randomly sampled otherwise. B generates all necessary keys to build the key pair (pk, sk) for the signer and (spk, ssk) for the sanitizer, then picks a random bit b * , and forwards pk and spk to A. B also initiates, as before, empty lists L and Q. It also At this point, there is no link between the original signature and its sanitization, that would differentiate the sanitization of σ 0 from that of σ 1 , thus the adversary cannot do any better than just guessing. Thus: Pr[S 6 ] = 1/2.

A.4 Proof of Theorem 4

Proof. We show that

Adv trans ULISS (λ) ≤ Adv adapt S (λ) + Adv Anon R (λ) + Adv IND$-CCA E (λ) + (q H + q F ) • Adv DDH G (λ) + Adv SUF ULISS (λ).
We write as S i the event "A wins at game i". In the following, the hash functions H and F are simulated by a random oracle.

Game 0. This is the original transparency experiment:

Adv trans ULISS,A (λ) = | Pr[S 0 ] -1/2| Game 1.
This game is the same as game 0 except the challenger aborts and returns a random bit if A queries the San oracle on a forged signature. We showed in A.1 that this event has negligible probability.

| Pr[S 1 ] -Pr[S 0 ]| ≤ Adv SUF ULISS,A (λ).
After this game, all signatures input to San were generated by the challenger. This means, in particular, that A cannot try to guess if a signature was sanitized or not by trying to "copy" the output of Sa/Si into a new forged signature with limit γ to try and see how many times it can be sanitized, thus differentiating the case where b = 0, and where b = 1.

Game 2. This game is the same as game 1 except the input to the encryption scheme is replaced with random. We claim that:

| Pr[S 2 ] -Pr[S 3 ]| ≤ Adv IND$-CCA E,A (λ)
We show that if there exists a PPT adversary A capable of distinguishing games 1 and 2, then we can build a successful adversary B against the IND$-CPA security of the encryption scheme E.

Let C be B's challenger, who, at the beginning of the experiment, picks a random bit b and generates a key pair (pk E , sk E ), forwarding pk E to B. B will also pick a random bit b , then generate a key pair (pk S , sk S ) for the Class-Equivalent Signature and two key pairs (pk 0 , sk 0 ), (pk 1 , sk 1 ) for the 2-Ring Signatures, set (pk, sk) = ((pk S , pk 1 ), (sk S , sk 1 )) and (spk, ssk) = ((pk E , pk 0 ), sk 0 ), and forward (pk, spk) to A. B initiates an empty list L to keep track of the "real" limit for each signature, and also initiates two empty list L C to store the content of the encryption, as it cannot decrypt its challenges.

B answers A's queries as follows:

Sig( B then sets pp = pk||spk and computes V ← F (pp) x , C ← H(γ||pp) x and all A i , B i as described in 1, then computes the signature s as S.ChRep(pk S , s, ( Ãi , Bi ) i∈[n] , C, Ṽ , t). B can then compute the proofs π 1 and π 2 as described in Def. 1. B then computes Game 3. This game is the same as game 2 except that the NIZKPs are "faked" by the simulator We claim that:

i , B i ) i∈[n] , C, V ), sets c = x, (A i , B i ) i∈[n] , C, V, s, computes e ← E.enc( s pk E , c), and finally r ← R.sig(sk R , {pk R , spk R }, (m, (A i , B i ) i∈[n] , C, V, π 1 , π 2 , s, e)). B outputs σ ← ((A i , B i ) [n] , C, V, π 1 , π 2 , s, e, r) to A. San(•, •, •, •, ssk) A sends (m, MOD, σ, pk), B parses MOD(m) as n blocks, parses σ as ((A i , B i ) [n] , C, V, π 1 , π 2 , s, e, r), picks t $ ← Z * p , if L C [e] exists it sets c ← L C [e],
r ← R.sig(ssk R , {pk R , spk R }, (MOD(m), (A i , B i ) i∈[n] , C , V , π 1 , π 2 , s , e )), and sets σ ← ((A i , B i ) i∈[n] , C , V , π 1 , π 2 , s , e , r ). B then checks the winning conditions : if L[σ] is null, it returns σ , else for ( m, γ) ← L[σ], it checks that D( m, MOD(m)) ≥ γ, in which case it sets L[σ ] = L[σ],
Pr[S 3 ] = Pr[S 4 ].
Indeed, of there exists a PPT adversary A capable of distinguishing games 2 and 3, then we can build a successful adversary B against the zero-knowledge property of π 1 and π 2 .

Let C be B's challenger, who, at the beginning of the experiment, picks a random bit b. B will also pick a random bit b , then generates the two key pairs (pk, sk) and (spk, ssk) adequately, forwarding pk and spk to A. B initiates an empty list L to keep track of the limit of each signature, and an empty list L R to keep track of what should have been encrypted, as the encryptions in Sa/Si are random.

B answers A's queries as follows: , the proofs are fake, then B simulated game 3, else it simulated game 2, which yields our equality. After this game, the proofs cannot be used by A to win the experiment.

Game 4. This game is the same as game 3, except that the commitments are replaced with random. We show that:

| Pr[S 3 ] -Pr[S 4 ]| ≤ q Sa/Si (q F + q H ) • Adv DDH G,A (λ), where q Sa/Si is the number of calls to the Sa/Si oracle.

Proof. To prove this, we reuse the notion of fixed n-DDH defined in Def. 17. We show the indistinguishability of Games 4 and 3 using a hybrid argument.

Let H i be the experiment such that the first i calls to Sa/Si use honest commitments and the q Sa/Si -i last ones use random commitments.

Then, we show that if there is a PPT adversary A capable of distinguishing H i and H i+1 , then we can build an adversary B against fixed (q F +q H )-DDH in G, where q H is the number of queries to the random oracle for hash function H, and q F is the number of queries to the random oracle for F . To make things clearer, we write these random oracles separately instead of implicitly including them in the signing oracles.

If b = 0, then in Sa/Si the class-equivalence signature s is a fresh signature, thus B simulates E 0 perfectly, and if b = 1, then s is a signature that was "sanitized", i.e., on a changed representative, thus B simulates H perfectly. The probability that B wins is the same as A, proving our inequality.

Finally, we have that:

Pr[S 4 ] = | Pr[1 ← E 1 ] -Pr[1 ← E 0 ] | = | Pr[1 ← E 1 ] -Pr[1 ← H] + Pr[1 ← H] -Pr[1 ← E 0 ] | ≤ | Pr[1 ← E 1 ] -Pr[1 ← H] | + | Pr[1 ← H] -Pr[1 ← E 0 ] | ≤ Adv Anon R (λ) + Adv Adapt S (λ)
A.5 Proof of Theorem 5

Proof. Upon querying the LRADM oracle on (m, (ADM 0 , γ 0 ), (ADM 1 , γ 1 )), the adversary A receives a signature σ = ((A i , B i ) i∈[n] , C, V, π 1 , π 2 , s, e, r), on m with ADM b , γ b , where b is the challenger's bit. In σ, the C value is directly linked to γ b , and the B i values are directly linked to ADM b . No other value depends on them. The idea of this proof is thus to randomize C and B i in an indistinguishable way. We show that:

Adv invis ULISS,A (λ) ≤Adv SUF U LISS (λ) + Adv IND$-CCA E (λ) + (q H + q F ) • Adv DDH G (λ), where q H and q F are the number of queries to the random oracle simulating H and F , respectively. We follow a logic very similar to the proof for the unlinkability and will thus refer to this proof for the straightforward game hops.

Game 0. This is the original Exp invis ULISS,A (λ) experiment, hence:

Adv invis ULISS,A (λ) = | Pr[S 0 ] -1/2| Game 1. This game is the same as the previous one except the challenger aborts and returns a random bit if A queries the San oracle on a forged signature.

| Pr[S 1 ] -Pr[S 0 ]| ≤ Adv SUF ULISS,A (λ). We showed in A.1 that this is negligible. After this game, all signatures input to San were generated by the challenger. This means, in particular, that A cannot try to guess if a signature was sanitized or not by trying to "copy" the output of LRADM into a new forged signature to test the limit or admissibility.

Game 2. This game is the same as the previous one, except the challenger replaces the input to the encryption scheme with random. We claim that:

| Pr[S 2 ] -Pr[S 1 ]| ≤ Adv IND$-CCA E (λ).
Proof. Follows the idea of the proof of Game 2 in the proof of unlinkability, i.e., we construct a secondary adversary B against IND$-CCA who injects its challenges by using them as the encryptions in A's queries to LRADM, and in San if A wishes to sanitize a signature that was output by LRADM. As in previous proofs, B must keep track of what should have been encrypted, as it cannot decrypt its challenges. Proof. Follows the idea of the proof of Game 4 in the proof of unlinkability. We construct a secondary adversary B against the zero-knowledge property of the NIZKPs. Now, in LRADM and in calls to San for signatures output by LRADM, B encrypts random messages instead of the commitments, to apply game 2 above, and queries its challenger for the proofs π 1 and π 2 .

Game 4. This game is the same as the previous one, except that the commitments that are computed when creating a signature are generated randomly. We argue that:

| Pr[S 4 ] -Pr[S 3 ]| ≤ q LRADM (q F + q H ) • Adv DDH G (λ).
Proof. Follows the idea of the proof of Game 5 in the proof of unlinkability. As in that game, we use hybrids, i.e. in experiment H i the first i queries to LRADM have honest commitments and the rest are random, from which we construct an adversary B against fixed (q H + q F )-DDH, as defined in 17. Recall that a challenger for (q H + q F )-DDH outputs tuples (g, X = g x , Y i = g yi , Z i = g zi ) for i ∈ [n], with the same x every time but a different y i , and such that either every z i is equal to x • y i , or they are all random.

As in the proof of unlinkability (and transparency), we set F (pp) = g, and B uses the random oracles as described in these proofs, setting hashes of values ending with pp as the Y i challenges. In LRADM, as in the unlinkability and transparency, B will use the Z i values as commitments in the i + 1st query, which will be legit if B's challenger is giving real DH elements, thus simulating hybrid H i+1 , and random otherwise, thus simulating H i . As all elements of the signatures output by LRADM linked to ADM or γ are random, we have that Pr[S 4 ] = 1/2.

  S.sig(sk, m): It computes and returns a signature σ on the equivalence class [m] of the message m using the private key sk. S.ver(pk, σ, m): It verifies the signature σ under the key pk on the equivalence class [m] of the message m. S.ChRep(pk, σ, m, t): It computes and returns a signature σ on (the same) equivalence class [m t ] = [m]

  Scheme 1 (ULISS) Let G be a group of prime order p, and g be a generator of G. Let E be a public key encryption scheme such that E = (E.ini, E.gen, E.enc, E.dec), S be an Equivalence-Class Signature such that S = (S.ini, S.gen, S.sig, S.ver, S.ChRep), R be a 2-Ring Signature scheme such that R = (R.ini, R.gen, R.sig, R.ver), and F and H be two hash functions (of domain {0, 1} * and codomain G). Our scheme instantiated with (G, E, S, F, H) is a γ-sanitizable signature scheme defined by the following algorithms:Init(1 λ ): It runs set E ← E.ini(1 λ ), set R ← R.ini(1 λ) and set S ← S.ini(1 λ ), then it returns the setup set = (set E , set R , set S ). SiGen(set): It parses set = (set E , set R , set S ), runs (pk S , sk S ) ← S.gen(set S ), (pk R , sk R ) ← R.gen(set R ), and returns (pk, sk) = ((pk S , pk R ), (sk S , sk R )). SaGen(set): It parses set, runs (spk E , ssk E ) ← E.gen(set E ), (spk R , ssk R ) ← R.gen(set R ), and returns (spk, ssk) = ((spk E , spk R ), (ssk E , ssk R )). Sig(m, sk, spk, ADM, γ): It parses sk as (sk S , sk R ), spk as (spk E , spk R ) and m as m 1 . . . m n and sets pp = pk spk. It picks x $ ← Z * p , sets V ← F (pp) x and C = H(γ pp) x , then for all i in [n]:-It computes A i ← H(i m i pp) x .-If i ∈ ADM, it computes B i ← F (i pp) x , else it computes B i ← F (i m i pp) x . It then computes the two following proofs: π 1 ← NIZK x :

Fig. 4 :

 4 Fig.4: A timeline of our proposed application.

  r) to A, and adds (m, σ) to S. San(•, •, •, •, ssk) A sends (m, MOD, σ, pk), B parses MOD(m) as n blocks, parses σ as ((A i , B i ) [n] , C, V, π 1 , π 2 , s, e, r), picks t $ ← Z * p , deciphers e to get c = x, ( Ãi ,

  r), and returns σ. At the end of the experiment, A returns a tuple (spk * , m * , σ * ). B extracts π * 1 and π * 2 and sends them to C. If A successfully forged the proofs then B wins, thus: Pr[abort 3 ] = Adv sound π1,π2,B (λ), which yields our inequality. After this game, signatures output by A can only contain sound NIZKPs, preventing A from winning this way by faking the proofs. Game 4. This is the same as Game 3, except that the challenger aborts if A returns a valid signature σ * containing an equivalence-class signature s that was not in any of the signatures output by the challenger. We have | Pr[S 4 ] -Pr[S 3 ] |≤ Pr[abort 4 ], we claim that Pr[abort 4 ] ≤ Adv EUF-CMA S (λ) and to prove it, we show how to build a PPT adversary B such that Pr[abort 4 ] = Adv EUF-CMA S,B

  it computes the sanitization of σ b : -B follows all of the sanitization as described in Scheme 1 to sanitize σ b except for the decryption/encryption; let e b be the encryption in σ b , then B retrieves c ← Q[e b ], queries C for a new encryption e of c, then continues normally, producing a sanitized signature σ using e as its encryption. finally, B sets L[σ ] ← ( mb , min(γ 0 , γ 1 ), and Q[e ] ← c, and returns σ , else it returns ⊥. San(•, •, •, •, ssk, spk): on input (m, MOD, σ, pk), B gets ( m, γ) ← L[σ], then if we have D(MOD(m), m) ≤ γ it computes the sanitization: -B computes the sanitized signature normally except for the encryption/decryption; let e be the encryption in σ, if pk = pk, then B queries C for a decryption of e and obtains c then re-encrypts it to obtain e , else if pk = pk, B gets c ← Q[e] then queries C on c for an encryption e , setting Q[e ] = c; B then uses the content of c to follow the steps and compute the sanitized signature σ , then sets L[σ ] = L[σ], and returns σ , else it returns ⊥. At the end of the experiment, A returns a bit b * . If b * = b , then B returns 1, else it returns 0. Analysis: If b = 0 then B perfectly simulates Game 2 to A, else it perfectly simulates Game 1. If B returns 1, it means A wins (b * = b ), thus :

  it encrypts a random string to obtain e, sets Q[e] = c, then continues normally to obtain a signature σ, then sets L[σ] = (m, γ), and returns σ. LRSan(b , pk, ssk, spk, •, •): on input ((m 0 , MOD 0 , σ 0 )(m 1 , MOD 1 , σ 1 )), this oracle returns ⊥ if for i ∈ {0, 1}, any of the following conditions do not hold: (1)Ver(m i , σ i , pk, spk) = 1, (2) ADM 0 = ADM 1 , (3) ADM 0 (MOD 0 ) = ADM 1 (MOD 1 ) and (4) MOD 0 (m 0 ) = MOD 1 (m 1 ), else it gets ( mi , γ i ) ← L[σ i ] for i ∈ {0, 1}, then if D(MOD 0 (m 0 ),m0 ) ≤ γ 0 and D(MOD 1 (m 1 ), m1 ) ≤ γ 1 , it computes the sanitization of σ b : -B follows all of the sanitization as described in Scheme 1 to sanitize σ b except for the decryption/encryption and the change of representative for the equivalence-class signature s: • let e b be the encryption in σ b , then B retrieves c ← Q[e b ], encrypts a random string to obtain e , and sets c ← Q[e ], then • after computing everything else normally (using the content of c), B queries C for a signature s with ((pk S , sk S ), s, ((A i , B i ) i∈[n] , C, V ), t), then B continues ordinarily, producing a sanitized signature σ using e as its encryption and s as its equivalence-class signature. Finally, B sets L[σ ] ← ( mb , min(γ 0 , γ 1 ), and returns σ , else it returns ⊥. San(•, •, •, •, ssk, spk): on input (m, MOD, σ, pk), if pk = pk it computes the sanitization normally, else B gets ( m, γ) ← L[σ], then if D(MOD(m), m) ≤ γ it computes the sanitization: -B computes the sanitized signature as above, i.e., normally except for the decryption/encryption for which it uses Q and encrypts a random string, respectively, and for the equivalence-class signature, for which it queries C, else it returns ⊥. At the end of the experiment, A returns a bit b * : if b * = b , then B answers 1 (guessing that C used S.ChRep), else it answers 0. Analysis: If b = 0 then B is perfectly simulating Game 3 (every change of representative is actually a new signature), and if b = 1 then B is perfectly simulating Game 2. Using the same justification as in the previous game, we have: | Pr[S 3 ] -Pr[S 2 ]| = | Pr[B → 1|b = 1] -Pr[B → 1|b = 0]| = Adv adapt S (λ).

  B computes everything normally, else B computes the signature as described in the previous game (including adding elements to L and Q) except instead of computing π 1 and π 2 itself, they are queried from C. LRSan(b , pk, ssk, spk, •, •): on input ((m 0 , MOD 0 , σ 0 )(m 1 , MOD 1 , σ 1 )), this oracle returns ⊥ if for i ∈ {0, 1}, any of the following conditions do not hold: (1) Ver(m i , σ i , pk, spk) = 1, (2) ADM 0 = ADM 1 , (3) ADM 0 (MOD 0 ) = ADM 1 (MOD 1 ) and (4) MOD 0 (m 0 ) = MOD 1 (m 1 ), else it gets ( mi , γ i ) ← L[σ i ] for i ∈ {0, 1}, then if D(MOD 0 (m 0 ), m0 ) ≤ γ 0 and D(MOD 1 (m 1 ), m1 ) ≤ γ 1 ,it computes the sanitization of σ b as in the previous game (again, including for L and Q), except it uses S.sig((, c) t ) instead of S.ChRep(c, t) to get s , and queries C for the proofs π 1 , π 2 instead of computing them; then finally returns the obtained sanitized signature σ , else it returns ⊥. San(•, •, •, •, ssk, spk): on input (m, MOD, σ, pk), if pk = pk, it computes the sanitizations normally, else B gets ( m, γ) ← L[σ], then if D(MOD(m), m) ≤ γ it computes the sanitization as in the previous game (once more, including for L and Q), except it uses S.sig(,i)nstead of S.ChRep as described for LRSan, and queries C for the proofs π 1 and π 2 , finally returning the obtained sanitized signature σ , else it returns ⊥. In the end A returns a bit b * , if b * = b B sends 1 to C (guessing that the proofs are real) else it answers 0. Analysis: If b = 0 then B is perfectly simulating Game 4 (the proofs are simulated), and if b = 1 then B is perfectly simulating Game 3. Using the same justification as in the previous games, we have: Pr[S 4 ] = Pr[S 3 ].

  and a $ ← Z * p and b $ ← {0, 1} such that c 0,i $ ← Z * p and c 1,i = a • b i , the fixed n-DDH problem is guessing b, and the fixed n-DDH assumption states than no PPT algorithm can solve this problem with a non-negligible advantage. Lemma 2. For any n ∈ N, fixed n-DDH holds under the DDH assumption, with

  m0 ) ≤ γ 0 and D(MOD 1 (m 1 ), m1 ) ≤ γ 1 , it computes the sanitization of σ b as in the previous game (again, including for L and Q), returning a sanitized signature σ ; else it returns ⊥.San(•, •, •, •, ssk R , •): on input (m, MOD, σ, pk, spk), B gets ( m, γ) ← L[σ], then if D(MOD(m), m) ≤ γ itcomputes the sanitization as in the previous game (once more, including for L and Q), finally returning a sanitized signature σ ; else it returns ⊥. In the end A returns a bit b * , if b * = b B sends 1 to C (guessing that the DDH elements are real) else it answers 0. Analysis: In the case where b = 1, as explained in LRSan above, B simulates H i . Now if b = O, there is no relation between x and the y and z values, and thus the commitments are completely random, simulating H i+1 . Hence, following the same logic as in the previous games:

  otherwise it queries C for the decryption c, to obtain c = x, ( Ãi , Bi ) i∈[n] , C, Ṽ , s, d and computes x = x • t. If c was not in L C [e], then B computes e ← E.enc(pk E , c), else it queries C for a challenge on c to get e , setting L C [e ] = c.

  and returns σ , else it returns 0. Sa/Si(b , pk, spk, sk, ssk, •, •, •): on input (m, ADM, MOD, γ), if ADM(MOD) = 0, B returns ⊥. If b = 1, then B proceeds as follows: B first obtains a signature σ by computing Sig on the message m, except instead of encrypting normally, it sets: c = x, (A i , B i ) i∈[n] , C, V, s, queries C for a challenge encryption on c, receiving e and setting L C [e] = c. Then, B computes San normally, except instead of decrypting e it simply uses the content of c (either having kept it or extracting it from L C ), and then instead of re-encrypting it, it queries it to C as a challenge, obtaining e as an answer and setting L C [e ] = c. B finally obtains a sanitization σ . B sets L[σ ] ← (m, γ), and finally returns σ to A. Else, if b = 0, then B obtains a signature σ by computing Sig on the message MOD(m), and, as above, instead of encrypting normally, it sets c = x, (A i , B i ) i∈[n] , C, V, s, queries C for a challenge encryption on c, receiving e and setting L C [e] = c. B then sets L[σ] ← (m, γ), and return σ to A. At the end of the experiment, A returns a bit b * . If b = b * , then B forwards 1 to C, else it returns 0. If b = 0, i.e., C encrypts a random message, then B simulated game 2, else it simulated game 1, which yields our inequality. After this game, the encryption cannot be of any help to A in the experiment.

  Sig(•, sk, •, •, •) on input (m, s pk, ADM, γ), B acts as in the above game. The lists are handled as above. San(•, •, •, •, ssk) A sends (m, MOD, σ, pk), acts as above except : if c was in L C , it encrypts a random message to compute e , setting L C [e ] (otherwise it uses sk E to decrypt and then re-encrypt with pk E ), then it queries C for the proofs π 1 and π 2 , else the proofs are computed normally. The lists are handled as above. Sa/Si(b , pk, spk, sk, ssk, •, •, •): on input (m, ADM, MOD, γ), if ADM(MOD) = 0, B returns ⊥. If b = 1, then B proceeds as follows: B first obtains a signature σ by computing Sig on the message m, except instead of encrypting normally, it sets: c = x, (A i , B i ) i∈[n] , C, V, s, and L C [e] = c, then generates a random message c and sets e ← E.enc(pk E , c), and the proofs π 1 and π 2 are queried from C. Then, B computes San normally, except instead of decrypting e it simply uses the content of c (either having kept it or extracting it from L C ), computes e as a random encryption, sets L C [e ] = c, and then it queries C for π 1 and π 2 . B finally obtains a sanitization σ . B sets L[σ ] ← (m, γ), and finally returns σ to A. Else, if b = 0, then B obtains a signature σ by computing Sig on the message MOD(m), and, again, as above, sets c = x, (A i , B i ) i∈[n] , C, V, s, encrypts a random message to get e, sets L C [e] = c, and queries C for the proofs π 1 , π 2 . B then sets L[σ] ← (m, γ), and return σ to A. At the end of the experiment, A returns a bit b * . B returns 1 to C if b = b * , else it returns 0. If b = 0, i.e.

Game 3 .

 3 This game is the same as the previous one, except that the NIZKPs are faked by the Simulator. We argue that: Pr[S 3 ] = Pr[S 2 ].

Table 2 :

 2 Size of the parameters (group elements). Scheme Sig. sk Sig. pk San. sk San. Parameter size comparison.

						pk Signature
	ULISS	2	2	2	2	3n 2 +10n+22
	[11]	n+1	n+1	2	2	4n + 18

Table 3 :

 3 Complexity comparison.

	Complexity (exponentiations and pairings).
	Scheme	Sign	Sanitize	Verify
	ULISS	exp. 3n 2 +9n+16 3n 2 +7n+12 4n 2 +8n+8 pairing 0 0 2n + 5
	[11]	exp. pairing	5n + 13 0	3n + 16 0	8 4n + 6

  •, sk, •, •, •) on input (m, s pk, ADM, γ), B parses m as n blocks, generates x p , then sets pp = pk|| s pk, and computes V ← F (pp) x , C ← H(γ||pp) x and the(A i , B i ) i∈[n]as described in Def. 1. With these, B can compute the two proofs π 1 and π 2 , again as described in Def. 1. B then computes s ← S.sig(sk S , (A

$ ← Z *

facebook.com/help/563229410363824/

facebook.com/help/271607792873806

Acknowledgements

We thank Chris Bruska for his very helpful comments and suggestions. This work was supported by the French ANR, grants 16-CE39-0012 (SafeTLS).

Following the same logic of decomposition-recomposition, and summing the "hybrids", we obtain, concluding the proof:

We now show the indistinguishability of Games 5 and 4 using a hybrid argument. Let q Sig be the number of queries made to the Sig oracle, let H i be the experiment such that the i first queries to the Sig oracle use honest commitments, and the q Sig -i last queries use random commitments. Suppose there exists an PPT adversary A capable of distinguishing H i from H i+1 for 0 ≤ i < q Sig , then we show how to build an adversary B against fixed q H + q F -DDH in G.

Let C be B's challenger, we now show how B simulates A's challenges. C starts by picking a random bit b. C will send B tuples that will amount into a fixed (q H +q F )•DDH instance, i.e., tuples of the form (g, X = g x , Y = g y , Z = g z ) with a different Y, Z in each tuple. B generates all necessary keys to build the pair (pk, sk) for the signer and (spk, ssk) for the sanitizer, then picks a random bit b * , and forwards (pk, spk) to A. B also initiates empty lists L and Q as above, along with a new list D, to keep track of the DDH queries, and a counter c Sig initated to 0, counting the number of calls to Sig. For clarity, we separate the random oracles by expliciting them, as they are the ones affected by the change: In the beginning, B sets F (pp) = g. B will embed its challenges in A's challenges by answering its queries as follows: Sig(•, sk, •, •, •): A sends (m, ADM, s pk, γ), if s pk = spk, then B computes everything normally, else B computes the signature as described in the previous game (including adding elements to L and Q) except it always fakes the NIZKP, and when generating the commitments, it proceeds as follows:

if c Sig ≤ i, it generates the commitments honestly, else if c Sig = i + 1, first, B generates a random t and sets V = X t (= (g x ) t = F (pp) xt ), then for all other commitments, if we denote with u their corresponding input to H or F (e.g., for C, u = γ||pp) then we get a hash h = F (u) (for B i ) or h = H(u) (for A i and C), and the "actual" commitment is then

), B generates random commitments, then B continues, to obtain a signature σ in the end, which it returns after incrementing c Sig . LRSan(b , pk, ssk, spk, •, •): on input ((m 0 , MOD 0 , σ 0 )(m 1 , MOD 1 , σ 1 )), this oracle returns ⊥ if for i ∈ {0, 1}, any of the following conditions do not hold: (1)

generates an empty list T to remember C's queries, and a counter c LRSan counting the queries to LRSan.

B will embed its challenges in A's challenges by answering its queries as follows:

Sig(•, sk, •, •, •): A sends (m, ADM, s pk, γ), as usual, if s pk = spk, B acts normally, else B computes the signature as described in the previous game (including adding elements to L and Q) except when generating the commitments, it queries C to get a pair (M, M ) and uses M as the commitments (which are thus random), to obtain a signature σ in the end, which it returns, and sets

, any of the following conditions do not hold: ( 1)

, it computes the sanitization of σ b as in the previous game (again, including for L and Q), except the commitments are computed as follows, first

LRSan ≤ i, it compute the commitments normally, i.e. using M else if c LRSan = i+1, it generates a random t and uses (M ) t , i.e., the elements of M elevated to the power of t, as the commitments (which will thus be in the class of M if M also is, otherwise they will be random), else (if c LRSan > i + 1), it computes random commitments, then finally returns the obtained sanitized signature σ and sets Analysis: If b = 1, then B perfectly simulates H i+1 , as explained in LRSan above, since the first i + 1 queries are answered honestly, else if if b = 0, then B perfectly simulates H i , as (M ) t is not linked to M and thus the i + 1st query uses random commitments. Using the same justification as in the previous games, we have:

In H 0 all commitments are computed randomly, which makes it identical to Game 6, and in H q LRSan all commitments are honest, which makes it identical to Game 5. Summing the hybrids, we get

Let C be B's challenger, who picks a random bit b at the beginning of the experiment. B also picks a random bit b and computes all necessary key material to obtain (pk, sk) and (spk, ssk), forwarding pk, spk to A, and setting pp = pk||spk. B initiates empty lists L, L E , as above, to keep track of the limit and the encryptions, respectively, and a list L D , which will be used to inject the fixed DDH challenges into A's queries, as well as a counter c Sa/Si counting the queries to Sa/Si.

Recall that C sends B challenges of the form (g, X = g x , Y = g y , Z = g z ), with a different Y, Z every time, such that if b = 0, then z is random, else z = x • y. First, B sets F (pp) = g, then handles the random oracles as follows: Other oracles are handled as follows:

Sig(•, sk, •, •, •) on input (m, s pk, ADM, γ), B acts as in the above game (even when computing the commitments, recall that we simply explicited the random oracles as they are different from usual: thus, if s pk = spk, we get commitments coming from a DDH challenge, otherwise simply random hashes). San(•, •, •, •, ssk) A sends (m, MOD, σ, pk), acts as above except it queries a simulator for the proofs if c was in L E (still encrypting a random message to compute e in this case). Sa/Si(b , pk, spk, sk, ssk, •, •, •): on input (m, ADM, MOD, γ), if ADM(MOD) = 0, B returns ⊥. If b = 1, then B proceeds as follows: B first obtains a signature σ by computing Sig on the message m as follows:

if c Sa/Si ≤ i, the commitments are computed normally, else if c Sa/Si = i + 1, B generates a random t, sets V = X t , then for all other commitments, if we denote with u the corresponding input for H or F (e.g., for A i , u = i||m i ||pp), then we get a hash h = F (u) (for B i ) or h = H(u) (for A i or C), and the final commitment will be (L D [h]) t , else (if c Sa/Si > i + 1), it just computes random commitments. They are then signed normally with the class-equivalent signature to obtain s, then a random message is encrypted to obtain e, setting L E [e] as c = t, (A i , B i ) i∈[n] , C, V, s. B queries the simulator for the proofs π 1 , π 2 before signing the whole with sk R to obtain r, and thus σ. Then, B computes San normally, except instead of decrypting e it simply uses the content of c (either having kept it or extracting it from L E ), computes e as a random encryption, and B queries the simulator for π 1 and π 2 . B finally obtains a sanitization σ . B sets L[σ ] ← (m, γ), and returns σ to A. Else, if b = 0, then B obtains a signature σ by computing Sig on the message MOD(m) the same way as described above for a signature on m if b = 1. B then sets L[σ] ← (m, γ), and returns σ to A.

In the end, A returns a bit b * , and if b = b * , then B sends 1 to C, else it sends 0. Analysis. If b = 0, then the commitments are random, and B simulates H i , else it simulates H i+1 , which yields our inequality, as H 0 is Game 4 (commitments are random), and H q Sa/Si is Game 3 (all commitments are honest).

At this point, the commitments can no longer be used by A to answer the Sa/Si challenge.

The only differences between the signature of MOD(m) (b = 0) and the sanitization of m into MOD(m) (b = 1) are now in s and r: if b = 1, s has had a change of representative and r was signed with ssk R , and if b = 0 then s is an "original" and r is signed with sk R .

We use a hybrid argument to show that these are indistinguishable. Let E 1 be the experiment for b = 1, let E 0 be the experiment for b = 0. Let H be a hybrid experiment where the challenger does everything as in E 1 , except the 2-Ring Signature is signed with the Signer's key, sk R .

We argue that

Indeed, if there exists a PPT adversary A able to distinguish between the two experiments with non-negligible probability, we can build an adversary B who wins the Anon experiment of the 2-Ring Signature scheme R with non-negligible probability.

Let C be the challenger for B, we show how B simulates the experiment for A.

At the beginning, C picks a random bit b, and gets two public/private key pairs (pk 0 , sk 0 ) and (pk 1 , sk 1 ), which it forwards to B. B sets (pk R , sk R ) ← (pk 1 , sk 1 ) and (spk R , ssk R ) ← (pk 0 , sk 0 ), then generates two key pairs (pk E , sk E ) and (pk S , sk S ) for the encryption and class-equivalence signature, respectively. B also initiates, as usual, a list L for the limits, and a list L E for the encryptions. B can then set (pk, sk) = ((pk S , pk R ), sk S ) and (spk, ssk) = ((pk E , pk R ), sk E ) and send (pk, spk) to A. B's answers to A's queries are as follows:

pk, ADM, γ), B parses m as n blocks. If s pk = spk, it computes the signature normally, except for the 2-Ring Signature, as B doesn't know sk R /ssk R , and must thus query C for the signature r "with key 1". Otherwise, if s pk = spk it acts as described in Sig for B against fixed-DDH (including the list additions), except the commitments are always random, and, as above, r is queried to C. San(•, •, •, •, ssk) A sends (m, MOD, σ, pk), B acts as described in the fixed-DDH above, except it must query C to obtain r using "key 0" (i.e., that of the sanitizer), and finally obtains σ . At the end of the experiment, A returns a bit b * , which B forwards to C. We can see that if C's bit b is 1, then in Sa/Si r is signed with ssk R and thus B simulates E 1 , else if b is 0, then r is signed with sk R , and B is simulating H. The probability that B wins is exactly the same as A, which yields our inequality.

In this hybrid, the 2-Ring Signature cannot be of any help to A in the experiment. Next, we argue that

Indeed, if there exists a polynomial-time adversary A able to distinguish between the two experiments with non-negligible probability, we can build an adversary B who wins the Adaptation experiment of the class-equivalence signature scheme S with nonnegligible probability.

Let C be B's challenger. At the beginning of the experiment, C picks a random bit b and generates a signing key pair (pk S , sk S ), which is sent to B. B generates the remaining key pairs to complete (pk, sk) and (spk, ssk) (i.e., the pairs for the 2-Ring Signature, and the pair for the encryption scheme), and forwards pk and spk to A. B also picks a random bit b .

B answers A's queries as follows: Sig(•, sk, •, •, •) on input (m, s pk, ADM, γ), if s pk = spk, B computes the signature normally except it queries C for the class-equivalent signature, as it doesn't know the key. Otherwise, it acts as described in the anon game above, except it can sign r itself, but queries C for the s signature. The lists are handled as before. San(•, •, •, •, ssk) A sends (m, MOD, σ, pk), then if pk = pk it computes the sanitization normally, querying C for the change of representative on s to obtain s , otherwise if pk = pk, it acts as described in the anon game above, except: if σ was output by Sa/Si, it queries C for the signature s , and signs r itself with sk R , and otherwise it queries C for the change of representative on s to get s , and signs r itself with ssk R . The lists are handled as before. Sa/Si(1, pk, spk, sk, ssk, •, •, •): on input (m, ADM, MOD, γ), if ADM(MOD) = 0, B returns ⊥.

Then, B first computes signature σ on m by following the steps of Sig described above, then follows all the steps for San with modification MOD on m for σ, except:

it queries C for a challenge on the class-equivalence signature s , and the 2-Ring Signature r is signed with sk R . B then returns the obtained signature σ . The lists are handled as before. At the end of the experiment, A returns a bit b * , which B forwards to C.