Xavier Bultel

Pascal Lafourcade

Russell W F Lai

Giulio Malavolta

Dominique Schröder

Sri Aravinda

Krishnan Thyagarajan

Efficient Invisible and Unlinkable Sanitizable Signatures

Keywords: SignO, ProveO (pp, pk S, i, pk Z, i

Sanitizable signatures allow designated parties (the sanitizers) to apply arbitrary modifications to some restricted parts of signed messages. A secure scheme should not only be unforgeable, but also protect privacy and hold both the signer and the sanitizer accountable. Two important security properties that are seemingly difficult to achieve simultaneously and efficiently are invisibility and unlinkability. While invisibility ensures that the admissible modifications are hidden from external parties, unlinkability says that sanitized signatures cannot be linked to their sources. Achieving both properties simultaneously is crucial for applications where sensitive personal data is signed with respect to data-dependent admissible modifications. The existence of an efficient construction achieving both properties was recently posed as an open question by Camenisch et al. (PKC'17). In this work, we propose a solution to this problem with a two-step construction. First, we construct (non-accountable) invisible and unlinkable sanitizable signatures from signatures on equivalence classes and other basic primitives. Second, we put forth a generic transformation using verifiable ring signatures to turn any non-accountable sanitizable signature into an accountable one while preserving all other properties. When instantiating in the generic group and random oracle model, the efficiency of our construction is comparable to that of prior constructions, while providing stronger security guarantees.

Introduction

Sanitizable signature schemes introduced by Ateniese et al. [START_REF] Ateniese | Sanitizable signatures[END_REF] are signature schemes that allow a certain degree of controlled malleability: The signer signs messages along with some "admissible modifications" with respect to another party called the sanitizer. The sanitizer can (only) convert a given message-signature pair into one that is admissible. When necessary, the signer can (dis)prove the authorship of a given signature to the public which is modelled by a party called the judge. Over the years, the originally informal security properties [START_REF] Ateniese | Sanitizable signatures[END_REF] were formalized [START_REF] Brzuska | Security of sanitizable signatures revisited[END_REF][START_REF] Brzuska | Unlinkability of sanitizable signatures[END_REF] and strengthened [START_REF] Krenn | Stronger security for sanitizable signatures[END_REF]. Beyond unforgeability, sanitizable signatures provide one with meaningful privacy guarantees, which are important when signing and sanitizing sensitive data. Furthermore, accountability of the signatures prevents the parties from misbehaving as they may eventually get caught. New properties, such as invisibility, were recently proposed [START_REF] Camenisch | Chameleon-hashes with ephemeral trapdoors -and applications to invisible sanitizable signatures[END_REF][START_REF] Beck | Practical strongly invisible and strongly accountable sanitizable signatures[END_REF]. To summarize, we recall the security properties which we consider in this work:

Immutability. The sanitizer cannot modify non-admissible messages.

Accountability. The signer cannot accuse the sanitizer (vice versa) of signing. Transparency. Non-sanitized and sanitized signatures are indistinguishable. Invisibility. The class of admissible modifications are hidden from external parties. Unlinkability. Sanitized signatures cannot be linked to their sources.

Applications. Ateniese et al. [START_REF] Ateniese | Sanitizable signatures[END_REF] suggested a wide range of applications of sanitizable signatures, including multicast transmission, database outsourcing, protecting health information, and secure routing. As an example, we highlight the importance of invisibility and unlinkability of sanitizable signatures for signing medical records. Suppose that a physician signs medical records of patients using a sanitizable signature scheme. The patients can then sanitize the medical record for different purposes. For example, they may 1) remove the personal information and delegate the anonymized record for analysis; 2) remove everything except for the personal information for financing purposes, in such a way that the receivers are convinced of the authenticity of the record. As discussed in [START_REF] Brzuska | Unlinkability of sanitizable signatures[END_REF], unlinkability ensures that colluding receivers cannot reconstruct the full medical records since they cannot link records sanitized from the same source.

However, suppose that the admissible modifications chosen by the physician, are data-dependent. For instance, patients suffering from certain sensitive medical condition that might possibly lead them to be discriminated against, may be allowed to change the fields corresponding to these conditions to NO, while other patients not suffering from any of these conditions are not allowed to change any of the fields to YES. Such a policy of assigning admissible modifications prevents the former patients from facing discrimination when revealing such conditions is not necessary, while preventing the latter patients from getting hold of drugs which are otherwise only issued to patients suffering from those conditions. The security property invisibility is crucial for such a scenario, since the receiver of a sanitized medical record can otherwise easily tell whether the corresponding patient suffers from a sensitive condition by just checking whether changing the corresponding field in the record is modifiable or not.

Open Problem

As discussed above, achieving both unlinkability and invisibility is desirable for certain applications. Obviously, realizing both notions simultaneously is rather easy from a theoretical point of view using common "encrypt and prove" techniques. Although the feasibility is clear, doing so efficiently turns out to be challenging.

One obvious starting point to answer this question is the idea to lift an existing invisible sanitizable signature scheme to an unlinkable one. Following this path does not seem to be fruitful, because existing invisible constructions adopt the "chameleonhash-then-sign" paradigm: The main ingredients in this approach are a signature scheme for which the signer has the secret key, and a chameleon hashing scheme 4 for which the sanitizer has the trapdoor. To sign a message, the signer first splits the message into message blocks, some of which are "admissible", meaning that they are allowed to be changed by the sanitizer, while some are not. The signer then computes the chameleon hashes of the individual message blocks, in such a way that the sanitizer can recover the trapdoors corresponding to the admissible blocks, and sign the hash values. Later, the sanitizer can change the admissible blocks by using the trapdoors to "explain" the hash values with new messages.

Under the "chameleon-hash-then-sign" paradigm, we can see that signatures are inherently linkable. This is because all signatures which are sanitized from a fresh signature contain the same set of hash values. One can of course hide the hash values by using generic non-interactive zero-knowledge arguments, but that would not yield a practical scheme. Therefore, [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] posed the following open problem:

"How to construct (efficient) sanitizable signature schemes which are simultaneously unlinkable and invisible?"

In this work, we answer this question by constructing the first efficient invisible and unlinkable sanitizable signature scheme.

Our Techniques

To solve the problem of constructing an efficient unlinkable and invisible sanitizable signature scheme, we suggest a modular approach visualized with the help of Figure 1. Fig. 1: Outline of our approach.

First, we decouple the problem by presenting a generic transformation that turns any non-accountable sanitizable signature into an accountable one while preserving or upgrading all other properties. Our transformation is very efficient as it only requires a verifiable [START_REF] Lu | Verifiable ring signature[END_REF] ring signature 5 . Recall that a ring signature scheme allows a signer to sign messages on behalf of an ad-hoc group picked during signature generation. Verifiability in this context means that a signer can (dis)prove the authorship of a given signature a posteriori. The basic idea of our transformation is as follows.

To sign (resp. sanitize), the signer (resp. the sanitizer) runs the sign (resp. sanitize) algorithm of the weak sanitizable signature scheme, and signs the whole output (ignoring the underlying structure) with a verifiable ring signature scheme, where the ring is composed by the verification keys of the signer and the sanitizer. The resulting scheme is accountable because the signer can (dis)prove the authorship of a certain signature using the accountability property of the ring signature itself. Our transformation does not only preserve the underlying properties of the (non-accountable) sanitizable signature scheme, but it also strengthens some of them: If the underling scheme is weakly immutable (resp. weakly unlinkable), then the resulting scheme is immutable (resp. unlinkable).

Next, we tackle the main problem of constructing an invisible and unlinkable (nonaccountable) sanitizable signature scheme. The (long-term) public and secret keys of the signer are the verification and signing keys of a certain signature scheme, which we refer to as the outer-layer scheme. To sign a message, the signer splits the message into message blocks, and generates pairs of signing and verification keys of an inner-layer signature scheme. Naturally, the signer signs each message block with the corresponding inner signing key, and signs the verification keys with its (long-term) outer secret key. To allow sanitization, the signer additionally delegates the inner signing keys corresponding to the admissible blocks by encrypting them under the sanitizer public key. Note that all message blocks are treated equally, which is critical for invisibility, except for the generation of the ciphertext. By the semantic security of the encryption scheme, the signature is still invisible to the eyes of an external observer.

To generate signatures for sanitized messages, the sanitizer simply uses the delegated inner signing keys to sign the modified message blocks. However, the resulting sanitized signature is now linkable since the outer signature on the inner verification keys and the keys themselves remain unchanged. To resolve this issue, we need to craft an inner signature scheme with some special properties. Our inner signatures scheme is very similar to the Boneh-Lynn-Shacham (BLS) signature scheme [START_REF] Boneh | Short signatures from the Weil pairing[END_REF] and works as follows:

The public key consists of two group elements (G x 1 , G xy 1 ) and the secret key y ∈ Z q can be used to sign a message m by computing σ := H(m) y ∈ G 2 . The verification is done using the pairing e (G x 1 , σ) = e (G xy 1 , H(m)) . The difference with respect to BLS lies in the extra term of the public key whose role will appear clear in a moment. The property that we need is that the keys and the signatures are publicly re-randomizable, i.e., one can compute consistent scalings of both the signature and the public key

(σ, (G x 1 , G xy 1 )) → (σ, (G x 1 , G xy 1 )) r := σ r , G rx 1 , G rx•y 1 .
It is easy to see that the resulting key-signature pair is still consistent, i.e., the verification checks out. Unfortunately, it turns out that the re-randomization strategy of above is too simplistic and it is prone to mix-and-match attacks. We therefore devise a slightly more sophisticated re-randomization procedure

(σ, (G x 1 , G xy 1 )) → σ s , G rx 1 , G rx•sy 1 .
which scales the two elements of the public keys by two different scalars r and rs respectively. Fortunately, this does not affect the correctness of the scheme. The last obstacle towards decorrelating signed and sanitized signatures is a mechanism to publicly rerandomize the outer signature so that it is consistent with the rerandomized inner verification keys. More concretely, the problem is to rerandomize signatures of (G ) respectively. It turns out that equivalence class signatures (EQS) provide exactly such functionality.

( + 1) Z * q 2 Z * q 1 G1+ G2 2 G1 ( + 5) Z * q + (2 + 11) G1+ ( + 2) G2 2 Z * q + 3 G1

Our Results

To summarize, in this paper we present the following results:

-We present the first efficient sanitizable signature scheme which simultaneously achieves unlinkability and invisibility. This resolves an open problem posed by Camenisch et al. [START_REF] Camenisch | Chameleon-hashes with ephemeral trapdoors -and applications to invisible sanitizable signatures[END_REF]. Our construction is over type-III pairing groups. It uses an equivalence class signature (EQS) scheme, a public-key encryption (PKE) scheme, a hash function (modeled as a random oracle) with images living in G 2 , and a verifiable ring signature (VRS) scheme. We suggest to instantiate our construction with the EQS scheme of Fuchsbauer, Hanser, and Slamanig [START_REF] Fuchsbauer | Structure-preserving signatures on equivalence classes and constant-size anonymous credentials[END_REF], the PKE scheme obtained by applying the Fujisaki-Okamoto transformation [START_REF] Fujisaki | Secure integration of asymmetric and symmetric encryption schemes[END_REF] to the ElGamal encryption scheme [?], and the VRS scheme of Bultel and Lafourcade [START_REF] Bultel | Unlinkable and strongly accountable sanitizable signatures from verifiable ring signatures[END_REF]. The efficiency of such an instantiation is summarized in Table 1 and2. -We construct a weak sanitizable signatures from equivalence class signatures and other basic primitives. The scheme is weak in the sense that it satisfies weak immutability, weak unlinkability, strong proof-restricted transparency 6 , and strong invisibility, but not accountability. -We present a generic transformation from weak sanitizable signatures to fullyfledged sanitizable signatures, using VRS. Fully-fledged sanitizable signatures satisfy immutability, unlinkability, strong proof-restricted transparency, strong invisibility, and strong accountability. The transformation is very efficient as it ignores the structure of the underlying weak sanitizable signature scheme. This allows the future design of sanitizable signatures to focus on achieving other properties while not worrying about accountability.

Related work

