Junqing Gong

Benoît Libert

Somindu C Ramanna

Compact IBBE and Fuzzy IBE from Simple Assumptions

Keywords: Identity-based broadcast encryption, fuzzy IBE, space efficiency, simple assumptions

We propose new constructions for identity-based broadcast encryption (IBBE) and fuzzy identity-based encryption (FIBE) in bilinear groups of composite order. Our starting point is the IBBE scheme of Delerablée (Asiacrypt 2007) and the FIBE scheme of Herranz et al. (PKC 2010) proven secure under parameterised assumptions called generalised decisional bilinear Diffie-Hellman (GDDHE) and augmented multi-sequence of exponents Diffie-Hellman (aMSE-DDH) respectively. The two schemes are described in the prime-order pairing group. We transform the schemes into the setting of (symmetric) composite-order groups and prove security from two static assumptions (subgroup decision). The Déjà Q framework of Chase et al. (Asiacrypt 2016) is known to cover a large class of parameterised assumptions (dubbed über assumption), that is, these assumptions, when defined in asymmetric composite-order groups, are implied by subgroup decision assumptions in the underlying compositeorder groups. We argue that the GDDHE and aMSE-DDH assumptions are not covered by the Déjà Q über assumption framework. We therefore work out direct security reductions for the two schemes based on subgroup decision assumptions. Furthermore, our proofs involve novel extensions of Déjà Q techniques of Wee (TCC 2016-A) and Chase et al.

Our constructions have constant-size ciphertexts. The IBBE has constant-size keys as well and guarantees stronger security as compared to Delerablée's IBBE, thus making it the first compact IBBE known to be selectively secure without random oracles under simple assumptions. The fuzzy IBE scheme is the first to simultaneously feature constant-size ciphertexts and security under standard assumptions.

Introduction

Identity-based encryption (IBE) [START_REF] Shamir | Identity-Based Cryptosystems and Signature Schemes[END_REF] is a public-key paradigm where users' private keys are generated by trusted authorities and derived from some easy-to-remember string (like an email address) that serves as a public key so as to simplify key management. Attribute-based encryption (ABE) [START_REF] Sahai | Fuzzy Identity-Based Encryption In Eurocrypt'05[END_REF][START_REF] Goyal | Attribute-based encryption for fine-grained access control of encrypted data[END_REF] is a powerful extension of IBE where ciphertexts are labeled with a set of descriptive attributes (e.g., "hiring committee", "admin", . . . ) in such a way that decryption works whenever these attributes satisfy an access policy which is hard-coded in the decryption key.

Functional encryption (FE) [START_REF] Sahai | Fuzzy Identity-Based Encryption In Eurocrypt'05[END_REF][START_REF] Boneh | Functional Encryption: Definitions and Challenges[END_REF] is an extreme generalization of IBE, where a master private key SK allows deriving sub-keys SK F associated with functions F . Given an encryption C of a message X, a sub-key SK F allows computing F (X) while revealing nothing else about X. The message X = (ind, M ) usually consists of an index ind, which is essentially a set of attributes, and a message M , which is sometimes called "payload". While the latter is always computationally hidden, the index ind of a ciphertext may be public or private. Not surprisingly, schemes in the public index setting tend to be significantly more efficient in terms of ciphertext and key sizes.

In the private-index setting, anonymous IBE [START_REF] Boneh | Public Key Encryption with Keyword Search[END_REF][START_REF] Boyen | Anonymous Hierarchical Identity-Based Encryption (Without Random Oracles)[END_REF] is an example of functional encryption for the equality testing functionality. In the public [START_REF] Sahai | Fuzzy Identity-Based Encryption In Eurocrypt'05[END_REF][START_REF] Goyal | Attribute-based encryption for fine-grained access control of encrypted data[END_REF] and private-index [START_REF] Katz | Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products[END_REF] cases, ABE can be cast as another particular flavour of FE, where private keys are associated with expressive access policies. These primitives provide fine-grained access control [START_REF] Sahai | Fuzzy Identity-Based Encryption In Eurocrypt'05[END_REF] or privacy-preserving searches over encrypted data [START_REF] Boneh | Public Key Encryption with Keyword Search[END_REF][START_REF] Abdalla | Searchable Encryption Revisited: Consistency Properties, Relation to Anonymous IBE, and Extensions[END_REF]. In its key-policy (KP-ABE) flavour, ABE involves private keys associated with a possibly complex Boolean expression F and, if the ciphertext encrypts the message X = (ind, M ), the private key SK F reveals M if and only if F (ind) = 1. Ciphertext-policy ABE (CP-ABE) schemes proceed the other way around: ciphertexts are labeled with a policy F ; private keys are associated with an attribute set ind and decryption succeeds whenever F (ind) = 1.

The usual "collusion-resistance" requirement captures the intuition that no collection of private keys should make it possible to decrypt a ciphertext that none of these keys can individually decrypt. While properly defining the security of FE turns out to be non-trivial [START_REF] Boneh | Functional Encryption: Definitions and Challenges[END_REF], the literature usually distinguishes selective adversaries [START_REF] Canetti | A Forward-Secure Public-Key Encryption Scheme[END_REF] -that have to declare the index of the challenge ciphertext ind upfront (even before seeing the master public key) -from adaptive adversaries, which can choose ind after having made a number of private key queries for functions of their choice.

In terms of expressiveness, a major challenge is certainly to efficiently evaluate any polynomialtime-computable function F over encrypted data. While theoretical solutions achieve this goal using the obfuscation machinery [START_REF] Garg | Candidate Indistinguishability Obfuscation and Functional Encryption for all Circuits[END_REF], practical instantiations of functional encryption are only known for very restricted classes of functions (such as IBE [START_REF] Boneh | Identity-Based Encryption from the Weil Pairing[END_REF][START_REF] Waters | Efficient Identity-Based Encryption without Random Oracles[END_REF] or ABE [START_REF] Katz | Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products[END_REF]) for the time being.

Even for particular functionalities and selective adversaries, proving security is challenging when we seek to optimise the size of ciphertexts and keys. For example, squeezing many attributes in the same ciphertext component often comes at the price of larger private keys [START_REF] Attrapadung | Expressive key-policy attribute-based encryption with constant-size ciphertexts[END_REF][START_REF] Attrapadung | Attribute-based encryption schemes with constant-size ciphertexts[END_REF] or security proofs under fancy q-type assumptions [START_REF] Boneh | Hierarchical Identity-Based encryption with Constant Size Ciphertext[END_REF][START_REF] Boneh | Collusion-Resistant Broadcast Encryption with Short Ciphertexts and Private Keys[END_REF] (or both). Likewise, short private keys and public parameters [START_REF] Lewko | Revocation Systems with Very Small Private Keys[END_REF][START_REF] Rouselakis | Practical constructions and new proof methods for large universe attribute-based encryption[END_REF] often entail strong, variable-size assumptions. Eventualy, constant-size ciphertexts or keys ("constant" meaning that it only depends on the security parameter and not on the number of adversarial queries or features of the system) often translate into non-constant-size assumptions. In some situations, information theoretic arguments [START_REF] Gay | Communication Complexity of Conditional Disclosure of Secrets and Attribute-Based Encryption[END_REF] even rule out the possibility of simultaneously achieving constant-size ciphertexts and keys, no matter which assumption is considered.

Here, we restrict ourselves to specific functionalities for which we are interested in proving the security of compact schemes under well-studied, constant-size assumptions. By "compact", we mean that ciphertexts can be comprised of a constant number of group elements -no matter how many attributes or users are associated with them -without inflating the private key size. In particular, private keys should be no longer than in realisations of the same functionality without short ciphertexts. Finally, we aim at avoiding the caveat of relying on variable-size, q-type assumptions, which should notoriously be used with caution [START_REF] Cheon | Security Analysis of the Strong Diffie-Hellman Problem[END_REF].

We achieve this goal for two natural extensions of IBE, which are known as identity-based broadcast encryption (IBBE) [START_REF] Abdalla | Generalized Key Delegation for Hierarchical Identity-Based Encryption[END_REF][START_REF] Sakai | Identity-Based Broadcast Encryption[END_REF] and fuzzy identity-based encryption (FIBE) [START_REF] Sahai | Fuzzy Identity-Based Encryption In Eurocrypt'05[END_REF]. In the former, ciphertexts are encrypted for a list of identities. The latter is an ABE for policies consisting of a single threshold gate: i.e., ciphertexts and private keys both correspond to a set of attributes and decryption succeeds whenever the two sets have a sufficiently large intersection. In fact, IBBE and FIBE can both be seen as special cases of CP-ABE for policies consisting of a single gate: an IBBE is nothing but a CP-ABE for one OR gate, which is implied by FIBE for 1-out-of-n gates. However, considering the two primitives separately allows obtaining shorter private keys in the IBBE case.

Our Contribution

We describe the first IBBE system with a security proof under constant-size assumptions and that simultaneously features constant-size ciphertexts and private keys. In our scheme, only the size of public parameters depends on the maximal number n of receivers per ciphertext. Users' private keys only consist of a single(!) group element while ciphertexts are only longer than plaintexts by 2 elements of a composite-order group. We prove selective security in the standard model under subgroup assumptions [START_REF] Lewko | New Techniques for Dual System Encryption and Fully Secure HIBE with Short Ciphertexts[END_REF] in bilinear groups of order N = p 1 p 2 p 3 . In comparison, all earlier IBBE realisations with short ciphertexts either incur O(n)-size private keys [START_REF] Abdalla | Generalized Key Delegation for Hierarchical Identity-Based Encryption[END_REF][START_REF] Boneh | Generalized Identity Based and Broadcast Encryption Schemes[END_REF][START_REF] Attrapadung | Functional encryption for inner product: Achieving constant-size ciphertexts with adaptive security or support for negation[END_REF][START_REF] Okamoto | Achieving short ciphertexts or short secret-keys for adaptively secure general innerproduct encryption[END_REF] or combine the random oracle model [START_REF] Bellare | Random Oracles are Practical: A Paradigm for Designing Efficient Protocols[END_REF] with very ad hoc assumptions [START_REF] Sakai | Identity-Based Broadcast Encryption[END_REF][START_REF] Delerablée | Identity-Based Broadcast Encryption with Constant Size Ciphertexts and Private Keys[END_REF] tailored to the result to be proved.

As a second contribution, we extend our IBBE scheme into a fuzzy IBE system with O(1)size ciphertexts and private keys made of O( ) group elements, where is the maximal number of attributes per identity. Our FIBE scheme thus asymptotically achieves the same private key size as [START_REF] Sahai | Fuzzy Identity-Based Encryption In Eurocrypt'05[END_REF] with the benefit of constant-size ciphertexts, regardless of the number of ciphertext attributes. In contrast, except [START_REF] Herranz | Constant-Size Ciphertexts in Threshold Attribute-Based Encryption[END_REF], previously known KP-ABE systems with short ciphertexts either inflate private keys by a factor O( ) [START_REF] Attrapadung | Expressive key-policy attribute-based encryption with constant-size ciphertexts[END_REF][START_REF] Okamoto | Achieving short ciphertexts or short secret-keys for adaptively secure general innerproduct encryption[END_REF][START_REF] Attrapadung | Dual System Encryption via Doubly Selective Security: Framework, Fully Secure Functional Encryption for Regular Languages, and More[END_REF][START_REF] Okamoto | Achieving short ciphertexts or short secret-keys for adaptively secure general innerproduct encryption[END_REF] or are restricted to small attribute universes [START_REF] Hohenberger | Attribute-Based Encryption with Fast Decryption[END_REF].

