Javier Herranz

Fabien Laguillaumie

Benoît Libert

Carla Ràfols

Short Attribute-Based Signatures for Threshold Predicates

Keywords: Attribute-based signatures, constant signature size, efficiency

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

Attribute-based cryptography offers a real alternative to public-key cryptography when the systems to be protected also require anonymity among users following a security policy. In this setting, users obtain their secret keys from an authority as a function of their attributes. The operation involving the secret key proves somehow that the user holds a certain subset of attributes, without leaking information on his identity or on his total set of attributes.

One of the major issues in attribute-based cryptography is to save bandwidth, and in particular to get ciphertexts or signatures of constant size, i.e., not depending on the number of involved attributes. Other important issues are the construction of systems achieving security in the strongest possible model and being as expressive as possible, i.e., admitting a wide variety of policies. The goal of this work is to address the first question in the context of signature design.

Attribute-based cryptography first appeared in [START_REF] Goyal | Attribute-based encryption for fine-grained access control of encrypted data[END_REF] with an attribute-based encryption scheme, as an extension of fuzzy identity-based cryptosystems [START_REF] Sahai | Fuzzy identity-based encryption In Eurocrypt'05[END_REF]. Since then, the notion of attribute-based encryption (ABE for short, conjugated into key policy or ciphertext policy) has received a lot of attention (see for example [START_REF] Bethencourt | Ciphertext-policy attribute-based encryption[END_REF][START_REF] Herranz | Constant-size ciphertexts in threshold attribute-based encryption[END_REF][START_REF] Lewko | Fully secure functional encryption: attribute-based encryption and (hierarchical) inner product encryption[END_REF]), with many attempts to reduce the length of the ciphertexts (see [START_REF] Emura | A ciphertext-policy attribute-based encryption scheme with constant ciphertext length[END_REF][START_REF] Herranz | Constant-size ciphertexts in threshold attribute-based encryption[END_REF][START_REF] Attrapadung | Expressive key-policy attribute-based encryption with constant-size ciphertexts[END_REF]).

Attribute-based signatures (shortened as ABS in the sequel) have been introduced more recently in [START_REF] Maji | Attribute-based signatures[END_REF] (see also [START_REF] Shahandashti | Threshold attribute-based signatures and their application to anonymous credential systems[END_REF][START_REF] Li | Attribute-based signature and its applications[END_REF][START_REF] Li | Hidden attribute-based signatures without anonymity revocation[END_REF]). They are related to the notion of (threshold) ring signatures [START_REF] Rivest | How to leak a secret[END_REF][START_REF] Bresson | Threshold ring signatures and applications to ad-hoc groups[END_REF] or mesh signatures [START_REF] Boyen | Mesh signatures[END_REF], but offer much more flexibility and versatility to design secure complex systems, since the signatures are linked not to the users themselves, but to their attributes. As a consequence, these signatures have a wide range of applications, like private access control, anonymous credentials, trust negotiations, distributed access control mechanisms for ad hoc networks, attribute-based messaging... (see [START_REF] Maji | Attribute-based signatures[END_REF] for detailed descriptions of applications). In terms of security, ABS must first satisfy unforgeability, which guarantees that a signature cannot be computed by a user who does not have the right attributes, even if he colludes with other users by pooling together their secret keys. The other required security feature is the privacy of user's attributes, in the sense that a signature should not leak any information about the actual attributes that have been employed to produce it. Related work. Among the schemes proposed up to now, those of Maji, Prabhakaran, Rosulek proposed in [START_REF] Maji | Attribute-based signatures[END_REF] work for very expressive signing predicates, but their most practical scheme is only proven secure in the generic group model. In [START_REF] Okamoto | Efficient attribute-based signatures for non-monotone predicates in the standard model[END_REF], this scheme is claimed to be "almost optimally efficient", although its signatures' length grows linearly in the size of the span program (which is greater than the number of involved attributes in the signing predicate). Our result shows that this claim is not true, at least for some families of predicates (e.g., threshold). Some other instantiations in [START_REF] Maji | Attribute-based signatures[END_REF] are secure in the standard model, but are pretty inefficient (i.e., the signature size is linear in the security parameter of the scheme), because they use Groth-Sahai proofs for relations between the bits of elements in the group. Okamoto and Takashima designed in [START_REF] Okamoto | Efficient attribute-based signatures for non-monotone predicates in the standard model[END_REF] a fully secure ABS in the standard model which supports general non-monotone predicates. The scheme is not built upon non-interactive zero-knowledge proof systems, but on dual pairing vector spaces [START_REF] Okamoto | Homomorphic encryption and signatures from vector decomposition[END_REF] and uses proof techniques from functional encryption [START_REF] Lewko | Fully secure functional encryption: attribute-based encryption and (hierarchical) inner product encryption[END_REF]. Escala, Herranz and Morillo also proposed in [START_REF] Escala | Revocable attribute-based signatures with adaptive security in the standard model[END_REF] a fully secure ABS in the standard model, with the additional property of revocability, meaning that a third party can extract the identity of a signer in case of dispute (thanks to a secret that can be computed by the master entity). None of the previous schemes achieves constant-size signatures.

Our contribution. In this paper we propose the first attribute-based signature schemes which produce such short signatures, and which are proven secure in the selective-predicate setting (i.e., not fully secure), in the standard model. We design two constant-size ABS schemes, both built (nongenerically) on two different constant-size attribute-based encryption schemes. In both schemes, let n denote the maximum size of the admitted signing predicates.

-Our first scheme supports (weighted) threshold predicates for small4 universes of attributes.

Its design is inspired by the constant-size ciphertext-policy ABE scheme from [START_REF] Herranz | Constant-size ciphertexts in threshold attribute-based encryption[END_REF] by Herranz, Laguillaumie and Ràfols, in the sense that the signer implicitly proves his ability to decrypt a ciphertext by using the Groth-Sahai proof systems [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF], and by binding the signed message (and the corresponding predicate) to the signature using a technique suggested by Malkin, Teranishi, Vahlis and Yung [START_REF] Malkin | Signatures resilient to continual leakage on memory and computation[END_REF]. The signature consists of 15 group elements, and the secret key of a user holding a set Ω of attributes is made up with |Ω| + n elements. Our scheme is selective-predicate and adaptive-message unforgeable under chosen message attacks if the augmented multi-sequence of exponents computational Diffie-Hellman assumption [START_REF] Herranz | Constant-size ciphertexts in threshold attribute-based encryption[END_REF] and the Decision Linear assumption [START_REF] Boneh | Short group signatures[END_REF] hold. The privacy of the attributes involved in the generation of a signature is preserved, under the Decision Linear assumption. -Our second scheme supports threshold predicates (as well as compartmented and hierarchical predicates) for large universes of attributes. It is built upon Attrapadung, Libert and de Panafieu's key-policy ABE scheme from [START_REF] Attrapadung | Expressive key-policy attribute-based encryption with constant-size ciphertexts[END_REF] and has signatures consisting of only 3 group elements. The secret keys are longer than in the first scheme, since they include (2n + 2) × (|Ω| + n) group elements. The assumption underlying the selective-predicate and adaptive-message unforgeability under chosen message attacks is the more classical n-Diffie-Hellman exponent assumption, and the scheme protects the privacy of the involved attributes unconditionally.

Organization of the paper. We give the algorithmic setting and define the syntactics of attributebased signatures and the required security properties in Section 2. In Section 3 we describe our first scheme, for threshold signing predicates, and prove its security. We do the same for our second scheme in Section 4, and discuss possible extensions of both schemes to more general signing predicates in Section 5. Concluding remarks are given in Section 6.

Background

Notation

We will treat a vector as a column vector, unless stated otherwise. For any vector α = (α 1 , . . . , α n ) ⊤ ∈ Z n p , and any element g of a group G, g α stands for the vector of group elements (g α 1 , . . . , g αn ) ⊤ ∈ G n . For a, z ∈ Z n p , we denote their inner product as a, z = a ⊤ z = n i=1 a i z i . Given g a and z, (g a ) z := g a, z is computable without knowing a. For equal-dimension vectors A and B containing exponents or group elements, A • B stands for their component-wise product. When C = (C 1 , C 2 , C 3 ) ⊤ ∈ G 3 is a vector of group elements and if g ∈ G, we denote by E(g, C) the vector of pairing values e(g, C 1 ), e(g, C 2 ), e(g, C 3 ) ⊤ . We denote by I n the identity matrix of size n. For any set U , we define 2 U = {S | S ⊆ U }. Additionally, given a set S ⊂ Z p , and some i ∈ S, the ith Lagrange basis polynomial is ∆ S i (X) = j∈S\{i} (Xj)/(ij).

Complexity Assumptions

Our two schemes work in the setting of bilinear groups. That is, we use a pair of multiplicative groups (G, G T ) of prime order p with an efficiently computable mapping e : G × G → G T s.t. e(g a , h b ) = e(g, h) ab for any (g, h) ∈ G × G, a, b ∈ Z and e(g, h) = 1 G T whenever g, h = 1 G . The security of our first scheme is partially based on the hardness of the computational version of a problem appeared in [START_REF] Herranz | Constant-size ciphertexts in threshold attribute-based encryption[END_REF] under the name of augmented multi-sequence of exponents decisional Diffie-Hellman problem. Its decisional version was proven to be hard in generic groups.

Definition 1 (( l, m, t)-aMSE-CDH - [START_REF] Herranz | Constant-size ciphertexts in threshold attribute-based encryption[END_REF]). The ( l, m, t)-augmented multi-sequence of exponents computational Diffie-Hellman (( l, m, t)-aMSE-CDH) problem related to the group pair (G, G T ) is to compute T = e(g 0 , h 0 ) κ•f (γ) on input: the vector x l+ m = (x 1 , . . . , x l+ m) ⊤ , whose components are pairwise distinct elements of Z p which define the polynomials

f (X) = l i=1 (X + x i ) and g(X) = l+ m i= l+1 (X + x i ),
and the values

                     g 0 , g γ 0 , . . . , g γ l+ t-2 0 , g κ•γ•f (γ) 0 , (l.1)