An alternative definition of accountability called non-interactive public accountability was given by Brzuska et al. [START_REF] Brzuska | Non-interactive public accountability for sanitizable signatures[END_REF]. This variant of accountability is mutually exclusive with transparency. Several existing works [START_REF] Brzuska | Unlinkability of sanitizable signatures[END_REF][START_REF] Fleischhacker | Efficient unlinkable sanitizable signatures from signatures with rerandomizable keys[END_REF][START_REF] Russell | Efficient sanitizable signatures without random oracles[END_REF][START_REF] Bultel | Unlinkable and strongly accountable sanitizable signatures from verifiable ring signatures[END_REF] proposed schemes that are both transparent and unlinkable. Recently, Krenn et al. [START_REF] Krenn | Stronger security for sanitizable signatures[END_REF] propose the "strong" versions of unforgeability, (non-interactive public) accountability, and transparency. The notion of invisibility dates back to the original work by Ateniese et al. [START_REF] Ateniese | Sanitizable signatures[END_REF], and was formalized by Camenisch et al. [START_REF] Camenisch | Chameleon-hashes with ephemeral trapdoors -and applications to invisible sanitizable signatures[END_REF]. Beck et al. [START_REF] Beck | Practical strongly invisible and strongly accountable sanitizable signatures[END_REF] refined the notion to strong invisibility and proposed a scheme that is both strongly invisible and strongly accountable. Recently Fischlin et al. [START_REF] Fischlin | Invisible sanitizable signatures and public-key encryption are equivalent[END_REF] shows that an invisible (but not unlinkable nor transparent) sanitizable signature scheme can be obtained from any public key encryption scheme.

Miyazaki et al. [START_REF] Miyazaki | Invisibly sanitizable digital signature scheme[END_REF] also considered "invisible sanitizable signatures" which is actually a different primitive known as redactable signatures [START_REF] Derler | A general framework for redactable signatures and new constructions[END_REF] as discussed in [START_REF] Camenisch | Chameleon-hashes with ephemeral trapdoors -and applications to invisible sanitizable signatures[END_REF]. Extensions of sanitizable signatures such as the multi-sanitizer setting [START_REF] Canard | Sanitizable signatures with several signers and sanitizers[END_REF] and a setting where the modification capabilities of the sanitizer are limited [START_REF] Canard | On extended sanitizable signature schemes[END_REF] were considered. Other primitives related to sanitizable signatures include homomorphic signatures [START_REF] Johnson | Homomorphic signature schemes[END_REF][START_REF] Johnson | Homomorphic signatures for digital photographs[END_REF], redactable signatures [START_REF] Derler | A general framework for redactable signatures and new constructions[END_REF][START_REF] Christopher | On updatable redactable signatures[END_REF][START_REF] Brzuska | Redactable signatures for tree-structured data: Definitions and constructions[END_REF], and proxy signatures [START_REF] Wang | Efficient one-time proxy signatures[END_REF][START_REF] Shim | An identity-based proxy signature scheme from pairings[END_REF][START_REF] Okamoto | Extended proxy signatures for smart cards[END_REF].

Preliminaries

Throughout this work we denote by λ ∈ N the security parameter and by poly(λ) any function that is bounded by a polynomial in λ. We denote any function that is negligible in the security parameter by negl(λ). We say that an algorithm is PPT if it is modelled as a probabilistic Turing machine whose running time is bounded by some function poly(λ). Given a set S, we denote by x ← S the sampling of and element uniformly at random from S, and we denote by x ← A(in) the output of the algorithm A on input in. The elements of the set {1, . . . , n} are succinctly represented as [n]. Next we define the necessary notions for understanding our constructions.

Class-Hiding Groups

Let BG := (G 1 , G 2 , G T , g 1 , g 2 , g T , e, q) ← BGGen(1 λ ) be the description of a multiplicative bilinear group of prime order q generated by some efficient PPT algorithm BGGen(1 λ ). Let X = (X 1 , . . . , X ) ∈ G 1 and ρ ∈ Z q . We write X := (X 1 , . . . , X ) ρ := (X ρ 1 , . . . , X ρ ). We then define the equivalence relation

R := {( M , N ) : ∃ > 1, ρ ∈ Z * q s.t. ( M , N ) ∈ G 1 × G 1 ∧ N = M ρ }.
For a vector M ∈ G 1 for some > 1, its equivalence class is defined by

[ M ] R := { N ∈ G 1 : ( M , N ) ∈ R}.
Next we define the notion of class hiding for a relation R, which intuitively says that it should be hard to distinguish elements from the same equivalence class from randomly sampled group elements 7 .

Definition 1 (Class-Hiding). A relation R is said to be class-hiding if for all > 1 and for all PPT adversaries A there exists a negligible function negl(λ) such that

Pr b = b : b ← {0, 1}; BG ← BGGen(1 λ ); (M, M 0 ) ← (G 1 ) 2 ; M 1 ← [M ] R ; b ← A(BG, M, M b ) - 1 2 ≤ negl(λ) .
The following lemma was proven (in different wordings) by Hanser and Slamanig [START_REF] Hanser | Structure-preserving signatures on equivalence classes and their application to anonymous credentials[END_REF]:

Lemma 1 ( [START_REF] Hanser | Structure-preserving signatures on equivalence classes and their application to anonymous credentials[END_REF]). R is class-hiding if and only if the DDH assumption holds in G 1 .

Equivalence Class Signatures

Equivalence class signatures allow users to sign representatives of the equivalence classes defined above, such that a representative and its corresponding signature can be adapted to give a fresh signature of a random representative in the same class. Below, we recall the formal definition of equivalence class signatures [START_REF] Hanser | Structure-preserving signatures on equivalence classes and their application to anonymous credentials[END_REF].

Definition 2 (EQS). An equivalence class signature (EQS) scheme is defined with respect to a bilinear group description BG and a message length > 1. An EQS scheme is a tuple of PPT algorithms (KGen, Sign, ChgRep, Vf, VfKey) defined as follows:

(pk, sk) ← KGen(BG, 1 ): The key generation algorithm inputs a group BG and the message length 1 . It outputs a key pair (pk, sk). We refer the reader to [START_REF] Hanser | Structure-preserving signatures on equivalence classes and their application to anonymous credentials[END_REF] for a formal treatment of correctness. We define existential unforgeability under random message attacks (EUF-CMA) in the following.

Definition 3 (EUF-CMA). An EQS scheme is said to be existentially unforgeable under chosen message attacks (EUF-CMA) if for all > 1, for all n ∈ poly(λ), and for all PPT adversaries A,

Pr   1 = Vf(pk, M * , σ * ) ∧ ∀M ∈ Q : [M ] R = [M * ] R : BG ← BGGen(1 λ ); (pk, sk) ← KGen(BG, 1 ); (M * , σ * ) ← A Sign(sk,•) (pk)   ≤ negl(λ) .
Next we recall the notion of signature adaptation which captures the fact that signatures output by ChgRep are distributed like fresh signatures on the new representative.

Definition 4 (Perfect Signature Adaptation). An EQS scheme is said to perfectly adapt signatures if for all tuples (sk, pk, M , σ, ρ) such that VfKey(pk, sk) = 1, Vf(pk, M , σ) = 1, M ∈ G 1 for some > 1, and ρ ← Z * q it holds that ChgRep(pk, M , σ, ρ) and Sign(sk, M ρ ) are identically distributed.

Verifiable Ring Signatures

Ring Signatures allow users to sign a message anonymously within a group of users, where the group is chosen upon signature creation in an ad-hoc way. Verifiable Ring Signatures (VRS) allow each user of the group to prove a posteriori whether he is the signer of a given message or not. VRS was formally defined and constructed in [START_REF] Lu | Verifiable ring signature[END_REF]. Below, we recall the syntax of VRS.

Definition 5 (Verifiable Ring Signature (VRS)). A Verifiable Ring Signature (VRS) scheme is a tuple of six algorithms VRS = (Setup, KGen, Sign, Verify, Prove, Judge) defined as follows: pp ← Setup(1 λ ): On input the security parameter 1 λ , return the public parameters pp.

(pk, sk) ← KGen(pp): On input the public parameters pp, return a pair of signer public/private keys (pk, sk). (resp. 0) then π proves that σ was (resp. was not) generated by the signer corresponding to the public key pk.

A VRS is required to be (strongly) unforgeable, (strongly) accountable, anonymous, and (strongly) non-seizable. For their formal definitions we refer to Appendix A.2.

Definition of Sanitizable Signatures

In the following we recall the syntax of sanitizable signatures. Let the signer and the sanitizer be denoted by S and Z respectively. Throughout this work we consider messages m = (m 1 , . . . , m ) to be tuples of parts for some > 1, where m k ∈ {0, 1} * for all k ∈ , and represent the admissible modification as a bit string α = α 1 . . . α ∈ {0, 1} . We write α k = 1 if and only if the k-th block is admissible. For ease of exposition, we sometimes write k ∈ α instead of α k = 1.

Let δ be a function which maps a message m to another message m = δ(m). Also, we say that δ is an admissible modification, denoted by α(δ) = 1, if and only if for all messages m and m = δ(m), it holds that m k = m k for all k ∈ α. Definition 6 (Sanitizable Signature Scheme). A sanitizable signature scheme consists of the PPT algorithms (Setup, KGen S , KGen Z , Sign, San, Verify, Prove, Judge). pp ← Setup(1 λ , 1 ): The setup algorithm inputs the security parameter 1 λ and the (maximum) length 1 of the messages and creates a public parameter pp. (pk S , sk S ) ← KGen S (pp): The signer key generation algorithm inputs the public parameter pp and outputs (pk S , sk S ), the public and secret key of the signer respectively. (pk Z , sk Z ) ← KGen Z (pp): The sanitizer key generation algorithm inputs the public parameter pp and outputs (pk Z , sk Z ), the public and secret key of the sanitizer respectively. σ ← Sign(sk S , pk Z , m, α): The signing algorithm inputs a message m ∈ ({0, 1} * ) , a signer private key sk S , a sanitizer public key pk Z , as well as a description α of the admissible modifications to m by the sanitizer and outputs a signature σ. σ ← San(pk S , sk Z , m, δ, σ): The sanitizing algorithm takes as input a message m ∈ ({0, 1} * ) , a description δ of the desired modifications to m, a signature σ, the signer public key pk S , and a sanitizer private key sk Z . It outputs a new signature σ . b ← Verify(pk S , pk Z , m, σ): The verification algorithm inputs a message m, a signature σ, a signer public key pk S , as well as a sanitizer public key pk Z and outputs a bit b. π ← Prove(sk S , pk Z , m, σ): The proof algorithm takes as input a signer private key sk S , a message m, a signature σ, and a sanitizer public key pk Z and outputs a proof π. d ← Judge(pk S , pk Z , m, σ, π): The judge algorithm inputs a message m, a signature σ, signer and sanitizer public keys pk S , pk Z , and proof π. It outputs a decision d ∈ {S, Z} indicating whether the message-signature pair was created by the signer or the sanitizer.

For a sanitizable signature scheme the usual correctness properties should hold, saying that genuinely signed or sanitized messages are accepted and that a genuinely created proof by the signer leads the judge to decide in favor of the signer. For a formal approach to correctness see [START_REF] Brzuska | Security of sanitizable signatures revisited[END_REF].

Unlinkability and Invisibility

In the original definition of unlinkability by Brzuska et al. [START_REF] Brzuska | Unlinkability of sanitizable signatures[END_REF], the property was modeled using an experiment where the adversary gets access to, among other oracles, a "leftor-right sanitize" oracle LoRSanitO, which inputs two message-modification-signature tuples and outputs a sanitized signature produced from one of the tuples. The adversary's task is to decide which tuple is used for the sanitization.

To define LoRSanitO, Brzuska et al. assumed that the description of admissible modifications α can be recovered from a valid signature, so that LoRSanitO can recover the admissible modifications from both input signatures and check whether they are equal. Note that if this check is omitted, then the adversary can trivially decide which signature is used by querying the sanitize oracle SanO on the output of LoRSanitO.

Brzuska et al. did not explicitly state if such recovery can be done publicly or requires a secret key. Indeed, in all existing constructions of unlinkable sanitizable signatures [START_REF] Brzuska | Unlinkability of sanitizable signatures[END_REF], the recovery mechanism is public, which violates invisibility. Therefore, to achieve unlinkability and invisibility simultaneously, we must explicitly state that the admissible modifications can be recovered from a valid signature (hopefully only) with

SignO(pk Z , m, α) σ ← Sign(sk † S , pk Z , m, α) L := L {(pk † S , pk Z , m, α, σ)} return σ ProveO(pk Z , m, σ) if pk Z = pk † Z (m, σ) ∈ Q then return ⊥ / /
Only triggered in transparency experiment.

