Thomas Laloë
email: tlaloe@math.univ-montp2.fr

A k-NEAREST NEIGHBOR APPROACH FOR FUNCTIONAL REGRESSION

Let (X, Y ) be a random pair taking values in H × R, where H is an infinite dimensional separable Hilbert space. We establish weak consistency of a nearest neighbor-type estimator of the regression function of Y on X based on independent observations of the pair (X, Y ). As a general strategy, we propose to reduce the infinite dimension of H by considering only the first d coefficients of an expansion of X in an orthonormal system of H, and then to perform k-nearest neighbor regression in R d . Both the dimension and the number of neighbors are automatically selected from the observations using a simple datadependent splitting device.

Introduction

Regression is the problem of predicting a variable from some observation. An observation is usually supposed to be a collection of numerical measurements represented by a d-dimensional vector. However, in many real-life problems, input data items are in the form of random functions (speech recordings, spectra, images) rather than standard vectors, and this casts the regression 1 problem into the general class of functional data analysis. Even though in practice such observations are observed at discrete sampling points, the challenge in this context is to infer the data structure by exploiting the infinitedimensional nature of the observations. The last few years have witnessed important developments in both the theory and practice of functional data analysis, and many traditional data analysis tools have been adapted to handle functional inputs. The book of Ramsay and Silverman [START_REF] Ramsay | Functional data analysis[END_REF] provides a comprehensive introduction to the area. For an updated list of references, we refer the reader to Cérou and Guyader [START_REF] Cerou | Nearest neighbor classification in infinite dimension[END_REF], Rossi and Villa [START_REF] Rossi | Support Vector Machine For Functional Data Classification[END_REF], and Tuleau [START_REF] Tuleau | Sélection de variables pour la discrimination en grande dimension, classification de données fonctionnelles[END_REF].

In the present paper, we consider the functional regression setting, where the goal is to predict a scalar response Y from some infinite-dimensional observations X. More precisely, we will denote by (X, Y ) a random pair taking values in Z = H × R, where H is an infinite dimensional separable Hilbert space.

Throughout the document, we will denote by ρ the (unknown) distribution of (X, Y ), and by ρ X the marginal distribution of X. Based on n independent copies (X 1 , Y 1 ), . . . , (X n , Y n ) of (X, Y ), we introduce an estimator f n of the regression function f ρ (x) = E[Y |X = x] which is designed as follows:

First, we reduce the dimension of H by considering the first d coefficients of an expansion of each observation in a orthonormal system of H; Second, we perform k-nearest neighbor regression (see Györfi, Kohler, Krzyzak, and Walk [START_REF] Györfi | A distribution free theory of nonparametric regression[END_REF])in R d . We select simultaneously the dimension d and the number of neighbors k by a data-splitting device. Our main result states weak consistency of the resulting estimator, thereby extending the general strategy introduced by Biau, Bunea, and Wegkamp [START_REF] Biau | Functional classification in Hilbert Spaces[END_REF] in the context of classification (ie, when Y takes its values in a finite set).

The paper is organised as follows. We start in Section 2.1 by introducing some notation. Then, in Section 2.2, we present the construction of the estimator, and state its weak consistency. Proof are collected in Section 3.

Consistent functional regression

Notation

We let the symbols .|. and . denote the inner product and the associated norm on H, respectively, and we let (φ j ) j≥1 be a complete orthonormal system of H (Akhiezer and Glazman [START_REF] Akhiezer | Theory of linear operators in Hilbert space[END_REF]). For each observation X i , we set

X ij = X i |φ j . We know that X i = ∞ j=1 X ij φ j ,
where the consistency holds in the L 2 sense.

Introduce H (d) , the finite-dimensional vector space spanned by the functions {φ 1 , φ 2 , . . . , φ d }, and let, for each X i ,

X (d) i = d j=1 X ij φ j .
Finally, denote by f ρ and f ρ,d the regression functions in H and H (d) , respectively, and by σ 2 ρ and σ 2 ρ,d their respective L 2 errors. More precisely, we have

f ρ (x) = E[Y |X = x], σ 2 ρ = Z (y -f ρ (x)
) 2 dρ(x, y), and the same in H (d) × R for f ρ,d and σ 2 ρ,d . Throughout the document, we suppose that Y < ∞ a.s., and all the integrals are to be understood over ρ or ρ X .

k-nearest neighbor in H (d)

Let us first formally define our k-nearest neighbor type estimator. To this aim, we consider the sequence (X

(d) 1 , Y 1 ), . . . , (X (d)
n , Y n ) where the observations have been projected onto H (d) . For x in H (d) , we reorder the data:

X (d) (1) (x), Y (1) (x) , . . . , X (d) (n) (x), Y (n) (x) , according to the increasing Euclidean distances X (d) i -x of the X (d) i to x.
In other words, X

(d) (i) (x) is the i-th nearest neighbor of x amongst X (d) j . If X (d) i -x = X (d) j -x , X (d) i is declared closer to x if i < j. The k-nearest 3
neighbor estimator of f ρ is then defined (Györfi, Kohler, Krzyzak, and Walk [START_REF] Györfi | A distribution free theory of nonparametric regression[END_REF]) as

f n,k,d (x) = 1 k k i=1 Y (i) (x). (1)
To select simultaneously the dimension d and the number of neighbors k,

we
( d, k) ∈ arg min d≥1,1≤k≤ℓ 1 m j∈Jm Y j -f ℓ,k,d (X (d) j ) 2 + λ d √ m . (2)
Here, the term λ d / √ m is a given penalty term which tends to infinity with d to prevent overfitting. This method, which is computationnaly simple, leads to the estimator

fn (x) := f ℓ, k, d(x ( d) ), (3)
which has an error

E( fn ) = Z y -fn (x) 2 dρ(x, y) = H fn (x) -f ρ (x) 2 dρ X (x) + σ 2 ρ .
The estimator f n satisfies the following oracle inequality:

Proposition 2.1 Let M be a positive constant such that (Y -f ℓ,k,d (x)) 2 ≤
M a.s., and suppose that

∆ := ∞ d=1 e -2(λ d /M ) 2 < ∞. (4)
Then there exists a constant c > 0, only depending on ∆ and M , such that, for every integer ℓ > 1/∆ and m = n -ℓ,

E H fn (x) -f ρ (x) 2 ≤ inf d≥1 (σ 2 ρ,d -σ 2 ρ ) + inf 1≤k≤ℓ E H (d) f ℓ,k,d (x) -f ρ,d (x) 2 + λ d √ m +c ln ℓ m .
(

) 5
The term σ 2 ρ,d -σ 2 ρ may be viewed as the price to be paid for using a finite dimensional approximation of the observations, and it converges to zero by Lemma 3.1 below. The term Pratically speaking, as discussed in Biau, Bunea, and Wegkamp [START_REF] Biau | Functional classification in Hilbert Spaces[END_REF], choosing the penalty in ( 2) is not an easy task. Indeed, an abusive penalisation of high dimensions can mask helpful information. For a more involved discussion about the penalty choice, and experimental results, we refer the reader to Tuleau [START_REF] Tuleau | Sélection de variables pour la discrimination en grande dimension, classification de données fonctionnelles[END_REF], who shows that that adding a penalty term improves the stability of the selected dimension d.