g ωγ 0 , . . . , g ωγ l+ t-2 0 , (l.2)

g α 0 , g αγ 0 , . . . , g αγ l+ t 0 , (l.3) h 0 , h γ 0 , . . . , h γ m-2 0 , h κ•g(γ) 0 (l.4) h ω 0 , h ωγ 0 , . . . , h ωγ m-1 0 , (l.5) h α 0 , h αγ 0 , . . . , h αγ 2( m-t)+3 0 (l.6)
where κ, α, γ, ω are unknown random elements of Z p and g 0 and h 0 are generators of G.

The other (decisional) hard problem that we need for the security analysis of our first signature scheme is the Decision Linear Problem.

Definition 2 (DLIN - [START_REF] Boneh | Short group signatures[END_REF]). In a group G of prime order p, the Decision Linear Problem (DLIN) is to distinguish the distributions (g, g a , g b , g a

•δ 1 , g b•δ 2 , g δ 1 +δ 2 ) and (g, g a , g b , g a•δ 1 , g b•δ 2 , g δ 3 ), with a, b, δ 1 , δ 2 , δ 3 R ← Z p .
This problem is to decide if vectors g 1 = (g a , 1, g) ⊤ , g 2 = (1, g b , g) ⊤ and g 3 = (g aδ 1 , g bδ 2 , g δ 3 ) ⊤ are linearly dependent in the Z p -module G 3 formed by entry-wise multiplication.

Finally, the security of our second attribute-based signature scheme is based on the hardness of the n-Diffie-Hellman Exponent problem.

Definition 3 (n-DHE - [START_REF] Boneh | Collusion resistant broadcast encryption with short ciphertexts and private keys[END_REF]). In a group G of prime order p, the n-Diffie-Hellman Exponent (n-DHE) problem is, given a tuple (g, g γ , g γ 2 , . . . , g γ n , g γ n+2 , . . . , g γ 2n ) where γ

R ← Z p , g R ← G, to compute g γ n+1 .
The generic hardness of this problem is a consequence of a general result given in [START_REF] Boneh | Hierarchical identity-based encryption with constant size ciphertext[END_REF]. In addition, the assumption that this problem is hard is non-interactive and thus falsifiable [START_REF] Naor | On cryptographic assumptions and challenges[END_REF].

Groth-Sahai Proof Systems

To simplify the description, our first scheme uses Groth-Sahai proofs based on the DLIN assumption, although instantiations based on the symmetric external Diffie-Hellman assumption are also possible. In the DLIN setting, the Groth-Sahai proof systems [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF] use a common reference string comprising vectors g 1 , g 2 , g 3 ∈ G 3 , where g 1 = (g 1 , 1, g) ⊤ , g 2 = (1, g 2 , g) ⊤ for some

g 1 , g 2 , g ∈ G. To commit to X ∈ G, one sets C = (1, 1, X) ⊤ • g 1 r • g 2 s • g 3 t with r, s, t R ← Z p . When
proofs should be perfectly sound, g 3 is set as

g 3 = g 1 ξ 1 • g 2 ξ 2 with ξ 1 , ξ 2 R ← Z * p . Commitments C = (g r+ξ 1 t 1 , g s+ξ 2 t
2 , X • g r+s+t(ξ 1 +ξ 2 ) ) ⊤ are then Boneh-Boyen-Shacham (BBS) ciphertexts [START_REF] Boneh | Short group signatures[END_REF] that can be decrypted using a = log g (g 1 ), b = log g (g 2 ).

In the witness indistinguishability (WI) setting, defining

g 3 = g 1 ξ 1 • g 2 ξ 2 •(1, 1, g -1 )
⊤ gives linearly independent { g 1 , g 2 , g 3 } and C is a perfectly hiding commitment. Under the DLIN assumption, the two settings are indistinguishable.

To prove that committed group elements satisfy certain relations, the Groth-Sahai techniques require one commitment per variable and one proof element (made of a constant number of group elements) per relation. Such proofs are available for pairing-product relations, which are of the type

n i=1 e(A i , X i ) • n i=1 • n j=1 e(X i , X j ) a ij = t T , for variables X 1 , . . . , X n ∈ G and constants t T ∈ G T , A 1 , . . . , A n ∈ G, a ij ∈ Z p , for i, j ∈ {1, . . . , n}.
At some additional cost (typically, auxiliary variables have to be introduced), pairing-product equations admit non-interactive zero-knowledge (NIZK) proofs (this is the case when the target element t T has the special form t T = t i=1 e(S i , T i ), for constants {(S i , T i )} t i=1 and some t ∈ N): on a simulated common reference string (CRS), prepared for the WI setting, a trapdoor makes it possible to simulate proofs without knowing the witnesses.

As far as efficiency goes, linear pairing product equations (where a ij = 0 for all i, j) consist of only 3 group elements and we only need linear equations here.

Syntax of Threshold Attribute-Based Signatures

Since we will focus on threshold signing predicates, we describe the syntax and security model of attribute-based signatures with respect to these threshold predicates Γ = (t, S): the sender chooses a subset S of the universe of attributes and a threshold t such that 1 ≤ t ≤ |S|, and signs a message Msg for the pair (t, S). A verifier will be convinced that the signature comes from a user who holds t or more attributes in S. The algorithms and security model for ABS schemes supporting more general signing predicates can be described in a very similar way.

An attribute-based signature scheme ABS = (ABS.TSetup, ABS.MSetup, ABS.Keygen, ABS.Sign, ABS.Verify) consists of five probabilistic polynomial-time (PPT, for short) algorithms. In the context of threshold predicates, their specification is the following:

-TSetup(λ, P, n): is the randomized trusted setup algorithm taking as input a security parameter λ, an attribute universe P and an integer n ∈ poly(λ) which is an upper bound on the size of threshold policies. It outputs a set of public parameters pms (which contains λ, P and n). An execution of this algorithm is denoted as pms ← ABS.TSetup(1 λ , P, n). -MSetup(pms): is the randomized master setup algorithm, that takes as input pms and outputs a master secret key msk and the corresponding master public key mpk. We write (mpk, msk) ← ABS.MSetup(pms) to denote an execution of this algorithm. -Keygen(pms, mpk, msk, Ω): is a (possibly randomized) key extraction algorithm which takes as input the public parameters pms, the master keys mpk and msk, and a set of attributes Ω ⊂ P held by the requesting user. The output is a private key SK Ω . We refer to an execution of this protocol as SK Ω ← ABS.Keygen(pms, mpk, msk, Ω). -Sign(pms, mpk, SK Ω , Msg, Γ ): is a randomized signing algorithm which takes as input the public parameters pms, the master public key mpk, a secret key SK Ω , a message Msg and a threshold signing policy Γ = (t, S) where S ⊂ P and 1 ≤ t ≤ |S| ≤ n. It outputs a signature σ. We denote the action taken by the signing algorithm as σ ← ABS.Sign(pms, mpk, SK Ω , Msg, Γ ). -Verify(pms, mpk, Msg, σ, Γ ): is a deterministic verification algorithm taking as input the public parameters pms, a master public key mpk, a message Msg, a signature σ and a threshold predicate Γ = (t, S). It outputs 1 if the signature is deemed valid and 0 otherwise. We write b ← ABS.Verify(pms, mpk, Msg, σ, Γ ) to refer to an execution of the verification protocol.

For correctness, if Γ = (t, S), it is required that ABS.Verify(pms, mpk, Msg, ABS.Sign(pms, mpk, SK Ω , Msg, Γ ), Γ ) = 1, whenever |Ω ∩ S| ≥ t and the values pms, mpk, msk, SK Ω have been obtained by properly executing the algorithms ABS.TSetup, ABS.MSetup and ABS.Keygen.

Security of Threshold Attribute-Based Signatures

Unforgeability and privacy are the typical requirements for attribute-based signature schemes.

Unforgeability. An attribute-based signature scheme must satisfy the usual property of unforgeability, even against a group of colluding users that put their secret keys together. In this work we consider a relaxed notion where the attacker selects the signing policy Γ ⋆ = (t ⋆ , S ⋆ ) that he wants to attack at the beginning of the game. Note however that the message Msg ⋆ whose signature is eventually forged is not selected in advance. The attacker can ask for valid signatures for messages and signing policies of his adaptive choice. The resulting property of selective-predicate and adaptive-message unforgeability under chosen message attacks (sP-UF-CMA, for short) is defined by considering the following game that an attacker F plays against a challenger: Definition 4. Let λ be an integer. Consider the following game between a probabilistic polynomial time (PPT) adversary F and its challenger.

Initialization. The challenger begins by specifying a universe of attributes P as well as an integer n ∈ poly(λ), which are sent to F. Then, F selects a subset S ⋆ ⊂ P of attributes such that |S ⋆ | ≤ n and a threshold t ⋆ ∈ {1, . . . , |S ⋆ |}. These define a threshold predicate Γ ⋆ = (t ⋆ , S ⋆ ). Setup. After receiving Γ ⋆ from F, the challenger runs pms ← ABS.TSetup(1 λ , P, n) and (mpk, msk) ← ABS.MSetup(pms), and sends pms, mpk to the forger F. Queries. F can interleave private key and signature queries.

Private key queries. F adaptively chooses a subset of attributes Ω ⊂ P under the restriction that |Ω ∩ S ⋆ | < t ⋆ and must receive SK Ω ← ABS.Keygen(pms, mpk, msk, Ω) as the answer. Signature queries. F adaptively chooses a pair (Msg, Γ ) consisting of a message Msg and a threshold predicate Γ = (t, S) such that 1 ≤ t ≤ |S| ≤ n. The challenger chooses an arbitrary attribute set Ω ⊂ P such that |Ω ∩ S| ≥ t, runs SK Ω ← ABS.Keygen(pms, mpk, msk, Ω) and computes a signature σ ← ABS.Sign(pms, mpk, SK Ω , Msg, Γ ) which is returned to F.

Forgery. At the end of the game, F outputs a pair (Msg ⋆ , σ ⋆ ). We say that F is successful if:

-ABS.Verify(pms, mpk, Msg ⋆ , σ ⋆ , Γ ⋆ ) = 1, and -F has not made any signature query for the pair (Msg ⋆ , Γ ⋆ ).