β := Vf(pk † S , pk Z , m, σ) if β = 0 then return ⊥ π ← Prove(sk † S , pk Z , m, σ) return π SanO (pk S , m, δ, σ) if pk S = pk † S then (m , σ ) ← San(pk S , sk † Z , m, δ, σ) return (m , σ ) elseif ∃α s.t. (m, σ, α) ∈ R ∧ δ ∈ α then (m , σ ) ← San(pk S , sk † Z , m, δ, σ) R ← R {(m , σ , α)} return (m , σ ) endif return ⊥ wLoRSanitO b (i0, δ0, i1, δ1) if L[i0] = ∨ L[i1] = then return ⊥ endif (pk S,0 , pk Z,0 , m0, α0, σ0) := L[i0] (pk S,1 , pk Z,1 , m1, α1, σ1) := L[i1] foreach β ∈ {0, 1} do σ β ← San(pk † S , sk † Z , m β , δ β , σ β ) endfor if α0 = α1 δ0 ∈ α0 ∧ δ1 ∈ α1 δ0(m0) = δ1(m1) then L := L {(pk † S , pk † Z , m b , α b , σ b )} return σ b endif return ⊥ SanO(pk S , m, δ, σ) α ← ExtAdm(pk S , sk † Z , σ) if Verify(pk S , pk † Z , m, σ) = 1 δ ∈ α then σ ← San(pk S , sk † Z , m, δ, σ) L := L {(pk S , pk † Z , δ(m), α, σ )} return σ endif return ⊥ LoRAdmO b (pk Z , m, α0, α1) if |α0| = |α1| = |m| pk Z = pk † Z ∨ α0 = α1 then σ ← Sign(sk † S , pk Z , m, α b ) if pk Z = pk † Z then R := R {(m, σ, α0 • α1)} endif return σ endif return ⊥ Sign/SanO b (m, δ, α) if δ / ∈ α then return ⊥ σ ← Sign(sk † S , pk † S , m, α) σ β ← Sign(sk † S , pk † S , δ(m), α) b = 0 San(pk † S , sk † Z , m, δ, α) b = 1 Q = Q (δ(m), σ ) return σ LoRSanitO b (m0, δ0, σ0, m1, δ1, σ1) b β ← Verify(pk † S , pk † Z , m β , σ β ), ∀β ∈ {0, 1} if b0 = 0 ∨ b1 = 0 then return ⊥ foreach β ∈ {0, 1} do α β ← ExtAdm(pk † S , sk † Z , σ β ) σ β ← San(pk † S , sk † Z , m β , δ β , σ β ) endfor if α0 = α1 δ0 ∈ α0 ∧ δ1 ∈ α1 δ0(m0) = δ1(m1) then L := L {(pk † S , pk † Z , m b , α b , σ b )} return σ b endif return ⊥

Fig. 2: Oracles for Sanitizable Signatures