While our constructions rely on composite order groups where pairings are rather expensive to compute [START_REF] Freeman | Converting Pairing-Based Cryptosystems from Composite-Order Groups to Prime-Order Groups[END_REF], they only require two pairing evaluations on behalf of the receiver (and no pairing on the sender's side). Our schemes are proved selectively secure using the Déjà Q technique of Chase and Meiklejohn [START_REF] Chase | Déjà Q: Using Dual Systems to Revisit q-Type Assumptions[END_REF], which was re-used by Wee [63] and refined by Chase et al. [START_REF] Chase | Déjà Q All Over Again: Tighter and Broader Reductions of q-Type Assumptions[END_REF]. In Appendix A, we provide detailed comparisons of our schemes with previously known realizations.

Overview of our Techniques

Our identity-based broadcast encryption scheme is obtained by instantiating (a variant of) Delerablée's IBBE [START_REF] Delerablée | Identity-Based Broadcast Encryption with Constant Size Ciphertexts and Private Keys[END_REF] in composite order groups and providing a direct security proof, analogously to Wee's IBE [63]. In prime order groups, Delerablée's construction [START_REF] Delerablée | Identity-Based Broadcast Encryption with Constant Size Ciphertexts and Private Keys[END_REF] is proved selectively secure in the random oracle model under a highly non-standard q-type assumption, where q simultaneously depends on the number of private key queries and the maximal number of receivers per ciphertext. While this assumption is a special case of the Uber assumption of Boneh, Boyen and Goh [START_REF] Boneh | Hierarchical Identity-Based encryption with Constant Size Ciphertext[END_REF], it seems to escape the family of assumptions that reduce the constant-size subgroup assumptions via the framework of Chase, Maller and Meiklejohn [START_REF] Chase | Déjà Q All Over Again: Tighter and Broader Reductions of q-Type Assumptions[END_REF]: in Section 3.1, we indeed explain why the results of [START_REF] Chase | Déjà Q All Over Again: Tighter and Broader Reductions of q-Type Assumptions[END_REF] alone do not immediately guarantee the security of Delerablée's IBBE in composite order groups. 4 Moreover, even if they did, a direct instantiation of [START_REF] Delerablée | Identity-Based Broadcast Encryption with Constant Size Ciphertexts and Private Keys[END_REF] in composite order groups would only be guaranteed to be secure in the random oracle model. 5 In contrast, we give a direct proof of selective security in the standard model.

Just like [START_REF] Delerablée | Identity-Based Broadcast Encryption with Constant Size Ciphertexts and Private Keys[END_REF]63], our scheme uses the private key generation technique of the Sakai-Kasahara IBE [START_REF] Sakai | ID-based Cryptosystems with Pairing on Elliptic Curve[END_REF], which computes inversions in the exponent. Letting G be a group of order N = p 1 p 2 p 3 with subgroups of order p i for each i ∈ {1, 2, 3}, if g γ ∈ G p 1 and G i = g (α i ) ∈ G p 1 are part of the public parameters, a private key for the identity id consists of SK id = u γ/(α+id) • X p 3 , where u ∈ G p 1 belongs to the master secret key and X p 3 ∈ R G p 3 . If S = {id 1 , . . . , id } denotes the set of authorised receivers, one of the ciphertext components packs their identities into one group element g s• i∈S (α+id) , which can be seen as a randomised version of Nguyen's accumulator [START_REF] Nguyen | Accumulators from Bilinear Pairings and Applications[END_REF]. As shown in [START_REF] Delerablée | Identity-Based Broadcast Encryption with Constant Size Ciphertexts and Private Keys[END_REF], by introducing g γ•s in the ciphertext and blinding the message as M ⊕ H(e(g, u) γ•s ), we can enable decryption by exploiting the divisibility properties of the polynomial p S (α) = i∈S (α + id), analogously to [START_REF] Nguyen | Accumulators from Bilinear Pairings and Applications[END_REF]. Like the security proof of Wee's IBE [63], our proof proceeds by first introducing G p 2 components in ciphertexts. Then, following the technique of [START_REF] Chase | Déjà Q: Using Dual Systems to Revisit q-Type Assumptions[END_REF], it uses the entropy of α, γ mod p 2 -which are information theoretically hidden by g γ and

G i = g (α i ) -to gradually introduce G p 2 components of the form g k j=1 γ•r j •p S (α j )/(α j +id) 2
, where {r j } k j=1 are shared by all private keys. At each step, we can increase the number of terms in the exponent so that, when k is sufficiently large, all keys SK id have independent random components of order p 2 . At this point, an information theoretic argument shows that the ciphertext statistically hides the plaintext.

The crucial step of the proof consists of arguing that the newly introduced term in the sum k j=1 r j • p S (α j )/(α j + id) is statistically independent of the public parameters. At this step, our information theoretic argument differs from Wee's [63] because, in our IBBE system, public parameters contain additional group elements of the form

U i = u α i • R 3,i , which inherit G p 2 components that depend on k j=1 r j • α i j mod p 2 ,
for the same coefficients r j ∈ Z p 2 as those showing up in private keys. Since private keys and public key components {U i } n i=1 have correlated semi-functional components 6 that share the same {r j mod p 2 } k j=1 , we have to consistently maintain this correlation at all steps of the sequence of game and argue that, when we reach the final game, the G p 2 components of SK id 1 , . . . , SK idq and {U i } n i=1 are uncorrelated in the adversary's view. In Wee's constructions [63], this is done by arguing that matrices of the form (α i j ) i,j∈[q] or 1/(α j + id i ) i,j are invertible. Here, we are presented with more complex square matrices that involve the two kinds of entries and also depend on the polynomial p S (α) = id∈S (α+id), where S is the set of the target identities. More precisely, these matrices contain sub-matrices of the form p S (α i )/(α i + id j ) i,j , where id j denotes the j-th private key query. We use the property that the overall square matrices are invertible over Z p 2 as long as none of the first-degree (α + id j ) divides p S (α) (i.e., id j ∈ S for all private key queries id j ). When this is the case, we are guaranteed that the G p 2 components of ciphertexts, private keys and public parameters are i.i.d. in the adversary's view.

Our fuzzy IBE construction is an adaptation of the system described by Herranz, Laguillaumie and Ràfols [START_REF] Herranz | Constant-Size Ciphertexts in Threshold Attribute-Based Encryption[END_REF][START_REF] Attrapadung | Attribute-based encryption schemes with constant-size ciphertexts[END_REF] in prime order groups, which is itself inspired by the dynamic threshold encryption primitive of Delerablée and Pointcheval [START_REF] Delerablée | Dynamic Threshold Public-Key Encryption[END_REF] and relies on a similarly strong assumption. The FIBE system of [START_REF] Herranz | Constant-Size Ciphertexts in Threshold Attribute-Based Encryption[END_REF] modifies [START_REF] Delerablée | Identity-Based Broadcast Encryption with Constant Size Ciphertexts and Private Keys[END_REF][START_REF] Delerablée | Dynamic Threshold Public-Key Encryption[END_REF] by randomizing the generation of private keys. In our construction, private keys for an attribute set {id 1 , . . . , id } similarly consist of

K i = u γ α+id i • X 3,i i=1 , K i = u α i • X 3,i n-1 i=1 , K 0 = u • u 0 • X 3,0 ,
where u ∈ R G p 1 and X 3,i ∈ R G p 3 are freshly chosen for each key and u 0 ∈ G p 1 is a master secret key component which is committed via e(g, u 0 ) γ in the master public key. Intuitively, the public parameters u α i 0 • R 3,i of Delerablée's IBBE are now replaced by similar-looking private key components K i = u α i • X 3,i for random u ∈ R G 1 that are used in K 0 to blind the master secret key u 0 (collusion-resistance is ensured by the fact that distinct keys involve fresh randomizers u).

Due to the strong structural similarity, the proof for the selective security of our fuzzy IBE can be viewed as an extension of that for our IBBE system. From the viewpoint of reduction, the fresh u ∈ G p 1 in each secret key allows us to correspond each secret key to a fresh IBBE instance and analyse them in an independent fashion. In particular, by considering K i as SK id i and K i as U i , we can apply the proof method of our IBBE to introduce independent random G p 2 component in all these components and K 0 (with u 0 • X 3,0 ). As discussed earlier, the core step is again to argue the invertibility of a matrix of some special form for each secret key. Although the matrices we are considering now look like those for the IBBE system, the situation is actually more complex. More specifically, the matrices contain sub-matrices of the form (p S ,τ (α i )/(α i + id j )) i,j where p S ,τ (α) = id∈S (α + id) • i∈[δ] (α + d i ) where S is the set for the target fuzzy identity, (d i ) i is a set of dummy identities and δ depends on the target threshold τ * . Unlike the IBBE case, there can be an id j ∈ {id 1 , . . . , id } such that id j ∈ S so that (α + id j ) divides p S ,τ (α) in the FIBE case. This prevents us from directly applying our previous result on the matrices. Instead, we will prove the property that these matrices are still invertible as long as the number of such id j do not exceed the target threshold τ * . Inspired by the recent proof for IBE in the multi-instance setting [START_REF] Chen | Tightly Secure IBE Under Constant-Size Master Public Key[END_REF], we can in fact change the distributions of all secret keys independently but simultaneously using the random self-reducibility of decisional subgroup assumptions. Once we have independent random G p 2 component in K 0 in each secret key, we then introduce semi-functional component (in G p 2 ) for the master secret key component u 0 and show that it will be hidden by the random G p 2 component in K 0 . This means the semi-functional component of u 0 will only appear in the challenge ciphertext which is adequate for proving the selective security of our fuzzy IBE system.

Related Work