The forger' success in breaking the sP-UF-CMA security of the ABS scheme is defined as

Succ sP-UF-CMA F ,ABS (λ) = Pr[F wins].
A threshold attribute-based signature scheme ABS is selective-predicate adaptive-message unforgeable (sP-UF-CMA unforgeable) if Succ sP-UF-CMA F ,ABS (λ) is negligible with respect to the security parameter λ, for any polynomial time adversary F.

Privacy (of Involved Attributes

). This property ensures that the only information that an attributebased signature leaks about the actual attributes that have been used to produce it is the fact that they satisfy the specified signing predicate. Privacy must hold even against attackers that control the master entity and is defined via the following game between an adversary D and its challenger. Depending on the computational resources allowed to D and on its success probability, we can define computational privacy and perfect (unconditional) privacy. Definition 5. Let λ be an integer, and consider the following game between a distinguisher D and its challenger. A threshold attribute-based signature scheme ABS is said to be computationally private if Adv Priv D,ABS (λ) is negligible with respect to the security parameter λ, for any distinguisher D running in polynomial time and is said to be perfectly / unconditionally private if Adv Priv D,ABS (λ) = 0, for any distinguisher D (with possibly unbounded computational power).

A First Short Attribute-Based Signature Scheme for Threshold Predicates

We present here our first scheme to produce attribute-based signatures with constant size, for threshold predicates. The secret key sk Ω for a user holding a set of attributes Ω contains |Ω| + n elements, where n is the maximum size of the attribute set for any signing policy. This construction is for "small" universes of attributes P = {at 1 , . . . , at η }, for some integer η ∈ N, as public parameters have linear size in η; therefore, η must be polynomial in the security parameter of the scheme. Attributes {at i } η i=1 are arbitrary strings which some encoding function ς maps to Z * p . Since the scheme is a small universe construction, we may set n = η in the description hereafter.

The construction builds on the ABE scheme put forth by Herranz et al. [START_REF] Herranz | Constant-size ciphertexts in threshold attribute-based encryption[END_REF]. The intuition is to have the signer implicitly prove his ability to decrypt a ciphertext corresponding to that ABE scheme. This non-interactive proof is generated using the Groth-Sahai proof systems [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF], by binding the signed message (and the corresponding predicate) to the non-interactive proof using a technique suggested by Malkin et al. [START_REF] Malkin | Signatures resilient to continual leakage on memory and computation[END_REF]. In some sense, this technique can be seen as realizing signatures of knowledge in the standard model: it consists in embedding the message to be signed in the Groth-Sahai CRS by calculating part of the latter as a "hash value" of the message. As noted in [START_REF] Malkin | Signatures resilient to continual leakage on memory and computation[END_REF], Waters' hash function [START_REF] Waters | Efficient identity-based encryption without random oracles[END_REF] is well-suited to this purpose since, in the security proof, it makes it possible to answer signing queries using simulated NIZK proofs. At the same time, with non-negligible probability, adversarially-generated signatures are produced using a perfectly sound Groth-Sahai CRS and they thus constitute real proofs, from which witnesses can be extracted.

In [START_REF] Malkin | Signatures resilient to continual leakage on memory and computation[END_REF], the above technique was applied to an instantiation of Groth-Sahai proofs based on the Symmetric eXternal Diffie-Hellman assumption (and thus asymmetric pairings). In this section, we adapt this technique so as to get it to work with symmetric pairings and the linear assumption.

◮ TSetup(λ, P, n): the trusted setup algorithm conducts the following steps. 1. Choose groups (G, G T ) of prime order p > 2 λ with an efficiently computable bilinear map e : G × G → G T . Select generators g, h R ← G and also choose a collision-resistant hash function H : {0, 1} * → {0, 1} k , for some k ∈ poly(λ). 2. Define a suitable injective encoding ς sending each of the n attributes at ∈ P onto an element

ς(at) = x ∈ Z ⋆ p . Choose a set D = {d 1 , . . . , d n-1 } consisting of n -1 pairwise different elements of Z *
p , which must also be different from the encoding of any attribute in P. For any integer i lower or equal to n -1, we denote as D i the set {d 1 , . . . , d i }.

Generate Groth-Sahai reference strings by choosing random generators

g 1 , g 2 R ← G and defining vectors g 1 = (g 1 , 1, g) ⊤ ∈ G 3 and g 2 = (1, g 2 , g) ⊤ ∈ G 3 . Then, for each i ∈ {0, . . . , k}, pick ξ i,1 , ξ i,2 R
← Z p at random and define a vector

g 3,i = g 1 ξ i,1 • g 2 ξ i,2 = g ξ i,1 1 , g ξ i,2
2 , g ξ i,1 +ξ i,2 ⊤ . Exponents {(ξ i,1 , ξ i,2 )} k i=0 can then be discarded as they are no longer needed. The resulting public parameters are

pms = P, n, λ, G, G T , g, h, g 1 , g 2 , { g 3,i } k i=0 , H, ς, D .
◮ MSetup(pms): the master setup algorithm picks at random α, γ ∈ Z * p and sets u = g αγ and v = e(g α , h).

The master secret key is msk = (α, γ) and the master public key is

mpk = u, v, g α , h αγ i i=0,...,
SK Ω = g r γ+ς(at) at∈Ω , h rγ i i=0,...,n-2 , h r-1 γ
and conducts the following steps.

1. Let Ω S be any subset of Ω ∩ S with |Ω S | = t. From all at ∈ Ω S , compute the value

A 1 = Aggregate({g r γ+ς(at) , ς(at)} at∈Ω S ) = g r at∈Ω S
(γ+ς(at))

using the algorithm Aggregate of [START_REF] Delerablée | Dynamic threshold public-key encryption[END_REF]. From A 1 , compute

T 1 = A 1 at∈(S∪D n+t-1-s )\Ω S ς(at) 1 .
2. Define the value P (Ω S ,S) (γ) as

P (Ω S ,S) (γ) = 1 γ   at∈(S∪D n+t-1-s )\Ω S (γ + ς(at)) - at∈(S∪D n+t-1-s )\Ω S ς(at)   .
Since |Ω S | = t, the degree of the polynomial P (Ω S ,S) (X) is n -2. Therefore, from SK Ω , one can compute h r•P (Ω S ,S) (γ)/( at∈(S∪D n+t-1-s )\Ω S ς(at)) and multiply this value with the last element in

SK Ω , which is h r-1
γ , to obtain at) .