inf 1≤k≤ℓ E H (d) (f ℓ,k,d (x) -f ρ,d (x)

Proof

Proof of Proposition 2.1 Let

L(k, d) = E Y -f ℓ,k,d X (d) 2 | (X i , Y i ), 1 ≤ i ≤ n , and
L(k, d) = 1 m j∈Jm Y j -f ℓ,k,d (X (d) j ) 2 .
We have to minimize L(k, d) + λ d /m in k and d.

Fix ε > 0. For every d ≥ 1 and every k satisfying 1 ≤ k ≤ ℓ, we may write

P L( k, d) -L(k, d) > λ d √ m + ε ≤ P L( k, d) -L( k, d) > λ d √ m + ε , since, by definition of ( k, d), L( k, d) + λ d √ m ≤ L(k, d) + λ d √ m .
Therefore,

P L( k, d) -L(k, d) > λ d / √ m + ε ≤ ∞ d=1 ℓ k=1 P L(k, d) -L(k, d) > λ d / √ m + ε (by the union bound) = ∞ d=1 ℓ k=1 EP L(k, d) -L(k, d) > λ d / √ m + ε | (X i , Y i ), i ∈ I ℓ ≤ ∞ d=1 ℓ exp -2[(λ d / √ m) + ε] 2 × (m/M 2 )
(by Hoeffding's inequality)

≤ ℓe -2mε 2 /M 2 ∞ d=1 e -2(λ d /M ) 2 = ∆ℓe -2mε 2 /M 2 ,
where ∆ = ∞ d=1 e -2(λ d /M ) 2 . Since, for every d ≥ 1 and k with 1

≤ k ≤ ℓ, EL( k, d) ≤ E L(k, d) + λ d √ m + ∞ 0 P L( k, d) -L(k, d) > λ d √ m + ε dε ,
we obtain, for every u > 0,

EL( k, d) ≤ E L(k, d) + λ d √ m + u + ∆ℓ ∞ u e -2mε 2 /M 2 dε . Note that ∞ u e -2mε 2 /M 2 dε ≤ 1 2 ∞ u 2 + M 2 2mε e -2mε 2 /M 2 dε = - 1 2 M 2 2mε e -2mε 2 /M 2 ∞ u = M 2 4mu e -2mu 2 /M 2 .
Whence, choosing u = M ln(∆ℓ)/2m, we obtain

EL( k, d) ≤ E L(k, d) + λ d √ m + M ln(∆ℓ) 2m + M 2 2m ln(∆ℓ) . Since k et d are arbitrary, EL( k, d) ≤ inf d≥1,1≤k≤ℓ E L(k, d) + λ d √ m + M ln(∆ℓ) 2m + M 2 2m ln(∆ℓ) .
The fact that E L(k, d) = EL(k, d) for each fixed k,d leads to the inequality [START_REF] Györfi | A distribution free theory of nonparametric regression[END_REF].

Proof of Theorem 2.1 will rely on the following lemma.

Lemma 3.1 We have σ 2 ρ,d -σ 2 ρ → 0 when d → ∞ .
Proof of Lemma 3.1 : Since ε is arbitrary the convergence is ensured.

σ 2 ρ,d -σ 2 ρ = E Y -E Y |X (d) 2 -E Y -E Y |X 2 = E Y -E Y |X 2 + E E Y |X -E Y |X (d) 2 -E Y -E Y |X 2 = E E Y |X -E Y |X (d) 2 . Since E[Y 2 ] < ∞, the sequence E[Y |X (d) ] d≥1 is a L 2 bounded Martingale, therefore we have E[Y |X (d) ] → E[Y |X] in the L 2 sense as d → ∞.

  suggest the following data-splitting device. First we split the data into a training set {(X i , Y i ), i ∈ I ℓ } of length ℓ, and a validation set {(X j , Y j ), j ∈ J m } of length m, with m+ℓ = n (ℓ and m possibly function of n). For each d ≥ 1, 1 ≤ k ≤ ℓ, we construct a k-nearest neighbor estimator based on the training set. Second we use the validation set to select d and k as follows:

Theorem 2 . 1 2 → 0

 2120 ) 2 converges also to zero by Lemma 3.2. Since the infimum is taken over all d ≥ 1, weak convergence of fn (x) to f ρ (x) is ensured. Under the assumption (4) weakly converges to f ρ , i.e. E H fn (x) -f ρ (x) as n → ∞.

Lemma 3 . 2 2 → 0 2 → 0 2 +

 3220202 Assume that k → ∞ and k/ℓ → 0 as ℓ → ∞. Then, for any fixed d,E H (d) f ℓ,k,d (x) -f ρ,d (x) as ℓ → ∞Proof of Lemma 3.2 See Györfi, Kohler, Krzyzak, and Walk[START_REF] Györfi | A distribution free theory of nonparametric regression[END_REF], Theorem 6.1, page 88.We are now in a position to prove Theorem 2.1.Proof of Theorem 2.1 Fix ε > 0. By Lemma 3.1, we know there exist d 0 such that σ ρ,d -σ 2 ρ ≤ ε for all d ≥ d 0 . Then, by Lemma 3.2, we haveE H (d 0 ) f ℓ,k,d 0 (x) -f ρ,d 0 (x) as ℓ → ∞.Finally by Proposition 2.1 we have :E H fn (x) -f ρ (x) f ℓ,k,d (x) -f ρ,d (x) k,d 0 (x) -f ρ,d 0 (x) λ d 0 √ m + c ln ℓ m ≤ ε + o(1), as n → ∞.


Olivier Blazy
email: olivier.blazy@unilim.fr

David Derler

Daniel Slamanig

Raphael Spreitzer

Non-Interactive Plaintext (In-)Equality Proofs and Group Signatures with Verifiable Controllable Linkability

Group signatures are an important privacy-enhancing tool that allow to anonymously sign messages on behalf of a group. A recent feature for group signatures is controllable linkability, where a dedicated linking authority (LA) can determine whether two given signatures stem from the same signer without being able to identify the signer(s). Currently the linking authority is fully trusted, which is often not desirable.

In this paper, we firstly introduce a generic technique for non-interactive zero-knowledge plaintext equality and inequality proofs. In our setting, the prover is given two ciphertexts and some trapdoor information, but neither has access to the decryption key nor the randomness used to produce the respective ciphertexts. Thus, the prover performs these proofs on unknown plaintexts. Besides a generic technique, we also propose an efficient instantiation that adapts recent results from Blazy et al. (CT-RSA'15), and in particular a combination of Groth-Sahai (GS) proofs (or sigma proofs) and smooth projective hash functions (SPHFs).

While this result may be of independent interest, we use it to realize verifiable controllable linkability for group signatures. Here, the LA is required to non-interactively prove whether or not two signatures link (while it is not able to identify the signers). This significantly reduces the required trust in the linking authority. Moreover, we extend the model of group signatures to cover the feature of verifiable controllable linkability.

Introduction

Group signatures, introduced by Chaum and van Heyst [START_REF] Chaum | Group Signatures[END_REF], allow users to anonymously sign messages on behalf of a group. In case of dispute, a so-called opening authority is able to reveal the identity of the actual signer. While many popular group signature schemes (GSSs) (such as [START_REF] Ateniese | A Practical and Provably Secure Coalition-Resistant Group Signature Scheme[END_REF][START_REF] Boneh | Short Group Signatures[END_REF]) simply trust the output of the opening authority, Camenisch and Stadler [START_REF] Camenisch | Efficient Group Signature Schemes for Large Groups[END_REF] proposed to require a proof of the correctness of the opening mechanism. Later, Bellare et al. [START_REF] Bellare | Foundations of Group Signatures: The Case of Dynamic Groups[END_REF] introduced a model for dynamic group signatures (BSZ model) that incorporates this issue by requiring publicly verifiable proofs of opening, i.e., the opening authority provides a proof that the claimed signer indeed produced a given signature. Recently, Sakai et al. [SSE + 12] identified an issue with this opening mechanism in the BSZ model and introduced an additional property called opening soundness. This property prevents signature hijacking, i.e., it prevents malicious group members (who cooperate with the opening authority) from claiming ownership of a signature produced by an honest group member. Over the years many other additional features for GSSs have been introduced (cf. Section 1.2).

One rather recent feature is called controllable linkability [HLhC + 11,HLC + 13, HCCN15,SSU14]. Here, a dedicated entity called linking authority (LA) can determine whether two given group signatures stem from the same signer, but the LA is not able to identify the signer(s). Consequently, the LA is strictly less powerful than the opening authority which can identify all signers by opening their signatures. Like early group signatures did not consider untrusted opening authorities, existing group signatures with controllable linkability [HLhC + 11, HLC + 13,HCCN15,SSU14] do not consider untrusted LAs. In particular, the LA simply provides a binary linking decision and thus has to be fully trusted. It is, however, desirable to reduce this trust. Ideally, in a way that the LA needs to provide verifiable evidence, i.e., a proof, of a correct decision. In this paper, we solve this open problem and introduce the novel concept of verifiable controllable linkability (VCL). Applications of VCL include different types of privacy-preserving data-mining scenarios in various fields such as online shopping, public transport, park-and road pricing. Essentially, whenever one requires to analyse customers' behavioural patterns in a privacy-respecting way and these computations are outsourced to a potentially untrusted party, e.g., a cloud provider, that needs to prove honest behaviour and must not be able to identify individuals. Moreover, their application to revocation mechanisms seems interesting to study.

Background and Motivation

Naive approaches to solve this problem, like abusing the opening authority or requiring the LA to sign its decision, are rather privacy intrusive and/or not satisfactory. To give an idea of how we approach this problem, we have to look at the existing approaches to achieve controllable linkability without verifiability. This concept has been proposed for several GSSs by Hwang et al. [HLhC + 11, HLC + 13, HCCN15]. As their approach to controllable linkability, however, is ad-hoc and always tailored to a specific GSS, Slamanig et al. [START_REF] Slamanig | Adding Controllable Linkability to Pairing-Based Group Signatures for Free[END_REF] proposed a generic approach to add controllable linkability to pairingbased group signature schemes following the sign-and-encrypt-and-prove (SEP) paradigm (cf. Section 2.3), which covers a large class of practical group signatures in the ROM. We recall that a group signature in the SEP paradigm is an encryption of a per-user unique value (certificate) under the public key of the opening authority and a non-interactive zero-knowledge proof of a signature (on this certificate) from the group manager. This generic approach allows the LA to perform the linking operation on the encrypted membership certificates (which are used for opening group signatures) by means of a variant of the all-or-nothing public key encryption with equality tests (AoN-PKeet * ) primitive. Basically, the LA obtains a single linking key (trapdoor) that allows plaintext equality tests on the membership certificates without being able to decrypt. Now, our idea is to require the LA to provide a proof that either two encrypted membership certificates contain the same or different unknown certificates (plaintexts). The particular challenge, however, is that the LA must not be able to identify the signers and thus needs to perform such proofs without knowing the plaintexts, the decryption key or the randomness used to produce the ciphertexts. Moreover, in contrast to opening proofs, we do not only need to provide a proof in case of a positive linking decision but also in case of a negative decision, i.e., when two ciphertexts contain different unknown plaintexts (certificates). This makes proving the correctness of a linking decision a much more challenging task.

Related Work

Group signatures. In traceable signatures [START_REF] Kiayias | Traceable Signatures[END_REF][START_REF] Sherman | Real Traceable Signatures[END_REF], the opening authority can compute a tracing trapdoor for a user, which allows the identification of all signatures generated by a particular user without violating the privacy of other users. In group signatures with message dependent opening [SEH + 12], the opening authority cannot open any signature unless an additional authority (the admitter) admits to open signatures for specified messages and thus restricts the power of the opening authority. In deniable group signatures [IEH + 15], the opener can, in addition to opening proofs, prove that a particular signature has not been generated by a particular signer. Apart from these opening capabilities, also linking capabilities have been investigated. For instance, the possibility to publicly link group signatures of users without identifying them [START_REF] Nakanishi | A Linkable Group Signature and Its Application to Secret Voting[END_REF] or to allow public tracing of signers who have produced a number of signatures above a certain threshold [START_REF] Victor | Tracing-by-Linking Group Signatures[END_REF]. But also the linkability of signatures for a specified time frame (by fixing the randomness for a certain time [START_REF] Malina | Short-Term Linkable Group Signatures with Categorized Batch Verification[END_REF] or by introducing specific time tokens [START_REF] Emura | Road-to-Vehicle Communications with Time-Dependent Anonymity: A Light Weight Construction and its Experimental Results[END_REF]) have been considered. Another direction is to put the user in charge of controlling which signatures can be linked, as it is used in DAA [START_REF] Brickell | Direct Anonymous Attestation[END_REF] and related schemes [BFG + 13]. These concepts are related to our work but do not help to realize our goals.

Plaintext equality/inequality proofs. Zero-knowledge proofs of plaintext equality (under distinct public keys) are well known from the twin-encryption paradigm [START_REF] Naor | Public-key Cryptosystems Provably Secure against Chosen Ciphertext Attacks[END_REF]. However, we require equality as well as inequality proofs and in our setting the prover neither has access to the decryption key nor the randomness used to produce the respective ciphertexts. Jakobsson and Juels [START_REF] Jakobsson | Mix and Match: Secure Function Evaluation via Ciphertexts[END_REF] introduced the concept of distributed plaintext equality tests (PETs) within their approach to general secure multiparty computation. Basically, it allows n > 1 entities to determine whether two ElGamal ciphertexts encrypt the same or a different message without learning the message. However, this requires access to the decryption key. Choi et al. [CEJ + 07] provide zero-knowledge equality/inequality proofs for boolean ElGamal ciphertexts. Their approach requires the knowledge of the decryption key and the randomness used to produce the two ciphertexts. Parkes et al. [START_REF] David | Practical Secrecy-Preserving, Verifiably Correct and Trustworthy Auctions[END_REF] provide zero-knowledge equality/inequality proofs of plaintexts within Paillier ciphertexts, which however require either access to the randomness used to produce the ciphertexts or access to the plaintexts. Recently, Blazy et al. [START_REF] Blazy | Non-Interactive Zero-Knowledge Proofs of Non-Membership[END_REF] introduced a generic approach to prove nonmembership with respect to some language in non-interactive zero-knowledge. Among others, they show how to prove plaintext inequality of two ElGamal ciphertexts, where the verifier knows the plaintext and the randomness used to produce one of the ciphertexts. Therefore, none of these approaches directly fits our requirements.

Contribution

The contributions of this paper are as follows: (1) Based upon the idea of public key encryption with equality tests, we define a generic non-interactive proof system that allows to perform zero-knowledge proofs about plaintext equality and inequality with respect to any two ciphertexts under the same public key. Thereby, the prover is neither required to have access to the decryption key nor to the randomness used to produce the respective ciphertexts. (2) We show how Groth-Sahai (GS) proofs [START_REF] Groth | Efficient Non-interactive Proof Systems for Bilinear Groups[END_REF] and an adaptation of non-interactive zeroknowledge proofs of non-membership [START_REF] Blazy | Non-Interactive Zero-Knowledge Proofs of Non-Membership[END_REF] can be combined to obtain an instantiation of our proof system. While an instantiation of such a proof system is of independent interest, it allows us to construct group signatures with verifiable controllable linkability (VCL-GS). (3) We adopt the model of GSSs with controllable linkability [HLhC + 11, HLC + 13, HCCN15] to a model for VCL-GS. In the vein of Sakai et al. [SSE + 12], we introduce a property called linking soundness, which requires that even corrupted LAs (colluding with malicious users) cannot produce false linking proofs. (4) We show how to transform GSSs with controllable linkability following the SEP paradigm into GSSs with verifiable controllable linkability by using the proposed non-interactive zero-knowledge proof system.

Preliminaries

Subsequently, we discuss preliminaries and recall assumptions and required tools. Notation. Let x ← R X denote the operation that picks an element x uniformly at random from a set X. A function : N → R + is called negligible if for all c > 0 there is a k 0 such that (k) < 1/k c for all k > k 0 . In the remainder of this paper, we use to denote such a negligible function. We use boldface letters to denote vectors, e.g., X = (X 1 , . . . X n ).

Let G 1 = g , G 2 = ĝ , and G T be groups of prime order p. We write elements in G 2 as ĝ, ĥ, etc. A bilinear map e :

G 1 × G 2 → G T is a map, where it holds for all (u, v, a, b) ∈ G 1 × G 2 × Z 2
p that e(u a , vb ) = e(u, v) ab , and e(g, ĝ) = 1, and e is efficiently computable. We assume the asymmetric setting where G 1 = G 2 . The required hardness assumptions are provided in Appendix A.

2.1 Groth-Sahai (GS) Non-Interactive Zero-Knowledge Proofs Groth and Sahai [START_REF] Groth | Efficient Non-interactive Proof Systems for Bilinear Groups[END_REF] provide a framework for efficient non-interactive witnessindistinguishable (NIWI) and non-interactive zero-knowledge (NIZK) proofs for languages defined over bilinear groups. It allows, among others, to prove statements about the satisfiability of so-called pairing product equations (PPEs). While the framework is quite independent of the underlying hardness assumption, we will use the instantiation based on the SXDH setting, and, thus, our further explanations are tailored to this setting. A PPE is of the form

n i=1 e(A i , Ŷi ) • m i=1 e(X i , Bi ) • m i=1 n j=1 e(X i , Ŷj ) γij = t T , where X ∈ G m 1 , Ŷ ∈ G n 2 are the secret vectors (to prove knowledge of) and A ∈ G n 1 , B ∈ G m 2 , Γ = (γ ij ) i∈[m],j∈[n] ∈ Z n•m p
, and t T ∈ G T are public constants. Informally, GS proofs use the following strategy. One commits to the vectors X and Ŷ, and uses the commitments instead of the actual values in the PPE. The proof π is used to cancel out the randomness used in the commitments. As this does not directly work when using the groups G 1 , G 2 , and G T , one projects the involved elements to the vector spaces G 2 1 , G 2 2 , and G 4 T by using the defined projection maps and proves the satisfiability of the PPE using the projected elements and corresponding bilinear map

F : G 2 1 × G 2 2 → G 4 T .
More formally, a GS proof for a PPE allows to prove knowledge of a witness w = (X, Ŷ) such that the PPE, uniquely defined by the statement x = (A, B, Γ, t T ), is satisfied. Henceforth, let BG denote the description of the used bilinear group and let R be the relation such that (BG, x, w) ∈ R iff w is a satisfying witness for x with respect to BG. Further, let L R be the corresponding language.

Formally, a non-interactive proof system in a bilinear group setting is defined as follows:

Definition 1. A non-interactive proof system Π is a tuple of PPT algorithms (BGGen, CRSGen, Proof, Verify), which are defined as follows:

BGGen(1 κ ) : Takes a security parameter κ as input, and outputs a bilinear group description BG. CRSGen(BG) : Takes a bilinear group description BG as input, and outputs a common reference string crs. Proof(BG, crs, x, w) : Takes a bilinear group description BG, a common reference string crs, a statement x, and a witness w as input, and outputs a proof π.

Verify(BG, crs, x, π) : Takes a bilinear group description BG, a common reference string crs, a statement x, and a proof π as input, and outputs 1 if π is valid and 0 otherwise.

The security definitions for non-interactive proof systems are provided in Appendix B. GS proofs are perfectly complete, perfectly sound, and witness indistinguishable. Furthermore, they are composably zero-knowledge if t T = 1 G T and the PPE does not involve a pairing of two public constants.

Throughout this paper we use the GS-based commit-and-prove approach from [START_REF] Escala | Fine-Tuning Groth-Sahai Proofs[END_REF], which allows to reuse the commitments in proofs for different statements. This allows us to prove statements with respect to commitments that are included in the common reference string (CRS) to obtain more efficient proofs. Moreover, the fact that the commitments are already contained in the CRS allows us to exclude the usage of trivial witnesses, i.e., 1 G1 or 1 G2 .

Smooth Projective Hash Functions

Smooth projective hash functions (SPHF) [START_REF] Cramer | Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption[END_REF] are families of pairs of functions (Hash, ProjHash) defined on a language L. They are indexed by a pair of associated keys (hk, hp), where the hashing key hk may be viewed as the private key and the projection key hp as the public key. On a word W ∈ L, both functions need to yield the same result, i.e., Hash(hk, L, W ) = ProjHash(hp, L, W, w), where the latter evaluation additionally requires a witness w that W ∈ L. Thus, they can be seen as a tool for implicit designated-verifier proofs of membership [START_REF] Abdalla | Smooth Projective Hashing for Conditionally Extractable Commitments[END_REF]. Formally SPHFs are defined as follows (cf. [BBC + 13b]). Definition 2. A SPHF for a language L is a tuple of PPT algorithms (Setup, Ha-shKG, ProjKG, Hash, ProjHash), which are defined as follows:

Setup(1 κ ) : Takes a security parameter κ and generates the global parameters pp (we assume that all algorithms have access to pp). HashKG(L) : Takes a language L and outputs a hashing key hk for L. ProjKG(hk, L, W ) : Takes a hashing key hk, a language L, and a word W and outputs a projection key hp, possibly depending on W . Hash(hk, L, W ) : Takes a hashing key hk, a language L, and a word W and outputs a hash H . ProjHash(hp, L, W, w) : Takes a projection key hp, a language L, a word W , and a witness w for W ∈ L and outputs a hash H.

The security properties as well as the concrete ElGamal-based instantiation from [START_REF] Gennaro | A Framework for Password-Based Authenticated Key Exchange[END_REF] used in this paper are provided in Appendix C.

Sign-and-Encrypt-and-Prove Paradigm

Group signature schemes following the sign-and-encrypt-and-prove (SEP) paradigm are popular and there are various efficient constructions (in the ROM) following this paradigm. Such a scheme consists of the following three building blocks: (1) A secure signature scheme DS = (KeyGen s , Sign, Vrfy), (2) an at least IND-CPA secure public key encryption scheme AE = (KeyGen e , Enc, Dec) and

(3) a non-interactive zero-knowledge proof of knowledge (NIZKPK) system, e.g., non-interactive versions of Σ-protocols obtained via the Fiat-Shamir transform in the ROM (denoted as signatures of knowledge (SoK) subsequently).

The group public key gpk consists of the public encryption key pk e , and the signature verification key pk s . The master opening key mok is the decryption key sk e , and the master issuing key mik is the signing key sk s . During the joining procedure a user i sends f (x i ) to the issuer, where f (•) is a one-way function applied to a secret x i . The issuer returns a signature cert ← Sign(sk s , f (x i )) which represents the user's certificate.

A group signature σ = (T, π) for a message M consists of a ciphertext T ← Enc(pk e , cert) and the following SoK π:

π ← SoK{(x i , cert) : cert = Sign(sk s , f (x i )) ∧ T = Enc(pk e , cert)}(M ).
We note that there are slight deviations in instantiations of this paradigm (cf. [START_REF] Nakanishi | Revocable Group Signature Schemes with Constant Costs for Signing and Verifying[END_REF][START_REF] Slamanig | Adding Controllable Linkability to Pairing-Based Group Signatures for Free[END_REF]), e.g., sometimes cert is computed for x i instead of f (x i ) (which, however, does not yield constructions providing non-frameability), or T may represent an encryption of f (x i ) or g(x i ) for some one-way function g(•). We, however, stress that for our approach in this paper it does not matter how T is exactly constructed (beyond being the encryption of a per-user unique value).

All-or-Nothing Public Key Encryption With Equality Tests

Following the work of Tang [Tan12a, Tan12b], Slamanig et al. [START_REF] Slamanig | Adding Controllable Linkability to Pairing-Based Group Signatures for Free[END_REF] modified the concept of all-or-nothing public key encryption with equality tests (AoN-PKeet * ). The idea of AoN-PKeet [START_REF] Tang | Public Key Encryption Schemes Supporting Equality Test with Authorisation of Different Granularity[END_REF][START_REF] Tang | Public Key Encryption Supporting Plaintext Equality Test and User-Specified Authorization[END_REF] is to allow specific entities in possession of a trapdoor to perform equality tests on ciphertexts without learning the underlying plaintexts. Slamanig et al. additionally require this primitive to be compatible with efficient zero-knowledge proofs regarding the plaintexts, to ensure compatibility with GSSs following the SEP paradigm.

An AoN-PKeet * scheme (KeyGen, Enc, Dec, Aut, Com) is a conventional (at least IND-CPA secure) public key encryption scheme (compatible with efficient zero-knowledge proofs) augmented by two additional algorithms Aut and Com (cf. [START_REF] Slamanig | Adding Controllable Linkability to Pairing-Based Group Signatures for Free[END_REF] for a formal treatment).

Aut(sk e ) : Takes the private decryption key sk e of the public key encryption scheme and returns a trapdoor tk that allows for equality tests. Com(T, T , tk) : Takes two ciphertexts (T , T ) and a trapdoor tk and returns 1 if both ciphertexts encrypt the same (unknown) message and 0 otherwise.

Definition 3 ([SSU14]

). An AoN-PKeet * scheme is called secure if it is sound, provides OW-CPA security against Type-I adversaries (trapdoor holders) and if the underlying encryption scheme provides IND-CPA/IND-CCA security against Type-II adversaries (outsiders).

Construction from ElGamal. In a bilinear group setting where the (S)XDH assumption is assumed to hold, one can rely on ElGamal encryption in G 1 .

Let the private key be a random element ξ ← R Z p and the corresponding public key be h ← g ξ ∈ G 1 , then the encryption of a message m is computed as T = (T 1 , T 2 ) = (g α , mh α ) for a randomly chosen element α ← R Z p . The trapdoor generation and comparison algorithms are as follows:

Aut(ξ) : Return the trapdoor tk ← (r, t = rξ ) ∈ G 2 2 for a random r ← R G 2 . Com(T, T , tk) : Given two ciphertexts T = (T 1 , T 2 ) = (g α , mh α ) and T = (T 1 , T 2 ) = (g α , m h α ) and a trapdoor tk = (r, t = rξ ), return 1 if e(T 2 , r) • e(T 1 , t) -1 = e(T 2 , r) • e(T 1 , t) -1
holds and 0 otherwise.

Lemma 1 ([SSU14]

). Under the co-CDH assumption AoN-PKeet * based on ElGamal in G 1 in an (S)XDH setting is secure.

3 Non-Interactive Plaintext (In-)Equality Proofs

We are interested in plaintext equality and inequality proofs where the prover neither knows the randomness used for encryption, nor the decryption key and consequently also does not know the plaintexts. By employing the idea of AoN-PKeet * [SSU14], the prover can use a trapdoor to determine whether two ciphertexts encrypt the same unknown plaintext, while not being able to decrypt. This, in turn, allows the prover to select which type of proof to conduct. Moreover, for AoN-PKeet * schemes in the pairing setting, we can use the pairing product equation that is used by the Com algorithm and a suitable proof framework to prove (1) knowledge of a trapdoor that is consistent with the respective public key and (2) the satisfiability of the pairing product equation corresponding to Com when used with the non-revealed trapdoor on two ciphertexts in question. As we will see later, this allows us to prove plaintext equality in a straightforward way, while plaintext inequality requires a slightly more sophisticated approach.

A Generic Construction

Let PKEQ = (KeyGen, Enc, Dec, Aut, Com) be a secure AoN-PKeet * scheme.

Building upon PKEQ, we define a generic non-interactive proof system Π thatfor two ciphertexts T and T under some public key pk-allows to prove knowledge of a trapdoor tk that either attests membership of (T, T , pk) in a language L R∈ or in a language L R / ∈ . The corresponding NP-relations are defined as follows:

((T, T , pk), tk) ∈ R ∈ ⇐⇒ Com(T, T , tk) = 1 ∧ tk ≡ pk, ((T, T , pk), tk) ∈ R / ∈ ⇐⇒ Com(T, T , tk) = 0 ∧ tk ≡ pk,
where tk ≡ pk denotes that tk corresponds to pk and we omit BG for simplicity.

To obtain a non-interactive proof system Π with the desired expressiveness, we compose two non-interactive proof systems, namely Π ∈ and Π / ∈ . Here, Π ∈ covers statements in L R∈ , whereas Π / ∈ covers statements in L R / ∈ . It is easy to see that-by the soundness of PKEQ-each tuple ((T, T , pk), tk) is either in R ∈ or in R / ∈ . Membership can be efficiently checked using the Com algorithm. The non-interactive proof system Π is presented in Scheme 1, where we assume that one can efficiently decide for which language a given proof π has been computed. a With Π ∈, / ∈ we denote that both proof systems are with respect to the same bilinear group description.

Scheme 1: NIPEI Proof System

We call a non-interactive plaintext equality and inequality (NIPEI) proof system secure if it is perfectly complete, perfectly sound, and at least computationally zero-knowledge. The subsequent lemma trivially follows from the fact that L R∈ and L R ∈ are disjoint.

Lemma 2. If Π ∈ and Π / ∈ are secure NIZK proof systems, then the resulting NIPEI proof system Π is also secure. Thereby, for every security property p ∈ of Π ∈ and corresponding security property p / ∈ of Π / ∈ , Π inherits p ∈ if p ∈ is implied by p / ∈ and p / ∈ otherwise. That is, Π inherits the weaker security notion of both.

Instantiation with PKEQ From ElGamal Encryption

We will now present a concrete instantiation of a NIPEI proof system in the SXDH setting where the PKEQ scheme is based on ElGamal encryption in G 1 . Recall that the public key is pk = g ξ ∈ G 1 , the trapdoor is tk = (r, t = rξ ) ∈ G2 2 and for two ciphertexts T and T , Com(T, T , tk) checks whether e(T 2 , r) • e(T 1 , t) -1 = e(T 2 , r) • e(T 1 , t) -1 holds. If so, the ciphertexts encrypt the same plaintexts and different plaintexts otherwise. Subsequently, we present the relations R ∈ and R / ∈ for this PKEQ scheme. For membership in R ∈ , the following PPEs need to be satisfied:

(((T 1 , T 2 ), (T 1 , T 2 )), (r, t)) ∈ R ∈ ⇐⇒ e(g ξ , r) • e(g -1 , t) = 1 G T ∧ r = 1 G2 ∧ t = 1 G2 ∧ e(T 2 • T -1 2 , r) • e(T -1 1 • T 1 , t) = 1 G T . (1)
By the soundness of the underlying PKEQ scheme, the PPEs above deliver the desired soundness properties for membership in R ∈ . For membership in R / ∈ , we have to exchange the last literal in the conjunction of the PPEs above by

e(T 2 • T -1 2 , r) • e(T -1 1 • T 1 , t) = 1 G T .
It is important to note that an inequality (as in the second part of the conjunction) cannot be proven using GS.

Instantiation of Π ∈ . We use the GS-based commit-and-prove scheme from [START_REF] Escala | Fine-Tuning Groth-Sahai Proofs[END_REF]. Thereby, the advantage is that it is possible to reach composable zeroknowledge even when reusing commitments in proofs for different statements. Consequently, we can include commitments to r and t in the CRS and we can reuse these commitments to prove the satisfiability of the following PPE

2 i=1 e(A i , Ŷi ) = e(T 2 • T -1 2 , r) • e(T -1 1 • T 1 , t) = 1 G T ,
where the prover is given access to the openings of the commitments and the underlined values are not revealed to the verifier. The fact that the commitments are already contained in the CRS forces the prover to use commitments to the actual values which are consistent with the public key (instead of plugging in r = 1 G2 , t = 1 G2 as the trivial solution). 2 The corresponding proof is very simple and can be communicated with two group elements in G 1 .3 Since our instantiation is a straightforward application of the GS-based commit-and-prove scheme, we obtain the following lemma:

Lemma 3. Π ∈ provides perfect completeness, perfect soundness and-because of the form of the PPE-composable zero-knowledge.4

Instantiation of Π / ∈ . To construct a proof for plaintext inequality statements, we build upon a recent technique by Blazy et al. [START_REF] Blazy | Non-Interactive Zero-Knowledge Proofs of Non-Membership[END_REF]. They proposed a generic way to (non-interactively) prove non-membership claims with respect to a language in zero-knowledge and provide multiple instantiations of their framework based on combinations of SPHFs and GS proofs. Informally, their generic technique for proving non-membership works as follows. They use a non-interactive proof system Π 1 that allows to prove possession of a witness demonstrating the membership of some statement in some language, where the respective proof fails. Then, they use a non-interactive proof system Π 2 that allows to prove that Π 1 .Proof has been computed honestly. This way, it is possible to express non-membership statements by producing a proof such that Π 1 .Verify returns 0 and proving that the proof itself was honestly computed (since otherwise such a faulty proof would be trivially computable).

We will build our instantiation upon a SPHF for Π 1 (where we can use the SPHF framework from [BBC + 13a], which allows to prove the required statements) and GS proofs for Π 2 . However, in contrast to how this technique is used in [START_REF] Blazy | Non-Interactive Zero-Knowledge Proofs of Non-Membership[END_REF], in our setting the verifier does not know the randomness of the commitments. This imposes an additional technicality to be discussed below. In particular, we additionally compute the hash value H using ProjHash on the prover side and prove that H was honestly computed using an additional non-interactive zero-knowledge proof system Π 3 (which we instantiate with GS proofs). In Scheme 2, we present our non-interactive proof system for membership in a language L R / ∈ that contains all tuples (T, T , pk, C tk ), where the trapdoor committed to in C tk allows to demonstrate plaintext inequality. For simplicity, crs is for Π 1 and Π 3 . A nice thing to note (which will allow us to improve the efficiency of Π / ∈ ) is that we do not need to simulate the proof φ. We will only require the proof to completely hide hk, i.e., to be witness indistinguishable.

P : LR ∈ , (T, T , pk, C tk ) ∈ LR ∈ , R tk , crs V : LR ∈ , (T, T , pk, C tk ),
Likewise to Π ∈ , we can include the commitments C tk to tk in the CRS and use these commitments in the SPHF. Accordingly, the corresponding PPE simplifies to e(T

2 • T -1 2 , r) • e(T -1 1 • T 1 , t) = 1 G T .
We additionally include commitments C R to the randomness R tk used to compute C tk in the CRS. Then we can use these commitments together with the GS-based commit-and-prove scheme from [START_REF] Escala | Fine-Tuning Groth-Sahai Proofs[END_REF] to prove the honest computation of the projective hash value more efficiently. Likewise to the other commitments in the CRS, this ensures that the prover uses the correct values (while also ensuring the simulatability).

Since the instantiation of Π 1 , Π 2 , and Π 3 with the required properties is quite involved, we provide a detailed description in Appendix C and Appendix D, respectively. Finally, for Scheme 2 we can show the following: Theorem 1. If Π 1 is correct and the verifier cannot distinguish a failing proof (i.e., H) from random, Π 2 is complete, sound and witness indistinguishable, Π 3 is complete, sound and zero-knowledge, then Π / ∈ is also complete, sound and zero-knowledge.

We prove Theorem 1 in Appendix D.3. By combining Lemma 2, Lemma 3, and Theorem 1 we straightforwardly derive the following corollary for our instantiation of the proof system Π = (Π ∈ , Π / ∈ ). Corollary 1. The NIPEI proof system Π obtained by combining the above instantiations of Π ∈ and Π / ∈ is secure, i.e., complete, sound, and zero-knowledge. Instantiations with Other Encryption Schemes. For simplicity, we have presented an instantiation in the SXDH setting using ElGamal, but it is straightforward to adapt to Cramer-Shoup [START_REF] Cramer | A Practical Public Key Cryptosystem Provably Secure Against Adaptive Chosen Ciphertext Attack[END_REF] or twin-ElGamal [START_REF] Delerablée | Dynamic Fully Anonymous Short Group Signatures[END_REF]. Furthermore, it is easy to adapt it to the DLIN setting and the corresponding linear encryption schemes.

GSSs with Verifiable Controllable Linkability

Subsequently, we propose a model for group signatures that considers verifiable controllable linkability and builds upon the model of Hwang et al. [HLhC + 11, HLC + 13, HCCN15] who formalized controllable linkability. Moreover, we consider the extension to the BSZ [BSZ05] model of Sakai et al. [SSE + 12], i.e., opening soundness. The model involves three authorities: an issuing authority possessing the master issuing key (mik), an opening authority possessing the master opening key (mok), and a linking authority possessing the master linking key (mlk).

Model for GSSs with Verifiable Controllable Linkability

We now define GSSs with verifiable controllable linkability (VCL-GS). Definition 4. A VCL-GS is a tuple of efficient algorithms GS = (GkGen, UkGen, Join, Issue, GSig, GVf, Open, Judge, Link, Judge Link ), which are defined as follows.

GkGen(1 κ ) : On input a security parameter κ, this algorithm generates and outputs a tuple (gpk, mok, mik, mlk), representing the group public key, the master opening key, the master issuing key, and the master linking key. UkGen(1 κ ) : On input a security parameter κ, this algorithm generates a user key pair (usk i , upk i ). Join(usk i , upk i ) : On input the user's key pair (usk i , upk i ), this algorithm interacts with Issue and outputs the group signing key gsk i of user i.

Issue(gpk, mik, reg) : On input of the group public key gpk, and the master issuing key mik and the registration table reg, this algorithm interacts with Join to add user i to the group. GSig(gpk, M, gsk i ) : On input of the group public key gpk, a message M , and a user's secret key gsk i , this algorithm outputs a group signature σ. GVf(gpk, M, σ) : On input of the group public key gpk, a message M , and a signature σ, this algorithm verifies whether σ is valid with respect to M and gpk. If so, it outputs 1 and 0 otherwise. Open(gpk, reg, M, σ, mok) : On input of the group public key gpk, the registration table reg, a message M , a valid signature σ, and the master opening key mok, this algorithm returns the signer i together with a publicly verifiable proof τ attesting the validity of the claim. If no group member produced σ, ⊥ is returned. Judge(gpk, M, σ, i, upk i , τ ) : On input of the group public key gpk, a message M , a valid signature σ, the claimed signer i, the public key upk i as well as a proof τ , this algorithm returns 1 if τ is a valid proof that i produced σ and 0 otherwise. Link(gpk, M, σ, M , σ , mlk) : On input of the group public key gpk, a message M , a corresponding valid signature σ, a message M , a corresponding valid signature σ and the master linking key mlk, this algorithm determines whether σ and σ have been produced by the same or different signers and returns the linking decision b ∈ {1, 0} as well as a publicly verifiable proof ρ attesting the validity of this decision. Judge Link (gpk, M, σ, M , σ , b, ρ) : On input of the group public key gpk, a message M , a corresponding valid signature σ, a message M , a corresponding valid signature σ , a linking decision b as well as the corresponding linking proof ρ, this algorithm returns 1 if ρ is a valid proof for b with respect to σ and σ and 0 otherwise. In addition to the above, in the vein of Sakai et al., we introduce the additional notion of linking soundness. We only consider a strong variant, where the adversary has access to all keys. Informally, linking soundness targets contradicting linking proofs, where the signatures as well as the proofs may be maliciously generated, yet accepted by GVf and Judge Link , respectively. In contrast, E-linkability targets contradicting results of Open and Link for maliciously generated signatures, where Open, Judge, and Link are honestly computed. Subsequently, we present a definition of linking soundness.

Definition 5 (Linking Soundness). A group signature scheme GS with verifiable controllable linkability is said to provide linking soundness if for any adversary A and any κ ∈ N, Pr[Exp ls GS,A (κ) = 1] ≤ (κ). The experiment Exp ls GS,A is formally defined in Figure 1 of Appendix E.

Verifiable Controllable Linkability

Recall that in group signatures with controllable linkability the LA runs the Com algorithm of a PKEQ scheme to decide whether two ciphertexts contain the same unknown plaintext. Publishing the required trapdoor key tk would allow any party to link any two group signatures, which is clearly not desired. However, by means of our proposed NIPEI proof system we are able to allow the LA to prove whether or not any two signatures stem from the same signer without being able to identify the signer(s) and still only requiring tk. Subsequently, we show how our generic construction for NIPEI proofs can be used to realize verifiable controllable linkability for group signatures following the SEP paradigm. Thereby, we assume that the used PKEQ is defined for bilinear groups, such that it is possible to set up the PKEQ and the proof systems in a compatible way. To this end, we assume that the group public key gpk contains a bilinear group description BG. Then, the modified group key generation algorithm GkGen looks as follows:

GkGen (1 κ ) : Run (gpk, mok, mik, mlk) ← GkGen(1 κ ) and obtain BG from gpk.

Then, run crs ← Π.CRSGen(BG), set gpk ← (gpk, crs) and return (gpk , mok, mik, mlk).

Furthermore, the algorithms Link and Link Judge operate as follows:

Link(gpk, M, σ, M , σ , mlk) : Extract the ciphertexts T and T from σ and σ , respectively. Obtain BG, pk e from gpk and tk from mlk. Compute ρ ← Π.Prove(BG, crs, (T, T , pk e ), tk) and return the linking decision b and the corresponding proof ρ. Link Judge (gpk, M, σ, M , σ , b, ρ) : Extract the ciphertexts T and T from σ and σ .

Obtain BG, crs and pk e from gpk. If b = 1 and ρ is a proof for language L R / ∈ or vice versa, return ⊥. Otherwise, return Π.Verify(BG, crs, (T, T , pk e ), ρ).

Security Analysis. We investigate to which extent the extension of a group signature scheme with controllable linkability (i.e., the constructions in [HLhC + 11, HLC + 13, HCCN15] and the generic conversion from [START_REF] Slamanig | Adding Controllable Linkability to Pairing-Based Group Signatures for Free[END_REF]) to one with verifiable controllable linkability requires to re-evaluate the original security properties. Note that the proof of the subsequent theorem is quite independent of the concrete definition of anonymity and works for group signature schemes providing the weaker anonymity notion by Hwang et al., but also with stronger notions such as CPA-full or CCA2-full anonymity (cf. the discussion in Appendix E).

Theorem 2. Let GS = (GkGen, UkGen, Join, Issue, GSig, GVf, Open, Judge, Link) be a secure group signature scheme with controllable linkability with or without (weak) opening soundness, let Π be a secure NIPEI proof system, and let PKEQ = (KeyGen, Enc, Dec, Aut, Com) be the used AoN-PKeet * scheme, where PKEQ is compatible with Π. Then, GS = (GkGen, UkGen, Join, Issue, GSig, GVf, Open, Judge, Link, Judge Link ) is a secure group signature scheme with verifiable controllable linkability with or without (weak) opening soundness.

We prove Theorem 2 in Appendix E.1.

Instantiating Π / ∈ for Group Signatures with Σ-Proofs. Many existing GSSs following the SEP paradigm are instantiated using the RO heuristic. Now, if one already relies on the ROM for the GSS, it might be an alternative to instantiate parts of Π / ∈ (i.e., Π 2 and Π 3 ) using a non-interactive Σ protocol obtained via the Fiat-Shamir transform, which is specifically crafted for the application with verifiable controllable linkability and the used SPHF instantiation. In Appendix D.4, we illustrate such an instantiation of Π / ∈ .

Decision Linear Assumption (DLIN). Let G = u = v = h be a group of prime order p, such that log 2 p = κ. Then, for all PPT adversaries A there exists a negligible function (•) such that:

Pr b ← R {0, 1}, r, s, t ← R Z p , b * ← A(u, v, h, u r , v s , h b•(r+s)+(1-b)•t ) : b = b * ≤ 1 2 + (κ).
Computational co-Diffie-Hellman Assumption (co-CDH). Let G 1 = g , and G 2 = ĝ be two distinct groups of prime order p, such that log 2 p = κ.

Then, for all PPT adversaries A there exists a negligible function (•) such that: Pr r ← R Z p , ĥ ← A(g, g r , ĝ) : ĥ = ĝr ≤ (κ).

External Diffie-Hellman Assumption (XDH). Let G 1 , G 2 , and G T be three cyclic groups of prime order p and let e : G 1 × G 2 → G T be a pairing. Then, the XDH assumption states that the DDH assumption holds in G 1 . Symmetric External Diffie-Hellman Assumption (SXDH). Let G 1 , G 2 , and G T be three cyclic groups of prime order p and e : G 1 × G 2 → G T a pairing. Then, the SXDH assumption states that the DDH assumption holds in G 1 and G 2 .

B Security of Non-Interactive Proof Systems

In the following, we state the security properties required for our construction (adapted from [START_REF] Groth | Efficient Non-interactive Proof Systems for Bilinear Groups[END_REF]).

Definition 6 (Perfect Completeness). A non-interactive proof system is perfectly complete, if for all adversaries A it holds that

Pr     BG ← BGGen(1 κ ), crs ← CRSGen(BG), (x, w) ← A(BG, crs), π ← Proof(BG, crs, x, w) : Verify(BG, crs, x, π) = 1 ∧ (BG, x, w) ∈ R     = 1.
Definition 7 (Perfect Soundness). A non-interactive proof system is perfectly sound, if for all adversaries A it holds that

Pr   BG ← BGGen(1 κ ), crs ← CRSGen(BG), (x, π) ← A(BG, crs) : Verify(BG, crs, x, π) = 1 ∧ x / ∈ L R   = 0.
Definition 8 (Witness Indistinguishability). A non-interactive proof system is composably witness indistinguishable, if there exists a simulator S such that for all PPT adversaries A there exists a negligible function (•) such that:

Pr BG ← BGGen(1 κ ), crs ← CRSGen(BG) : A(BG, crs) = 1 - Pr BG ← BGGen(1 κ ), crs ← S(BG) : A(BG, crs) = 1 ≤ (κ),
and

Pr   b ← R {0, 1}, BG ← BGGen(1 κ ), crs ← S(BG), (x, w 0 , w 1 , st) ← A(BG, crs), π ← Proof(BG, crs, x, w b ), b * ← A(π, st) : b = b * ∧ (BG, x, w 0 ) ∈ R ∧ (BG, x, w 1 ) ∈ R   = 1 2 .
Definition 9 (Zero-Knowledge). A non-interactive proof system is composably zero-knowledge, if there exist two simulators S 1 and S 2 such that for all PPT adversaries A there exists a negligible function (•) such that: Here, T denotes a simulation trapdoor.

Pr BG ← BGGen(1 κ ),

C Security and Instantiation of SPHFs

Security Properties. The correctness requires that Hash(hk, L, W ) = Proj-Hash(hp, L, W, w) for all W ∈ L and their corresponding witnesses w. Smoothness requires that if W ∈ L, the following distributions are statistically indistinguishable:

{(L, pp, W, hp, H ) | param ← Setup(1 κ ), hk ← HashKG(L), hp ← ProjKG(hk, L, W ), H ← Hash(hk, L, W )} ≈ {(L, pp, W, hp, H ) | param ← Setup(1 κ ), hk ← HashKG(L), hp ← ProjKG(hk, L, W ), H ← R Dom(Hash)}
The pseudo-randomness requires that if W ∈ L, then without a witness of membership the distributions considered in smoothness remain computationally indistinguishable. We call a SPHF secure if it satisfies all the above properties.

Languages that can be used with SPHFs have recently been extended to every kind of pairing product equations over graded rings [BBC + 13a]. These constructions build upon SPHFs on linear Cramer-Shoup ciphertexts [GL03, BBC + 13a], but can easily be adapted to the SXDH setting.

Instantiation of the SPHF. For efficiency reasons, we use ElGamal commitments together with the SPHF on ElGamal ciphertexts as proposed by Gennaro and Lindell [START_REF] Gennaro | A Framework for Password-Based Authenticated Key Exchange[END_REF]. In Scheme 3, we recall the aforementioned SPHF for

Computing the hash value using the hashing key hk i = (η i , θ) ∈ Z 2 p for i ∈ {1, 2} yields:

H ← 2 i=1 e(A i , ûηi i êθ i ) = 2 i=1 e(A i , ĝηiri • Ŷ θ i • pk riθ ) = 2 i=1 e(A i , (ĝ ηi pk θ ) ri ) • e(A i , Ŷ θ i ) (ii) = H,
where for the last step (ii), we know that 2 i=1 e(A i , Ŷi ) = 1 G T by definition. While the PPE above is tailored to our specific setting, this approach also works for arbitrary i ∈ N. Subsequently, we prove smoothness (for the general case) by adapting the proof strategy from [BBC + 13a, GL03]: Proof (Smoothness). We can without loss of generality assume that one of the n ElGamal commitments encrypts a value such that the overall PPE is not fulfilled. In particular, this means that at least one commitment is of the form (g ri , Ŷi • pk r i ) ∈ G 2 2 , where r i = r i . With hp i = ĝηi pk θ , the hash value H is defined to be:

H ← n i=1 e(A i , ĥi ), where ĥi = (ĝ riηi ( Ŷi • pk r i ) θ ).
We can rewrite ĥi as ĥi = (ĝ riηi pk r i θ ) • Ŷ θ i . Assuming that Ŷ θ i cancels out when plugging into the pairing product equation, it suffices to consider the following discrete logarithms: log ĝ ĥi = r i η i + r i x pk θ, and log ĝ hp i = η i + x pk θ.

As we know that r i = r i we have that these two values are linearly independent, which shows that H looks perfectly random.

Proof (Pseudo-Randomness). We know that smoothness holds. We prove pseudorandomness by showing that a distinguisher between the distributions considered in smoothness and pseudo-randomness is a distinguisher for DDH. For simplicity we assume that i = 1. We obtain a DDH instance (ĝ r , ĝs , ĝt ) ∈ G 3 2 and compute the ciphertext to Ŷ1 as (ĝ r , Ŷ1 • ĝt ), set pk ← ĝs , choose hk 1 = (η, θ) ← R Z 2 p and set hp 1 ← ĝη pk θ . Consequently, if we have a valid DDH instance, we have a distribution as in the pseudo-randomness game, whereas we have a distribution as in the smoothness game if the DDH instance is random.

By a standard hybrid argument, this proof can be extended to arbitrary i ∈ N .

D Instantiation of Non-Interactive Proof Systems for Π /

∈

For our instantiations of Π 2 and Π 3 we use the following observation to obtain the zero-knowledge property for Π / ∈ : The value H (computed using Hash) looks perfectly random to the verifier, whereas the value H (computed using ProjHash) looks computationally random to the verifier. Furthermore, the values H and H are not fixed prior to the proof, meaning that the prover can choose them at the time when computing the proof to ensure simulatability. Let us briefly recall the setup with i ∈ {1, 2}:

hk i = (η i , θ) ∈ R Z 2 p , hp i = ĝηi pk θ ∈ G 2 , H = i e(A i , ûηi i êθ i ) = e(A 1 , ûη1 1 êθ 1 ) • e(A 2 , ûη2 2 êθ 2 ) = e(A 1 , ĥ1 ) • e(A 2 , ĥ2 ) ∈ G T , C i = (û i , êi ) = (ĝ ri , Ŷi • pk ri ) ∈ G 2
2 , where Ŷ1 = r and Ŷ2 = t, H = i e(A i , hp ri i ). Here, A 1 , A 2 , hp = (hp 1 , hp 2 ), C tk = (C 1 , C 2 ) are available to the prover and the verifier and the verifier also learns H and H during the proof. The values r i , hk i and ĥ = ( ĥ1 , ĥ2 ) are only known to the prover.

D.1 Instantiation of Π 2

To prove the consistency of H and hp with respect to hk using the GS commitand-prove approach, we prove the validity of the following conjunction of PPEs, where the underlined values are not revealed to the verifier: e(g, hp i ) = e(g ηi , ĝ) • e(g θ , pk) ∧ e(g, ĥi ) = e(g ηi , ûi ) • e(g θ , êi )

∧ H = i e(A i , ĥi ).
As we only require witness indistinguishability for Π 2 , the GS framework allows to straightforwardly prove equations of the form above. We require the commitment to g for the first and the second literal to be included in the CRS to ensure that the prover uses the correct values while ensuring enough freedom for the simulator of our overall proof system Π / ∈ .

D.2 Instantiation of Π 3

When proving the consistency of H and hp with respect to r i using the GS commit-and-prove approach, one can observe that-as long as hk is unknownthe values hp i constitute random values in G 2 and the values hp ri i look random under DDH in G 2 . Thus, one only has to prove the satisfiability of e(g ri , hp i ) = e(g, hp ri i ),

and the verifier can compute H ← i e(A i , hp ri i ) on its own. The commitments to g and g ri are included in the CRS to ensure that the prover uses the correct values while the simulator can use commitments to 1 G1 .

Using standard Groth-Sahai techniques, this PPE admits efficient non-interactive zero-knowledge proofs.

We note that although the Groth-Sahai framework allows us to prove a statement like Equation (3) in a zero-knowledge way, we still need to argue that revealing the hp ri i does not reveal too much information in the global scheme (as we do subsequently in the proof of Theorem 1).

D.3 Proof of Theorem 1

Proof. While completeness follows from inspection, we subsequently prove soundness and zero-knowledge.

Soundness:

We setup the CRSs of the GS proof systems Π 2 and Π 3 so that they provide perfect soundness. Under the CRS indistinguishability of GS proofs, the prover will only be able to distinguish this setup from the perfect witness indistinguishability/zero knowledge setup with negligible probability. Then the perfect soundness of Π 2 and Π 3 guarantees the honest computation of the hash values H and H , whereas the perfect correctness of the SPHF guarantees that H = H only holds if the proven statement is actually true. Thus, the overall proof system provides perfect soundness as long as the CRS indistinguishability holds. Zero-knowledge: We setup the CRSs of the GS proof systems Π 2 and Π 3 so that they provide perfect witness indistinguishability/zero knowledge. Under the CRS indistinguishability of GS proofs, the prover will only be able to distinguish this setup from the perfect soundness setup with negligible probability. Subsequently, we prove zero-knowledge using a sequence of games. Game 0: The original zero-knowledge game.

Game 1: We pick hp i ← R G 2 . Furthermore, we use random values ĥi ← R G 2 inside ĥi , defining a random H . Finally, instead of the actual commitments to g, g ηi , and g θ we use commitments to 1 G1 . Transition Game 0 → Game 1: Since the witness indistinguishability of Π 2 is perfect, the adversary will not be able to detect this game change (H already looks perfectly random under the smoothness of the SPHF; H = H will only occur with negligible probability). Game 2: We simulate the GS proof ψ and, thereby, use commitments to 1 G1 instead of the actual values g and g ri . Transition Game 1 → Game 2: Since the zero-knowledge property of Π 3 is perfect, the adversary will not be able to detect this game change. Game 3: We pick

hp ri i ← R G 2 . Transition Game 2 → Game 3: Besides hp ri i ← R G 2
, the only components depending on the values r i are contained in C tk = (C 1 , C 2 ) = ((ĝ r1 , Ŷ1 • pk r1 ), (ĝ r2 , Ŷ2 • pk r2 )). To see that Game 2 and Game 3 are indistinguishable, assume that the simulator obtains a DDH instance (ĝ, ĝs1 , ĝt1 , ĝr1 ), and-by the random self reducibility of DDH-generates a second instance (ĝ, ĝs2 , ĝt2 , ĝr2 ). For i ∈ {1, 2}, it sets (ĝ, ĝri , hp i , hp ri i ) ← (ĝ, ĝsi , ĝti , ĝr i ) and computes Ŷi • pk ri by using the secret key sk corresponding to pk, i.e., as Ŷi • (ĝ ri ) sk . Then, if the DDH instance is valid we have a distribution as in Game 2, whereas we have a distribution as in Game 3 if the DDH instance is random. Again H = H only occurs with negligible probability. Game 4: We replace the commitments to tk, i.e., C tk , in the CRS by commitments to random values. Transition Game 3 → Game 4: By the hiding property of the commitments, this game change will remain indistinguishable for the adversary (again, H = H only occurs with negligible probability).

The last game represents a game that is simulated without knowledge of the trapdoor tk, whereas the first game represents the real game. Both games are indistinguishable, which proves the zero-knowledge property.

D.4 Instantiation of Π 2 and Π 3 with Σ-Protocols

Let us recall where we require WI or NIZK proofs in Π / ∈ : Namely, a WI proof φ to prove the consistency of the hash value, the projection key and the hash key as well as a NIZK proof ψ to prove the consistency of the hash value, the projection key and the commitments in the CRS. Furthermore, recall that the crs contains two commitments C 1 = (û 1 , ê1 ) = (ĝ r1 , r • pk r1 ), C 2 = (û 2 , ê2 ) = (ĝ r2 , t • pk r2 ), where the hashing/projection keys are chosen as hk i = (η i , θ) and hp i = ĝηi pk θ , i ∈ {1, 2}. Since we can as well instantiate φ as a NIZK proof, we combine the predicates for φ and ψ straightforwardly using an AND composition and obtain the following relation, where vi = hp ri i :

PoK (η 1 , η 2 , θ, ρ 1 , ρ 2 ) : H =

E Security for VCL Group Signatures

In the following, CU, HU, GSet represent the set of corrupted users, honest users, and message-signature pairs corresponding to queries to the challenge oracle, respectively. Furthermore, REG is the list of transcripts generated by the join process. , i.e., the adversary has no access to the Open oracle and the challenge oracle can only be called once. Without those restrictions, one can achieve the stronger notions of CPA-full and CCA2-full-anonymity (as defined in the BSZ model [START_REF] Bellare | Foundations of Group Signatures: The Case of Dynamic Groups[END_REF]) for this model.

E.1 Proof of Theorem 2

Proof. In all security games except the anonymity experiment, the adversary is in possession of the master linking key mlk. Thus, it is easy to see that the existing security notions with exception of anonymity are not influenced by the modifications. Now, what remains is to show that anonymity and that the new notion of linking soundness holds.

Anonymity. We show that anonymity holds using a sequence of games, where the event that the adversary wins Game i is denoted by S i : Game 0: The original anonymity game. Game 1: As the original game, but the proofs obtained from the linking oracle are simulated 8 without using the trapdoor key tk. Transition: Game 0 → Game 1: By the zero-knowledge property of Π, the adversary will only be able to distinguish Game 0 and Game 1 with negligible probability, i.e., | Pr[S 0 ] -Pr[S 1 ]| ≤ zk (κ). It is easy to see that the advantage of the adversary in Game 1 is the same as in the anonymity game without extensions. Observe that the signatures obtained from Ch b cannot be submitted to the Link oracle. This means that the (in-)equality decisions obtained from the simulated linking proofs are independent of the challenge bit b, while the simulation ensures that the proofs do not contain information about the trapdoor key tk. Taking all together, we obtain an upper bound of the advantage of an adversary in the anonymity game with extensions, i.e., Pr[S 0 ] ≤ Adv anon (κ) + zk (κ), where Adv anon denotes the advantage of an adversary in the plain anonymity game without extensions. Linking soundness. It is immediate that the output of an adversary against the linking soundness game contradicts the perfect soundness of the underlying proof system.

8 Observe that the zero-knowledge property of Π implies the existence of a simulator.

Scheme 2 :

 2 Scheme 2: NIPEI Proof System. P . . . Prover, V . . . Verifier.

≤

  crs ← CRSGen(BG) : A(BG, crs) = 1 -Pr BG ← BGGen(1 κ ), (crs, T) ← S 1 (BG) : A(BG, crs) = 1 BGGen(1 κ ), (crs, T) ← S 1 (BG), (x, w, st) ← A(BG, crs, T), π ← Proof(BG, crs, x, w) : A(π, st) BGGen(1 κ ), (crs, T) ← S 1 (BG), (x, w, st) ← A(BG, crs, T), π ← S 2 (BG, crs, x, T) : A(π, st) = 1   .

  i , ûηi i êθ i ) ∧ hp 1 = ĝη1 pk θ ∧ hp 2 = ĝη2 pk θ ∧ v1 = hp ρ1 1 ∧ v2 = hp ρ2 2 ∧ û1 = ĝρ1 ∧ û2 = ĝρ2 ,and the verifier additionally checks whether i e(A i , vi ) = H . The proof above can be instantiated by only revealing H , A i , C tk , hp i , hp ri i to the verifier.

1

  BGGen(1 κ ) : Takes a security parameter κ as input, runs BG ← Π ∈, / ∈ .BGGen(1 κ ) and returns BG. a CRSGen(BG) : Takes a bilinear group description BG as input, runs crs∈ ← Π∈.CRSGen(BG), and crs / ∈ ← Π / ∈ .CRSGen(BG), and outputs a common reference string crs ← (crs∈, crs / ∈ ). Proof(BG, crs, (T, T , pk), tk) : Takes a bilinear group description BG, a common ref-

erence string crs, a statement (T, T , pk), and a witness tk. If ((T, T , pk), tk) ∈ R∈, return π∈ ← Π∈.Proof(BG, crs∈, (T, T , pk), tk). Otherwise, return π / ∈ ← Π / ∈ .Proof(BG, crs / ∈ , (T, T , pk), tk). Verify(BG, crs, (T, T , pk), π) : Takes a bilinear group description BG, a common reference string crs, a statement (T, T , pk) and a proof π. If π is for language LR ∈ return Π∈.Verify(BG, crs∈, (T, T , pk), π) and if π is for language LR / ∈ return Π / ∈ .Verify(BG, crs / ∈ , (T, T , pk), π).

  Now we present the security properties for group signature schemes with verifiable controllable linkability. They are adopted from the model of Hwang et al. [HLhC + 11, HLC + 13, HCCN15] for GSSs with controllable linkability, which builds upon the BSZ [BSZ05] model.5 In addition to the properties correctness, anonymity, non-frameability, and traceability defined in the BSZ model, Hwang et al. [HLhC + 11, HLC + 13, HCCN15] introduced properties to cover controllable linkability, namely LO-linkability (link-only linkability), JP-unforgeability (judge-proof unforgeability), and E-linkability (enforced linkability). Additionally, we integrate the proposal of Sakai et al. [SSE + 12] who introduced the additional property of (weak) opening soundness as an optional property.6 We briefly sketch them below and present formal definitions in Appendix E. Colluding issuers, users, linkers, and openers are not able to produce two different (contradicting) opening proofs, even when allowed to corrupt users and/or the opener. 7

	-Traceability: All valid signatures open correctly and allow to compute a
	valid opening proof.
	-Non-Frameability: No entity is able to produce a valid opening proof that
	falsely accuses an honest user as the signer.
	-JP-Unforgeability: The linking key is not useful to generate valid opening
	proofs.
	-LO-Linkability: The linking key is only useful to link signatures, but not
	to open signatures.
	-E-Linkability: Colluding users, linkers, and openers are not able to gener-
	ate two message-signature pairs yielding contradicting opening and linking
	decisions.
	-Opening Soundness:
	-Anonymity: Signers remain anonymous for all entities except for the open-
	ing authority.

  The oracles SndToU, AddU, WReg, RReg, GSig, USK, and CrptU represent a send to user oracle (by a corrupted issuer), an add user oracle, a write registration table oracle, a read registration table oracle, a group signing oracle, a user secret key oracle, and a corrupt user oracle. Furthermore, Ch b represents the challenge oracle. We note that the model of Hwang et al. [HLhC + 11, HLC + 13, HCCN15] does only consider a weaker version of CPAfull-anonymity[START_REF] Boneh | Short Group Signatures[END_REF]

As LR ∈ and LR / ∈ are disjoint, one can otherwise just run Verify for both languages.

For the simulation we may still use r = 1 G 2 , t = 1 G 2 .

This is due to the fact that-for equations of this type-one can omit the π part of a GS proof π = (π, θ) and only needs to send θ. In addition, due to the nature of the used projection map, the first components of theG 2 1 elements in θ ∈ G 2 1 × G 2 1are 1 G 1 , meaning that the proof only consists of two elements in G1.

We note that, due to using the commit-and-prove approach from[START_REF] Escala | Fine-Tuning Groth-Sahai Proofs[END_REF], we also use their composable zero-knowledge notion for commit-and-prove schemes. This notion can be seen as a generalization of standard composable zero-knowledge.

Actually, it uses a weaker anonymity notion similar to CPA-full anonymity[START_REF] Boneh | Short Group Signatures[END_REF], where the challenge oracle can only be called once.

We emphasize that this property is optional as there are no known GSSs with controllable linkability that have been shown to provide this property.

Note that Sakai et al. [SSE + 12] also introduced a weaker version of this property denoted as weak opening soundness.

This is the full version of a paper to appear at CT-RSA 2016. ‡ Supported by EU H2020 project Prismacloud, grant agreement n • 644962. § Supported by the Austrian Research Promotion Agency (FFG) and the Styrian Business Promotion Agency (SFG), grant agreement n • 836628 (SeCoS).

A Computational Hardness Assumptions

Decisional Diffie-Hellman Assumption (DDH). Let G = g be a group of prime order p, such that log 2 p = κ. Then, for all PPT adversaries A there exists a negligible function (•) such that:

the group G 2 in an SXDH setting, where the language L contains all triples (pk, C M , M ) of ElGamal public keys pk, ciphertexts C M with respect to pk and corresponding messages M , where membership in this language is witnessed by the used randomness r. Applying the techniques presented in [BBC + 13b,

Setup(1 κ ) : On input of κ, this algorithm generates a bilinear group description BG ← (p, G1, G2, GT , e, g, ĝ) such that G1, G2 and GT are groups of common prime order p with log 2 p = κ, e is a pairing, G1 = g and G2 = ĝ . It returns pp ← BG. HashKG(L) : On input of pp and L, this algorithm returns hk ← (η, θ) ← R Z 2 p . ProjKG(hk, L, W ) : On input of pp, hk, L and some word W = (pk, CM , M ), where CM = (ĝ r , M • pk r ) this algorithm computes and returns hp ← ĝη pk θ . Hash(hk, L, W ) : On input of pp, hk, L and W = (pk, CM , M ) ∈ G2 × G 2 2 × G2, where CM = (û, ê), this algorithm computes and returns H ← ûη ( ê/M ) θ . ProjHash(hp, L, W, w) : On input of pp, hp, L, W , w = r, this algorithm computes and returns H ← hp r .

Scheme 3: SPHF on ElGamal Ciphertexts [START_REF] Gennaro | A Framework for Password-Based Authenticated Key Exchange[END_REF] BBC + 13a] to the SPHF in Scheme 3, allows to prove satisfiability of pairing product equations. In our setting, we have PPEs of the form

where Ŷi are not revealed to the verifier and are thus encrypted using ElGamal (further denoted as

. Let the setup be as follows: θ ← R Z p and for i ∈ {1, 2}, η i ← R Z p , hk i = (η i , θ) ∈ Z 2 p as well as hp i = ĝηi pk θ , where hp = (hp 1 , hp 2 ) is handed over to the prover. Then the SPHF is defined as follows

Subsequently, we prove the following:

Lemma 4. The SPHF described above is a secure SPHF for a language defined by Equation 2.

Subsequently, we show correctness, smoothness, and pseudo-randomness.

Proof (Correctness). Let r 1 and r 2 be the randomness used to compute the encryptions of Ŷ1 and Ŷ2 , respectively (which represents the witness). Then, the projective hash value using the projection key hp i = ĝηi pk θ for i ∈ {1, 2} is computed as -If all of the following conditions hold, then return 1 and 0 otherwise

Experiment Exp lo-link GS,A (κ):

-If all of the following conditions hold, then return 1 and 0 otherwise • i 0 , i 1 ∈ HU;

• GSig(i 0 , •) and GSig(i 1 , •) and Open(M, σ) have not been queried;

-(gpk, mok, mik, mlk) ← GkGen(1 κ ), CU ← ∅, HU ← ∅, GSet ← ∅; -(i, M ) ← A SndToU,AddU,WReg,GSig,Open,USK,CrptU (gpk, mik, mlk); σ ← GSig(gpk, i, M ); τ ← A SndToU,WReg,GSig,Open,USK,CrptU (gpk, mik, mlk, i, M, σ); -If all of the following conditions hold, then return 1 and 0 otherwise

:

-If all of the following conditions hold, then return 1 and 0 otherwise

Experiment Exp e-link GS,A (κ):

-(gpk, mok, mik, mlk) ← GkGen(1 κ ), CU ← ∅, HU ← ∅, GSet ← ∅; -(M 0 , σ 0 , M 1 , σ 1 ) ← A SndToU,AddU,RReg,GSig,USK,CrptU (gpk, mok, mlk); -If GVf(gpk, M 0 , σ 0 ) = 0 or GVf(gpk, M 1 , σ 1 ) = 0 then return 0; -(i 0 , τ i 0 ) ← Open(gpk, REG, M 0 , σ 0 , mok)

-If Judge(gpk, i 0 , upk[i 0 ], M 0 , σ 0 , τ i 0 ) = 0 or Judge(gpk, i 1 , upk[i 1 ], M 1 , σ 1 , τ i 1 ) = 0 then return 0;

-(b, ρ) ← Link(gpk, M 0 , σ 0 , M 1 , σ 1 , mlk) -If Judge Link (gpk, M 0 , σ 0 , M 1 , σ 1 , b, ρ) = 0 then return 0; -If i 0 = i 1 and b = 1 (i.e., the two signatures link) then return 1; elif i 0 = i 1 and b = 0 (i.e., the two signatures do not link) then return 1; else return 0;

Experiment Exp ls GS,A (κ):

-(gpk, mok, mik, mlk) ← GkGen(1 κ ), CU ← ∅, HU ← ∅; -(s, M 0 , σ 0 , M 1 , σ 1 , b, ρ, b , ρ ) ← A WReg,CrptU (gpk, mik, mok, mlk); -If GVf(gpk, M 0 , σ 0 ) = 0 or GVf(gpk, M 1 , σ 1 ) = 0 then return 0; -If Judge Link (gpk, M 0 , σ 0 , M 1 , σ 1 , b, ρ) = 0 then return 0;

-If Judge Link (gpk, M 0 , σ 0 , M 1 , σ 1 , b , ρ ) = 0 then return 0;

-If b = b , then return 1; else return 0;