ExpImmutability A,Π (1 λ ) L := , Q := , pp ← Setup(1 λ ) (pk † S , sk † S ) ← KGen S (pp) (pk * Z , m * , σ * ) ← A SignO,ProveO (pp, pk † S ) parse L as {(pk S,i , pk Z,i , mi, αi, σi)} [|L|] i=1 b0 := Verify(pk † S , pk * Z , m * , σ * ) b1 := ∃i ∈ [|L|], δ ∈ αi s.t. pk * Z = pk Z,i m * = δ(mi) return b0 ∧ ¬b1 w ExpSanAcc A,Π (1 λ ) L := , Q := , pp ← Setup(1 λ ) (pk † S , sk † S ) ← KGen S (pp) (pk [|L|] i=1 b0 := Verify(pk * S , pk † Z , m * , σ * ) b1 := (pk * S , m * , σ * ) / ∈ {(pk S,i , mi, σi)} [|L|] i=1 b2 := (Judge(pk * S , pk † Z , m * , σ * , π * ) = S) return b0 ∧ b1 ∧ b2 ExpTransparency b A,Π (1 λ ) L := , Q := , pp ← Setup(1 λ ) (pk † S , sk † S ) ← KGen S (pp), (pk † Z , sk † Z ) ← KGen Z (pp) O := SignO, SanO, ProveO, Sign/SanO b b ← A O (pp, pk † S , pk † Z ) return b wExpUnlink b A,Π (1 λ ) L := , pp ← Setup(1 λ ) (pk † S , sk † S ) ← KGen S (pp), (pk † Z , sk † Z ) ← KGen Z (pp) O := SignO, SanO, ProveO, wLoRSanitO b b ← A O (pp, pk † S , pk † Z ) return b ExpUnlink b A,Π (1 λ ) L := , pp ← Setup(1 λ ) (pk † S , sk † S ) ← KGen S (pp), (pk † Z , sk † Z ) ← KGen Z (pp) O := SignO, SanO, ProveO, LoRSanitO b b ← A O (pp, pk † S , pk † Z ) return b ExpInvisibility b A,Π (1 λ ) L := , Q := , R := , pp ← Setup(1 λ ) (pk † S , sk † S ) ← KGen S (pp), (pk † Z , sk † Z ) ← KGen Z (pp) O := SanO , ProveO, LoRAdmO b b ← A O (pp, pk † S , pk † Z ) return b
Fig. 3: Security Experiments for Sanitizable Signatures. Oracles are defined in Figure 2. the corresponding sanitizer secret key. We say that a sanitizable signature scheme has privately extractable admissible modifications, if there exists a PPT algorithm ExtAdm which performs the following: α ← ExtAdm(pk S , sk Z , σ): The admissible modifications extraction algorithm inputs a signer public key pk S , a sanitizer secret key sk Z , and a signature. It outputs a description α of the admissible modifications.

In what follows, we only consider sanitizable signature schemes which have privately extractable admissible modifications.

Security of Sanitizable Signatures

We require a sanitizable signature scheme to be immutable, strongly accountable, strongly invisible, strongly proof-restrictedly transparent, and unlinkable. Different variations of these properties were defined in the literature [START_REF] Brzuska | Security of sanitizable signatures revisited[END_REF][START_REF] Brzuska | Unlinkability of sanitizable signatures[END_REF][START_REF] Krenn | Stronger security for sanitizable signatures[END_REF][START_REF] Beck | Practical strongly invisible and strongly accountable sanitizable signatures[END_REF]. We will recall the definitions below for completeness. Additionally, we define the notions of weak immutability and weak unlinkability, which are achieved by our first construction. Our second construction then upgrades these properties to their regular counterparts.

We remark that (strong) unforgeability and privacy were considered in the literature. It is known that (strong) signer accountability and (strong) sanitizer accountability together imply (strong) unforgeability, while (strong) proof-restricted transparency implies proofrestricted privacy [START_REF] Brzuska | Security of sanitizable signatures revisited[END_REF][START_REF] Krenn | Stronger security for sanitizable signatures[END_REF]. Unlinkability is also shown to imply privacy [START_REF] Brzuska | Unlinkability of sanitizable signatures[END_REF]. We therefore do not consider unforgeability and privacy explicitly.

Immutability. Immutability requires that a malicious sanitizer cannot change inadmissible blocks. That is, an adversary should not be able to produce a forgery (pk * Z , m * , σ * ), such that m * cannot be produced by any admissible modifications delegated to pk * Z . Note that the set of admissible modifications of a signature is bound to (the public key of) the sanitizer to which the signature is issued. We also consider a relaxed notion called weak immutability, where a forgery is not considered valid if m * can be produced by a modification which is admissible for some (not necessarily pk * Z ) sanitizers. Definition 7 (Immutability [START_REF] Brzuska | Security of sanitizable signatures revisited[END_REF]). A sanitizable signature scheme Π is said to be immutable if for all PPT adversaries A, the probability that the experiment Pr ExpImmutability A,Π (1 λ ) = 1 ≤ negl (λ) where ExpImmutability A,Π (1 λ ) is defined in Figure 3. Additionally, we say that Π is weakly immutable if, in the experiment wExpImmutability A,Π (1 λ ), the condition pk * Z = pk Z,i in the dashed box is dropped.

Strong Transparency. Transparency means that sanitized signatures look like nonsanitized signatures. Rigorously speaking, transparency cannot be achieved if one is given oracle access to a prove oracle, which distinguishes sanitized signatures from fresh signatures. A relaxed notion, known as proof-restricted transparency is thus considered, which requires that one cannot decide whether a signature is sanitized or fresh, without the help of the prove oracle.

Definition 8 (Strong (Proof-Restricted) Transparency [START_REF] Krenn | Stronger security for sanitizable signatures[END_REF]). A sanitizable signature scheme Π is strongly proof-restrictedly transparent if for all PPT adversaries A,

|Pr ExpTransparency 0 A,Π (1 λ ) = 1 -Pr ExpTransparency 1 A,Π (1 λ ) = 1 | ≤ negl(λ)
where ExpTransparency b A,Π (1 λ ) is defined in Figure 3. If Pr ExpTransparency 0 A,Π (1 λ ) = 1 = Pr ExpTransparency 1 A,Π (1 λ ) = 1 then we say Π is perfectly strongly proof-restrictedly transparent. Furthermore, if the step Q = Q (δ(m), σ ) in the Sign/SanO b oracle (highlighted in the dashed box) is dropped, so that Q remains empty throughout the experiment, then we simply say Π is perfectly strongly transparent.

Strong Accountability. This property demands that the origin of a (possibly sanitized) signature should be undeniable by the signer. Definition 9 (Strong Sanitizer-Accountability [START_REF] Krenn | Stronger security for sanitizable signatures[END_REF]). A sanitizable signature scheme Π is strongly sanitizer-accountable if for all PPT adversaries A,

Pr ExpSanAcc A,Π (1 λ ) = 1 ≤ negl(λ)
where ExpSanAcc A,Π (1 λ ) is defined in Figure 3.

Definition 10 (Strong Signer-Accountability [START_REF] Krenn | Stronger security for sanitizable signatures[END_REF]). A sanitizable signature scheme Π is strongly signer-accountable if for all PPT adversaries A,

Pr ExpSigAcc A,Π (1 λ ) = 1 ≤ negl(λ)
where ExpSigAcc A,Π (1 λ ) is defined in Figure 3.

Invisibility. Invisibility requires that the admissible modifications of a signature are hidden from an external observer.

Definition 11 (Strong Invisibility [START_REF] Beck | Practical strongly invisible and strongly accountable sanitizable signatures[END_REF]). A sanitizable signature scheme Π is strongly invisible if for all PPT adversaries A,

|Pr ExpInvisibility 0 A,Π (1 λ ) = 1 -Pr ExpInvisibility 1 A,Π (1 λ ) = 1 | ≤ negl(λ) where ExpInvisibility b A,Π (1 λ
) is defined in Figure 3.

Unlinkability. Unlinkability means that one cannot decide the source of a given sanitized signature, unless it is revealed trivially by the message. The notion is modeled by considering an experiment where the adversary is given a "left-or-right sanitize" oracle LoRSanitO which, on input two signatures, sanitizes one of them and returns the resulting signature. We also consider a relaxed notion called weak unlinkability, where the adversary is only allowed to query LoRSanitO on honestly generated signatures.

Definition 12 (Weak Unlinkability). A sanitizable signature scheme SS is weakly unlinkable if for all PPT adversaries A,

|Pr wExpUnlink 0 A,SS (1 λ ) = 1 -Pr wExpUnlink 1 A,SS (1 λ ) = 1 | ≤ negl(λ) where wExpUnlink b A,SS (1 λ
) is defined in Figure 3. Definition 13 (Unlinkability [START_REF] Brzuska | Security of sanitizable signatures revisited[END_REF]). A sanitizable signature scheme SS is unlinkable if for all PPT adversaries A,

|Pr ExpUnlink 0 A,SS (1 λ ) = 1 -Pr ExpUnlink 1 A,SS (1 λ ) = 1 | ≤ negl(λ) where ExpUnlink b A,SS (1 λ
) is defined in Figure 3.

Construction

We propose a two-step construction of sanitizable signatures with immutability, strong accountability, strong proof-restricted transparency, strong invisibility, and unlinkability.

In the first step, using equivalence class signatures and other basic primitives, we construct a scheme with weak immutability, perfect strong transparency, strong invisibility, and weak unlinkability. This scheme does not achieve accountability. Next, we show how one can transform any schemes with these properties one with all desirable properties, using verifiable ring signatures.

Construction I: Achieving Unlinkability and Invisibility

Let > 1 be an integer. Let EQS be an equivalence class signature scheme, H : {0, 1} * → G 2 be a hash function (to be modeled as a random oracle), and PKE be a public-key encryption scheme. We present in Figure 4 a construction of sanitizable signatures Π 1 . The construction satisfies weak immutability, strong invisibility, perfect strong transparency, and weak unlinkability, but not accountability.

Informally, the signer issues signatures as follows. On input a message m = m 1 . . . m , the signer samples fresh BLS-like public and secret keys, which are used to sign the messages. Concretely, the i-th public key consists of a tuple

(X i , Y i ) ∈ G 2 1 with Y i = X yi
i for some y i ∈ Z q , and the secret key is y i . It then signs the vectors X = (X 1 , . . . , X ) and Ȳ = (Y 1 , . . . , Y ) using EQS. Next, in the same way as in [START_REF] Beck | Practical strongly invisible and strongly accountable sanitizable signatures[END_REF], it encrypts the BLS-like secret keys y i corresponding to the admissible message blocks using the PKE public key of the sanitizer. Finally, it outputs the signature which consists of two EQS signatures, BLS-like signatures and public keys, and a PKE ciphertext.

To sanitize, the sanitizer decrypts the PKE ciphertext and obtains the BLS-like secret keys corresponding to the admissible blocks, which are then used to sign the corresponding modified messages. Using the homomorphic property of the BLS-like scheme, the sanitizer can rerandomize X and Ȳ to Xr and Ȳ r•s respectively, and rerandomize the signatures accordingly so that they are compatible with the new public keys. Using the signature adaptation properties of EQS, it can also obtain fresh-looking EQS signatures on Xr and Ȳ r•s respectively. Finally, the sanitizer re-encrypts the new BLS-like secret keys, and outputs the signature.

Since we do not aim to provide accountability, the prove algorithm always returns the empty string and the judge algorithm always outputs S. The correctness of Π 1 follows trivially from the correctness of the building blocks. Below, we state our main theorem and we defer its proof to Section 5.

Theorem 1. Let q > 2 λ . If EQS is EUF-CMA-secure, then Π 1 is weakly immutable in the generic group and random oracle model. If PKE is IND-CCA-secure, then Π 1 is strongly invisible. If EQS perfectly adapts signatures, then Π 1 is perfectly strongly transparent (and hence also perfectly strongly proof-restrictedly transparent). If the equivalence relation R is class-hiding, EQS perfectly adapt signatures, and PKE is correct and is IND-CCA-secure, then Π 1 is weakly unlinkable in the generic group random oracle model.

Finally, we remark that it is trivial to extend the construction to the multi-sanitizer setting by encrypting the (possibly different subsets of) BLS-like keys for different sanitizers.

Setup(1 λ , 1 ) (G1, G2, GT , G1, G2, GT , e, q) ← BGGen(1 λ ) BG := (G1, G2, GT , G1, G2, GT , e, q) return pp := (BG, 1 λ , 1 ) KGen S (pp) return (pk S , sk S ) ← EQS.KGen(BG, 1 )

KGen Z (pp) return (pk Z , sk Z ) ← PKE.KGen(1 λ ) Sign(sk S , pk Z , m, α) if |α| = then return ⊥ xi, yi ← Z * q , ∀i ∈ [ ] Xi := G x i 1 , Yi := X y i i , ∀i ∈ [ ] µ ← EQS.Sign(sk S , (X1, . . . , X )) η ← EQS.Sign(sk S , (Y1, . . . , Y )) σi := H(i mi) y i , ∀i ∈ [ ] ζi := yi i ∈ α 0 otherwise , ∀i ∈ [ ]
foreach i ∈ [ ] do ζ i := s • ζi σ i := H(i m i ) ζ i i ∈ α σ s i otherwise endfor c ← PKE.Enc(pk Z , (α, {ζ i } i∈[ ] )) σ := (µ , η , {σ i , X i , Y i } i=1 ,
return Z b = 0 S b = 1 Π2.ExtAdm(pk S , sk Z , σ) α ← Π1.ExtAdm(spk S , ssk Z , σ SS ) return α
Fig. 5: Generic Transformation from Weak to Fully-Fledged Sanitizable Signatures.

Construction II: Generic Transformation for Accountability

In this section, we show a generic transformation (Figure 5), from any weakly immutable, non-accountable, strongly invisible, strongly proof-restricted transparent, and weakly unlinkable schemes Π 1 , to an immutable, strongly accountable, strongly invisible, strongly proof-restricted transparent, and unlinkable scheme Π 2 , using a verifiable ring signature scheme VRS.

An overview of the transform follows. The signer signs the public key of the sanitizer and the message in σ SS using Π 1 , then signs σ SS in σ VRS using VRS, where the ring contains the public key of the signer and the public key of the sanitizer. The signer outputs the signature σ = (σ SS , σ VRS ). To sanitize, the sanitizer sanitizes σ SS using Π 1 to produce σ SS , then signs σ SS in σ VRS using VRS. The sanitized signature is σ = (σ SS , σ VRS ). To verify any signature σ = (σ SS , σ VRS ), the verifier uses the verification algorithm of Π 1 on σ SS and the verification algorithm of VRS on σ VRS . To prove that a signature σ = (σ SS , σ VRS ) is sanitized, the signer proves that he did not generate σ VRS using the prove algorithm of VRS, which gives accountability.

Next, we sketch why the other security properties are preserved. For conciseness, we omit the qualitative attributes such as strong and proof-restricted in the following discussion. First, since Π 1 is weakly immutable, the sanitizer is not able to forge the part σ SS of a sanitized signature for a non-admissible message nor changing the sanitizer public key (which is signed as a message of Π 1 ). This implies that the resulting scheme is immutable. Next, since Π 1 is transparent, one cannot guess whether a signature is sanitized or not from the part σ SS . On the other hand, since VRS is anonymous, one cannot guess whether the part σ VRS was created by the signer or by the sanitizer. Combining both properties, we conclude that one cannot guess whether the signature was sanitized or not, i.e., Π 2 is transparent. Thirdly, Π 1 is invisible, so the part σ SS hides all information about the possible modifications of the message. Moreover, The signature σ VRS contains no information about the modifiable parts of the message. This implies that Π 2 is invisible. Finally, Π 1 is unlinkable, so the first part σ SS of a sanitized signature hides any information about the original signature, and the second part σ VRS does not depend on the original signature, so our resulting scheme Π 2 is also unlinkable. Note that Π 1 is weakly unlinkable in the sense that it is no longer secure if the adversary is allowed to send fresh signatures to the oracle LoRSanitO. This does not impact the security of Π 2 , because σ SS is signed in σ VRS , so to produce a fresh signature (σ SS , σ VRS ), the adversary should be able to forge σ VRS , which is supposed to be hard under the hypothesis that the VRS scheme is unforgeable.

The correctness of Π 2 follows trivially from the correctness of Π 1 and VRS. Below, we state the formal security results for the construction. Due to space constraints, we refer to Appendix B for the formal security proofs. Theorem 2. If Π 1 is weakly immutable, then Π 2 is immutable. If Π 1 is weakly unlinkable, and VRS is strongly unforgeable, then Π 2 is unlinkable. If Π 1 is strongly invisible then Π 2 is strongly invisible. If VRS is strongly accountable, then Π 2 is strongly signer accountable. If VRS is strongly non-seizable, then Π 2 is strongly sanitizer accountable. If VRS is anonymous and Π 1 is strongly proof-restrictedly transparent, then Π 2 is strongly proof-restrictedly transparent.

We remark that verifiable ring signatures can be constructed generically from linkable ring signatures [START_REF] Liu | Linkable spontaneous anonymous group signature for ad hoc groups (extended abstract)[END_REF], which in turn can be generically constructed from unique ring signatures [START_REF] Franklin | A framework for unique ring signatures[END_REF]. It is also possible to use any stronger primitive such as traceable [START_REF] Fujisaki | Traceable ring signature[END_REF] or accountable [START_REF] Xu | Accountable ring signatures: A smart card approach[END_REF] ring signatures, as long as the signers are accountable. Furthermore, the transform can be easily extended to a multi-sanitizer setting by signing with respect to a ring which consists of the signer and multiple sanitizers. Depending on the variant of ring signatures used, we obtain different flavors of accountability. As the implications are straightforward, we do not elaborate further.

Security Proof for Construction I

The following proof uses the generic group model abstraction of Shoup [?] and we refer the reader to [?] for a comprehensive introduction to the bilinear group model. Here we state the central lemma useful for proving facts about generic attackers.

Lemma 2 Let F (X 1 , . . . , X m ) be a non-zero polynomial of degree d ≥ 0 over a field F. Then the probability that F (x 1 , . . . , x m ) = 0 for randomly chosen values (x 1 , . . . , x m ) in F n is bounded from above by d |F| .

Weak Immutability

Proof (Weak Immutability). To prove that Π 1 is weakly immutable, we first show the generic hardness of the following problem.

Lemma 3. Let (G 1 , G 2 , G T , G 1 , G 2 , G
T , e, q) ← BGGen(1 λ ) with q > 2 λ , and a, b, c ← Z q . For all generic group adversary A, the probability that A on input

(G 1 , G a 1 , G b 1 , G 2 , G b 2 , G c 2 ) outputs (G u 1 , G v 1 , G x 1 , G y 1 , G z 2 ) such that          au -x = 0 bv -y = 0 cy -xz = 0 v = 0 is negligible. Proof. Let (G u 1 , G v 1 , G x 1 , G y 1 , G z 2 ) be the output of A. Since A is generic, it holds that u = u 1 + u a a + u b b v = v 1 + v a a + v b b x = x 1 + x a a + x b b y = y 1 + y a a + y b b z = z 1 + z b b + z c c for some coefficients u 1 , u a , u b , v 1 , v a , v b , x 1 , x a , x b , y 1 , y a , y b , z 1 , z b , z c ∈ Z q . By the relation au -x = 0, we have -x 1 + (u 1 -x a )a -x b b + u a a 2 + u b ab = 0. Note that f (A, B) := -x 1 + (u 1 -x a )A -x b B + u a A 2 + u b AB
is a quadratic polynomial in the variables A and B. Suppose f is not a zero polynomial, by the Schwartz-Zippel lemma (Lemma 2), for a, b ← Z q , the probability that f (a, b) = 0 is upper bounded by 2/q < 2 1-λ which is negligible. Therefore we can assume that f is always zero.

In particular, we have x 1 = x b = 0. Similarly, by examining the relation bv -y = 0, we can assume that v 1 = y b , and y 1 = y a = 0. We can therefore write x = x a a and y = y b b. Next, we examine the relation cy -xz = 0, which implies

y b bc -x a z 1 a -x a z b ab -x a z c ac = 0.
Using the Schwartz-Zippel lemma again, we can assume that y b = 0. However, this means that v = v 1 = y b = 0, which contradicts with the fourth relation v = 0. Now, suppose there exists a generic group adversary A against the weak immutability of Π 1 . We construct a generic group adversary C which solves the problem defined in Lemma 3. C receives as challenge

(G 1 , G a 1 , G b 1 , G 2 , G c
2 ) from its challenger. It then simulates the ExpImmutability experiment for A by setting the public parameters and the signer keys honestly. Without loss of generality, assume that A makes Q 1 = poly(λ) signing oracle queries and Q 2 = poly(λ) random oracle queries for H(). C additionally samples i † , j † ← [Q 1 ] as a guess of which Sign oracle query A will attack against, k † ← [ ] as the index of the inadmissible block that will be modified in the forgery message, l † ← [Q 2 ] as a guess of which H() oracle query A will include as the inadmissible modification in the forgery message.

Answering Random Oracle Queries Upon receiving (k l , m l ) as the l-th distinct query to the H() oracle, if l = l † , C answers the query by picking t l ← Z * q and return h

l := G t l 2 ∈ G 2 to A. If l = l † , then C sets h l = G c
2 where G c 2 was received as a challenge as described above. If (k l , m l ) was a message that was queried previously, then reply with the same response as before.

Answering Sign Oracle Queries Upon receiving (pk Z,, m i , α i ) as the i-th query to the SignO oracle, if i = i † and i = j † , C answers the query honestly by running the procedures as defined in the SignO oracle.

In the case i = i † or i = j † , C generates the signature honestly except for the following changes:

1. If i = i † , then C picks the elements X i † ,1 , . . . , X i † , as follows. C picks X i † ,k † = G a 1
which it had received from its challenger in the beginning. For all other k ∈ [ ]\{k † }, C generates the X k honestly by picking

x i † ,k ← Z * q and setting X i † ,k = G x i † ,k 1
(as done in the SignO oracle). The rest of the signature is generated as in the SignO oracle.

Suppose

i = j † . If k † ∈ α j † , or (k † , m j † ,k † ) = (k l † , m l † ), then abort. Otherwise, let t † be such that H(k † m j † ,k † ) = G t † 2 . C first generates X i † ,1 , . . . , X i † , by picking x j † ,k ← Z * q and setting X j † ,k := G x j † ,k 1 for all k ∈ [ ]. Then C picks the elements Y i † ,1 , . . . , Y i † , as follows. C picks Y j † ,k † = G b
1 which it had received from its challenger in the beginning. It then generates

σ j † ,k † as (G b 2 ) t † x j † ,k † . For all other k = k † , C generates the Y j † ,
k and the rest of the signature honestly as done in the SignO oracle. Note that as we assume k † / ∈ α j † in this case, the value y j † ,k † is not needed to generate the signature. Therefore the signature can be simulated faithfully.

Answering Prove Oracle Queries. The Prove oracle is trivially simulatable since the Prove algorithm always returns .

Clearly, assuming that C did not abort, C simulates the wExpImmutability experiment for A faithfully. Eventually, A outputs (pk * Z , m * , σ * ) as a forgery such that

Verify(pk † S , pk * Z , m * , σ * ) = 1, and m * k = m i,k for some i, k such that k / ∈ α i . Since Q 1 , ∈ poly (λ), with non-negligible probability it holds that m * k † = m j † ,k † and k † / ∈ α j † . Moreover, since Q 2 ∈ poly (λ), with non-negligible probability it holds that (k † , m * k † ) = (k l † , m l † ).
If that is the case, then the abort conditions in the above procedures of answering sign oracle queries are never triggered.

Parse σ * as (µ * , η * , {σ * j , X * j , Y * j } j=1 , c * ). By the EUF-CMA-security of EQS, with overwhelming probability we have that

[X * 1 , . . . , X * ] R = [X i * ,1 , . . . , X i * , ] R for some i * , and [Y * 1 , . . . , Y * ] R = [Y j * ,1 , . . . , Y * j * , ]
R for some j * (otherwise we can construct an adversary against the EUF-CMA-security of EQS by simply outputting µ or η). Therefore, there exists r, s ∈ Z q such that (X i * ,1 , . . . , X i * , ) r = (X * 1 , . . . , X * ) and

(Y j * ,1 , . . . , Y * j * , ) r•s = (Y * 1 , . . . , Y * ). Since Q 1 ∈ poly (λ), it happens with non-negligible probability that (i † , j † ) = (i * , j * ). Suppose this is the case. Let k be arbitrary with k = k † . C extracts G r 1 and G rs 1 by computing (X * k ) 1 x i * ,k = G r•(x i * ,k )• 1 x i * ,k 1 = G r 1 (Y * k ) 1 ( x j * ,k ) • ( y j * ,k ) = (G r•s 1 ) ( x j * ,k ) • ( y j * ,k ) ( x j * ,k ) • ( y j * ,k ) = G r•s 1 . Since Verify(pk S , pk * Z , m * , σ * ) = 1, this implies that Y * k † = G r•s•b 1 = G 1 . This means that r • s = 0. Furthermore, we have e(X * k † , σ * k † ) = e(Y * k † , H(k † m * k † )) e(X r i † ,k † , σ * k † ) = e(Y r•s j † ,k † , G c 2 ) e(G r•a 1 , σ * k † ) = e(G r•s•b 1 , G c 2 ) σ * k † = G s•b•c a 2 Now, set C outputs (G u 1 , G v 1 , G x 1 , G y 1 , G z 2 ) := (G r 1 , G r•s 1 , G r•a 1 , G r•s•b 1 , G s•b•c a 2
). By a routine calculation, one can verify that au-x = 0, bv-y = 0, cy-xz = 0 and v = 0. Since A only performs generic group operations, so does C, which contradicts with Lemma 3.

Strong Invisibility

Proof (Strong Invisibility). We prove strong invisibility by hybrid argument. We define an intermediate experiment Hyb b which is identical to ExpInvisibility b A,Π (1 λ ) for both b ∈ {0, 1}, except for the following changes: When answering LoRAdmO b oracle queries, the challenger signs with respect to the policy α 0 • α 1 instead of α b . We argue that, in the view of the adversary, the experiments Hyb b and ExpInvisibility b A,Π (1 λ ) are computationally indistinguishable for b ∈ {0, 1}. Suppose that is the case, since obviously Hyb 0 is functionally equivalent to Hyb 1 , it holds that ExpInvisibility 0

A,Π (1 λ ) is computationally indistinguishable to ExpInvisibility 1 A,Π (1 λ ).
Before proving the claim above, we state two key observations. First, note that the signatures returned by the LoRAdmO b oracle in the all experiments are identically distributed if pk Z = pk † Z (since now it must hold that α 0 = α 1 for the oracle to not abort). In the case pk Z = pk † Z , the signatures returned by the oracle are almost identically distributed, except for the ciphertext c. In particular, in the experiment ExpInvisibility b A,Π (1 λ ), the ciphertext is an encryption of the message (α b , {ζ b,i } i=0 ), where ζ b,i = x i for all i ∈ α b , and is zero otherwise. On the other hand, in Hyb b , the ciphertext is an encryption of the message Let (pk Z , m j , α j,0 , α j,1 ) be thej-th query to the LoRAdmO b oracle. C answers the query honestly if pk Z = pk † Z . In the case where pk Z = pk † Z , C generates the ciphertext c j in the following way. It samples y j,i ←$ Z * q for all i ∈ [ ], and prepares

(α 0 • α 1 , {ζ b,i } i=0 ), where ζ b,i = x i for all i ∈ α 0 • α 1 ,
ζ b,j,i := y j,i i ∈ α j,b 0 otherwise , ∀i ∈ [ ] τ b,j :=(α j,b , {ζ b,j,i } i=1 ) ζ b,j,i := y j,i i ∈ α j,0 • α j,1 0 otherwise , ∀i ∈ [ ] τ b,j :=(α j,0 • α j,1 , {ζ b,j,i } i=1
) and queries the EncO b oracle provided by the IND-CCA challenger on (τ b,j , τ b,j ) and receive c j . C generates the rest of the signature honestly.

Upon receiving a query (pk S , m, δ, σ) to the SanO oracle, C parses σ as (µ, η, {σ i , X i , Y i } i=1 , c) and checks if c = c j for some j. If so, it uses {y j,i } i∈αj,0∩αj,1 to answer the oracle query. If not, it queries the DecO oracle provided by the IND-CCA challenger on c, receives τ = (α, {ζ i } i∈ ), and uses it to answer the oracle query.

Clearly, depending on the choice of the IND-CCA challenger, our adversary simulates either the experiment ExpsInvis b Π,A (1 λ ) or Hyb b faithfully. Therefore, if there exists a distinguisher which distinguishes the two experiments with a certain probability, then our adversary can guess the choice of the IND-CCA challenger with the same probability.

Perfect Strong Transparency

Proof (Perfect Strong Transparency). We show that the construction is perfectly strongly transparent through hybrid argument. First, observe that the Prove algorithm, and hence also the ProveO oracle, always returns the empty string , it is safe to drop the step Q = Q (δ(m), σ ) in the Sign/SanO b oracle. Now, let Q = poly (λ) be the number of queries that the adversary A make to the Sign/SanO b oracle. We define the hybrids Hyb 0 , . . . , Hyb q as follows. The hybrid Hyb 0 is identical to ExpTrans 0 Π,A (1 λ ). For j ∈ [Q], Hyb j is almost identical to Hyb j-1 , except that in the former the j-th query to the Sign/SanO b is answered as in ExpTrans 1 Π,A (1 λ ). That is, the first j signatures returned by Sign/SanO b are sanitized, while the last Q -j signatures are freshly signed. Note that

Hyb Q is identical to ExpTrans 1 Π,A (1 λ ). Obviously, if Pr Hyb j-1 = 1 = Pr Hyb j = 1 for all j ∈ [Q], then Pr ExpTrans 0 Π,A (1 λ ) = 1 = Pr ExpTrans 1 Π,A (1 λ ) = 1 . Fix j ∈ [Q].
In the following, we show that Pr Hyb j-1 = 1 = Pr Hyb j = 1 . Let (m, δ, α) be the j-th query of A to the Sign/SanO b oracle. If δ / ∈ α, then the oracle returns ⊥ in both experiments and thus the equality holds trivially. Otherwise, let m := δ(m), and let σ be the response. In Hyb j-1 , the signature σ is drawn from a distribution D where

D :=                              σ : x i , y i ← Z * q , X i := G xi 1 , Y i := X yi i , ∀i ∈ [ ] µ ← EQS.Sign(sk † S , (X 1 , . . . , X )) η ← EQS.Sign(sk † S , (Y 1 , . . . , Y )) σ i ← H(i m i ) yi , ∀i ∈ [ ] ζ i := y i i ∈ α 0 otherwise , ∀i ∈ [0, ] τ := (α, {ζ i } i∈[ ] ) c ← PKE.Enc(pk † Z , τ ) σ := (µ, η, {σ i , X i , Y i } i=1 , c)                              .
Replacing x i and y i with r • x i and s • y i respectively for some r, s ← Z * q , we obtain a distribution D = D where

D :=                                  σ : r, s ← Z * q x i , y i ← Z * q , X i := G xi 1 , Y i := X yi i , ∀i ∈ [ ] µ ← EQS.Sign(sk † S , (X 1 , . . . , X ) r ) η ← EQS.Sign(sk † S , (Y 1 , . . . , Y ) r•s ) σ i ← H(i m i ) s•yi , ∀i ∈ [ ] ζ i := s • y i i ∈ α 0 otherwise , ∀i ∈ [ ] τ := (α, {ζ i } i∈[ ] ) c ← PKE.Enc(pk † Z , τ ) σ := (µ, η, {σ i , X r i , Y r•s i } i=1 , c)                                 
.

By the perfect adaption of EQS, the distribution of EQS.Sign(sk

D :=                                            σ : r, s ← Z * q x i , y i ← Z * q , X i := G xi 1 , Y i := X yi i , ∀i ∈ [ ] µ ← EQS.Sign(sk † S , (X 1 , . . . , X )) η ← EQS.Sign(sk † S , (Y 1 , . . . , Y )) µ ← ChgRep(pk † S , (X 1 , . . . , X ), µ , r) η ← ChgRep(pk † S , (Y 1 , . . . , Y ), η , r • s) σ i ← H(i m i ) s•yi , ∀i ∈ [ ] ζ i := s • y i i ∈ α 0 otherwise , ∀i ∈ [ ] τ := (α, {ζ i } i∈[ ] ) c ← PKE.Enc(pk † Z , τ ) σ := (µ, η, {σ i , X r i , Y r•s i } i=1 , c)                                            .
Note that in Hyb j , the signature σ is drawn exactly from D . Therefore we can conclude that Hyb j-1 and Hyb j are functionally equivalent. Therefore if the tuple (X 1 , . . . , X ) has the same distribution in both experiments the indistinguishability follows. It remains to show that

G 1 , X 1 , . . . , X Z 1 , . . . , Z ≈ G 1 , X 1 , . . . , X X r 1 , . . . , X r
over the random choice of (Z 1 , . . . , Z , r). It is easy to show that the two distributions are indistinguishable by the hardness of the decisional Diffie-Hellman problem [?]. For completeness, and as a warm-up for the proof of the next lemma, we show that this holds in the generic group model. For ease of exposition, we denote symbolically

X k := G x k 1 and Z k := G z k 1 for all k ∈ [ ].
For the left distribution we can rewrite all equations that the adversary learns as symbolic degree 1 polynomials

x 1 x 1 + . . . + x x + z 1 z 1 + . . . + z z + c = 0
for some coefficients (x 1 , . . . , x , z 1 , . . . , z , c). For the right distributions we have

x 1 x 1 + . . . + x x + z 1 x 1 r + . . . + z x r + c = 0.
Since (x 1 , . . . , x ) and (z 1 , . . . , z ) are uniformly chosen, by Lemma 2 all coefficients in the left distribution must be 0 with all but negligible probability. The same holds for the right distribution, since r is uniformly sampled. It follows that a generic adversary cannot learn any non-trivial relation when it is given either the left or the right distribution. Therefore the left and right distributions look identical. 2 respectively, where (t 0 1 , t 1 1 , . . . , t 0 , t 1 ) is a randomly sampled vector in Z 2 q . The indistinguishability of the two hybrids reduces to arguing about the proximity of the following distributions

            G 1 , G y1 1 , . . . , G y 1 , G z1 1 , . . . , G z 1 , G sy1z1 1 , . . . , G sy z 1 , G 2 , G t 0 1 y1 2 , . . . , G t 0 y 2 , G st 1 1 y1 2 , . . . , G st 1 y 2 , G t 0 1 2 , . . . , G t 0 2 , G t 1 1 2 , . . . , G t 1 2             ≈             G 1 , G y1 1 , . . . , G y 1 , G z1 1 , . . . , G z 1 , G w1z1 1 , . . . , G w z 1 , G 2 , G t 0 1 y1 2 , . . . , G t 0 y 2 , G t 1 1 w1 2 , . . . , G t 1 w 2 , G t 0 1 2 , . . . , G t 0 2 , G t 1 1 2 , . . . , G t 1 2            
where the LHS corresponds to the distributions in Hyb b 4 and the RHS corresponds to the distributions in Hyb b 5 . Note that all non-trivial relations that the generic attacker can learn are restricted to certain polynomials of degree at most 2. For illustration, we can symbolically write the relations obtained from the RHS as

i∈[ ],j∈[ ] a i,j t 1 i w i • w j z j + i∈[ ],j∈[ ] b i,j t 1 i w i • y j + i∈[ ],j∈[ ] c i,j t 0 i y i • w j z j + i∈[ ],j∈[ ] d i,j t 0 i y i • y j + i∈[ ],j∈[ ],b∈{0,1} e b i,j t b i • w j z j + i∈[ ],j∈[ ],b∈{0,1} f b i,j t b i • y j + i∈[ ],j∈[ ] g i,j t 1 i w i • z j + i∈[ ] h i t 1 i w i + i∈[ ],j∈[ ] i i,j t 0 1 y i • z j + i∈[ ] j i t 0 1 y i + i∈[ ],j∈[ ],b∈{0,1} k b i,j t b i • z j + i∈[ ],b∈{0,1} l b i t b i + i∈[ ] m i (y i ) + i∈[ ] n i (z i ) + i∈[ ] o i (w i z i ) +p = 0.
whereas for the LHS the equation is identical except that all occurrences of w i and w j are replaced with y i • s and y j • s, respectively. Since all variables are uniformly distributed, by Lemma 2 we have that the coefficient of each unique monomial must be 0 with all but negligible probability. It is left to argue that each non-trivial relation obtained on the RHS imply also a corresponding non-trivial relation on the LHS, and viceversa. By inspection we isolate the pairs

  i∈[ ],j∈[ ],b∈{0,1} e b i,j t b i • w j z j , i∈[ ],j∈[ ] g i,j t 1 i w i • z j   and   i∈[ ],j∈[ ],b∈{0,1} f b i,j t b i • y j , i∈[ ] j i (t 0 i y i )  
that have potentially common monomials. For the latter case it is enough to observe that the monomials are identical for both the LHS and the RHS distributions as they are independent of w i and s for all

i ∈ [ ]. Therefore if i∈[ ],j∈[ ],b∈{0,1} f i,j (t b i • y j ) + i∈[ ] j i (t 0 i y i ) = 0
in the RHS then so it does in the LHS, and vice versa. For the former case we have that collisions occur only when i = j and b = 1, as otherwise the monomials are distinct and therefore any non trivial set of coefficients will not cancel out (with very high probability). Setting i = j and b = 1, for the RHS we have the following constraint

i∈[ ] e 1 i,i t 1 i w i z i + i∈[ ] g i,i t 1 i w i z i = 0
which implies that, with overwhelming probability, for all i ∈ [ ] it holds that e 1 i,i = -g i,i . Applying this constraint to the LHS we obtain a corresponding non-trivial relation

i∈[ ] e 1 i,i st 1 i y i z i + i∈[ ] g i,i st 1 i y i z i = 0.
The reverse direction holds with an identical argument. Since there is a bijection between the non-trivial relations on the LHS and those on the RHS, we can conclude that the view of A in the two cases are indistinguishable.

, pk * Z m * , σ * SS ). Parse L as {(pk S,i , pk Z,i , m i , α i , σ i )} [|L|]
i=1 . Assume that ExpImmutability A,Π2 (1 λ ) returns 1, then the following holds:

-Π 2 .Verify(pk † S , pk * Z , m * , σ * ) = 1 -For all i ∈ [|L|], pk * Z = pk Z,i ∨ m * / ∈ {δ(m i ) | δ with α i (δ) = 1 }.
The first condition implies that Π 1 .Verify(spk † S , spk * Z , pk * Z m * , σ * SS ) = 1. For the second condition, recall that given any δ i , δ i is defined so that δ

i (pk Z,i m i ) := pk Z,i δ i (m i ). Therefore if pk * Z = pk Z,i or m * / ∈ {δ(m i ) | δ with α i (δ) = 1 } , then pk * Z m * / ∈ δ (pk Z,i m i ) | δ with α i (δ ) = 1 .
We therefore conclude that ExpImmutability B,Π1 (1 λ ) = 1. To summarize, if ExpImmutability A,Π2 (1 λ ) returns 1 with non-negligible probability, then wExpImmutability B,Π1 (1 λ ) also returns 1 with non-negligible probability, which contradicts that Π 1 is weakly immutable.

B.2 Unlinkability

Proof (Unlinkability). We define the following sequence of hybrid experiments:

Hyb b 0 : is identical to ExpUnlink b A,Π2 (1 λ ). Hyb b 1 : is identical to Hyb b 0 except for the following change. Let (m 0 , δ 0 , σ 0 , m 1 , δ 1 , σ 1 ) be a query from A to LoRSanitO b . Suppose that Π 2 .Vf(pk † S , pk † Z , m β , σ β ) = 1 for all β ∈ {0, 1}. Then if for some β ∈ {0, 1}, there is no α β which satisfies (pk † S , pk † Z , m β , α β , σ SS,β ) ∈ L, the challenger aborts. Lemma 9.
If VRS is strongly unforgeable, then the probability of the challenger aborting is negligible, which implies

Pr Hyb b 0 = 1 -Pr Hyb b 1 = 1 ≤ negl(λ) .
Proof. Suppose that there exists a polynomial time adversary A that forces the challenger to abort in Hyb b 1 with non negligible probability, we show how to build a polynomial time adversary B that breaks the unforgeability of the VRS scheme with non-negligible probability. B receives the set of public keys {vpk ‡ S , vsk Answering LoRSanitO b Queries. Let (m 0 , δ 0 , σ 0 , m 1 , δ 1 , σ 1 ) be a query from A. Suppose that Π 2 .Vf(pk † S , pk † Z , m β , σ β ) = 1 for all β ∈ {0, 1} (otherwise the oracle outputs ⊥). This implies that VRS.Verify({vpk Z , vpk S }, pk † S pk † Z m β σ SS,β , σ VRS,β ) = 1. Suppose further that for some β ∈ {0, 1}, there is no α β which satisfies ). Clearly, if B aborts and returns a forgery, then it breaks the strong unforgeability of VRS. We can therefore assume that B does not abort with overwhelming probability, which implies our claim. Answering SanO Queries. On input (pk S , m, δ, σ), it parses pk S as (spk S , vpk S ) and σ as (σ SS , σ VRS ) and sets m := pk † Z m and δ such that δ (m ) = pk † Z δ(m). B generates σ SS by calling Π 1 .SanO on (spk S , pk † Z m , δ , σ SS ). It generates the rest of the signature honestly.

At the end of the experiment, B returns b . Clearly, the experiment is perfectly simulated for A, so ExpInvisibility b B,Π1 (1 λ ) returns 1 with at least the probability that ExpInvisibility b A,Π2 (1 λ ) returns 1, which is a contradiction. This concludes the proof.

B.4 Strong Accountability

Proof (Strong Signer accountability). Assume that there exists a polynomial time adversary A that breaks the strong signer accountability of Π 2 . We show how to build an algorithm B that breaks the strong accountability of VRS for n = 1. Answering Sanitize Oracle Queries. On input a tuple (pk S,i , m i , δ i , σ i ), the oracle parses σ i as (σ SS,i , σ VRS,i ) and pk S,i as {spk S,i , vpk S,i }, and sets m i = pk † Z m i and δ i such that δ i (m i ) = pk † Z δ i (m i ). The oracle computes σ SS,i ← Π 1 .San(ssk † Z , spk S,i , m i , δ i , σ SS,i ) and sends ({vpk S,i , vpk ‡ Z }, 1, pk S,i pk † Z δ i (m i ) σ SS,i ) to the oracle VRS.SignO and receives σ VRS,i . It sets σ i := (σ SS,i , σ VRS,i ) and returns it to A. Clearly, the experiment is perfectly simulated for A. Assume that A wins its experiment, then for all i the following holds: Finally, note that L * * ⊆ ({vpk ‡ Z } ∪ {pk * * }). Therefore, ExpAcc VRS,B (1 λ ) returns 1 with at least the probability that ExpSigAcc A,Π2 (1 λ ) returns 1, which is a contradiction. This concludes the proof.

-(pk
Proof (Sanitizer accountability). Assume that there exists a polynomial time adversary A that breaks the strong sanitizer accountability of Π 2 . We show how to build an algorithm B that breaks the strong non-seizability of VRS. The algorithm B receives (pp VRS , vpk ‡ S ) as input, then it runs pp SS ← Π 1 .Setup(1 λ ) and (spk † S , ssk † S ) ← VRS.KGen(pp SS ). It sets pp := (pp SS , pp VRS ) and pk † S := (spk † S , vpk ‡ S ). It runs (pk * Z , m * , σ * ) ← A(pp, pk † S ). While A is running, B simulates the oracles Π 2 .SignO and Π 2 .ProveO as follows.

  σ ← Sign(sk, M ): The signing algorithm inputs the secret key sk and a message M ∈ G 1 . It outputs a signature σ on the equivalence class [ M ] R . σ ← ChgRep(pk, M , σ, ρ): The change representation algorithm inputs the public key pk, a message M ∈ G 1 , a signature σ on the equivalence class [ M ] R , and a scalar ρ. It outputs a new signature σ on the (same) equivalence class [ M ρ ] R = [ M ] R . b ← Vf(pk, M , σ): The signature verification algorithm inputs the public key pk, a message M ∈ G 1 , and a signature σ. It returns b = 1 if σ is a valid signature under pk on the equivalence class [ M ] R , and b = 0 otherwise. b ← VfKey(pk, sk): The key verification algorithm inputs a public key pk and a secret key sk. It returns b = 1 if the keys are consistent and b = 0 otherwise.

  σ ← Sign(sk, L, m): On input the secret key sk, a ring L, and a message m, return a signature σ on the message m under the set of public keys L. b ← Verify(L, m, σ): On input a ring L, a message m, and a signature σ, return a bit b or the distinguished symbol ⊥. π ← Prove(L, m, σ, pk, sk): On input a ring L, a message m, a signature σ, a public key pk, and a secret key sk, return a proof π. b ← Judge(L, m, σ, pk, π): On input a ring L, a message m, a signature σ, a public key pk, and a proof π, return a bit b or the distinguished symbol ⊥. By convention, if b = 1

c- 2 bi

 2 ← PKE.Enc(pk Z , (α, {ζi} i∈[ ] ))σ := (µ, η, {σi, Xi, Yi} i=1 , c) return σ Verify(pk S , pk Z , m, σ) b-2 := (∀k ∈ [ ], Y k = G1) b-1 := EQS.Vf(pk S , (X1, . . . , X ), µ) b0 := EQS.Vf(pk S , (Y1, . . . , Y ), η) bi := (e(Xi, σi) = e(Yi, H(i mi))), ∀i ∈ [ ] return i=San(pk S , sk Z , m, δ, σ) (α, {ζi} i∈[ ] ) ← PKE.Dec(sk Z , c) if δ / ∈ α then return ⊥ m := δ(m) r, s ← Z * q (X 1 , . . . , X ) := (X1, . . . , X ) r (Y 1 , . . . , Y ) := (Y1, . . . , Y )r•s X := (X1, . . . , X ) Ȳ := (Y1, . . . , Y ) µ ← EQS.ChgRep(pk S , X, µ, r) η ← EQS.ChgRep(pk S , Ȳ , η, s)

  and is zero otherwise. The second observation is that, due to the restriction imposed on the SanO oracle, the values x i for all i ∈ (α b -(α 0 • α 1 )) are never used in any experiments. With the above observations, we show how one can construct an algorithm C, which breaks the IND-CCA-security of PKE, using a distinguisher which distinguishes Hyb b from ExpInvisibility b A,Π (1 λ ). C receives a public key pk PKE from the IND-CCA challenger, and acts as the challenger of either the experiment ExpInvisibility b A,Π (1 λ ) or Hyb b by setting pk † Z := pk PKE and generating other keys honestly.

5. 4 2 : 3 : 4 :

 4234 Weak Unlinkability Proof (Weak Unlinkability). To show that the experiments wExpUnlink b Π,A (1 λ ), where b ∈ {0, 1}, are computationally indistinguishable in the view of the adversary we define the following sequence of hybrids. Hyb b 0 : Defined as wExpUnlink b Π,A (1 λ ). Hyb b 1 : Defined as Hyb b 0 , except that an additional list L is initialized empty at the beginning of the experiment. Then, when a ciphertext c ← PKE.Enc(pk † Z , τ ) is generated in the subroutine Sign of the oracle SignO, a new entry (c, τ, {x i , y i } i∈[ ] ) is added to L. The wLoRSanit oracle runs the following modified version of the subroutine S an: On input a certain c, it first checks whether there is an entry (c, τ , {x i , ỹi } i∈[ ] ) in L and, if so, proceeds by setting τ = τ . Otherwise the algorithm aborts. Hyb b Defined as Hyb b 1 , except that the ciphertext c is computed as c ← PKE.Enc(pk † Z , (α, 0 )) in the SignO oracle. The suboutine S an also computes c ← PKE.Enc(pk † Z , (α, 0 )). Hyb b Defined as Hyb b 2 , except that the subroutine S an is modified to compute the signatures µ and η as µ ← EQS.Sign(sk † S , (X 1 , . . . , X )) and η ← EQS.Sign(sk † S , (Y 1 , . . . , Y )), respectively. Hyb b Defined as Hyb b3 , except that the subroutine S an samples a fresh tuple (Z 1 , . . . , Z ) ← G 1 is sampled and (X 1 , . . . , X ) := (Z 1 , . . . , Z ) and (Y 1 , . . . , Y ) := (Z ỹ1 1 , . . . , Z ỹ ) s .

Lemma 8 .

 8 Let q > 2 λ . For all generic group adversary A and b ∈ {0, 1} it holds that Pr Hyb b 4 = 1 -Pr Hyb b 5 = 1 ≤ negl(λ) . Proof (of Lemma 8). The two experiments differ in the way the variables (Y 1 , . . . , Y ) and (σ 1 , . . . , σ ) are computed. Suppose that H(i m i ) and H(i m i ) are programed to G

  (pk † S , pk † Z , m β , α β , σ SS,β ) ∈ L.Then B aborts the simulation and outputs({vpk Z , vpk S }, pk † S pk † Z m β σ SS,β , σ VRS,β ) as a forgery. Otherwise, B simulates this oracle honestly except that it generates σ VRS by calling VRS.SignO on ({vpk S , vpk Z }, pk † S pk † Z δ b (m b ) σ SS,b ), where σ b = (σ SS,b , σ VRS,b

Lemma 10 .

 10 If Π 1 is weakly unlinkable, then |Pr Hyb 0 1 = 1 -Pr Hyb 1 1 = 1 | ≤ negl(λ) . Proof. Assume that there exists a polynomial time adversary A distinguishes between the above hybrids with non-negligible probability. We show how to build an algorithm B that breaks the weak unlinkability of Π 1 . The algorithm B receives (pp SS , spk ‡ S , spk ‡ Z ) as input, then it runs pp VRS ← VRS.Setup(1 λ ), it sets pp := (pp SS , pp VRS ), it runs(vpk † S , vsk † S ) ← VRS.KGen(pp VRS ) and (vpk † Z , vsk † Z ) ← VRS.KGen(pp VRS ), and it sets pk † S := {spk ‡ S , vpk † S } and pk Z := {spk ‡ Z , vpk † Z }. It runs b * ← A(pp, pk † S , pk † Z ).While A is running, B answers to the sign and proof oracle queries as in proof of immutability, and it simulates the other oracles Π 2 .SanO and Π 2 .LoRSanitO b to A as follows.

B

  parses σ * as (σ * SS , σ * VRS ) and pk * S as {spk * S , vpk S * }. It sets L * * := {vpk S * , vpk ‡ Z }, m * * := σ * SS , σ * * := σ * VRS , pk * * := vpk S * and π * * := π * . Finally, B returns (L * * , m * * , σ * * , pk * * , π * * ).

Table 1 :

 1 Size of the parameters.

	Op.	Signing	Sanitizing Verifying Proving Judging
	Exp.	(4 + 11) G1+ ( + 2) G2	(2 + 14) G1+ ( + 2) G2	8 G1	3 G1	4 G1
	Pairing	-	-	4 + 6	-	-

Table 2 :

 2 Dominating operations in algorithms.

	(G rsx1y1

1 , . . . , G rsx y 1

  SS ← Π1.San(spk S , ssk Z , pk Z m, δ , σ SS ) t := pk S pk Z δ(m) σ SS σ VRS ← VRS.Sign(vsk Z , {vpk S , vpk Z }, t)

	Π2.Setup(1 λ , 1 )	Π2.San(pk S , sk Z , m, δ, σ)
	pp SS ← Π1.Setup(1 λ , 1 )	set δ such that δ (pk Z m) = pk Z δ(m)
	pp VRS ← VRS.Setup(1 λ )	σ
	return pp := (pp SS , pp VRS )
	Π2.KGen S (pp)
	(spk return b0 ∩ b1	return α
	Fig. 4: Construction of Weak Sanitizable Signatures. Prove and Judge always output
	(the empty string) and S (the signer) respectively, and are omitted.

c ) return σ ExtAdm(pk S , sk Z , σ) τ ← PKE.Dec(sk Z , c) parse τ as (α, {ζi} i∈[ ] ) S , ssk S ) ← Π1.KGen S (pp SS ) (vpk S , vsk S ) ← VRS.KGen(pp VRS ) (pk S , sk S ) := ((spk S , vpk S ), (ssk S , vsk S ))

return (pk S , sk S ) Π2.KGen Z (pp) (spk Z , ssk Z ) ← Π1.KGen Z (pp SS ) (vpk Z , vsk Z ) ← VRS.KGen(pp VRS ) (pk Z , sk Z ) := ((spk Z , vpk Z ), (ssk Z , vsk Z )) return (pk Z , sk Z ) Π2.Sign(sk S , pk Z , m, α) σ SS ← Π1.Sign(ssk S , spk Z , pk Z m, 0 α) t := pk S pk Z m σ SS σ VRS ← VRS.Sign(vsk S , {vpk S , vpk Z }, t) return σ := (σ SS , σ VRS ) Π2.Verify(pk S , pk Z , m, σ) t := pk S pk Z m σ SS b0 := Π1.Verify(spk S , spk Z , pk Z m, σ SS ) b1 := VRS.Verify({pk Z , vpk S }, t, σ VRS ) σ := (σ SS , σ VRS ) return σ Π2.Prove(sk S , pk Z , m, σ) t := pk S pk Z m σ SS L := {vpk S , vpk Z } π ← VRS.Prove(vsk S , L, t, σ VRS ) return π Π2.Judge(pk S , pk Z , m, σ,

π) t := pk S pk Z m σ SS L := {vpk S , vpk Z } b := VRS.Judge(L, t, σ VRS , vpk S , π)

  † S , (X 1 , . . . , X ) r ) and EQS.Sign(sk † S , (Y 1 , . . . , Y ) r•s ) is identical to that of ChgRep(pk † S , (X 1 , . . . , X ), µ , r) and ChgRep(pk † S , (Y 1 , . . . , Y ), η , r•s), where µ ← EQS.Sign(sk † S , (X 1 , . . . , X )) and η ← EQS.Sign(sk † S , (Y 1 , . . . , Y )). Therefore, we obtain a distribution D = D with

  Answering Sign Oracle Queries. On input (pk Z , m, α), it parses pk Z as (spk Z , vpk Z ), then it sets α := 0 α and m := pk Z m. B sends (spk Z , m , α ) to the sign oracle Π 1 .SignO that answers σ SS . It sets t := pk † S pk Z m σ SS and runs σ VRS ← VRS.Sign(vsk † S , {vpk † S , vpk Z }, t) and returns σ = (σ SS , σ VRS ) to A. Answering Prove Oracle Queries. On input (pk Z , m, σ), it parses σ as (σ SS , σ VRS ) and pk Z as (spk Z , vpk Z ), then it sets t := pk † S pk Z m σ SS . It runs π ← VRS.Prove(vsk † S , {vpk † S , vpk Z }, t, σ VRS ) and returns π.

	B parses σ * as (σ * SS , σ * VRS ) and pk * Z as (spk * Z , vpk * Z ). It returns (spk * Z

  ‡ S }. It runs pp SS ← Π 1 .Setup(1 λ , 1 ), (spk † S , ssk † S ) ← Π 1 .KGen S (pp SS ) and (spk † Z , ssk † Z ) ← Π 1 .KGen Z (pp SS ); and it sets pk † S := (spk † S , vpk ‡ S ) and pk † Z := (spk † Z , vpk ‡ Z ). It then runs A((pp SS , pp VRS ), pk † S , pk † Z ). While A is running, B simulates the oracles Π 2 .SignO, Π 2 .SanO, Π 2 .ProveO and Π 2 .LoRSanitO b as follows: Answering SignO Queries. B simulates this oracle honestly except that it generates σ VRS by using the oracle VRS.SignO on the input ({vpk S , vpk Z }, 1, pk S pk Z m σ SS ). Answering SanO Queries. B simulates this oracle honestly except that it generates σ VRS by calling VRS.SignO on ({vpk S , vpk Z }, 2, pk S pk Z δ(m) σ SS ). Answering ProveO Queries. B simulates this oracle honestly except that it generates the proof π by calling VRS.ProveO on ({vpk S , vpk Z }, 1, pk S pk Z m σ SS , σ VRS ).

  The algorithm B receives (pp VRS , vpk ‡ Z ) as input, then it runs pp SS ← Π 1 .Setup(1 λ ) and (spk † Z , ssk † Z ) ← Π 1 .KGen Z (pp SS ). It sets pp := (pp SS , pp VRS ) and and pk † Z := (spk † Z , vpk ‡ Z ). It runs (pk * S , m * , σ * , π * ) ← A(pp, pk † Z ). While A is running, B runs the sanitize oracle Π 2 .SanO as follows.

  By rearranging the terms, we have((pk * S , pk † Z , m * , σ * SS ), σ * VRS ) = ((pk S,i , pk † Z , δ i (m i ), σ SS,i ), σ VRS,i ). -Π 2 .Verify(pk * S , pk † Z , m * , σ * ) = 1. It implies that VRS.Verify(L * * , σ * * , m * * ) = 1. -Π 2 .Judge(pk * S , pk † Z , m

* S , m * , σ * ) = (pk S,i , δ i (m i ), σ i ). Parse σ * as (σ * SS , σ * VRS ). * , σ * , π * ) = S. So VRS.Judge(L * * , m * * , σ * * , pk * * , π * * ) = 0.

A chameleon hashing scheme allows to generate a probabilistic hash function H together with a trapdoor. With the latter, one can efficiently compute a randomness r when given any message m and hash value h such that h = H(m, r).

We remark that verifiable ring signatures can be implemented from unique[START_REF] Franklin | A framework for unique ring signatures[END_REF], linkable[START_REF] Liu | Linkable spontaneous anonymous group signature for ad hoc groups (extended abstract)[END_REF], accountable[START_REF] Xu | Accountable ring signatures: A smart card approach[END_REF], or traceable[START_REF] Fujisaki | Traceable ring signature[END_REF] ring signatures, so the transformation also works with these kinds of signature.

Our construction actually achieves perfect strong (non-proof-restricted) transparency.

Class-hiding was originally introduced[START_REF] Hanser | Structure-preserving signatures on equivalence classes and their application to anonymous credentials[END_REF] as a property of equivalence class signatures.

Hyb b

5 : Defined as Hyb b 4 , except that the subroutine S an samples a tuple (w 1 , . . . , w ) ← Z q and computes σ i as H(m i ) wi and (Y 1 , . . . , Y ) as (Z w1 1 , . . . , Z w ).

Observe that in the experiment Hyb b 5 the output of the wLoRSanit oracle in Hyb b 5 is completely decorrelated from the random coin b. It follows that for all PPT adversaries we have that Pr Hyb 0 5 = 1 -Pr Hyb 1 5 = 1 ≤ negl(λ) . We now proceed by showing the indistinguishability of each pair of hybrids. Proof (of Lemma 4). The experiments differ in the fact that in Hyb b 1 the LoRSanit oracle aborts when queried on some c such that no entry (c, •) is present in L. This implies that c was not produced by the signing oracle SignO, therefore also Hyb b 0 aborts on the same input. The indistinguishability follows by the correctness of the encryption scheme. Proof (of Lemma 5). The lemma follows by a simple reduction to the (multiple-message) CCA-security of the encryption scheme. On input a public key pk † Z , the reduction computes c by querying the challenger on (τ, (α, 0 )) and plugging in the corresponding ciphertext c * . The ciphertext c is computed analogously. The oracle SanO is simulated by passing the input ciphertexts c to the decryption oracle and setting τ to be the corresponding output. It is easy to show that in the one case the reduction perfectly simulates the distributions of Hyb b 1 and in the other case it is identical to Hyb b 2 . By the CCA-security of the encryption scheme the claim follows. Lemma 6. If EQS perfectly adapts signatures, then for all PPT A and b ∈ {0, 1},

Proof (of Lemma 6). Trivial.

Lemma 7. Let q > 2 λ . For all generic group adversary A and b ∈ {0, 1} it holds that

Proof (of Lemma 7). First observe that in Hyb b 4 (with a slight notation abuse)

A More Preliminaries

A.1 Public-Key Encryption

Here we recall the notion of public key encryption together with the standard definition of CCA-security. Security of a public key encryption scheme is formalized as follows.

Definition 15 (CCA Security). A PKE scheme is said to have indistinguishability against chosen-ciphertext attacks (IND-CCA) if for all PPT adversaries A,

where ExpCCA b A,PKE is defined in Figure 6.

A.2 Properties of Verifiable Ring Signatures

We define slightly simplified and strengthened security definitions for VRS. We note that the existing construction in [START_REF] Bultel | Unlinkable and strongly accountable sanitizable signatures from verifiable ring signatures[END_REF] satisfies all properties defined below.

Unforgeability. A VRS is unforgeable when no adversary that has access to the signature oracle and the proof oracle is able to forge a fresh message-signature pair (m, σ), such that the corresponding ring contains public keys of honest users only. In the following definition, the oracle VRS.SignO defined as in Def. 17 and Q is the set of message-signature pairs associated to the queries to the oracle VRS.SignO. Additionally, the adversary has access to the proof oracle VRS.ProveO that takes as input a tuple (L, m, σ, ), returns VRS.Prove(L, m, σ, pk , sk ) if 1 ≤ ≤ n and ⊥ otherwise.

Definition 16 (Unforgeability).

A VRS scheme VRS is strongly unforgeable if for all n ∈ poly(λ) and for all PPT adversary A,

Fig. 7: Oracles for Verifiable Ring Signatures

Anonymity. A VRS is anonymous when no adversary is able to link a signature to the public key of its signer. In the formal definition, the adversary has access to the oracles defined in Figure 7.

Definition 17 (Anonymity). A VRS scheme VRS is anonymous if for all PPT

where ExpAnon b VRS,A (1 λ ) is defined in Figure 8.

Strong Accountability. A VRS is strongly accountable when no adversary that has access to the signature oracle and the proof oracle is able to forge a fresh message-signature pair (m, σ) together with a proof that it is not the signer of σ, such that the corresponding ring contains at most one public key of a non-honest user. In the following definition, the oracle VRS.SignO defined as in Def. 17 and Q is the set of message-signature pairs associated to the queries to the oracle VRS.SignO. Additionally, the adversary has access to the proof oracle VRS.ProveO that takes as input a tuple (L, m, σ, ), returns VRS.Prove(L, m, σ, pk , sk ) if 1 ≤ ≤ n and ⊥ otherwise.

Definition 18 (Strong Accountability).

A VRS scheme VRS is strongly accountable if for all n ∈ poly(λ) and for all PPT adversary A,

where ExpAcc n VRS,A (1 λ ) is defined in Figure 8. It follows immediately that strong accountability implies strong unforgeability.

Strong Non-Seizability. A VRS is strongly non-seizable when no adversary that has access to the signature and the proof oracle is able to forge a fresh message-signature pair (m, σ), such that the proof algorithm ran by the honest user returns a proof that σ was computed by the honest user. In the following definition, the oracles SignO and ProveO and the list Q are defined as in Def. [START_REF] Franklin | A framework for unique ring signatures[END_REF].

Fig. 8: Experiments for Verifiable Ring Signatures.

Definition 19 (Strong Non-Seizability). A VRS scheme VRS is strongly non-seizable if for all PPT adversary A,

where ExpNonSeiz VRS,A (1 λ ) is defined in Figure 8.

B Security Proofs for Construction II B.1 Immutability

Proof (Immutability). Assume that there exists a polynomial time adversary A that breaks the immutability of Π 2 . We show how to build an algorithm B that breaks the weak immutability of Π 1 . The algorithm B receives (pp SS , spk ‡ S ) as input, then it runs pp VRS ← VRS.Setup(1 λ ), it sets pp := (pp SS , pp VRS ), it runs (vpk † S , vsk † S ) ← VRS.KGen(pp VRS ) and sets pk † S := (spk ‡ S , vpk † S ). It runs (pk * Z , m * , σ * ) ← A(pp, pk † S ). While A is running, B simulates the oracles Π 2 .SignO and Π 2 .ProveO as follows.

Answering LoRSanitO b Queries. Let ((m 0 , δ 0 , σ 0 ), (m 1 , δ 1 , σ 1 )) be a query from A. Note that the abort conditions in Hyb 0 1 and Hyb 1 1 are identical. Therefore if B aborts, then Hyb 0 1 = Hyb 1 1 . Suppose that B does not abort. Then it must be the case that for all β ∈ {0, 1}, there exists i β , α β which satisfies L[i β ] = (pk † S , pk † Z , m β , α β , σ β ). B can thus generate σ b by calling Π 1 .wLoRSanitO b on (i 0 , δ 0 , i 1 , δ 1 ).

Eventually, A returns b * which is also returned by B. Clearly, the game is perfectly simulated for A, therefore

where the inequality is due to the weak unlinkability of Π 1 .

Combining the two lemmas, we conclude that Π 2 is unlinkable.

B.3 Strong Invisibility

Proof (Strong Invisibility). Assume that there exists a polynomial time adversary A that breaks the strong invisibility of Π 2 . We show how to build an algorithm B that breaks the strong invisibility of Π 1 . The algorithm B receives (pp SS , spk ‡ S , spk ‡ Z ) as input, then it runs pp VRS ← VRS.Setup(1 λ ), it sets pp := (pp SS , pp VRS ), it runs (vpk † S , vsk † S ) ← VRS.KGen(pp VRS ) and (vpk † Z , vsk † Z ) ← VRS.KGen(pp VRS ), and it sets pk † S := (spk ‡ S , vpk † S ) and pk † Z := (spk ‡ Z , vpk † Z ). It initializes Q := ∅, then it runs b ← A(pp, pk † S , pk † Z ). While A is running, B answers to the proof oracle queries as in proof of immutability, and it simulates the other oracles Π 2 .SanO and Π 2 .LoRAdmO b to A as follows.

Answering SanO Queries. On input a tuple (pk S,i , m i , δ i , σ i ), the oracle returns

, otherwise it parses σ i as (σ SS,i , σ VRS,i ) and pk S,i as {spk S,i , vpk S,i }, sets m i := pk † Z m i and δ such that δ i (m i ) = pk † Z δ i (m i ), and sends (spk S,i , m i , δ i , σ SS,i ) to the oracle Π 1 .San O and receives σ SS,i . It then sets t

Answering SignO Oracle Queries. On input a tuple (pk Z,i , m i , α i ), the oracle parses pk Z,i as {spk Z,i , vpk Z,i }. The oracle computes σ SS,i ← Π 1 .Sign(ssk † S , spk Z,i , pk Z,i m i , 0 α i ) and sends ({vpk ‡ S , vpk Z,i }, 1, pk S † pk Z,i m i σ SS,i ) to the oracle VRS.SignO and receives σ VRS,i . It sets σ i := (σ SS,i , σ VRS,i ) and returns it to A.

Answering ProveO Oracle Queries. On input a tuple ( pk Z,i , mi , σi ), the oracle parses pk Z,i as { s pk Z,i , ṽ pk Z,i } and σi as (σ SS,i , σVRS,i ). The oracle sends ({vpk ‡ S , ṽ pk Z,i }, 1, pk S † pk Z,i mi σSS,i ) to the oracle VRS.ProveO and receives π i , then it returns it to A.

Clearly, the experiment is perfectly simulated for A. Assume that A wins its experiment, then for all i, and for any π ← Π 2 .Prove(sk † S , pk * Z , m * , σ * ), the following holds:

. By rearranging the terms, we have

Judge(L * * , m * * , σ * * , pk * * , π * * ) = 0. Therefore, ExpNonSeiz VRS,B (1 λ ) returns 1 with at least the probability that ExpSanAcc A,Π2 (1 λ ) returns 1, which is a contradiction. This concludes the proof.

B.5 Strong Proof-Restricted Transparency

Proof (Strong Proof-Restricted Transparency). We prove by hybrid argument. For any polynomial time algorithm A, we define the hybrid experiment ExpHTransparency A,Π2 (1 λ ) as the same experiment as ExpTransparency 0 A,Π2 (1 λ ) except that, on input (m i , δ i , α i ) the oracle Π 2 .Sign/SanO b returns σ i = (σ SS,i , σ VRS,i ) where σ VRS,i is a signature generated by the signer instead of the sanitizer. Concretely, σ VRS,i is generated as σ VRS,i ← VRS.Sign(vsk S , {vpk S , vpk Z }, pk S pk Z δ i (m i ) σ SS,i ).

We first argue that for any PPT adversary A, the probabilities that the experiments ExpHTransparency A,Π2 (1 λ ) and ExpTransparency 0 A,Π2 Next, we argue that for any PPT adversary A, the probabilities that the experiments ExpHTransparency A,Π2 (1 λ ) and ExpTransparency 1 A,Π2 (1 λ ) output 1 are negligibly close if Π 1 is strongly proof-restricted transparent. Suppose not, we construct a PPT adversary B against the strongly proof-restricted transparency of Π 1 .

B receives (pp SS , spk ‡ Z , spk ‡ S ), then it runs pp VRS ← VRS.Setup(1 λ ), (vpk † Z , vsk † Z ) ← VRS.KGen(pp VRS ) and (vpk † S , vsk † S ) ← VRS.KGen(pp VRS ), and it sets pp := (pp SS , pp VRS ), pk † S := (spk ‡ S , vpk † S ) and pk † Z := (spk ‡ Z , vpk † Z ). B then simulates the Π 2 .SignO, Π 2 .SanO, Π 2 .ProveO, and Π 2 .Sign/SanO b oracles of Π 2 for A by querying the corresponding oracles of Π 1 and, when appropriate, signing their outputs using the honestly generated VRS secret keys.

Clearly, depending on the choice of the transparency challenger of Π 1 , B simulates either the experiment ExpHTransparency A,Π2 (1 λ ) or ExpTransparency 1 A,Π2 (1 λ ) perfectly. Therefore, if the probabilities that the experiments ExpHTransparency A,Π2 (1 λ ) and ExpTransparency 1 A,Π2 (1 λ ) output 1 differ in non-negligible probability, then the probabilities that ExpTransparency 0 B,Π1 (1 λ ) and ExpTransparency 1 B,Π1 (1 λ ) output 1 differ by the same non-negligible probability, which contracts the assumption that Π 1 is strongly proof-restricted transparent.


In order to implement a realistic output in a song learning model, we investigated one of the models proposed in the long research quest of Minldin. We were looking for a model with few degrees of freedom, and replicated the RA model proposed in Laje & Mindlin (2002). The model describes three neural populations of RA receiving inputs from HVC: two of which are excitatory and control the syringeal muscles and respiratory muscles (x k and x p resp.); one which stands for inhibitory interneurons. This model is able to produce syllables sounds. We implemented this model in Python language and tried to reproduced several figures of the original paper: a bifurcation diagram and three synthetic syllables.

Abstract

Bifurcation diagram obtained as 𝜌 2 is varied. 𝜌 1 = 0, 𝜌 3 = 6. FP fixed-point, P1: period-one limit cycle, P2 period-two limit cycle. The P1 oscillation is represented by two points indicating maximum and minimum of the oscillation, and the P2 oscillation is represented by four points indicating two local maxima and two local minima. Solid line: stable solutions; dashed line: unstable solutions.

Original figures

Bifurcation diagram obtained by two pass iterative simulations. (blue) local minima (red) local maxima. Scale is piece-wise linear in order to keep a similar shape than in the original figure. We used a sampling rate of 63,000 when generating the sounds.

Reproduced figures

Replication of Laje & Mindlin's model producing synthetic syllables J.B. Zacchello 1,2,3 , X. Hinaut 1,2,3 , A. Leblois 3 1. Inria Bordeaux Sud-Ouest, Talence, France. 2. LaBRI, UMR 5800, CNRS, Bordeaux INP, Université de Bordeaux, Talence, France. 3. Institut des Maladies Neurodégénératives, UMR 5293, CNRS, Université de Bordeaux, Bordeaux, France.

We could partly reproduce the results (i.e. figures) of the original paper of Laje & Mindlin (2002). According to our experiments it seems that the original bifurcation diagram was probably interpolated by hand because we obtain a qualitatively similar figure but not a quantitatively similar figure. We could also produce a few different synthetic syllables with the model. However, we were not able to reproduce the same "song" composed of the three syllables as it is shown in the original figure. Moreover, we were not able to find the initial conditions which enable to produce a syllable "right away" when setting a particular 𝜌 2 value: a transitory period was necessary before the corresponding syllable (of their paper) could be produced. In conclusion, the model can produce a few isolated syllables but, and, as far as we experimented, it seems difficult to produce songs.

Discussion

We show the three syllables obtained when changing sequentially the values of 𝜌 2 (-11.0; -11.8; -7.1), while keeping 𝜌 1 = 0 and 𝜌 3 = 6. Moreover, we give the corresponding pressure and tension activity. We used a sampling rate of 105,000 when generating the sounds.

We thank Juliette Chabassier for useful discussions and advises.

Synthetic syllables

  Laje, R., & Mindlin, G. B. (2002). Diversity within a birdsong. Physical review letters, 89(28), 288102.

Acknowledgements

where S denotes a sigmoid function S(x) = 1/(1+e -x ) and 𝜌 i are the excitatory inputs from HVC into the sets of neurons with activities x p (pression), y (inhibitory), and x k (tension) respectively.

Materials & Methods

Mean-field population model

Bifurcation diagram

Reproduced figures

The neural sets within RA: two excitatory sets (shaded circles) connected to a long-range inhibitory one (open square). All sets receive excitatory inputs from HVC, denoted here by dashed lines. Inset: averaged activity of one of the populations (bottom), and spiking activity consistent with the averaged activity (top).

Synthetic syllables

The interaction between these populations are described by three ordinary differential equations (ODE).