T 2 = h r-1 γ • h r P (Ω S ,S) (γ) at∈(S∪D n+t-1-s )\Ω S ς (

Note that the obtained values

T 1 , T 2 ∈ G satisfy the equality e(T 2 , u -1 ) • e T 1 , h α• at∈(S∪D n+t-1-s ) (γ+ς(at)) = e(g α , h) (1)
and that, in the terms in the left-hand-side of equality (1), the second argument of each pairing is publicly computable using pms and mpk.

Compute

M = m 1 . . . m k = H(Msg, Γ ) ∈ {0, 1} k and use M to form a message-specific Groth- Sahai CRS g M = ( g 1 , g 2 , g 3,M ). Namely, for i = 0 to k, parse g 3,i as (g X,i , g Y,i , g Z,i ) ⊤ ∈ G 3 .
Then, define the vector

g 3,M = g X,0 • k i=1 g m i X,i , g Y,0 • k i=1 g m i Y,i , g Z,0 • k i=1 g m i Z,i ⊤ .
4. Using the newly defined g M = ( g 1 , g 2 , g 3,M ), generate Groth-Sahai commitments to T 1 and

T 2 . Namely, pick r 1 , s 1 , t 1 , r 2 , s 2 , t 2 R ← Z p and compute C T j = (1, 1, T j ) ⊤ • g 1 r j • g 2 s j • g t j
3,M for j ∈ {1, 2}. Then, generate a NIZK proof that committed variables (T 1 , T 2 ) satisfy the pairingproduct equation [START_REF] Attrapadung | Expressive key-policy attribute-based encryption with constant-size ciphertexts[END_REF]. To this end, we introduce an auxiliary variable Θ ∈ G (with its own

commitment C Θ = (1, 1, Θ) ⊤ • g 1 r θ • g 2 s θ • g t θ 3,M , for r θ , s θ , t θ R ← Z p )
, which takes on the value Θ = h, and actually prove that e(T 1 , H S ) = e(g α , Θ) • e(T 2 , u)

(2) e(g, Θ) = e(g, h),

where

H S = h α• at∈(S∪D n+t-1-s ) (γ+ς(at))
. The proofs for relations (2) and ( 3) are called π 1 and π 2 , respectively, and they are given by

π 1 = (π 1,1 , π 1,2 , π 1,3 ) ⊤ = H r 1 S • (g α ) -r θ • u -r 2 , H s 1 S • (g α ) -s θ • u -s 2 , H t 1 S • (g α ) -t θ • u -t 2 ⊤ π 2 = (π 2,1 , π 2,2 , π 2,3 ) ⊤ = g r θ , g s θ , g t θ ⊤ . Finally, output the signature σ = C T 1 , C T 2 , C θ , π 1 , π 2 ∈ G 15 .
◮ Verify(pms, mpk, Msg, σ, Γ ): it first parses Γ as a pair (t, S) and σ as

C T 1 , C T 2 , C θ , π 1 , π 2 . It computes M = m 1 . . . m k = H(Msg, Γ ) ∈ {0, 1} k
and forms the corresponding vector

g 3,M = g X,0 • k i=1 g m i X,i , g Y,0 • k i=1 g m i Y,i , g Z,0 • k i=1 g m i Z,i ⊤ ∈ G 3 .
Then, parse the proofs π 1 and π 2 as vectors (π 1,1 , π 1,2 , π 1,3 ) ⊤ and (π 2,1 , π 2,2 , π 2,3 ) ⊤ , respectively.

Define

H S = h α• at∈(S∪D n+t-1-s ) (γ+ς(at))
and return 1 if the relations

E(H S , C T 1 ) = E(g α , C θ ) • E(u, C T 2 ) • E(π 1,1 , g 1 ) • E(π 1,2 , g 2 ) • E(π 1,3 , g 3,M ) (4)
E(g, C θ ) = E g, (1, 1, h) • E(π 2,1 , g 1 ) • E(π 2,2 , g 2 ) • E(π 2,3 , g 3,M ) (5)
are both satisfied. Otherwise, return 0.

Correctness. The correctness of the scheme immediately follows from the correctness of Groth-Sahai proofs.

An alternative scheme in the ROM. Steps 3 and 4 in the previous signing protocol can be replaced with a Σ-protocol, using the well-known Fiat-Shamir technique [START_REF] Fiat | How to prove yourself: practical solutions of identification and signature problems[END_REF]. The result is a noninteractive zero-knowledge signature of knowledge for the message Msg, related to the knowledge of secret values T 1 , T 2 satisfying equality (1). The resulting signatures would consist of 4 group elements, but the security of the scheme would rely on the assumption that the underlying hash function behaves as a random oracle.

Security Analysis

This first scheme is selective-predicate and adaptive-message unforgeable under chosen-message attacks, assuming the hardness of both the DLIN problem and the (ns ⋆ , n + t ⋆ -1, t ⋆ + 1)-aMSE-CDH problem, where s ⋆ and t ⋆ are the size of the attribute set and the threshold of the challenge signing policy. Computational privacy can be proven based on the hardness of the DLIN problem.

Theorem 1. The scheme is selective-predicate and adaptive-message unforgeable under chosenmessage attacks assuming that (1) H is a collision-resistant hash function; (2) the DLIN assumption holds in G;

(3) the (ns ⋆ , n + t ⋆ -1, t ⋆ + 1)-aMSE-CDH assumption holds in (G, G T ), where n is the maximal number of attributes in the attribute set S and where s ⋆ and t ⋆ are the size of the attribute set and the threshold of the challenge signing policy.

The proof of this theorem can be found in Appendix A.1.

Theorem 2. This first ABS scheme enjoys computational privacy, assuming that the DLIN assumption holds in G.

Proof. (Sketch.) The proof consists in considering two games: Game 0 and Game 1 . The first game, Game 0 , is the real privacy game as described in Definition 5. In particular, when executing the trusted setup algorithm ABS.TSetup, the challenger chooses the vectors ( g 1 , g 2 , { g 3,i } k i=0 ) such that g 3,i is linearly dependent with ( g 1 , g 2 ), for all i = 0, . . . , k. The only difference between Game 1 and Game 0 is that, in Game 1 , the vector g 3,i is chosen at random so that it is linearly independent with ( g 1 , g 2 ), for all i = 0, . . . , k. Groth-Sahai [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF] proved that this change is indistinguishable, under the DLIN assumption. Finally, in Game 1 , the only values that could leak any information about the subset of attributes held by the signer are C T 1 , C T 2 , π 1 . But in the setting of Game 1 , these commitments and proofs are perfectly hiding: they do not reveal any information about the committed values T 1 , T 2 . Therefore, privacy of the attributes holds unconditionally in Game 1 . ⊓ ⊔

A Second Short Attribute-Based Signature Scheme for Threshold Predicates

The main advantage of our second ABS scheme over the previous one is that signatures are much shorter, since they have only three group elements. This comes at the cost of longer secret keys sk Ω , containing (2n + 2) × (|Ω| + n) group elements. Another advantage is that the size of the considered universe of attributes may be much larger, even exponential in the security parameter λ; we only need that all attributes in the universe P are encoded as different elements of Z * p .

◮ TSetup(λ, P, n): chooses a collision-resistant hash function H : {0, 1} * → {0, 1} k , for some integer k ∈ poly(λ), as well as bilinear groups (G, G T ) of prime order p > 2 λ with g R ← G. It also picks u 0 , u 1 , . . . , u k R ← G and sets U = (u 0 , u 1 , . . . , u k ) ⊤ . It finally chooses a set D = {d 1 , . . . , d n } of n distinct elements of Z p that will serve as dummy attributes.

The resulting public parameters are pms = P, n, λ, G, G T , g, U , D, H .

◮ MSetup(pms): randomly chooses α, α 0 R ← Z p , α = (α 1 , . . . , α N ) ⊤ R ← Z N p , where N = 2n + 1. It then computes e(g, g) α , h 0 = g α 0 , H = (h 1 , . . . , h N ) ⊤ = g α .
The master secret key is defined to be msk = g α and the master public key is mpk = e(g, g) α , h 0 , H . ◮ Keygen(pms, mpk, msk, Ω): to generate a key for the attribute set Ω, the algorithm first chooses an implicit polynomial

Q Ω [X] = α + β 1 X + • • • + β n-1 X n-1 for random coefficients β 1 , . . . , β n-1 R ← Z p .
Then, it proceeds as follows.

1. For each attribute ω ∈ Ω, choose a random exponent r ω R ← Z p and generate a key component SK ω = (D ω,1 , D ω,2 , K ω,1 , . . . , K ω,N -1 ) where

D ω,1 = g Q Ω (ω) • h rω 0 , D ω,2 = g rω , K ω,i = h -ω i 1 • h i+1 rω i=1,...,N -1 . (6
D d,1 = g Q Ω (d) • h r d 0 , D d,2 = g r d , K d,i = h -w i 1 • h i+1 r d i=1,...,N -1 . (7)
The

P S (Z) = n-t+s+1 i=1 y i Z i-1 = ω∈S (Z -ω) • d∈D n-t (Z -d). (8)
Since nt + s + 1 ≤ 2n + 1 = N , the coordinates y n-t+s+2 , . . . , y N are all set to 0.

For each

ω ∈ S t , use SK ω = (D ω,1 , D ω,2 , {K ω,i } N -1 i=1 ) to compute D ′ ω,1 = D ω,1 • N -1 i=1 K y i+1 ω,i = g Q Ω (ω) • h 0 • N i=1 h y i i rω . (9)
The last equality comes from the fact that P S (ω) = 0 for all ω ∈ S.

Likewise, for each dummy attribute

d ∈ D n-t , use SK d = (D d,1 , D d,2 , {K d,i } N -1 i=1 ) to compute D ′ d,1 = D d,1 • N -1 i=1 K y i+1 d,i = g Q Ω (d) • h 0 • N i=1 h y i i r d . (10)
4. Using the values {D ′ ω,1 } ω∈St and {D ′ d,1 } d∈D n-t and the corresponding D ω,2 = g rw , D d,2 = g r d , compute

D 1 = ω∈St D ′ ω,1 ∆ S t ∪D n-t ω (0) • d∈D n-t D ′ d,1 ∆ S t ∪D n-t d (0) = g α • (h 0 • N i=1 h y i i ) r (11)
D 2 = ω∈St D ω,2 ∆ S t ∪D n-t ω (0) • d∈D n-t D d,2 ∆ S t ∪D n-t d (0) = g r , (12)
where r = ω∈St ∆

St∪D n-t ω (0) • r ω + d∈D n-t ∆ St∪D n-t d (0) • r d .
5. Parse M ∈ {0, 1} k as a string m 1 . . . m k where m j ∈ {0, 1} for j = 1, . . . , k. Then, choose z, w R ← Z p and compute

σ 1 = D 1 • h 0 • N i=1 h y i i w • u 0 • k j=1 u m j j z , σ 2 = D 2 • g w , σ 3 = g z .
Return the signature σ = (σ 1 , σ 2 , σ 3 ) ∈ G 3 .

◮ Verify(pms, mpk, Msg, σ, Γ ): it first parses Γ as a pair (t, S). It computes M = H(Msg, Γ ) ∈ {0, 1} k and considers the subset D n-t ⊂ D containing the nt first dummy attributes of D. Then, it defines the vector Y = (y 1 , . . . , y N ) ⊤ from the polynomial P S (Z) as per [START_REF] Boneh | Collusion resistant broadcast encryption with short ciphertexts and private keys[END_REF]. The protocol accepts the signature σ = (σ 1 , σ 2 , σ 3 ) as valid and thus outputs 1 if

e(g, g) α = e(σ 1 , g) e(σ 2 , h 0 • N i=1 h y i i ) • e(σ 3 , u 0 • k j=1 u m j j ) . ( 13
)
Otherwise, it outputs 0.

Correctness. The correctness of the scheme follows from the property that for each attribute ω ∈ S t ⊂ S ∩ Ω, the vector

X N ω = (1, ω, ω 2 , . . . , ω N -1
) is orthogonal to Y , so that we have

D ′ ω,1 = D ω,1 • N -1 i=1 K y i+1 ω,i = g Q Ω (ω) • h 0 • h -( X N ω , Y -y 1 ) 1 N i=2 h y i i rω = g Q Ω (ω) • h 0 • N i=1 h y i i rω ,
which explains the second equality of ( 9) and the same holds for [START_REF] Brickell | Some ideal secret sharing schemes[END_REF]. In addition, the values (D 1 , D 2 ) obtained as per ( 11)-( 12) satisfy e(D 1 , g) = e(g, g) α • e(h 0 • N i=1 h y i i , D 2 ), which easily leads to the verification equation ( 13).

Security Analysis

Our second scheme is selective-predicate and adaptive-message unforgeable under chosen-message attacks, by reduction to the hardness of the n-Diffie-Hellman Exponent (n-DHE) problem ( [START_REF] Boneh | Collusion resistant broadcast encryption with short ciphertexts and private keys[END_REF]). This scheme also enjoys unconditional privacy, which is another advantage over our first scheme. Theorem 3. The scheme is selective-predicate and adaptive-message unforgeable under chosenmessage attacks if H is a collision-resistant hash function and if the (2n + 1)-DHE assumption holds in G, where n is the maximal number of attributes in the attribute set S.

The proof of this theorem can be found in Appendix A.2.

Theorem 4. This second ABS scheme enjoys perfect privacy.

Proof. A valid signature for the threshold policy (t, S) which was produced using the subset of attributes S t ⊂ S, |S t | = t and with randomness w can also be produced for any other set

S ′ t ⊂ S, |S ′ t | = t with randomness w ′ . More specifically, if r = ω∈St ∆ St∪D n-t ω (0)•r ω + d∈D n-t ∆ St∪D n-t d (0)• r d and r ′ = ω∈S ′ t ∆ St∪D n-t ω (0) • r ω + d∈D n-t ∆ St∪D n-t d
(0) • r d , any pair (w, w ′ ) satisfying r + w = r ′ + w ′ will result in the same signature for S t and S ′ t . ⊓ ⊔

More General Signing Predicates

Our schemes admit some extensions to deal with more general monotone predicates. In general, a predicate is a pair (S, Γ ), where S = {at 1 , . . . , at s } is a set of attributes and Γ ⊂ 2 S is a monotone increasing family of subsets of S. An attribute-based signature for a pair (S, Γ ) convinces the verifier that the signer holds some subset of attributes A ∈ Γ , without revealing any information on A.

Extensions for the First Scheme

Similarly to what is suggested in [START_REF] Herranz | Constant-size ciphertexts in threshold attribute-based encryption[END_REF], our first signature scheme can be extended to admit weighted threshold predicates. A pair (S, Γ ) is a weighted threshold predicate if there exist a threshold t and an assignment of weights ω : S → Z + such that Ω ∈ Γ ⇐⇒ at∈Ω ω(at) ≥ t. If K is an upper bound for ω(at), for all attributes at ∈ P and all possible assignments of weights that realize weighted threshold predicates, the idea is to consider an augmented universe of attributes P ′ = {at 1 ||1, at 1 ||2, . . . , at 1 ||K, . . . , at m ||1, . . . , at m ||K}. The size of each user's secret key is just increased by a factor of K. To sign a message for the weighted threshold predicate (S, Γ ), where Γ is defined by ω and t, the signer can use the threshold signature routine of our first scheme with the threshold t and attribute set S ′ = {at 1 ||1, . . . , at 1 ||ω(at 1 ), . . . , at s ||1, . . . , at s ||ω(at s )}. If the user holds a subset of attributes Ω ∈ Γ , he will have ω(at) valid elements in his secret key, for each attribute at ∈ Ω; and since at∈Ω ω(at) ≥ t, he will be able to run the threshold signing protocol.

Furthermore, since the final form of the signatures in our first threshold scheme is that of a Groth-Sahai non-interactive proof, one could consider signing predicates which are described by a monotone formula (OR / AND gates) over threshold clauses. The Groth-Sahai proof would be then a proof of knowledge of some values that satisfy a monotone formula of equations. The size of such a proof (and therefore, the size of the resulting attribute-based signatures) would be linear in the number of threshold clauses in the formula. We stress that this is still better than having size linear in the number of involved attributes, as in all previous constructions.

Extensions for the Second Scheme

The idea of our second scheme is that a (threshold) attribute-based signature can be computed only if the signer holds t attributes in S which, combined with nt dummy attributes, lead to n attributes at such that P S (at) = 0. This makes it possible to interpolate a polynomial Q Ω (X) with degree n -1, recover in some way the value g α and produce a valid signature. To admit any possible value of the threshold t in {1, . . . , n}, the number of dummy attributes must be n. The key generation protocol for a subset of attributes Ω already restricts the usability of the signature protocol to threshold predicates. But this can be extended to admit some more general families of predicates, specifically for those that can be realized with a secret sharing scheme with similar properties to Shamir's threshold secret sharing scheme. We give here two examples of such families of predicates. The ideas underlying this extension are somehow related to those in [START_REF] Daza | Extended access structures and their cryptographic applications[END_REF], where dummy attributes were used to design attribute-based encryption schemes for general decryption predicates.

Hierarchical Threshold Predicates. We follow the definitions and notations of hierarchical threshold families that appear in [START_REF] Tassa | Hierarchical threshold secret sharing[END_REF]. The set of involved attributes is divided in c disjoint levels, S = S 1 ∪ S 2 ∪ . . . ∪ S c , where c ≥ 1 is an integer. A predicate Γ ⊂ 2 S is hierarchical threshold if there exists a strictly increasing sequence of integers 0 < k 1 < k 2 < . . . < k c such that

Γ = {Ω ⊂ S : Ω ∩ ℓ i=1 S i ≥ k ℓ , ∀ℓ ∈ {1, 2, . . . , c}}
That is, a subset is authorized if it contains at least k 1 attributes from the first level, and at least k 2 players from the two first levels, and so on. Tassa constructed in [START_REF] Tassa | Hierarchical threshold secret sharing[END_REF] a secret sharing scheme realizing this kind of predicates, using Birkhoff interpolation: the dealer chooses a polynomial f (X) with degree k c -1, the secret is α = f (0) and the share of an attribute at i,j ∈ S i from level i is α i,j = f (k i-1 ) (j), the k i-1 derivative of f evaluated in j.

To extend our second attribute-based signature scheme so that the admitted signing predicates are exactly those hierarchical threshold predicates with c levels, let n be the size of the universe of attributes P = {at 1 , . . . , at n }. In the Setup phase, n dummy attributes must be placed in each level i = 1, . . . , c. Therefore, there will be cn dummy attributes in total. In the Key Generation phase, for a subset of attributes Ω, the master entity will use Tassa's secret sharing scheme for a hierarchical threshold predicate Γ ′ defined by the sequence 0 < n < 2n < . . . < cn. That is, the master entity chooses a fresh polynomial Q Ω (X) of degree cn -1 such that Q Ω (0) = α. The master entity will compute the shares for the attributes in Ω and for the cn dummy attributes (placed in different levels) to derive the values D ω,1 , D d,1 that appear in SK Ω . Finally, if a user wants to sign for a hierarchical threshold predicate (S, Γ ) defined by the sequence 0

< k 1 < k 2 < . . . < k c ,
where k c ≤ n, the polynomial P S (Z) is defined from the set S and from nk i dummy attributes in level i, for i = 1, . . . , c. The user can combine his attributes (in S) with nk i dummy attributes in level i, for i = 1, . . . , c, to interpolate from SK Ω the polynomial Q Ω (X), in the exponent, and recover the value product containing factor g α that is needed to sign. The form of the signatures, the Verification phase and the security analysis are almost identical as in our threshold scheme in Section 4.

The extension is limited in the sense that the number of levels c in the admitted hierarchical threshold policies is set at the beginning. If more flexibility is desired, both the Setup and the Key Generation processes should be repeated in parallel for any desired number of levels, at the cost of an increase in the length of the public parameters and the secret keys.

Compartmented Access Structures. Compartmented families were introduced in [START_REF] Brickell | Some ideal secret sharing schemes[END_REF]. Again, the set of involved attributes is partitioned: Brickell constructed in [START_REF] Brickell | Some ideal secret sharing schemes[END_REF] a vector space secret sharing scheme to realize a compartmented predicate (S, Γ ) defined by a sequence of thresholds t; t 1 , t 2 , . . . , t c . The dealer is associated to the vector v 0 = (1, 0, . . . , 0) and then each attribute at i,j ∈ S j in compartment j is associated to a vector v i,j in such a way that Ω ∈ Γ if and only if v 0 ∈ { v i,j } at i,j ∈Ω (in other words, if the vectors associated to the attributes in Ω span the vector v 0 ). To distribute a secret α, the dealer chooses a random vector a such that a • v 0 = α, and assigns to each attribute at i,j the share α i,j = a • v i,j . The secret α can be easily obtained from the shares of any subset of attributes Ω ∈ Γ .

S = S 1 ∪ S 2 ∪ . . . ∪ S c , with S i 1 ∩ S i 2 = ∅ for all i 1 = i 2 . A predicate Γ ⊂ 2 S is
Similarly, our second attribute-based signature scheme can be extended to admit compartmented predicates with a fixed number, c, of compartments. If n is the size of the universe of attributes, n dummy attributes must be placed in each of the compartments during the Setup. This means we need cn dummy attributes in total, again. In the Key Generation for a subset of attributes Ω, the master entity will use Brickell's secret sharing scheme for the compartmented predicate Γ ′ defined by sequence of thresholds cn; n, n, . . . , n. The shares corresponding to the attributes in Ω and to the cn dummy attributes, according to the compartment where they belong, will be computed and used to get the values D ω,1 , D d,1 in SK Ω . When a user wants to sign for such a predicate (S, Γ ) defined by the sequence of thresholds t; t 1 , t 2 , . . . , t c , where t ≤ n, he combines his real attributes (satisfying Γ ) with nt i dummy attributes in the compartment i, for i = 1, . . . , c.

The resulting subset of attributes will be authorized for the predicate Γ ′ , and so the distributed secret α (or a product containing the factor g α , as it is needed in our signature scheme) can be recovered from the shares of the user. The polynomial P S (Z) (see equation [START_REF] Boneh | Collusion resistant broadcast encryption with short ciphertexts and private keys[END_REF] in Section 4) is again defined from the set S and from nt i dummy attributes in compartment i, for i = 1, . . . , c.

Concluding Remarks

We have proposed the first two threshold ABS schemes which produce constant-size signatures. The signatures consist respectively of 15 and 3 group elements, whereas the secret keys sk Ω contain respectively |Ω| + n and (2n + 2) × (|Ω| + n) group elements. The security of both schemes is proven in the standard model with respect to assumptions related to bilinear groups. Note that the considered unforgeability model is not the strongest possible, since the attacker has to choose the signing policy he wants to attack at the beginning of the unforgeability game.

ς of the attributes with the restriction that the encodings of the attributes in P\S ⋆ correspond to the opposite of the roots of f (X), while the encodings of the elements in S ⋆ correspond to the opposite of some of the roots of g(X).

The values {d 1 , . . . , d n+t ⋆ -1-s ⋆ } corresponding to the first n + t ⋆ -1s ⋆ dummy attributes are defined as the opposite of the rest of the roots of g(X) (in some arbitrary order). For j = n + t ⋆s ⋆ , . . . , n -1, the d j 's can be chosen at random in Z p until they are distinct from {x 1 , . . . , x 2n+t ⋆ -1-s ⋆ , d n+t ⋆ -s ⋆ , . . . , d j-1 }.

The algorithm B defines g := g f (γ) 0

. Note that B can compute g with the elements of line (l.1) of its input, since f is a polynomial of degree l = ns ⋆ . To complete the setup phase, B sets h = h 0 and computes

-u = g αγ = g α•γ•f (γ) 0
with line (l.3) of its input, which is possible since Xf (X) is a polynomial of degree l + 1. Indeed, α • γ • f (γ) is a linear combination of {αγ, . . . , αγ l+1 } and the coefficients of this linear combination are known to B, so the value u can be computed from line (l.3).

v = e(g, h) α = e(g f (γ)α 0 , h 0 ) with line (l.3) for g f (γ)α 0 .

-{h αγ i } i=0,...,2n-1 from line (l.6) of its input.

Private key queries: Whenever the adversary F makes a key extraction query for a subset of attributes Ω ⊂ P satisfying that 0 ≤ |Ω S = Ω ∩ S ⋆ | ≤ t ⋆ -1, the algorithm B must produce a tuple of the form

sk Ω = g r γ+ς(at) at∈Ω , h rγ i i=0,...,n-2 , h r-1 γ
, for some random value r ∈ Z p . To do so, B implicitly defines r = (ωy Ω γ + 1)Q Ω (γ), where y Ω is randomly picked in Z p , and the polynomial Q ω (X) is defined as

Q Ω (γ) = 1 when |Ω S | = 0, or Q Ω (X) = λ Ω • at∈Ω S
(X + ς(at)) otherwise, in which case λ Ω = ( at∈Ω S ς(at)) -1 .

The elements which form sk Ω are then computed as follows:

-For any attribute at ∈ Ω S , B defines

Q at (γ) = Q Ω (γ)/(γ + ς(at)) = λ Ω • ãt∈Ω S , ãt =at (γ + ς( ãt))
and then g r γ+ς(at) = g

f (γ)ωy Ω γQat(γ) 0 • g f (γ)Qat(γ) 0
. The first factor of the product (whose exponent is a polynomial in γ of degree at most (n-s ⋆ )+1+t ⋆ -2) can be computed from line (l.2), whereas the second factor (whose exponent is a polynomial in γ of degree at most (ns ⋆ ) + t ⋆ -2) can be computed from line (l.1).

-For any attribute at ∈ Ω \ Ω S , B defines the polynomial f at (X) = f (X)/(X + ς(at)) and then g r γ+ς(at) = g fat(γ)ωy Ω γQ Ω (γ) 0

• g fat(γ)Q Ω (γ) 0
. Again, the first factor of this product can be computed from line (l.2), and the second factor can be computed from line (l.1).

-The values h rγ i i=0,...,n-2 can be computed from line (l.4) and (l.5), since

h rγ i = h Q Ω (γ)ωy Ω γ i+1 • h Q Ω (γ)γ i . -Finally, B has to compute h r-1 γ = h Q Ω (γ)ωy Ω • h Q Ω (γ)-1 γ
. The first factor of the product can be computed from line (l.5) and the second factor can be computed from line (l.4), since by definition of λ Ω , Q Ω (X) is a polynomial with independent term equal to 1 and thus Q Ω (γ)-1 γ is a linear combination of {1, γ, . . . , γ t-2 }.

Note that Q Ω (γ) = 0 (otherwise γ = ς(at) for some at ∈ Ω S and γ is public), in which case it is not hard to see that r is uniformly distributed in Z p . If the choice of y Ω leads to r = 0 (which occurs only with negligible probability anyhow), it suffices to pick a different value for y Ω . That is, in the simulation r is uniformly distributed in Z p .

Signing queries: At each signing query, F chooses a message Msg and a threshold access policy Γ = (t, S), where S is an attribute set of size s ≤ n and t ∈ {1, . . . , s}. To answer such a query, B computes M = H(Msg, Γ ) ∈ {0, 1} k and parses it as a k-bit string M = m 1 . . . m k ∈ {0, 1} k . It evaluates the functions

J(M ) = -ν • τ + ρ 0 + k j=1 ρ j • m j , (14)
K 1 (M ) = ξ 0,1 + k j=1 ξ j,1 • m j , K 2 (M ) = ξ 0,2 + k j=1 ξ j,2 • m j , (15)
for which the message-dependent vector g 3,M equals g

3,M = g 1 K 1 (M ) • g 2 K 2 (M ) • (1, 1, g) -J(M )
and aborts in the event that J(M ) = 0. Otherwise, B can generate a signature σ = C T 1 , C T 2 , C θ , π 1 , π 2 by simulating NIZK proofs for relations (2)-(3) as follows. First, B computes the query-dependent vector g ) . Observe that, as long as J(M ) = 0, g M = ( g 1 , g 2 , g 3,M ) forms a Groth-Sahai CRS for the WI setting (meaning that commitments generated using it are always perfectly hiding) and using the trapdoor information (K 1 (M ), K 2 (M ), J(M )), B can simulate proofs without knowing witnesses.

3,M = g 3,0 • k i=1 g 3,i m i = g 1 K 1 (M ) • g 2 K 2 (M ) • (1, 1, g) -J(M
To this end, B generates C T 1 , C T 2 and C θ as commitments to the identity element 1 G and uses the variable assignment T 1 = T 2 = Θ = 1 G to honestly generate a proof for equation [START_REF] Bethencourt | Ciphertext-policy attribute-based encryption[END_REF]. As for relation (3), B uses the trapdoor (K 1 (M ), K 2 (M ), J(M )) of the simulated reference string g M to generate a fake proof that Θ = h. Namely, with C θ = g 1 r θ • g 2 s θ • g t θ 3,M being a commitment to 1 G , the proof elements

π 2,1 = g r θ • h -K 1 (M )/J(M ) , π 2,2 = g s θ • h -K 2 (M )/J(M ) , π 2,3 = g t θ • h 1/J(M ) ,
are easily seen to satisfy the verification equation [START_REF] Boneh | Short group signatures[END_REF]. To make sure that π 2 = (π 2,1 , π 2,2 , π 2,3 ) is uniformly distributed in the space of valid proofs, B then performs a proof re-randomization as explained in [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF].

Forgery: at the end of the game, the adversary

F outputs σ ⋆ = C ⋆ T 1 , C ⋆ T 2 , C ⋆ θ , π ⋆ 1 , π 2
⋆ for some message Msg ⋆ and the expected target access policy Γ ⋆ = (t ⋆ , S ⋆ ). At this step, B computes

M ⋆ = m ⋆ 1 . . . m ⋆ k = H(Msg ⋆ , Γ ⋆
) and evaluates the functions J(M ⋆ ), K 1 (M ⋆ ) and K 2 (M ⋆ ) as per ( 14)- [START_REF] Fiat | How to prove yourself: practical solutions of identification and signature problems[END_REF]. It aborts if it holds that either:

1. The hash value M ⋆ = H(Msg ⋆ , Γ ⋆ ) is such that J(M ⋆ ) = 0. 2. F made a signing query (Msg, Γ ) for which (Msg, Γ ) = (Msg ⋆ , Γ ⋆ ) and H(Msg, Γ ) = H(Msg ⋆ , Γ ⋆ ).
Situation 2 obviously breaks the collision-resistance of H and we will only have to bound the probability of situation 1 occurring. If neither situation occurs (which implies J(M ⋆ ) = 0), the proofs π ⋆ 1 , π 2 ⋆ must be valid w.r.t. the Groth-Sahai CRS g M ⋆ = ( g 1 , g 2 , g 3,M ⋆ ), for which the third vector is given by

g 3,M ⋆ = g 3,0 • k i=1 g m ⋆ i 3,i = g 1 K 1 (M ⋆ ) • g 2 K 2 (M ⋆ ) = g K 1 (M ⋆ ) 1 , g K 2 (M ⋆ ) 2 , g K 1 (M ⋆ )+K 2 (M ⋆ ) ,
so that g M ⋆ forms a perfectly sound Groth-Sahai CRS. The latter perfect soundness property guarantees that, with respect to g M ⋆ , C ⋆ T 1 and C ⋆ T 2 are extractable Groth-Sahai commitments and that, by BBS-decrypting them using a, b ∈ Z p , B obtains values T 1 , T 2 that satisfy relation [START_REF] Attrapadung | Expressive key-policy attribute-based encryption with constant-size ciphertexts[END_REF]. From the values T 1 , T 2 , B can easily find the solution to the (ns ⋆ , n + t ⋆ -1, t ⋆ + 1)-aMSE-CDH problem. Indeed, from h κ•g(γ) 0 (line (l.4)) and g κ•γf (γ) 0 -1 (and line (l.1)), algorithm B simply computes

e(T 1 , h κ•g(γ) 0 )e(T 2 , g κ•γf (γ) 0 -1
) = e(g 0 , h 0 ) κf (γ) .

Using a similar analysis to the probabilistic analysis of the simulator in Waters' identity-based encryption scheme [START_REF] Waters | Efficient identity-based encryption without random oracles[END_REF] (but without the artificial abort step), we find that, with probability 1/(8 • q • (k + 1)), B has J(M ⋆ ) = 0 in the forgery stage whereas J(M ) = 0 in all signing queries. Hence, if F's advantage is ε, B's probability of success is ε/(8

• q • (k + 1)), which is non-negligible. ⊓ ⊔ A.2 Proof of Theorem 3
We show that a forger F allows constructing either a collision-finder for H or an algorithm B that computes g γ N +1 from (g, g γ , . . . , g γ N , g γ N +2 , . . . , g γ 2N ), where N = 2n + 1. In the following notations, we denote by γ the vector γ = (γ, γ 2 , . . . , γ N ) and also define z i = g γ i , for each i ∈ {1, . . . , 2N }\{N + 1}. At the very beginning of the attack game, the forger F declares which policy Γ ⋆ = (t ⋆ , S ⋆ ) it wants to be challenged upon, where t ⋆ ∈ {1, . . . , |S ⋆ |}. Armed with this information, B prepares the trusted public parameters pms and the master public key mpk as follows. It first selects a set D of n dummy attributes, then B computes the vector Y associated to the polynomial P S ⋆ (Z) according to equation (8) using a set D n-t ⋆ containing the first nt ⋆ dummy attributes. More precisely, B chooses θ 0 , δ 0 as well as a random vector θ R ← Z N p and computes H = (h 1 , . . . , h N ) ⊤ = g γ • g θ (which implicitly sets α = γ + θ), h 0 = g θ 0 • g -γ, Y and e(g, g) α = e(z 1 , z N ) δ 0 , so that the corresponding (unknown) master secret is g α = z δ 0 N +1 . In addition, B prepares a vector U = (u 0 , . . . , u k ) ⊤ ∈ G k+1 that will serve as a key for a programmable hash function [START_REF] Hofheinz | Programmable hash functions and their applications[END_REF], as in Waters' identity-based encryption scheme [START_REF] Waters | Efficient identity-based encryption without random oracles[END_REF]. Namely, B randomly picks ν R ← {0, . . . , k}, φ 0 , φ 1 , . . . , φ k R ← Z p and ρ 0 , ρ 1 , . . . , ρ k R ← {0, . . . , τ -1}, where τ = 2q (here q is an upper bound on the number of signing queries) and defines u i = z ρ i 1 • g φ i for i = 1, . . . , k and u 0 = z -ν•τ +ρ 0 1 • g φ 0 . Finally, B selects a collision-resistant hash function H. The master public key mpk = g, e(g, g) α , h 0 , H, U , D, H is given to F.

In the following, for any ω ∈ Z p , we define the vector X n ω = (1, ω, . . . , ω n-1 ) ⊤ . We note that given any set S ⊂ Z p of cardinality less than n, the vectors { X n ω } ω∈S are linearly independent.

Private key queries: During the game, F can obtain private keys for any attribute set Ω such that |Ω ∩ S ⋆ | < t ⋆ . Since |S ⋆ ∩ Ω| < t ⋆ , the cardinality of (S ⋆ ∩ Ω) ∪ D n-t ⋆ is strictly less than n. Consequently, the vector X n 0 = (1, 0, . . . , 0) ⊤ cannot be in the span of the vectors { X n ω } ω∈(S ⋆ ∩Ω)∪D n-t ⋆ . Hence, there must exist an efficiently computable vector τ such that X n ω , τ = 0 for any ω ∈ (S ⋆ ∩ Ω) ∪ D n-t ⋆ and such that X n 0 , τ = 0 (according to Proposition 1 in [START_REF] Goyal | Attribute-based encryption for fine-grained access control of encrypted data[END_REF]). Let µ denote this value X n 0 , τ . To construct a private key, B has to define a vector u = α • β ∈ Z n p satisfying the constraint X n 0 , u = α, for some random constrained vector β = (1, β1 , . . . , βn-1 ) ⊤ that implicitly defines the coefficients of Q Ω [X] as β i = α • βi for i = 1, . . . , n -1. To this end, B proceeds as in the proof of Theorem 3 in [START_REF] Goyal | Attribute-based encryption for fine-grained access control of encrypted data[END_REF], by implicitly setting u as u = v + ψ • τ , where v = (v 1 , . . . , v n ) ⊤ ∈ Z n p is a randomly chosen vector and ψ = (αv 1 )/µ, so that X n 0 , u = α. The task of B is thus to simulate (without knowing u) the private key components for any ω ∈ Ω ∪ D, which are:

SK ω = D ω,1 , D ω,2 , {K ω,i } N -1 i=1 = g Q Ω (ω) • h rω 0 , g rω , {h -ω i 1 h i+1 } N -1 i=1 ,
where Q Ω (ω) = X n ω , u . Let us divide the set Ω ∪ D into two subsets: Υ 1 = (Ω ∪ D) ∩ ((S ⋆ ∩ Ω) ∪ D n-t ⋆ ) and Υ 2 , its complement.

1. For each ω ∈ Υ 1 , we have Q Ω (ω) = X n ω , u = X n ω , v which is efficiently computable by B. Hence, B can simply pick r ω R ← Z * p and define

D ω = D ω,1 , D ω,2 , {K ω,i } N -1 i=1 = g Q Ω (ω) • h rω 0 , g rω , {(h -ω i 1 h i+1 ) rω } N -1 i=1 .
2. For each ω ∈ Υ 2 , B can construct a valid key component SK ω = D ω,1 , D ω,2 , {K ω,i } N -1 i=1 in two steps. The first step consists in building a tuple of the form

D * ω,1 , D * ω,2 , {K * ω,i } N -1 i=1 = g α • h rω 0 , g rω , {(h -ω i 1 h i+1 ) rω } N -1 i=1
using that attribute ω is not in the set (S ⋆ ∪ D n-t ⋆ ). To this end, B proceeds as in [START_REF] Boneh | Generalized identity based and broadcast encryption schemes[END_REF]. Let M ω be the N × (N -1) matrix

M ω = -ω -ω 2 • • • -ω N -1 I N -1 .
Pick ξ 1 R ← Z * p . Note that the vector ξ = ξ 1 • (1, ω, . . . , ω N -1 ) ⊤ satisfies that ξ ⊤ M ω = 0 while Y , ξ = ξ 1 • P S ⋆ (ω) = 0. The simulator B computes

D * ω,1 , D * ω,2 = g α • h rω 0 , g rω (16)
and

K * ω,1 , . . . , K * ω,N -1 ⊤ = g rωM ⊤ ω α , (17)
with α = (α 1 , . . . , α N ) ⊤ and where the exponent rω is defined as rω = r + δ 0 (γ N , γ N -1 , . . . , γ) ⊤ , ξ / Y , ξ for some r R ← Z p chosen by B. Since g M ⊤ ω α = (h -ω 1 h 2 , . . . , h -ω N -1 1 h N ) ⊤ , if we can argue that both expressions [START_REF] Goyal | Attribute-based encryption for fine-grained access control of encrypted data[END_REF] and [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF] are computable by B, we will have concluded the first step of the key generation process.

Observe that for any vector f ∈ Z N p the coefficient of γ N +1 in the product rω f , γ is δ 0 f , ξ / Y , ξ . The reason why B can compute the second factor of side of D * ω,1 in expression ( 16) is that the coefficient of g γ N +1 in D * ω,1 is 0. Indeed, D * ω,1 = g α • h rω 0 = z δ 0 N +1 • g θ 0 • g -γ, Y rω and the

Setup.

  The adversary D specifies a universe of attributes P and an integer n ∈ poly(λ), that are sent to the challenger. The challenger runs pms ← ABS.TSetup(1 λ , P, n) and sends pms to D. The adversary D runs (mpk, msk) ← ABS.MSetup(pms) and sends (mpk, msk) to the challenger (who must verify consistency of this master key pair). Challenge. D outputs a tuple (Γ, Ω 0 , Ω 1 , Msg), where Γ = (t, S) is a threshold predicate such that 1 ≤ t ≤ |S| ≤ n and Ω 0 , Ω 1 are attribute sets satisfying |Ω b ∩ S| ≥ t for each b ∈ {0, 1}. The challenger picks a random bit β R ← {0, 1}, runs SK Ω β ← ABS.Keygen(pms, mpk, msk, Ω β ) and computes σ ⋆ ← ABS.Sign(pms, mpk, SK Ω β , Msg, Γ ), which is sent as a challenge to A. Guess. D outputs a bit β ′ ∈ {0, 1} and wins if β ′ = β. The advantage of D is measured in the usual way, as the distance Adv Priv D,ABS (λ) := |Pr[β ′ = β] -1 2 |.

  2n-1 . ◮ Keygen(pms, mpk, msk, Ω): to generate a key for the attribute set Ω, pick r SK Ω , Msg, Γ ): to sign Msg ∈ {0, 1} * w.r.t. the policy Γ = (t, S), where S ⊂ P is an attribute set of size s = |S| ≤ n and 1 ≤ t ≤ s ≤ n, the algorithm returns ⊥ if |Ω ∩ S| < t. Otherwise, it first parses SK Ω as

									R ← Z * p and compute
	the private key
	SK Ω =	g	r γ+ς(at)	at∈Ω	, h rγ i	i=0,...,n-2	, h	r-1 γ	.
	◮ Sign(pms, mpk,

  ) 2. For each d ∈ D, generate a private key component SK d = (D d,1 , D d,2 , K d,1 , . . . , K d,N -1 ) in the same way as in (6), by choosing a fresh random value r d ∈ Z p and computing

  private key finally consists of SK Ω = {SK ω } ω∈Ω , {SK d } d∈D . ◮ Sign(pms, mpk, SK Ω , Msg, Γ ): to sign Msg ∈ {0, 1} * w.r.t. the policy Γ = (t, S), where S is an attribute set of size s = |S| ≤ n and t ∈ {1, . . . , s}, the algorithm first computes M = H(Msg, Γ ) ∈ {0, 1} k and parses the private key SK Ω as {SK ω } ω∈Ω , {SK d } d∈D . 1. It considers the subset D n-t ⊂ D containing the nt first attributes of D (chosen in some pre-specified lexicographical order). It also chooses an arbitrary subset S t ⊂ Ω ∩ S such that |S t | = t and defines Y = (y 1 , . . . , y N ) ⊤ as the vector containing the coefficients of the polynomial

  compartmented if there exists a sequence of thresholds t; t 1 , t 2 , . . . , t We can assume t ≥ t 1 + . . . + t c ; otherwise, replacing t with t ′ = t 1 + . . . + t c and obtain the same predicate.