Broadcast encryption was introduced by Fiat and Naor [START_REF] Fiat | Broadcast Encryption[END_REF] and comes either in combinatorial [START_REF] Naor | Revocation and Tracing Schemes for Stateless Receivers[END_REF] or algebraic flavors [START_REF] Naor | Efficient Trace and Revoke Schemes[END_REF][START_REF] Boneh | Collusion-Resistant Broadcast Encryption with Short Ciphertexts and Private Keys[END_REF][START_REF] Gentry | Adaptive Security in Broadcast Encryption Systems (with Short Ciphertexts)[END_REF][START_REF] Waters | Dual System Encryption: Realizing Fully Secure IBE and HIBE under Simple Assumptions[END_REF][START_REF] Lewko | Revocation Systems with Very Small Private Keys[END_REF]. One of the most appealing tradeoffs was given in the scheme of Boneh, Gentry and Waters [START_REF] Boneh | Collusion-Resistant Broadcast Encryption with Short Ciphertexts and Private Keys[END_REF], which features short ciphertexts and private keys but linear-size private keys in the total number of users. While its security was initially proved under a parameterised assumption, recent extensions [63,[START_REF] Chase | Déjà Q All Over Again: Tighter and Broader Reductions of q-Type Assumptions[END_REF] of the Déjà Q framework [START_REF] Chase | Déjà Q: Using Dual Systems to Revisit q-Type Assumptions[END_REF] showed how to prove the security (against static adversaries) of its composite-order-group instantiations under constant-size subgroup assumptions. Boneh et al. suggested a variant [START_REF] Boneh | Low-overhead Broadcast Encryption from Multi-Linear Maps[END_REF] of the BGW scheme [START_REF] Boneh | Collusion-Resistant Broadcast Encryption with Short Ciphertexts and Private Keys[END_REF] with polylogarithmic complexity in all metrics using multi-linear maps. Unfortunately, the current status of multi-linear maps does not enable secure instantiations of [START_REF] Boneh | Low-overhead Broadcast Encryption from Multi-Linear Maps[END_REF] for now (see, e.g., [START_REF] Cheon | Cryptanalysis of the Multilinear Map over the Integers[END_REF]).

Identity-based broadcast encryption was formally defined by Abdalla, Kiltz and Neven [START_REF] Abdalla | Generalized Key Delegation for Hierarchical Identity-Based Encryption[END_REF] and independently considered by Sakai and Furukawa [START_REF] Sakai | Identity-Based Broadcast Encryption[END_REF]. One of the salient advantages of IBBE over traditional public-key broadcast encryption is the possibility of accommodating an exponential number of users with polynomial-size public parameters. IBBE was recently used [START_REF] Derler | Bloom Filter Encryption and Applications to Efficient Forward-Secret 0-RTT Key Exchange[END_REF] in the design of efficient 0-RTT key exchange protocols with forward secrecy. Abdalla et al. [START_REF] Abdalla | Generalized Key Delegation for Hierarchical Identity-Based Encryption[END_REF] gave a generic construction with short ciphertexts and private keys of size O(n 2 ), where n is the maximal number of receivers. Sakai and Furukawa [START_REF] Sakai | Identity-Based Broadcast Encryption[END_REF] suggested a similar construction to [START_REF] Delerablée | Identity-Based Broadcast Encryption with Constant Size Ciphertexts and Private Keys[END_REF] with security proofs in the generic group and random oracle model. Boneh and Hamburg [START_REF] Boneh | Generalized Identity Based and Broadcast Encryption Schemes[END_REF] obtained a system with O(1)-size ciphertexts and O(n)-size keys. Using the Déja Q technique, Chen et al. [START_REF] Chen | Non-Zero Inner Product Encryption with Short Ciphertexts and Private Keys[END_REF] described an identity-based revocation mechanism [START_REF] Lewko | Revocation Systems with Very Small Private Keys[END_REF] with short ciphertexts and private keys under constantsize assumptions. The aforementioned constructions were all only proven secure against selective adversaries. Gentry and Waters [START_REF] Gentry | Adaptive Security in Broadcast Encryption Systems (with Short Ciphertexts)[END_REF] put forth an adaptively secure construction based on q-type assumptions while Attrapadung and Libert [START_REF] Attrapadung | Functional encryption for inner product: Achieving constant-size ciphertexts with adaptive security or support for negation[END_REF] showed a fully secure variant of [START_REF] Boneh | Generalized Identity Based and Broadcast Encryption Schemes[END_REF] under simple assumptions. To our knowledge, the only IBBE realisations that simultaneously feature constantsize ciphertexts and private keys are those of [START_REF] Delerablée | Identity-Based Broadcast Encryption with Constant Size Ciphertexts and Private Keys[END_REF][START_REF] Sakai | Identity-Based Broadcast Encryption[END_REF], which require highly non-standard assumptions and the random oracle model. As mentioned by Derler et al. [START_REF] Derler | Bloom Filter Encryption and Applications to Efficient Forward-Secret 0-RTT Key Exchange[END_REF], the short ciphertexts and private keys of Delerablée's scheme [START_REF] Delerablée | Identity-Based Broadcast Encryption with Constant Size Ciphertexts and Private Keys[END_REF] make it interesting to instantiate their generic construction of Bloom Filter Encryption, which in turn implies efficient 0-RTT key exchange protocols. Until this work, even for selective adversaries, it has been an open problem to simultaneously achieve short ciphertext and private keys without resorting to variable-size assumptions.

Attribute-based encryption was first considered in the seminal paper by Sahai and Waters [START_REF] Sahai | Fuzzy Identity-Based Encryption In Eurocrypt'05[END_REF]. Their fuzzy IBE primitive was later extended by Goyal et al. [START_REF] Goyal | Attribute-based encryption for fine-grained access control of encrypted data[END_REF] into more expressive forms of ABE, where decryption is possible when the attribute set of the ciphertext satisfies a more complex Boolean formula encoded in the private key. After 2006, a large body of work was devoted to the design of adaptively secure [42, 47-49, 7, 50, 58] and more expressive ABE systems [START_REF] Ostrovsky | Attribute-based encryption with non-monotonic access structures[END_REF][START_REF] Lewko | Revocation Systems with Very Small Private Keys[END_REF]61,62,[START_REF] Gorbunov | Attribute-Based Encryption for Circuits from LWE[END_REF][START_REF] Boneh | Fully Key-Homomorphic Encryption, Arithmetic Circuit ABE and Compact Garbled Circuits[END_REF]. In contrast, little progress has been made in the design of ABE schemes with short ciphertexts. The first reasonably expressive ABE systems with constant-size ciphertexts were given in [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][START_REF] Attrapadung | Attribute-based encryption schemes with constant-size ciphertexts[END_REF] under q-type assumptions. The solution of Herranz et al. [START_REF] Herranz | Constant-Size Ciphertexts in Threshold Attribute-Based Encryption[END_REF] is a fuzzy IBE (i.e., a CP-ABE system for one threshold gate) with private keys of size O(n) where n is the maximal number of attributes per ciphertext. The more expressive KP-ABE systems of [START_REF] Attrapadung | Expressive key-policy attribute-based encryption with constant-size ciphertexts[END_REF][START_REF] Attrapadung | Attribute-based encryption schemes with constant-size ciphertexts[END_REF] support arbitrary Boolean formulas, but enlarge the private keys of [START_REF] Goyal | Attribute-based encryption for fine-grained access control of encrypted data[END_REF] by a factor n. The construction of [START_REF] Hohenberger | Attribute-Based Encryption with Fast Decryption[END_REF]Section 3.4] eliminates the upper bound on the number of ciphertext attributes, but lengthens private keys by a factor |U |, where U is the universe of attributes. Several follow-up works improved upon [START_REF] Attrapadung | Expressive key-policy attribute-based encryption with constant-size ciphertexts[END_REF] by proving security under simple assumptions [START_REF] Chen | Semi-Adaptive Attribute-Based Encryption and Improved Delegation for Boolean Formula In SCN 2014[END_REF][START_REF] Takashima | Expressive Attribute-Based Encryption with Constant-Size Ciphertexts from the Decisional Linear Assumption[END_REF] or achieving full security [START_REF] Attrapadung | Dual System Encryption via Doubly Selective Security: Framework, Fully Secure Functional Encryption for Regular Languages, and More[END_REF]. However, all known KP-ABE schemes with short ciphertexts under simple assumptions suffer from similarly large private keys. While our scheme only supports one threshold gate, it turns out to be the first solution with short ciphertexts under simple assumptions that avoids blowing up private keys by a factor O(n).

Preliminaries

Notation. We write x 1 , . . . , x k where G and G T are cyclic groups of order N = p 1 • • • p m (a square-free, hard-to-factor integer) and e : G × G → G T is a non-degenerate and efficiently computable bilinear map. The primes are chosen so that p i > 2 η for i ∈ {1, 2, 3}. We will use hardness assumptions which require the factorisation of N to remain hidden. Given G = (p 1 , . . . , p m , G, G T , e), let G pub = (N, G, G T , e) denote the public description of G where N = p 1 • • • p m and we assume that G, G T contain respective generators (of the full groups). Letting G p i be the subgroup of order p i of G, we denote elements of G p i with subscript i for i ∈ [m]. We now describe decisional subgroup (DS) assumptions w.r.t. (G = (p 1 , p 2 , p 3 , G, G T , e)) ←-GroupGen(η, 3), which is stated in terms of two distributions: D, T 1 and D, T 2 . We define

Adv B G,DS (η) = | Pr[B(D, T 1 ) = 1] -Pr[B(D, T 2 ) = 1]
| to be the advantage of a distinguisher B against DS. We now describe D, T 1 , T 2 for the assumptions we use.

Assumption DS1. Pick generators g 1 R ←-G × p 1 and g 3 R ←-G × p 3 . Define D = (G pub , g 1 , g 3 ), T 1 R ←- G p 1 and T 2 R ←-G p 1 p 2 . DS1 holds if for all PPT B, Adv B G,DS1 (η) is negligible in η. Assumption DS2. Pick g 1 R ←-G × p 1 , g 3 R ←-G × p 3 , h 12

Compact IBBE from Subgroup Decision Assumptions

This section describes our IBBE scheme with short ciphertexts and keys. The structure is similar to Delerablée's IBBE [START_REF] Delerablée | Identity-Based Broadcast Encryption with Constant Size Ciphertexts and Private Keys[END_REF] in asymmetric prime-order groups.

Déjà Q Framework and its implications on Delerablée's IBBE

The scheme proposed by Delerablée in [START_REF] Delerablée | Identity-Based Broadcast Encryption with Constant Size Ciphertexts and Private Keys[END_REF] is based on prime-order asymmetric pairings and offers constant-size ciphertexts and keys. However, its proof of security relies on random oracles and a parameterised assumption called generalised decisional Diffie-Hellman exponent (GDDHE) with instances containing O(q + n) group elements. A scheme/proof without random oracles is also suggested but at the cost of an interactive GDDHE-like assumption and a more restrictive security definition (called IND-na-sID-CPA) in which the adversary has to commit to the identities for key extract queries during the initialisation phase (in addition to the challenge identity set).

It is natural to ask whether the scheme can be lifted to the composite-order setting and proved secure based on subgroup decision assumptions via the Déjà Q framework [START_REF] Chase | Déjà Q: Using Dual Systems to Revisit q-Type Assumptions[END_REF][START_REF] Chase | Déjà Q All Over Again: Tighter and Broader Reductions of q-Type Assumptions[END_REF]. That is, we ask whether the Uber assumption in asymmetric composite-order bilinear groups defined in [START_REF] Chase | Déjà Q All Over Again: Tighter and Broader Reductions of q-Type Assumptions[END_REF] covers the GDDHE assumption or not? The answer is negative. To see why, let us take a closer look at the Uber assumption of [START_REF] Chase | Déjà Q All Over Again: Tighter and Broader Reductions of q-Type Assumptions[END_REF] and the (asymmetric) GDDHE-assumption. For clarity, we avoid formal descriptions of assumptions and other details.

Uber assumption [START_REF] Chase | Déjà Q All Over Again: Tighter and Broader Reductions of q-Type Assumptions[END_REF]. Assume G = (N, p 1 , p 2 , p 3 , G 1 , G 2 , G T , e) be an asymmetric compositeorder pairing group. Let R(x), S(x), V (x) denote sets of polynomials in n variables x = (x 1 , . . . , x n ) and let z(x) be a polynomial in x. Let g be a generator of G 1 and h, ĥ be two independent generators of G 2 . The uber assumption states that given g, ĥ, g R(x) , h S(x) , e(g, h) V (x) , T it is hard to decide if T = e(g, ĥ) z(x) or T ∈ R G T . It known [START_REF] Chase | Déjà Q All Over Again: Tighter and Broader Reductions of q-Type Assumptions[END_REF] that the uber assumption is implied by constant-size subgroup decision assumptions in G 1 and G 2 if R(x), z(x) are linearly independent along other requirements (see [24, Proposition 3.9] for formal statement).

In order to simplify our analysis, we may let ĥδ = h for an independent exponent δ R ←-Z N and re-state the uber assumption as: given g, ĥ, g R(x) , ĥδ•S(x) , e(g, ĥ)

δ•V (x) , T it is hard to decide if T = e(g, ĥ) z(x) or T ∈ R G T . Here, δ • S(x) = {δ • s(x) : s ∈ S(x)} and δ • V (x) = {δ • v(x) : v ∈ V (x)}.
We highlight that the Déjà Q framework in [START_REF] Chase | Déjà Q All Over Again: Tighter and Broader Reductions of q-Type Assumptions[END_REF] requires the polynomials in the exponents of ĥ to be in the form of δ • poly(x) with an independent δ. Déjà Q framework does not cover GDDHE assumption [START_REF] Delerablée | Identity-Based Broadcast Encryption with Constant Size Ciphertexts and Private Keys[END_REF]. Let an asymmetric primeorder pairing configuration G = (p, G 1 , G 2 , G T , e). Let g 0 , h 0 be the respective generators of G 1 , G 2 . Pick k, γ R ←-Z p and let f, g be two co-prime polynomials with pairwise distinct roots of respective orders q, n. The GDDHE assumption states that given g 0 , g γ 0 , g γ 2 0 , . . . , g γ q-1 0 , g γf (γ) 0

, g kγf (γ) 0 , h 0 , h γ 0 , h γ 2 0 , . . . , h γ 2n 0 , h kg(γ) 0

, along with T ∈ G T , it is hard to determine whether T = e(g 0 , h 0 ) kf (γ) or T ∈ R G T . As a direct attempt to put GDDHE into the Déjà Q framework, we can let g = g 0 and ĥ = h 0 . This means we are considering x = (γ, k) and

z(γ, k) = kf (γ), V = ∅, R(γ, k) = {1, γ, γ 2 , . . . , γ q-1 , γf (γ), kγf (γ)}.
In this case, polynomials in the exponents of ĥ include {1, γ, γ 2 , . . . , γ 2n , kg(γ).} Since both γ and k has appeared in z(x) and R(x), there's no means to write these polynomials in the form of δ • poly(x) with an independent variable δ.

With our current choice of g, all polynomials in the exponents of g fit the Déjà Q framework quite well. To get around this problem, we try another definition of ĥ. The best choice can be setting ĥ = h k 0 , x = γ and z(γ) = f (γ). The basic idea is to set δ = k -1 . However, the polynomials in the exponents of ĥ become

k -1 , k -1 • γ, k -1 • γ 2 , . . . , k -1 • γ 2n , g(γ)
where the last polynomial is still in the wrong form and we can not publish ĥ itself this time. Even worse, δ will also appear in the exponent of g = g 0 since the input to the adversary contains g kγf (γ) (in the original assumption) which will become g δ -1 γf (γ) in the current setting. We can make this argument more general. If we want to borrow δ from kf (γ), which seems to be the unique random source we can use in the challenge, it will finally appear (in some form) in the term g kγf (γ) . Therefore, the Déjà Q transform fails.

In this forthcoming sections, instead of trying to reduce subgroup decision to the GDDHE, we give direct security reductions (via Déjà Q techniques) for constructions in composite-order groups (similar to [START_REF] Delerablée | Identity-Based Broadcast Encryption with Constant Size Ciphertexts and Private Keys[END_REF]) from subgroup decision assumptions. Our construction has constant-size ciphertexts and keys and is selectively secure under the static subgroup decision assumptions, thus achieving a stronger security guarantee as compared to [START_REF] Delerablée | Identity-Based Broadcast Encryption with Constant Size Ciphertexts and Private Keys[END_REF].

Construction

We now describe the construction IBBE = (Setup, KeyGen, Encrypt, Decrypt).

Setup(1 λ , 1 n ): Let M = {0, 1} ρ where ρ ∈ poly(λ). Generate a composite-order pairing ensemble (G = (p 1 , p 2 , p 3 , G, G T , e)) ←-GroupGen(ρ + 2λ, 3). Set N = p 1 p 2 p 3 and I = Z N . Pick genera- tors g, u R ←-G p 1 and g 3 R ←-G p 3 . Sample R 3,i R ←-G p 3 for i = [n]. Also, choose α, γ R ←-Z N .
Let H : G T → {0, 1} ρ be a universal hash function with output length ρ. Define the master secret as MSK = (u, α, γ, g 3 ) while the public parameters consist of

PP = G pub , g, g γ , (G i = g α i , U i = u α i • R 3,i ) n
i=1 , e(g, u) γ , H .

KeyGen(MSK, id): Pick X 3 R ←-G p 3 and generate the key for identity id as

SK id = u γ α+id • X 3 . Encrypt(PP, S = {id 1 , . . . , id }, M ): To encrypt M ∈ {0, 1} ρ for the set S, expand the polynomial p S (x) = i=1 (x + id i ) = j=0 c j x j ∈ Z N [x]. Choose s R ← Z N and output CT = C 0 = M ⊕ H(e(g, u) sγ ), C 1 = g sγ , C 2 = g c 0 • j=1 G c j j s = g s•p S (α) .
Decrypt(PP, S, CT, id, SK id ): If id ∈ S, return ⊥. Otherwise, p S (x)/(x+id) = p S\{id} (x) = -1 i=0 z i x i is a polynomial, where z 0 = id i ∈S\{id} id i . Output M = C 0 ⊕ H (A 2 /A 1 ) 1/z 0 , where

A 1 = e(C 1 , -1 j=1 U z j j ) = e(g sγ , u p S\{id} (α)-z 0 ) = e(g, u) sγ(p S\{id} (α)-z 0 ) , A 2 = e(C 2 , SK id ) = e(g sp S (α) , u γ α+id • X 3 ) = e(g, u) sγp S\{id} (α) .
The correctness of the scheme follows from the divisibility properties of p S (x) and is easy to verify.

Proof of Security

In the security reduction, we use an additional parameter

U 0 = u • R 3,0 where R 3,0 R ←-G p 3 that is not part of either PP or MSK.
Theorem 1. For any adversary A attacking IBBE in the sid-cpa model making at most q key extraction queries, there exist algorithms B 1 , B 2 such that

Adv A IBBE,sid-cpa (λ) ≤ 2 • Adv B 1 G,DS1 (λ) + (q + n + 2) • Adv B 2 G,DS2 (λ) + (q+n+1) 2 p 2 + 1 p 2 + 1 2 λ .
Proof. We organise the proof as a sequence of 2(q + n) + 8 hybrid games. Let E denote the event that A wins in G . Let id 1 , . . . , id q denote the identities provided in extract queries.

G r : This is the real security game. G 0 : This game is like G r with the following modifications regarding private key queries.

-No two distinct identities id = id mod N satisfy id ≡ id mod p 2 .

-A does not provide any id such that α + id ≡ 0 mod p 1 . These events can be detected without knowing the factorization of N , by a simple gcd calculation (indeed, since PP only reveal α mod p 1 we can only have α+id ≡ 0 mod N with negligible probability). If either of these rules is broken, the challenger aborts the game. Assuming that N is hard to factor, these modifications do not affect A 's view. Since Assumptions DS1 and DS2 imply the hardness of factoring N , we have

| Pr[E r ]-Pr[E 0 ]| ≤ Adv B 1 G,DS1 (λ)+Adv B 2 G,DS2 (λ)
. G 1 : This is similar to G 0 with the following changes. Let S * = {id * 1 , . . . , id * * } be the set of challenge identities chosen by A . In the setup phase, we pick α, γ R ←-Z N and set γ = γ •p S * (α) mod N . The public parameters and challenge ciphertext are generated as in G 0 (as the challenger knows γ). Upon a query on id y (y ∈ [q]), the secret key is computed as

SK idy = u γ•p S * (α) α+idy • X 3,y ,
where

X 3,y R ←-G p 3 . Since this is only a conceptual change, we have Pr[E 0 ] = Pr[E 1 ]. G 2 :
In this game, the session key is generated using the parameter U 0 and the component C * 1 of the challenge ciphertext is sampled at random from G p 1 .

C * 1 R ←-G p 1 , C * 2 = C * 1 1/γ , C * 0 = M β ⊕ H(e(C * 1 , U 0 )), where β R ←-{0, 1} and U 0 = u • R 3.0 with R 3,0 R ←-G p 3 . If we write C * 1 = g sγ for some uniformly random s ∈ R Z p 1 , then C *
2 is given by (C * 1 ) 1/γ = g sγ/(γ/p S * (α)) = g sp S * (α) and is thus well-formed. Also, C * 0 has the correct distribution since -In G 4.k.0 , change the distribution of U i for i ∈ [0, n] as follows.

C * 0 = M β ⊕ H(e(C * 1 , U 0 )) = M β ⊕ H(e(g sγ , u • R 3,0 )) = M β ⊕ H(e(g, u) sγ
u α i • g k-1 j=1 r j α i j 2 • R 3,i -→ u α i • g rα i 2 • g k-1 j=1 r j α i j 2 • R 3,i
Also, change the distribution of the secret key SK idy for a query on id y for y ∈ [q]:

u γ•p S * (α) α+idy • g k-1 j=1 r j •γ•p S * (α j ) α j +idy 2 • X 3,y -→ u γ•p S * (α) α+idy • g r•γ•p S * (α) α+idy 2 g k-1 j=1 r j •γ•p S * (α j ) α j +idy 2 • X 3,y -In G 4.k.1 (k ∈ [0, q + n + 1]
), the distribution of {U i } i∈[0,n] and keys {SK idy } y∈[q] is now G,DS2 (λ).

U i = u α i • g k j=1 r j •α i j 2 • R 3,i , SK idy = u γ•p S * (α) α+idy • g k j=1 r j •γ•p S * (α j ) α j +idy
In the transition from G 4.k.0 to G 4.k.1 , α and r in the exponent of g 2 are replaced by random α k , r k ∈ R Z p 2 . This change does not affect A 's view since none of the other public parameters or the challenge ciphertext reveal α mod p 2 . In particular, due to the change introduced in G 2 , C * 2 is computed using γ, which is independent of p S * (α) mod p 2 since PP only reveals γ • p S * (α) mod p 1 via g γ and e(g, u) γ . Hence, by the CRT, we can replace α mod p 2 by α k mod p 2 without A noticing. As a result, we have Pr

[E 4.k.0 ] = Pr[E 4.k.1 ] for each k ∈ [0, n + q + 2]. G 5 :
We replace the exponents in the G p 2 -components of SK id 1 , . . . , SK idq and {U i } n i=0 by independent random elements t 0 , t 1 , . . . , t q+n ∈ Z p 2 . Namely, (U i ) n i=0 and keys are computed as

U i = u α i • g t i 2 • R 3,i ∀i ∈ [0, n], SK idy = u γ•p S * (α) α+idy • g t n+y 2
• X 3,y .

We argue that G 5 is statistically close to G 4 . We consider the G p 2 components of U 0 , U 1 , . . . , U n , SK id 1 , . . . , SK idq . In G 4 , their logarithms t 0 , . . . , t n+q ∈ Z p 2 w.r.t.

g 2 are         t 0 t 1 . . . t n t n+1 . . . t n+q         =           1 1 ••• 1 α 1 α 2 ••• α q+n+1 . . . . . . . . . . . . α n 1 α n 2 ••• α n q+n+1 γ•p S * (α 1 ) α 1 +id 1 γ•p S * (α 2 ) α 2 +id 1 ••• γ•p S * (α q+n+1 ) α q+n+1 +id 1 . . . . . . . . . . . . γ•p S * (α 1 ) α 1 +idq γ•p S * (α 2 ) α 2 +idq ••• γ•p S * (α q+n+1 ) α q+n+1 +idq           A • r 1 r 2 . . . r q+n+1 . ( 1
)
Since id y / ∈ S * for all y ∈ [q], the modifications introduced in G 0 ensure that none of the first-degree polynomials (x + id y ) mod p 2 divides p S * (x) ∈ Z p 2 [x]. In addition, remainders f y obtained upon division of p S * (x) by x + id y are constant-degree non-zero polynomials (i.e., non-zero constants in Z p 2 ). Using elementary row and column operations on A, we obtain that det A = c • det B mod p 2 , where c = γq

• f 1 f 2 • • • f q and B =          1 1 ••• 1 α 1 α 2 ••• α q+n+1 . . . . . . . . . . . . α n 1 α n 2 ••• α n q+n+1 1 α 1 +id 1 1 α 2 +id 1 ••• 1 α q+n+1 +id 1 . . . . . . . . . . . . 1 α 1 +idq 1 α 2 +idq ••• 1 α q+n+1 +idq          . Lemma 3 provides an explicit computation of the determinant of B. Lemma 3. det B = δ • 1≤y<j≤q (id y -id j ) 1≤i<k≤q+n+1 (α i -α k ) q+n+1 k=1 q y=1 (α k + id y ) for constant δ ∈ Z * p 2 .
From Lemma 3 and the distinctness of id 1 , . . . , id q mod p 2 (which is ensured since G 0 ), it is clear that det B = 0 as long as α i = α j mod p 2 for all i, j ∈ [q + n + 1], which happens with probability > 1-(q+n+1) 2 p 2

. In this case, we have det(A) = 0 mod p 2 , so that the left-hand-side member of ( 1) is uniform over

Z n+q+1 p 2 . Therefore, | Pr[E 4 ] -Pr[E 5 ]| ≤ (q + n + 1) 2 /p 2 . G 6 :
In this game, challenge ciphertext is generated as

C * 1 R ←-G p 1 p 2 , C * 2 = C * 1 1/γ , C * 0 = M β ⊕ K where K R ←-{0, 1} ρ .
In game G 5 , we note that t 0 only appears in C * 0 and it is independent of (U i ) n i=1 and the keys obtained by A . Letting

C * 1 = g sγ • g ω 2 2 for some ω 2 ∈ R Z p 2 , we have H(e(C * 1 , U 0 )) = H(e(g s•γ , u) • e(g ω 2 2 , g t 0 2
)). Conditionally on A 's view, e(C * 1 , U 0 ) has log(p 2 ) bits of min-entropy as long as C * 1 has a nontrivial G p 2 component. Since ω 2 = 0 mod p 2 with probability 1-1/p 2 and H is a universal hash function, the Leftover Hash Lemma ensures that H(e(C * 1 , U 0 )) is within distance at most 2 -λ from the uniform distribution over {0, 1} ρ . This implies that | Pr[E 5 ] -Pr[E 6 ]| ≤ 1/p 2 + 1/2 λ . Since β ∈ {0, 1} is perfectly hidden from the adversary in G 6 , we have Pr[E 6 ] = 1/2.

Combining the above, A 's advantage can be bounded as Adv

A IBBE,sid-cpa (λ) = | Pr[E r ] -Pr[E 6 ]|.

Fuzzy IBE with Short Ciphertexts

We now present a fuzzy IBE scheme obtained by transposing the prime-order construction of Herranz et al. [START_REF] Herranz | Constant-Size Ciphertexts in Threshold Attribute-Based Encryption[END_REF][START_REF] Attrapadung | Attribute-based encryption schemes with constant-size ciphertexts[END_REF] to composite order groups. The security of their scheme relies on the augmented multi-sequence of exponents decisional Diffie-Hellman (aMSE-DDH) assumption. As in Section 3, we start with an explanation of why this assumption is not covered by the Uber assumption of [START_REF] Chase | Déjà Q All Over Again: Tighter and Broader Reductions of q-Type Assumptions[END_REF].

Déjà Q framework does not cover aMSE-DDH assumption [START_REF] Herranz | Constant-Size Ciphertexts in Threshold Attribute-Based Encryption[END_REF][START_REF] Attrapadung | Attribute-based encryption schemes with constant-size ciphertexts[END_REF]. Let an asymmetric prime-order pairing configuration G = (p, G 1 , G 2 , G T , e). We describe an asymmetric version of the ( , m, t)-aMSE-DDH assumption. 7 With a length-( +m) vector y = (y 1 , . . . , y l+m ), define functions

f (Y ) = i=1 (Y + y i ) and g(Y ) = +m i= +1 (Y + y i ). Let g 0 , h 0 be generators of G 1 and G 2 and pick k, γ, α, β R ←-Z p . The ( , m, t)-aMSE-DDH assumption states that given g 0 , g γ 0 , . . . , g γ +t-2 0 , g kγf (γ) 0 , h 0 , h γ 0 , . . . , h γ m-2 0 , h kg(γ) 0
, g βγ 0 , . . . , g βγ +t-2 0 , h β 0 , h βγ 0 , . . . , h βγ m-1 0 , g α 0 , g αγ 0 , . . . , g αγ +t 0 , h α 0 , h αγ 0 , . . . , h αγ 2(m-t)+3 0 , and T ∈ G T , it is hard to determine whether T = e(g 0 , h 0 ) kf (γ) or T ∈ R G T . We observe that the first line of the input is quite similar to the input of the GDDHE assumption [START_REF] Delerablée | Identity-Based Broadcast Encryption with Constant Size Ciphertexts and Private Keys[END_REF] (cf. Section 3.1). We can transpose the discussion in Section 3.1 to the aMSE-DDH assumption. As we have shown, the gap between the uber assumption [START_REF] Chase | Déjà Q All Over Again: Tighter and Broader Reductions of q-Type Assumptions[END_REF] and the aMSE-DDH assumption is due to the structures of polynomials in the exponents of h 0 and the entry g kγf (γ) 0 which shares kf (γ) with the challenge. We therefore conclude that the Déjà Q framework [START_REF] Chase | Déjà Q All Over Again: Tighter and Broader Reductions of q-Type Assumptions[END_REF] does not subsume the ( , m, t)-aMSE-DDH assumption.

In this section as well, we are not going to start from the aMSE-DDH assumption. Instead, we will try to adapt Herranz et al.'s prime-order construction [START_REF] Herranz | Constant-Size Ciphertexts in Threshold Attribute-Based Encryption[END_REF] into composite-order groups and analyse its selective security directly. Our fuzzy IBE scheme preserves the advantages of Herranz et al.'s [START_REF] Herranz | Constant-Size Ciphertexts in Threshold Attribute-Based Encryption[END_REF] such as constant-size ciphertexts and can now be proved secure under static assumptions.

Construction

Before presenting the construction, we first describe the algorithm Aggregate of [START_REF] Delerablée | Dynamic Threshold Public-Key Encryption[END_REF][START_REF] Attrapadung | Attribute-based encryption schemes with constant-size ciphertexts[END_REF].

Aggregate Algorithm. The Aggregate algorithm of [START_REF] Delerablée | Dynamic Threshold Public-Key Encryption[END_REF] was given for elements in G T , but it carries over to any prime order group [START_REF] Attrapadung | Attribute-based encryption schemes with constant-size ciphertexts[END_REF]. Our construction requires it to work in composite order groups. Let a cyclic group G of composite order N . Given a set of pairs {u

1 α+x i , x i } n i=1
, where u ∈ G and α ∈ Z N are unknown and x 1 , . . . , x n ∈ Z N are pairwise distinct elements such that gcd(x i -x j , N ) = 1 for all i = j,

the algorithm computes the value Aggregate({u

1 α+x i , x i } n i=1 ) = u 1 n i=1
(α+x i ) using O(n 2 ) exponentiations. (See Appendix C for details.) It is unlikely to encounter a pair (x i , x j ) violating restriction (2) since it exposes a non-trivial factorisation of N and violate the decisional subgroup assumption.

Our Fuzzy IBE Construction. In the description hereunder, we denote by n an upper bound on the number of attributes per identity. The construction goes as follows.

Setup(1 λ , 1 n ): Choose ρ ∈ poly(λ) and define M = {0, 1} ρ . Generate a composite-order pairing ensemble (G = (p 1 , p 2 , p 3 , G, G T , e)) ←-GroupGen(ρ+2λ, 3) and set N = p 1 p 2 p 3 . Then, arbitrarily select n-1 distinct dummy identities

d 1 , . . . , d n-1 ∈ Z N . Define the set I = Z N \{d 1 , . . . , d n-1 }. Pick g, u 0 R ←-G p 1 and g 3 R ←-G p 3 and choose α, γ R ←-Z N .
Let H : G T → {0, 1} ρ be a universal hash function. Define MSK = (u 0 , α, γ, g 3 ) while the public parameters consist of

PP = G pub , g, g γ , G i = g α i 2n-1 i=1 , e(g, u 0 ) γ , (d i ) n-1 i=1 , H . KeyGen(MSK, S = {id 1 , . . . , id }): Pick u R ← G p 1 , X 3,1 , . . . , X 3, , X 3,1 , . . . , X 3,n-1 , X 3,0 R
← G p 3 and output the secret key

SK S = K i = u γ α+id i • X 3,i i=1 , K i = u α i • X 3,i n-1 i=1 , K 0 = u • u 0 • X 3,0 .
Encrypt(PP, S = {id 1 , . . . , id }, τ ≤ , M ): To encrypt M ∈ {0, 1} ρ for the set S with threshold τ , compute coefficients {c j } j∈[0,n+τ -1] for the polynomial

p S,τ (x) = i=1 (x + id i ) • n+τ -1- i=1 (x + d i ) = n+τ -1 i=0 c i x i ∈ Z N [x].
Choose s R ←-Z N and output the ciphertext

CT S,τ = C 0 = M ⊕ H(e(g, u 0 ) sγ ), C 1 = g sγ , C 2 = g c 0 • n+τ -1 i=1 G c i i s = g s•p S,τ (α) .
Decrypt(PP, S, τ, CT, S , SK S ): If |S ∩ S | < τ , return ⊥. Otherwise, we can find a set S ⊆ I satisfying S ⊆ S ∩ S and | S| = τ . Note that the choice of S is arbitrary. By invoking algorithm Aggregate, we can compute

K Agg = u γ id∈ S (α+id) • X 3,Agg for some X 3,Agg ∈ G p 3 . Let p S, S,τ (x) = p S,τ (x)/ id∈ S (x + id) = n-1 i=0 z i x i where z 0 = id∈S\ S id • n+τ -1-|S| i=1 d i . We can compute A 1 = e(C 1 , n-1 i=1 (K i ) z i ) = e(g sγ , u p S, S,τ (α)-z 0 ) = e(g, u) sγ(p S, S,τ (α)-z 0 ) , A 2 = e(C 2 , K Agg ) = e(g s•p S,τ (α) , u γ id∈ S (α+id) • X 3,Agg ) = e(g, u) sγp S, S,τ (α) , A 3 = e(C 1 , K 0 ) = e(g sγ , u • u 0 • X 3,0 ) = e(g, u) sγ • e(g, u 0 ) sγ ,
and recover the message as

M = C 0 ⊕ H A 3 /(A 2 /A 1 ) 1/z 0 .
The scheme is easily seen to be correct. We note that Decrypt can be optimized to consume only 2 pairing operations by recovering e(g, u

) sγ = e(C 1 , K 0 • ( n-1 i=1 (K i ) z i ) 1/z 0 )/e(C 2 , K 1/z 0 Agg ).

Proof of Security

Theorem 2. For any adversary A attacking FIBE in the sid-cpa model making at most q key extraction queries, there exist algorithms B 1 , B 2 such that

Adv A FIBE,sid-cpa (λ) ≤ 2 • Adv B 1 G,DS1 (λ) + ( + n + 2) • Adv B 2 G,DS2 (λ) + q•( +2n) 2 p 2 + 1 p 2 + 1 2 λ .
where is maximum size of attribute sets.

Proof Sketch. Let (S * = (id * 1 , . . . , id * * ), τ * ) be the challenge set and challenge threshold; S 1 , . . . , S q denote the sets provided in extract queries. It is worth noting that each secret key corresponds to an instance of our IBBE with its own random source u, denoted by u 1 , . . . , u q for SK S 1 , . . . , SK Sq , respectively. Following a game sequence analogous to that for IBBE (from G r to G 4 ), we reach the following simulation strategy: the public parameters are

( G pub , g, g γ , G i = g α i 2n-1 i=1 , e(g γ , U 0 ) , (d i ) n-1 i=1 , H ) where γ = γ • p S * ,τ * (α) mod N with γ R ← Z N and U 0 = u 0 • X 3.0 with X 3,0 R ← G p 3 . The challenge is ( C * 1 R ←-G p 1 p 2 , C * 2 = C * 1 1/γ , C * 0 = M β ⊕ H(e(C * 1 , U 0 )
) ); a secret key for S y = {id 1,y , . . . , id y ,y } (y ∈ [q]) consists of • U 0 • X 3,0,y , where α, α 1 , . . . , α +n R ←-Z N are shared among all keys but r 1,y , . . . , r +n,y R ←-Z N are fresh. As in the IBBE case, we want to claim that it is a ( y + n)-wise independent function that has been formed on the exponent of g 2 (in the boxed term). For each key, say SK S with S = {id 1 , . . . , id } for simplicity, it must hold that τ = |S ∩ S * | < τ * and we can assume id 1 = id * 1 , . . . , id τ = id * τ . This claim (w.r.t. SK S ) follows from the fact that the ( + n) × ( + n) matrix containing

K 0 α 0 = 1, K i {α i } n-1 i=1 , K i ζ∈[τ ]\{i} (α + id ζ ) • n+τ -1- ζ=1 (α + d ζ ) τ i=1 , p S * ,τ * (α) α + id i i=τ +1
for α ∈ {α 1 , . . . , α +n } has a non-zero determinant with high probability under the restriction τ < τ * . This then implies that K 0,y in SK Sy (y ∈ [q]) will have a non-trivial G p 2 component independent of all other information, denoted by U y . Finally, we introduce a non-trivial G p 2 component into U 0 by the DS2 assumption, and argue that, conditioned on e(g, U 0 ), U 0 • U 1 , . . . , U 0 • U q , the G p 2 component of U 0 is still distributed uniformly. That is e(C * 1 , U 0 ) has min-entropy of log(p 2 ) bits, and the leftover hash lemma ensures that the information about β will be statistically hidden. See Appendix D for more details.

A Comparisons with Prior Works

We give detailed comparisons between our two schemes and earlier realizations along with more discussions.

Table 1 provides a detailed comparison between our IBBE system and other IBBE with short ciphertexts and secret keys. Table 2 compares our FIBE with previous FIBE with short ciphertexts. We fix the following notation: CT: ciphertext; SK id : secret key for identity id; #dec: cost of decryption; ρ is the length of the message to be encrypted; G N : symmetric pairing group with order N (a composite number); G 1 , G 2 : source groups of an asymmetric prime-order pairing of order p, a prime;

[P] + O(τ 2 + n)[M] sID aMSE-DDH [6],[4] 2|G1| + ρ (n 2 + n)|G2| 2[P] + O(nτ )[M] sID DBDHE [22] 2|GN | + ρ (n 2 + n)|GN | 2[P] + O(nτ )[M] saID Static [57] 17|G1| + ρ (6n 2 + 5)|G2| 17[P] + O(nτ )[M] saID DLIN [7] 6|G1| + ρ (n 2 + 2n + 3)|G2| 6[P] + O(nτ )[M] aID Static Ours 2|GN | + ρ 2n|GN | 2[P] + O(τ 2 + n)[M] sID Static Table 2. Comparison among compact FIBE.
Here n is the (maximum) size of attribute set and τ is the threshold.

Proof (of Lemma 2). On input an instance (G pub , g 1 , g 3 , h 12 , h 23 , T ) of DS2 problem, the reduction B 2 simulates the sid-cpa game as follows.

Setup. Once A commits to the identity set

S * = {id * 1 , . . . , id * * }, B 2 chooses α, γ R ←-Z N , sets γ = γ•p S * (α), g = g 1 and computes G i = g α i for each i ∈ [n]. It then chooses {r j , α j } k-1 j=1 R ←-Z N and generates {U i } n i=0 as U i = T α i • h k-1 j=1 r j α i j 23 • R 3,i ∀i ∈ {0, . . . , n}, where R 3,i R ←-G p 3 .
It provides the adversary with public parameters

PP = (G pub , g, g γ , (G i = g α i , U i = u α i • R 3,i ) n i=1 , e(g, u) γ , H)
, where e(g, u) γ is computed as e(g, U 0 ) γ , which has the proper distribution. Key Extraction Phase. For a private key query on id y for y ∈ [q], a secret key is produced as

SK idy = T γ•p S * (α) α+idy • h k-1 j=1 r j •γ•p S * (α j ) α j +idy 23 • X 3,y , where X 3,y R ←-G p 3 . Writing h 23 = g t 2 • h 3 with t ∈ Z * p 2 and h 3 ∈ G p 3
, we have r j = tr j mod p 2 for j ∈ [q + n + 1], which is distributed uniformly over Z p 2 , as required. Also, we observe that Proof (of Lemma 3). We want to show that 

R 3,i = R 3,i • h k-1 j=1 r j α i j 3 and X 3,y = X 3,y • h k-1 j=1 r j γ•p S * (α j ) α j +idy 3 have the correct distribution in G p 3 . Challenge. In the challenge phase, A provides two messages M 0 , M 1 ∈ {0, 1} ρ . At this point, B 2 picks β R ←-{0, 1} n , computes challenge ciphertext as C * 1 = h 12 , C * 2 = (C * 1 ) 1/γ , C * 0 = M β ⊕ H(e(C * 1 , U 0
 q+n+1 k=1 q y=1 (α k + id y )   • det B =   1≤y<j≤q (id y -id j )     1≤i<k≤q+n+1 (α i -α k )   ,
where B is the (q + n + 1) × (q + n + 1) matrix given by

B =                  1 1 • • • 1 α 1 α 2 • • • α q+n+1 α 2 1 α 2 2 • • • α 2 q+n+1 . . . . . . . . . . . . α n 1 α n 2 • • • α n q+n+1 1 α 1 +id 1 1 α 2 +id 1 • • • 1 α q+n+1 +id 1 . . . . . . . . . . . . 1 α 1 +idq 1 α 2 +idq • • • 1 α q+n+1 +idq                  . G 1 :
This game is identical to G 0 except that, in the initialisation phase, we pick γ R ←-Z N and define γ = γ • p S * ,τ * (α) mod N . This change is conceptual and Pr[E 0 ] = Pr[E 1 ]. We note that γ can be explicitly computed. The master public key is

PP = G pub , g, g γ , G i = g α i 2n-1
i=1 , e(g, u 0 ) γ , (d i ) n-1 i=1 , H ; upon a query on S y = (id 1,y , . . . , id y ,y ) (y ∈ [q]), the corresponding secret key SK Sy is generated as

K i,y = u γ•p S * ,τ * (α) α+id i,y y • X 3,i,y y i=1 , K i,y = u α i y • X 3,i,y n-1 i=1 , K 0,y = u y • u 0 • X 3,0,y , where u y R ←-G p 1 and X 3,1,y , . . . , X 3, y ,y , X 3,1,y , . . . , X 3,n-1,y , X 3,0,y R ←-G p 3 ; the challenge ciphertext is C 0 = M β ⊕ H(e(g, u 0 ) sγ•p S * ,τ * (α) ), C 1 = g sγ•p S * ,τ * (α) , C 2 = g s•p S * ,τ * (α) . where β R ←-{0, 1} and s R ←-Z N . G 2 :
In this game, the public parameters are

PP = G pub , g, g γ , G i = g α i 2n-1 i=1 , e(g, U 0 ) γ , (d i ) n-1 i=1 , H ; where U 0 = u 0 • X 3.0 with X 3,0 R ←-G p 3 ; the challenge ciphertext is generated as follows C * 1 R ←-G p 1 , C * 2 = C * 1 1/γ , C * 0 = M β ⊕ H(e(C * 1 , U 0 )),
while the secret key SK Sy for S y is

K i,y = u γ•p S * ,τ * (α) α+id i,y y • X 3,i,y y i=1 , K i,y = u α i y • X 3,i,y n-1 i=1 , K 0,y = u y • U 0 • X 3,0,y
Since e(g, U 0 ) = e(g, u 0 ), we do not change the distribution of the public parameters. Following the reasoning in Section 3.3, we know that the modification here won't change the distribution of the challenge ciphertext. The change on K 0,y will not change its distribution either due to the fresh randomness X 3,0,y in each key. Thus, we have Pr

[E 1 ] = Pr[E 2 ]. G 3 : This game is identical to G 2 except that the challenge ciphertext is created by first sampling C * 1 R ←-G p 1 p 2 rather than C * 1 R ←-G p 1 and computing C * 2 and C * 0 as in G 2 .
As in Section 3.3, we can prove the following lemma. t0,y , t 1,y , . . . , t n-1,y , t1,y , . . . , t y ,y . With the notations

B y =                  1 1 • • • 1 α 1 α 2 • • • α y +n α 2 1 α 2 2
B q      A      r 1 r 2 . . . r q     
The special structure of matrix A and the following lemma imply that all ty are uniform over

Z y +n p 2
with probability 1 -q( + 2n) 2 /p 2 and thus | Pr[E 4 ] -Pr[E 5 ]| ≤ q( + 2n) 2 /p 2 .

Lemma 6. The matrices B 1 , . . . , B q are all invertible with overwhelming probability 1-q( + 2n) 2 /p 2 .

Compare with the matrix A in Equation ( 1), the matrices B 1 , . . . , B q here are more complicated in the sense that, for each y ∈ [q], there can be an id ∈ S y such that γp S * ,τ * (x) x+id is a polynomial in x, i.e., id ∈ S * . We can prove that when the number of such identities does not reach τ * for each y ∈ [q], all matrices B 1 , . . . , B q are still invertible with overwhelming probability. G 6 : In this game, we change the distribution of U 0 as follows.

U 0 = u 0 • X 3.0 -→ U 0 = u 0 • g t 0 2 • X 3.0 .
where t 0 R ←-Z N . This changes the distributions of both secret keys and challenge ciphertext. We have the following lemma. Following the idea of Chase and Meiklejohn [START_REF] Chase | Déjà Q: Using Dual Systems to Revisit q-Type Assumptions[END_REF], it is sufficient to argue the following polynomials (in x) are linearly independent.

q(x), xq(x), . . . , x n-1 q(x), p -1 (x)q(x), . . . , p -τ (x)q(x), p S * ,τ * (x)q -(τ +1) (x), . . . , p S * ,τ * (x)q -(x). a i x i q(x)

+ i∈[τ ]
b i p -i (x)q(x) + i∈[τ +1, ] c i p(x)q -i (x) is a zero polynomial. We prove that all these coefficients are zero in two steps.

Step 1. For all i ∈ [τ + 1, ], we have C(-id i ) = c i p(-id i )q -i (-id i ) = 0, because -id i is a common root of q(x) and q -j (x) with j = i. Since -id i is not a root of p(x) and q -i (x), we can deduce that c i = 0.

Step 2. It remains to show that all a i and b i are zero. We should prove that 1, x, . . . , x n-1 , p -1 (x), . . . , p -τ (x) [START_REF] Attrapadung | Functional encryption for inner product: Achieving constant-size ciphertexts with adaptive security or support for negation[END_REF] are linearly independent. To this end, let us take a closer look at the polynomials p -i (x) with i ∈ [τ ]. For each i, we may rewrite .

p -i (x) =
We rely on two observations: (1) p(x) divides all p -i (x) and deg(p) = n + τ * -1 -τ ≥ n; (2) p-1 (x), . . . , p-τ (x) are linearly independent polynomials of degree τ -1. The second observation means p-1 (x), . . . , p-τ (x) form a basis of all polynomial of degree at most τ -1. This means that proving the independence of ( 5) is equivalent to proving the independence of 1, x, . . . , x n-1 , p(x), xp(x), . . . , x τ -1 p(x) [START_REF] Attrapadung | Expressive key-policy attribute-based encryption with constant-size ciphertexts[END_REF] because 1, x, x 2 , . . . , x τ -1 also form a basis of the linear space of all polynomials of degree ≤ τ -1. for some non-negative integer . This immediately derives that the + n polynomials in Eq.( 6) are linearly independent and so are the polynomials in Eq. [START_REF] Attrapadung | Functional encryption for inner product: Achieving constant-size ciphertexts with adaptive security or support for negation[END_REF].

Combining this two steps, we prove that polynomials in Eq.( 4) are linearly independent. Since det( B) is a polynomial in α 1 , . . . , α +n of degree at most ( + 2n) 2 , the Schwartz-Zippel implies det( B) = 0 with the probability bounded by ( + 2n) 2 /p 2 and so does the event det(B) = 0 when sampling α 1 , . . . , α +n R ←-Z p 2 . By the union bound, we immediately prove the lemma.

R

  ←-X to indicate that x 1 , . . . , x k are sampled independently and uniformly from the set X . For a PPT algorithm A, y R ←-A(x) means that y is chosen according to the output distribution of A on input x. For integers a < b, [a, b] denotes the set {x ∈ Z : a ≤ x ≤ b} and we let [b] = [1, b]. If G is a cyclic group, G × denotes the set of generators of G.

2. 1

 1 Composite-Order Pairings and Hardness AssumptionsA (symmetric) composite-order pairing ensemble generator GroupGen() is an algorithm that inputs a security parameter η and an integer m and returns an (m + 3)-tuple G = (p 1 , . . . , p m , G, G T , e)

2. 3

 3 Fuzzy Identity-Based Encryption (FIBE) Definition 3 (FIBE). A fuzzy IBE scheme is defined by probabilistic algorithms -Setup, KeyGen, Encrypt and Decrypt. The identity space is denoted by I and the message space is denoted by M.Setup(1 λ , 1 n ): Takes as input a security parameter λ, the maximum size n (= poly(λ)) of sets associated with ciphertexts and generates the public parameters PP and the master secret MSK.The algorithm also defines the identity space I and message space M. KeyGen(MSK, S ⊆ I): Inputs a set S and MSK; outputs a secret key SK S for S. Encrypt(PP, S ⊆ I, τ, m ∈ M): Takes as input the public parameters PP, a set of identities S along with a threshold τ and a message m. If τ ≤ |S| ≤ n, the algorithm outputs the ciphertext CT S,τ . Decrypt(PP, S, τ, CT S,τ , S , SK S ): This algorithm inputs the public parameters PP, a set S ⊆ I with a threshold τ and a ciphertext CT S,τ associated with them, another set S ⊆ I and its corresponding secret key SK S , outputs a message m ∈ M if |S ∩ S | ≥ τ and ⊥ otherwise. Correctness. The FIBE scheme is correct if, for all sets S ⊆ I, all thresholds τ ≤ |S| ≤ n, all S ∈ I satisfying |S ∩ S | ≥ τ , all m ∈ M, when (PP, MSK) R ←-Setup(1 λ , 1 n ), SK S R ←-KeyGen(MSK, S ) and CT S,τ R ←-Encrypt(PP, S, τ, m), then Pr[m = Decrypt(PP, S, τ, CT S,τ , S , SK S )] = 1. Definition 4 (FIBE Security). A FIBE system FIBE = (Setup, KeyGen, Encrypt, Decrypt) provides selective security if no PPT adversary A has non-negligible advantage in the following game. Initialise: A commits to a target set S * ⊆ I and threshold τ * satisfying τ * ≤ |S * | ≤ n. Setup: The challenger runs the Setup algorithm of FIBE and gives PP to A . Key Extraction Phase 1: A makes a number of key extraction queries. For a query on S ⊆ I such that |S * ∩ S| < τ * , the challenger runs SK S ← FIBE.KeyGen and otuputs SK S . Challenge: A provides two messages m 0 , m 1 . The challenger chooses β R ←-{0, 1}, computes CT * R ←-FIBE.Encrypt(PP, S * , τ * , m β ) and returns CT * to A . Key Extraction Phase 2: A makes more key extraction queries with the restriction that it cannot query a key for any set S such that |S * ∩ S| ≥ τ * . Guess: A outputs a bit β . We say A wins the game if β = β . The advantage of A in winning the sid-cpa game is defined to be Adv A FIBE,sid-cpa (λ) = | Pr[β = β ] -1/2|.

3 : 2 . 1 .

 321 ). The modifications G 1 are thus conceptual and hence Pr[E 1 ] = Pr[E 2 ]. G This game is identical to G 2 except that C * 1 is sampled uniformly in G p 1 p 2 .Other components of the challenge ciphertext and the secret keys are generated as in GLemma There is a PPT algorithmB 1 such that | Pr[E 2 ] -Pr[E 3 ]| ≤ Adv B 1G,DS1 (λ).

G 4 :

 4 We change the distribution of parameters {U i } n i=0 and secret keys SK id 1 , . . . , SK idq by gradually introducing G p 2 components. This is done via sub-games G 4.k.0 , G 4.k.1 for k ∈ [q+n+1] defined as follows. For convenience, we define G 4.0.1 = G 3 and G 4.(q+n+2).1 = G 4 .

2 •

 2 X 3,y . The following lemma shows that G 4.(k-1).1 and G 4.k.0 are computationally indistinguishable. Lemma 2. There is a PPT algorithm B 2 such that | Pr[E 4.(k-1).1 ]-Pr[E 4.k.0 ]| ≤ Adv B 2

K 2 •• g y +n j=1 α i j r j,y 2 • X 3

 223 i,y = u γ•p S * ,τ * (α) ,τ * (α j ) α j +id i,y r j,y X 3,i,y y i=1 , K i,y = u α i y y = u y • g y +n j=1 r j,y 2

  [P]: a pairing operation; [M]: scalar multiplication in the source groups; aID: adaptive/full security; sID: security selective identity model; na-sID: security in the selective model with non-adaptive key extraction queries; saID: security in semi-adaptive model; GDDHE: generalised decision Diffie-Hellman exponent assumption; O-GDDHE: an oracle variant of GDDHE; GGM: proven secure in the generic (bilinear) group model; aMSE-DDH: augmented multi-sequence of exponents decisional Diffie-Hellman assumption; Static: standard assumption in composite-order pairing group, such as subgroup decision assumption and subgroup Diffie-Hellman assumption.

  )) and sends CT * = (C * 0 , C * 1 , C * 2 ) to A . Guess. A guesses β ∈ {0, 1} of β and B 2 returns 1 if and only if β = β . The distribution of CT * is identical to that in game G 4.(k-1).1 if T ∈ G p 1 p 3 and as in G 4.k.0 if T ∈ G p 1 p 2 p 3 . This immediately proves the lemma.

Lemma 4 .

 4 There is a PPT algorithm B 1 such that| Pr[E 2 ] -Pr[E 3 ]| ≤ Adv B 1G,DS1 (λ).

G 4 :

 4 We change the distribution of secret keys SK S 1 , . . . , SK Sq by gradually introducing G p 2 components. To do so, we need the help of two sub-games G 4.k.0 , G 4.k.1 defined as follows. Recall that = max{|S 1 |, . . . , |S q |} which ensures that each secret key has adequate randomness in G p 2 for the future argument. As before, we define G 4.0.1 = G 3 and G 4. +n.1 = G 4 .

Lemma 7 .

 7 There exists a PPT algorithm B 2 such that we have the inequality| Pr[E 5 ] -Pr[E 6 ]| ≤ Adv B 2G,DS2 (λ).

( 4 )

 4 Let us assume that there exist coefficients a 0 , a 1 , . . . ,a n-1 , b 1 , . . . , b τ , c τ +1 , . . . , c ∈ Z N such that C(x) = i∈[0,n-1]

  j∈[τ ]\{i} (x + id j ) p-i (x) • j∈[τ +1, * ] (x + id * j ) • i∈[n+τ * -1- * ] (x + d i ) p(x)

  From the first observation, we can see thatdeg(p(x)) = n + , deg(xp(x)) = n + 1 + , . . . , deg(x τ -1 p(x)) = n + τ -1 +

  61. B. Waters. Ciphertext-Policy Attribute-Based Encryption: An Expressive, Efficient, and Provably Secure Realization. In PKC 2011, LNCS 6571. 2011. 62. B. Waters. Functional Encryption for Regular Languages. In Crypto 2012, LNCS 7417. 2012. 63. H. Wee. Déjà Q Encore! Un petit IBE. In TCC 2016, LNCS 9563, 2016.

Table 1 .

 1 Comparison among compact IBBE (with short ciphertexts and secret keys). Here, n is the maximum number of recipients.

	IBBE	|CT|	|SK id |	#dec	Security Assumption RO
	[27]-1 |G1| + |G2| + ρ	|G1|	2[P]+O(n)[M]	sID	GDDHE	Yes
	[27]-2 8 |G1| + |G2| + ρ |G1| + |Zp| 2[P]+O(n)[M] na-sID O-GDDHE No
	[53]	2|G1| + ρ	|G2|	2[P]+O(n)[M] aID	GGM	Yes
	Ours	2|GN | + ρ	|GN |	2[P]+O(n)[M]	sID	Static	No
	FIBE	|CT|	|SK id |	#dec		Security Assumption
	[37] 2|G1| + ρ n|G1| + n|G2| 2

  +n γp S * ,τ * (α 1 ) α 1 +id 1,y γp S * ,τ * (α 2 ) α 2 +id 1,y • • • γp S * ,τ * (α y +n ) α y +n +id 1,y S * ,τ * (α 1 ) α 1 +id y ,y γp S * ,τ * (α 2 ) α 2 +id y ,y • • • γp S * ,τ * (α y +n ) α y +n +id y ,y

							
	. . . α n-1 1 . . .	. . . α n-1 2 . . .	• • • . . . • • • . . .	α 2 y +n . . . α n-1 . . .	              
							
	and
	r N	,
	we have
	 t1			 B 1
	    t2 . . .	   	=	   	B 2	. . .
	tq

y γp y = (r 1,y , . . . , r y +n,y ) ∈ Z y +n N , ty = ( t0,y , t 1,y , . . . , t n-1,y , t1,y , . . . , t y ,y ) ∈ Z y +n

We believe our arguments showing that the assumptions under question are not covered by the Déjà Q framework are sufficient. Also, we do not know if there exist other parameterised assumptions in this class that could possibly be used to prove security of the IBBE and FIBE schemes.

Alternatively, the scheme of[START_REF] Delerablée | Identity-Based Broadcast Encryption with Constant Size Ciphertexts and Private Keys[END_REF] can be proved secure in the standard model if the adversary also announces all its private keys queries (in addition to the target set of identities) before seeing the public parameters.

The proof of Wee's broadcast encryption [63,Section 4] has a similar correlation between the Gp 2 components of private keys and public parameters but, in the final step, the statistical argument involved simpler-to-analyse Vandermonde matrices.

The assumption is originally given in symmetric groups. In order to work with the Déjà Q framework, one must transform it into asymmetric groups (using Abe et al.'s method[START_REF] Abe | Converting cryptographic schemes from symmetric to asymmetric bilinear groups[END_REF] as suggested in[START_REF] Chase | Déjà Q All Over Again: Tighter and Broader Reductions of q-Type Assumptions[END_REF]) which depends on the scheme and the reduction.

The parameters provided here are only based on the claims made in[START_REF] Delerablée | Identity-Based Broadcast Encryption with Constant Size Ciphertexts and Private Keys[END_REF]. It is claimed that there are two possible ways to remove the random oracles -one is to randomise the keys and the other is to use an oracle variant of GDDHE, without a proof for the latter. Furthermore, it is not clear how the construction obtained by randomising the keys (similar to the IBE of[START_REF] Boneh | Efficient Selective-ID Secure Identity-Based Encryption Without Random Oracles[END_REF]) really works, since the ciphertexts in the broadcast setting are structurally different from those of the IBE.

Although composite order groups are known to have less efficient implementations than prime order bilinear groups, we feel that using the former for our constructions is justified. There is a clear asymptotic efficiency benefit over existing constructions (e.g., [START_REF] Boneh | Generalized Identity Based and Broadcast Encryption Schemes[END_REF]) achieving comparable security guarantees. In both schemes, the number of pairing evaluations is constant. Indeed, a product of two pairings (which is significantly faster to compute than two independent pairings) suffices to decrypt whereas the encryption algorithm does not require any pairing evaluation at all. In the FIBE case, we go from quadratic to linear key sizes in the maximal number of attributes per ciphertext when we compare it to, e.g., [START_REF] Attrapadung | Expressive key-policy attribute-based encryption with constant-size ciphertexts[END_REF]. In the IBBE case, we get constant-size ciphertexts and keys for the first time under constant-size assumptions.

When the underlying assumptions are taken into account, the benefit of composite order groups becomes even clearer as we only rely on well-established assumptions whereas the prime order variants [START_REF] Delerablée | Identity-Based Broadcast Encryption with Constant Size Ciphertexts and Private Keys[END_REF][START_REF] Herranz | Constant-Size Ciphertexts in Threshold Attribute-Based Encryption[END_REF] of our schemes require completely ad hoc assumptions that are not even easy to memorise. We believe the longer the description of an assumption is, the more it looks like another way to state that the scheme is insecure. The following statement from [START_REF] Katz | Introduction to Modern Cryptography[END_REF] (p25) buttresses our belief: "...there is a general preference for assumptions that are simpler to state, since such assumptions are easier to study and to refute.".

We further remark that the security loss of both our schemes is proportional to the maximum size of the sets associated with ciphertexts or than the number of key extraction queries, whichever is higher. Furthermore we emphasize that a reduction to a standard assumption with some security loss is more reasonable than a tight reduction to an ad-hoc parameterized assumption since the actual strength of a parameterized assumption is typically questionable [START_REF] Cheon | Security Analysis of the Strong Diffie-Hellman Problem[END_REF].

B Deferred Proofs for the IBBE System

Proofs of Lemmas

Proof (of Lemma 1). The reduction B 1 receives an instance (G pub , g 1 , g 3 , T ) of DS1 and simulates the sid-cpa game to A as follows.

Setup. The adversary A commits to the challenge identity set

. Sampling from G p 1 and G p 3 is done using g 1 and g 3 , respectively. B 1 chooses H : G T → {0, 1} ρ , a universal hash function and provides the following public parameters to A .

i=1 , e(g, u) γ , H).

Key Extraction Phase.

Upon a key extraction query on id y , B 1 picks X 3,y R ←-G p 3 and responds with

In the challenge phase, A provides two messages M 0 , M 1 ∈ {0, 1} ρ . Challenge. The reduction algorithm picks a random bit β R ←-{0, 1} and sets

At the end of the game, A returns its guess β and B 1 returns 1 if and only if β = β .

Observe that the distribution of CT * is as in game

This readily proves the lemma.

Multiplying det B by q+n+1 k=1 q y=1 (α k + id y ) results in a sum P of homogeneous polynomials of degree n(n + 1) 2 + q(q + n + 1) -q = n(n + 1) 2 + q(q + n).

We note that det B vanishes if α i = α j for some i, j ∈ [q + n + 1] and columns i, j become identical.

rows i, j (for some i, j ∈ [n + 2, q + n + 1]) become equal which happens when id i = id j mod p 2 .

From these observations, it follows that P must be a multiple of

which happens to be equal to deg P. Therefore, P must be a constant multiple of Q from which the statement of the lemma follows.

C Description of Aggregate algorithm

We describe the detail of Aggregate algorithm: Define Λ 0,η = u 1/(α+xη) for each η ∈ [n] and observe that, if we define

these values satisfy the formula

As long as the distinct scalars x 1 , . . . , x n satisfy the condition (2), relation (3) allows sequentially computing Λ j,η for j = 1 to n -1 and η = j + 1 to n and finally obtains Λ n-1,n = u

D Proof of Theorem 2

Proof. We prove the theorem via a game sequence. As usual we let E denote the event that A wins in G . Furthermore, we let (1) (S * = (id * 1 , . . . , id * * ), τ * ) be the challenge set and challenge threshold; (2) (M 0 , M 1 ) be the challenge message pair; (3) S 1 , . . . , S q denote the sets provided in extract queries. We define = max{|S 1 |, . . . , |S q |} and describe the game sequence as follows.

G r : This is the real security game. G 0 : This game is like G r with the following modifications regarding the identities belonging to the set S = S 1 ∪ • • • ∪ S q : (1) No two distinct identities id = id mod N in S satisfy id ≡ id mod p 2 ;

(2) No identity id ∈ S satisfies α + id ≡ 0 mod p 1 . By the argument in Section 3.3, we have

-

a generator of G p 2 and r 1,y , . . . , r k,y R ←-Z N are fresh for each secret key. However we note that α 1 , . . . , α k-1 R ←-Z N are shared among all secret keys. For the other case (i.e., k > y + n), the secret key is defined as in

where

G 5 : We replace the exponents in the G p 2 -components of SK Sy (y ∈ [q]) with independent random elements t 0,y , t 1,y . . . , t n-1,y , t 1,y , . . . , t y ,y ∈ Z N . In particular, a private key SK Sy for S y (y ∈ [q]) is computed as

We are going to prove that G 5 and G 4 are statistically indistinguishable. For y ∈ [q], we let the G p 2 component of K 0,y , K 1,y , . . . , K n-1,y , K 1,y , . . . , K y ,y in G 4 have logarithms

In this game, the challenge ciphertext is generated as

In order to prove that G 6 and G 7 are statistically close, we only need to check the following terms in G 6 :

• X 3,0,1 , . . . , K 0,q = u q • u 0 • g t 0,q +t 0 2

• X 3,0,q for some ω 2 ∈ Z N . We emphasize that t 0 and t 0,1 , . . . , t 0,q only appear in the above terms (labelled by the boxes) and {t 0 , t 0,1 + t 0 , . . . , t 0,q + t 0 } are uniformly distributed over Z q+1 p 2 . This means that, conditioned on A 's view, e(C * 1 , U 0 ) still has log(p 2 ) bits of min-entropy when C * 1 has a non-trivial G p 2 component (i.e., ω 2 = 0 mod p 2 ). Therefore we can conclude as in Section 3.

It is not hard to observe that the challenge ciphertext reveals nothing about β ∈ {0, 1} in G 7 . Thus we have Pr[E 7 ] = 1/2. Combining all the above together, we may prove the theorem.

Proofs of Lemmas

Proof (of Lemma 4). The reduction B 1 receives an instance (G pub , g 1 , g 3 , T ) of DS1 and simulates the sid-cpa game to A as follows.

Setup. Received the challenge set S * and threshold τ * from A , algorithm B 1 samples α, γ R ←-Z N and computes γ = γ • p S * ,τ * (α). It sets g = g 1 , picks u 0 R ←-G p 1 (taking g 1 as a generator) and computes

and returns the following public parameters to

where d 1 , . . . , d n-1 ∈ Z N are selected arbitrarily. Key Extraction Phase. Upon a key extraction query on S y of size y , the reduction B 1 picks u y R ←-G p 1 (using g = g 1 as the generator), X 3,1,y , . . . , X 3, y ,y , X 3,1,y , . . . , X 3,n-1,y , X 3,0,y R ←-G p 3 (using g 3 as the generator) and responds the query with

because both α and γ are known to B 1 . Challenge. The reduction algorithm receives two messages M 0 , M 1 ∈ {0, 1} ρ , it picks a random bit β R ←-{0, 1} and returns

where

Guess. Finally, A returns its guess β and B 1 returns 1 if and only if β = β .

Observe that the distribution of CT * is as in game

This proves the lemma.

Proof (of Lemma 5). On input an instance (G pub , g 1 , g 3 , h 12 , h 23 , T ) of DS2 problem, the reduction B 2 simulates the sid-cpa game as follows.

Setup. A commits to the challenge set S * and the challenge threshold

using g 1 as the generator, r1,y , . . . , r y +n,y R ←-Z N and X3,1,y , . . . , X3, y ,y , X 3,1,y , . . . , X 3,n-1,y , X3,0,y R ←-G p 3 . The secret key can be computed as

Challenge. In the challenge phase, A chooses two messages M 0 , M 1 ∈ {0, 1} ρ . The reduction B 2 picks β R ←-{0, 1} n and returns the challenge ciphertext

Guess. When A has its guess β , B 2 returns 1 if and only if

2 is either a random element in Z N or equals 0, and h 3 , T 3 are uniformly distributed over G p 3 . In the key extraction phase, the simulation for the second case is correct where B 2 implicitly sets r 1,y = ω 2 • r1,y , . . . , r y +n,y = ω 2 • r y +n,y for S y ; for the first case, B 2 implicitly sets

Note that u y only reveals µ y mod p 1 . Therefore when ω * 2 = 0 (i.e., T ∈ G p 1 p 2 p 3 ), r k,y is uniformly distributed over Z N and the simulation is identical to G 4.k.0 ; otherwise, when ω * 2 = 0 (i.e., T ∈ G p 1 p 3 ), we have r k,y = 0 and the simulation is as G 4.(k-1).1 . This readily proves the lemma.

Proof (of Lemma 6). For convenience, we discard the subscript y ∈ [q]. We note that our analysis can be applied to all B 1 , . . . , B q . Let (S * = (id * 1 , . . . , id * * ), τ * ) be the challenge set and threshold while S = (id 1 , . . . , id ) be the set associated with the key we are looking at. According to the security model, the size of S ∩ S * must be smaller than τ * . W.L.O.G, we may let τ < τ * be the size and assume id 1 = id * 1 , . . . , id τ = id * τ (In fact this can be achieved via re-ordering.) We define the polynomials

We will argue the following matrix is invertible w.h.p when α 1 , . . . , α +n

Proof (of Lemma 7

). On input an instance (G pub , g 1 , g 3 , h 12 , h 23 , T ) of DS2 problem, the reduction B 2 simulates the sid-cpa game as follows.

Setup. A commits to the challenge set S * and the challenge threshold τ 2 is either a random element in Z N or equals 0, and h 3 , T 3 are uniformly distributed over G p 3 . In the key extraction phase, B 2 implicitly sets t 0,y = ω 2 • t0,y , t 1,y = ω 2 • t 1,y , . . . , t n-1,y = ω 2 • t n-1,y , t 1,y = ω 2 • t1,y , . . . , t y ,y = ω 2 • t y ,y . Because we implicitly set t 0 = ω * 2 , when ω * 2 = 0 (i.e., T ∈ G p 1 p 2 p 3 ), the simulation is identical to G 6 ; otherwise, when ω * 2 = 0 (i.e., T ∈ G p 1 p 3 ), the simulation is as G 5 . This proves the lemma.