c such that Γ = {Ω ⊂ S : |Ω| ≥ t and |Ω ∩ S ℓ | ≥ t ℓ , ∀ℓ ∈ {1, 2, . . . , c}} Such a predicate makes sense only when t ≤ |S| and t ℓ ≤ |S ℓ |, for ℓ = 1, . . . , c.

which means that the number of possible attributes is polynomial in the security parameter, which is highly sufficient for most applications

A Unforgeability Proofs

In this appendix we detail the unforgeability proofs of the two ABS schemes proposed in this work.

A.1 Proof of Theorem 1

We prove the theorem by considering a modified distribution of vectors ( g 1 , g 2 , { g 3,i } k i=0 ) that are used to generate Groth-Sahai reference strings.

Namely, to prepare g 1 , g 2 and { g 3,i } k i=0 , we randomly pick ν R ← {0, . . . , k}, ξ 0,1 , ξ 1,1 , . . . , ξ k,1 R ← Z p , ξ 0,2 , ξ 1,2 , . . . , ξ k,2 R ← Z p and ρ 0 , ρ 1 , . . . , ρ k R ← {0, . . . , τ -1}, where τ = 2q (where q is the number of signing queries). We first set g 1 = (g 1 , 1, g) ⊤ and g 2 = (1, g 2 , g) ⊤ , where g 1 = g a and g 2 = g b for randomly chosen a, b R ← Z p . We then defines { g 3,i } k i=0 by setting g 3,0 = g 1 ξ 0,1 • g 2 ξ 0,2 •((1, 1, g) ⊤ ) ν•τ -ρ 0 as well as g 3,i = g

i=0 is obviously different from its distribution in the real scheme. However, we argue that, if this modification in the distribution of public parameters noticeably affects the adversary's probability of success, the DLIN assumption can be broken. This statement if proved by lemma 1.

In a second step, lemma 2 proves that, with the above way of generating g 1 , g 2 , {g 3,i } k i=0 , a successful forger F implies either a PPT algorithm to find collisions on H, a distinguisher for the DLIN problem or an algorithm B that solves the (ns ⋆ , n + t ⋆ -1, t ⋆ + 1)-aMSE-CDH problem. Lemma 1. Under the above distribution of g 1 , g 2 , { g 3,i } k i=0 , F's advantage is negligibly close to its advantage in the real scheme if the DLIN assumption holds in G.

Proof. The proof uses a sequence of 2k + 2 games Game real , Game 0 , Game ′ 0 , Game 1 , Game ′ 1 , . . . , Game k , Game ′ k which proceed as follows.

Game real : is a game where the adversary is given vectors ( g 1 , g 2 , { g 3,i } k i=0 ) as in the real scheme. Game 0 : is a game where the vectors g 1 = (g 1 , 1, g) ⊤ and g 2 = (1, g 2 , g) ⊤ are chosen as in Game real but g 3,0 is chosen as

Game ′ 0 : is identical to Game 0 with a modification in the distribution of the vector g 3,0 which is now given by g 3,0 = g 1 ξ 0,1 • g 2 ξ 0,2 • ((1, 1, g) ⊤ ) ν•τ -ρ 0 , for some ν R ← {0, . . . , k} and ρ 0 R ← {0, . . . , τ -1}, while the distribution of { g 3,i } k i=1 remains the same as in Game real . Game j (1 ≤ j ≤ k): is identical to Game ′ j-1 but the distribution of the vector g 3,j is changed into

As for vectors { g 3,i } k i=j+1 , they still live in the span of g 1 and g 2 as in Game real . Game ′ j (1 ≤ j ≤ k): is like Game j but, instead of being a truly random vector of G 3 , g 3,j is now obtained as

In Game ′ k , the distribution of g 1 , g 2 , {g 3,i } k i=0 is clearly identical to the one suggested in the proof of theorem 1 and we just have to argue that all these games are computationally indistinguishable under the DLIN assumption. We first explain how the indistinguishability of Game 1 , Game ′ 1 , . . . , Game k , Game ′ k can be proved. Claim 1. Under DLIN, no PPT adversary can distinguish Game j from Game ′ j-1 for all 1 ≤ j ≤ k.

Proof. We construct a distinguisher B DLIN that takes as input (g,

It generates g 3,0 , . . . , g 3,j-1 as Game ′ j-1 and g 3,j+1 , . . . , g 3,k as in Game real . As for g 3,j , algorithm B DLIN defines it as g 3,j = (g

At the end of the attack game, the distinguisher B DLIN outputs 1 if the forger F manages to create a valid forgery and 0 otherwise. Claim 2. Under DLIN, Game ′ j is computationally indistinguishable from Game j for all 1 ≤ j ≤ k.

Proof. We show a distinguisher B DLIN that takes as input a tuple (g, g 1 , g 2 , g δ 1 1 , g δ 2 2 , χ) and decides if χ = g δ 1 +δ 2 or χ ∈ R G. To this end, B DLIN first defines g 1 = (g 1 , 1, g) ⊤ , g 2 = (1, g 2 , g) ⊤ . Vectors g 3,0 , g 3,1 , . . . , g 3,j-1 are then chosen as in Game ′ j-1 while vectors g 3,j+1 , . . . , g 3,k are selected as in the real game Game real . To prepare the vector g 3,j , the distinguisher B DLIN randomly picks

is playing Game j with the forger F since g 3,j has the same distribution no matter if χ is multiplied by g -ρ i or not. If χ = g δ 1 +δ 2 , B DLIN is rather playing Game ′ j with F. At the end of its interaction with F, B DLIN outputs 1 if F outputs a successful forgery and 0 otherwise. The computational indistinguishability of Game 0 , Game ′ 0 and Game 1 is proved in the same way. The only change is that, during the transition from Game 0 to Game ′ 0 , χ is multiplied by g ν•τ -ρ 0 . Finally, the indistinguishability of Game real and Game 0 is established exactly in the same way as that of Game ′ j-1 and Game j , for j ∈ {1, . . . , k}, in the proof of Claim 1. ⊓ ⊔ Lemma 2. Under the modified distribution of g 1 , g 2 , {g 3,i } k i=0 , F's advantage is negligible if the (ns ⋆ , n + t ⋆ -1, t ⋆ + 1)-aMSE-CDH assumption holds in (G, G T ) and if H is a collision-resistant hash function.

Proof. We denote by I( -→ x 2n+t * -s * -1 , κ, α, γ, ω, T ) the input of the algorithm B that we design to solve the aMSE-CDH problem (recall Definition 1 in Section 2.2). At the outset of the game, the adversary F declares its chosen challenge policy Γ ⋆ = (t ⋆ , S ⋆ ), with s ⋆ = |S ⋆ |. Using this information, B chooses g 1 , g 2 , {g 3,i } k i=0 as specified in the second paragraph of the proof of Theorem 1. It then generates the rest of pms and mpk as follows. The algorithm B defines an arbitrary encoding coefficient of γ N +1 is -δ 0 in the product -r j γ, Y , as we can see applying the observation above in the case f = Y . Since M ⊤ ω ξ = 0, applying again the observation above, now to the case where f ⊤ is successively set as the rows of M ⊤ ω , we have that the unknown term z N +1 = g γ N +1 does not appear in g rj M ⊤ ω α , which is thus computable.

This concludes the first step of the key generation process. In the second step, we just have to turn

into a suitable key component SK ω . Note that

where the coefficients

) by setting

Signing queries: At any time, F is also allowed to obtain signatures on arbitrary messages. At each signing query, F supplies a message Msg and a threshold access policy Γ = (t, S), where S is an attribute set of size s ≤ n and t ∈ {1, . . . , s}. To answer such a query, B computes M = H(Msg, Γ ) ∈ {0, 1} k and parses it as a k-bit string m 1 . . . m k . It evaluates the functions

for which the programmable hash function implemented by the vector U = (u 0 , . . . , ) , and aborts in the event that J(M ) = 0. Then, B constructs the vector Y = (y 1 , . . . , y N ) ⊤ whose coordinates are the coefficients of the polynomial P S (Z) which is obtained following relation [START_REF] Boneh | Collusion resistant broadcast encryption with short ciphertexts and private keys[END_REF], by augmenting S with nt dummy attributes. Recall that B has to generate a signature of the form

for some r, z ∈ R Z p . To this end, B uses the usual technique (which dates back to [START_REF] Boneh | Efficient selective-ID secure identity-based encryption without random oracles[END_REF]) consisting in implicitly defining z = z -γ N •δ 0 J(M ) , for a randomly chosen z R ← Z p , and computing

and α is implicitly defined as α = γ N +1 • δ 0 , the above triple is easily seen to have the required distribution [START_REF] Hofheinz | Programmable hash functions and their applications[END_REF].

Forgery: The game ends with the adversary outputting a forgery σ ⋆ = (σ ⋆ 1 , σ ⋆ 2 , σ ⋆ 3 ) for some message Msg ⋆ and the target access policy Γ ⋆ = (t ⋆ , S ⋆ ) without having made any illegal query. At this step, B computes m ⋆ 1 . . . m ⋆ k = M ⋆ = H(Msg ⋆ , Γ ⋆ ) and evaluates the functions J(M ⋆ ) and K(M ⋆ ) as per [START_REF] Herranz | Constant-size ciphertexts in threshold attribute-based encryption[END_REF]. It aborts if it holds that either:

1. The hash value M ⋆ = H(Msg ⋆ , Γ ⋆ ) is such that J(M ⋆ ) = 0. 2. F made a signing query (Msg, Γ ) such that (Msg, Γ ) = (Msg ⋆ , Γ ⋆ ) and H(Msg, Γ ) = H(Msg ⋆ , Γ ⋆ ).

We will see that situation 1 is avoided with noticeable probability and case 2 obviously breaks the collision-resistance of H. If neither of the above situation occurs (and thus J(M ⋆ ) = 0), B can obtain the searched value z N +1 = g γ N +1 as follows. Since the vector Y = (y 1 , . . . , y N ) ⊤ derived from Γ ⋆ is such that h 0 • N i=1 h y i i = g θ 0 + θ, Y and given that J(M ⋆ ) = 0 and σ ⋆ satisfies the verification equation ( 13), we must have e(g, g) (γ N +1 )•δ 0 = e(σ ⋆ 1 , g) e(σ ⋆ 2 , g θ 0 + θ, Y ) • e(σ ⋆ 3 , g K(M ⋆ ) )

,

1/δ 0 is computable by B.

The same analysis as in Waters' identity-based encryption scheme [START_REF] Waters | Efficient identity-based encryption without random oracles[END_REF] shows that, with probability 1/(8 • q • (k + 1)), B gets lucky and has J(M ⋆ ) = 0 in the forgery stage whereas J(M ) = 0 in all signing queries. It comes that, if F's advantage is ε, B's success probability is ε/(8 • q • (k + 1)), which is non-negligible.

⊓ ⊔