Somindu C Ramanna
email: somindu.ramanna@ens-lyon.fr

More Efficient Constructions for Inner-Product Encryption

Keywords: inner-product encryption, attribute-hiding, constant-size ciphertexts, quasi-adaptive non-interactive zero knowledge proofs

We propose new constructions for inner product encryption -IPE1 and IPE2, both secure under the eXternal Diffie-Hellman assumption (SXDH) in asymmetric pairing groups. The first scheme has constant-size ciphertexts whereas the second one is weakly attribute hiding. IPE2 is derived from the identity-based encryption scheme of Jutla Roy (Asiacrypt 2013), that was extended from tag-based quasi-adaptive non-interactive zero-knowledge (QA-NIZK) proofs for linear subspaces of vector spaces over bilinear groups. The verifier common reference string (CRS) in these tag-based systems are split into two parts, that are combined during verification. We consider an alternate form of the tag-based QA-NIZK proof with a single verifier CRS that already includes a tag, different from the one defining the language. The verification succeeds as long as the two tags are unequal. Essentially, we embed a two-equation revocation mechanism in the verification. The new QA-NIZK proof system leads to IPE1, a constant-sized ciphertext IPE scheme with very short ciphertexts. Both the IPE schemes are obtained by applying the nequation revocation technique of Attrapadung and Libert (PKC 2010) to the corresponding identity based encryption schemes and proved secure under SXDH assumption. As an application, we show how our schemes can be specialised to obtain the first fully secure identity-based broadcast encryption based on SXDH with a trade-off among the public parameters, ciphertext and key sizes, all of them being sub-linear in the maximum number of recipients of a broadcast.

Introduction

Inner product encryption (IPE) is a special form of the more general attributebased encryption (ABE), which provides fine-grained access control to encrypted data. In ABE, a ciphertext is encrypted to some attribute x and a secret key is associated to some attribute y such that decryption succeeds iff some relation R on x, y holds true i.e., R(x, y) = 1. The standard notion of security for ABE requires resistance to collusion attacks. More precisely, the privacy of a message encrypted to attribute x must not be compromised in the event of an attack by a group of users possessing secret keys for y 1 , y 2 , . . . , y q where R(x, y i ) = 0 for all i = 1, . . . , q. Another useful security property, called weak attribute hiding, requires that given a ciphertext, the group of corrupt users unauthorised to decrypt the ciphertext, learn nothing about the attribute x. In both cases, adaptive security allows users to be corrupted adaptively.

A simple form of ABE is identity-based encryption, where x and y represent identities and the relation R tests equality of identities. IPE is a more complex form with R testing orthogonality of x and y that are vectors in some inner product space. In other words, R(x, y) = 1 if x, y = 0 and 0 otherwise. Though they appear restricted, inner products cover a wide range of functionalities useful in practice including polynomial functions, boolean formulae evaluating conjunctive and disjunctive normal forms, and identity-based broadcast encryption and revocation.

Most efficient constructions of IPE are based on pairings. A pairing e : G 1 × G 2 → G T is a bilinear, non-degenerate and efficiently computable map defined over three groups G 1 , G 2 , G T all having the same order. The common order of the groups may be composite or prime. Prime order pairings where G 1 = G 2 are called asymmetric. The best choices for implementation are asymmetric pairings, particularly those with no efficiently computable isomorphisms between G 1 and G 2 (called Type-3 pairings), from a point of view of security as well as efficiency. A consequence of the absence of efficient isomorphisms makes the decisional Diffie-Hellman (DDH) problem hard in both groups G 1 and G 2 , collectively called the symmetric eXternal decisional Diffie-Hellman (SXDH) problem. We mainly focus on security under this assumption.

A powerful technique to obtain adaptive security for attribute-based encryption schemes is the dual system methodology introduced by Waters [START_REF] Waters | Dual System Encryption: Realizing Fully Secure IBE and HIBE under Simple Assumptions[END_REF]. Important features of the underlying algebraic structure that facilitate a dual system proof are cancelling and parameter-hiding. These features are explicitly available in composite order pairing groups that are not really suitable for practical deployment. A number of works have investigated the possibilities of translating the properties of composite order pairings to the prime-order setting, mostly in the context of dual system hierarchical IBE and ABE. However, the constructions resulting from these translations are not necessarily optimised in terms of various system parameters (such as ciphertext/key size, time required for decryption and so on). In contrast, direct constructions in the prime-order setting circumventing the route via composite order pairings, holds more promise in this regard. We believe that IPE as a cryptographic primitive is significant enough to justify attempts for direct constructions.

The goal of this work is to obtain new direct Type-3 pairing-based constructions of IPE that are efficient, adaptively secure with a focus on achieving either of the following properties -attribute-hiding or compact ciphertexts -from the SXDH assumption.

Our Contributions. We propose two new IPE schemes based on prime-order pairings named IPE 1 and IPE 2 -the former with constant-sized ciphertexts and the latter achieving weak attribute hiding, both secure under the SXDH assumption. The constructions are derived from quasi-adaptive non-interactive zero knowledge (QA-NIZK) proofs of Jutla and Roy [START_REF] Jutla | Shorter quasi-adaptive NIZK proofs for linear subspaces[END_REF] and an IBE proposed in the same work (denoted JR -IBE in the rest of the paper). IPE 2 is obtained from JR -IBE by a novel application of the n-equation revocation technique of Attrapadung and Libert [START_REF] Attrapadung | Functional encryption for inner product: Achieving constant-size ciphertexts with adaptive security or support for negation[END_REF]. But a constant-size ciphertext IPE cannot be constructed in a similar way from JR -IBE. To get around this problem, we propose a small tweak to the Jutla-Roy QA-NIZK proofs that leads to an alternate form of JR -IBE (named JR -IBE-D). The n-equation revocation method is then combined with JR -IBE-D to construct IPE 1 . QA-NIZK proofs were only known to yield IBE [START_REF] Jutla | Shorter quasi-adaptive NIZK proofs for linear subspaces[END_REF] , hierarchical IBE (HIBE) [START_REF] Somindu | Efficient (anonymous) compact HIBE from standard assumptions[END_REF] and identitybased broadcast encryption [START_REF] Somindu | Efficient adaptively secure IBBE from standard assumptions[END_REF] but the question of whether they are useful in constructing other forms of ABE remained open. Thus, we (partially) settle an open question posed in [START_REF] Chen | Improved dual system ABE in prime-order groups via predicate encodings[END_REF].

Tables 1 and 2 compare our constructions to those recently proposed by Chen, Gay and Wee [START_REF] Chen | Improved dual system ABE in prime-order groups via predicate encodings[END_REF]. The reason we do not include other previous constructions in the comparison is that the constructions in [START_REF] Chen | Improved dual system ABE in prime-order groups via predicate encodings[END_REF] are the most efficient instantiations known so far and their constructions achieve security from the SXDH assumption. First, we define some abbreviations/notation we use in the comparison. #pp, #cpr and #key denote the sizes of public parameters, ciphertexts and keys respectively. #dec denotes the time required for decryption. |X| denotes the size of representation of an element from X. [P], [M i ] (for i = 1, 2) and [E] respectively denote the time required for pairing operation, scalar multiplication in G i (for i = 1, 2) and exponentiation in G T respectively.

Scheme #pp #cpr #key #dec [CGW15] (2n + 4)|G1| + |GT | 4|G1| + |GT | (2n + 2)|G2| 4[P] + 2n[M2] IPE1 (n + 3)|G1| + |GT | 3|G1| + |Z p | + |GT | (2n + 1)|G2| + (n -1)|Z p | 3[P] + (2n -2)[M2] + [E] Table 1. Constant-size ciphertext IPE. Scheme #pp #cpr #key #dec [CGW15] (2n + 4)|G1| + |GT | (2n + 2)|G1| + |GT | 4|G2| 4[P] + 2n[M1] IPE2 (n + 3)|G1| + |GT | (n + 1)|G1| + (n -1)|Z p | + |GT | 5|G2| 3[P] + (n + 1)[M1]
Table 2. Attribute-hiding IPE.

Note that both our schemes are at least as efficient as the corresponding instantiations in [START_REF] Chen | Improved dual system ABE in prime-order groups via predicate encodings[END_REF]. The public parameters and decryption time are better in our schemes. The ciphertext size in both IPE 1 and IPE 2 are at least as short as those in [START_REF] Chen | Improved dual system ABE in prime-order groups via predicate encodings[END_REF].

Quasi-Adaptive NIZK Proofs to IPE. Jutla and Roy [START_REF] Jutla | Shorter quasi-adaptive NIZK proofs for linear subspaces[END_REF] proposed constructions of quasi-adaptive non-interactive zero knowledge (QA-NIZK) proofs for linear equations over pairing groups that have a weaker soundness criterion called quasi-adaptive soundness. The difference with regular NIZKs is that the common reference string (CRS) is allowed to depend on the language. These are useful in constructing a number of primitives, such as signatures, CCA2secure public key encryption, commitment schemes and so on. From the signature scheme, they obtained an IBE using Naor's transform, which is the most efficient IBE known till date in terms of size of public parameters and ciphertexts achieving adaptive security under standard assumptions. Building upon this IBE, we obtain a weakly attribute hiding IPE scheme using the n-equation revocation method proposed in [START_REF] Attrapadung | Functional encryption for inner product: Achieving constant-size ciphertexts with adaptive security or support for negation[END_REF].

The NIZK construction that leads to the IBE is actually a split-CRS NIZK for tag-based languages, where the CRS for the verifier is split into two components. These two components are then combined using a public random tag ctag, which is also a parameter defining the language. We make a slight modification by combining the two components of the split-CRS with another tag ktag and only providing the combination as the CRS. This ensures that verification is successful unless the two tags are equal, thus making unconditional failure of verification a possibility. Nevertheless, the probability of failure is negligible and this small modification leads to an IBE scheme that has tags in both ciphertexts and keys. Decryption requires the two-equation revocation technique of Sahai and Waters [START_REF] Lewko | Revocation systems with very small private keys[END_REF] as used in Waters' IBE [START_REF] Waters | Dual System Encryption: Realizing Fully Secure IBE and HIBE under Simple Assumptions[END_REF] and fails unconditionally with (negligible) probability equal to that of NIZK verification failure. The resulting IBE which we denote as JR -IBE-D, allows extension to primitives that were not possible from JR -IBE, such as identity-based revocation schemes with small secret keys, constant-size ciphertext IBBE and so on. We present a construction of constant-size ciphertext IPE that can then be specialised to the afore-mentioned primitives. Unlike earlier constructions based on dual pairing vector spaces, specialising the IPE to specific cases actually leads to optimal constructions, i.e., these schemes are as efficient as direct constructions obtained from JR -IBE-D.

The reason for first constructing an IBE is two-fold. Firstly, it provides better intuition and acts as a basis for moving to inner product functionality. Second and most importantly, we do not know a direct generic transformation from QA-NIZK proofs to IBE, let alone IPE. To this end, there has been some recent work [START_REF] Jutla | Dual-system simulation-soundness with applications to UC-PAKE and more[END_REF] that defines the so-called dual system simulation sound QA-NIZK proofs that explain the JR -IBE construction better in generic terms. It may be possible to explain our constructions too within this framework.

Application. As an application of IPE, we consider identity-based broadcast encryption (IBBE) wherein the goal is to securely broadcast an encrypted message to users associated with identities so that only a subset of privileged users can decrypt the message. Unlike the public key broadcast setting where the number of public keys varies polynomially with the security parameter, the number of valid identities in an IBBE are allowed to be exponential. Some direct constructions of adaptively secure constructions of IBBE schemes already exist in the literature [START_REF] Gentry | Adaptive security in broadcast encryption systems (with short ciphertexts)[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] Somindu | Efficient adaptively secure IBBE from standard assumptions[END_REF]. Most of these schemes require the number of privileged recipients for any broadcast to be bounded during setup (call this bound n). Previous schemes had either constant-sized ciphertexts or constantsized keys with at least one out of public parameters, ciphertext, key having size depending linearly on n.

We show how to construct an IBBE from IPE 1 that achieves parameters, ciphertexts and keys all having size sublinear in n while maintaining security under static complexity assumptions. (Here, static means that the number of elements in instance is a constant). Due to lack of space, we present this discussion in Appendix C. Related Work. There have been several constructions of attribute encryption schemes based on pairings [SW05,GPSW06,OSW07,BSW07,Wat11,LW12], some focussing only on inner product encryption [KSW08,OT09,OT10,AL10]. Latticebased constructions include ABE of [START_REF] Boyen | Attribute-Based Functional Encryption on Lattices[END_REF] for formulas and [GVW13,GGH + 13] for circuits. We are mostly interested in constructions based on bilinear maps with prime order. Several approaches have been taken to constructing ABE schemes in the prime order pairing setting, most of them attempting to simulate properties of composite order pairings in suitably defined primeorder counterparts. A widely used technique is based on dual pairing vector spaces [START_REF] Okamoto | Homomorphic Encryption and Signatures from Vector Decomposition[END_REF][START_REF] Okamoto | Hierarchical Predicate Encryption for Inner-Products[END_REF] which obtains all the nice theoretical properties but fails to preserve efficiency. The sparse DPVS technique introduced in [OT11] uses subgroups of sparse matrices (those mostly covered with zero entries) with the hope of improving efficiency. But the conversions are no longer generic and involve very complex security analysis. Another generic technique is that of dual system groups [START_REF] Chen | Fully, (almost) tightly secure IBE and dual system groups[END_REF] that provides more efficient translations in the context of IBE. However, it does not extend to primitives that require anonymity or attribute-hiding. Two works [START_REF] Wee | Dual system encryption via predicate encodings[END_REF][START_REF] Attrapadung | Dual system encryption via doubly selective security: Framework, fully secure functional encryption for regular languages, and more[END_REF] present unifying frameworks for predicate encryption schemes fully secure within the dual system framework. These frameworks were defined in the composite order setting and later translated to prime-order groups [START_REF] Chen | Improved dual system ABE in prime-order groups via predicate encodings[END_REF][START_REF] Attrapadung | Dual system encryption framework in prime-order groups[END_REF]. The translations to prime-order setting required additional restrictions on the structure of encodings that do not hold for most encodings proposed in [START_REF] Wee | Dual system encryption via predicate encodings[END_REF][START_REF] Attrapadung | Dual system encryption via doubly selective security: Framework, fully secure functional encryption for regular languages, and more[END_REF]. A recent work [START_REF] Agrawal | A study of pair encodings: Predicate encryption in prime order groups[END_REF] provides a new instantiation of the encoding framework of [START_REF] Attrapadung | Dual system encryption via doubly selective security: Framework, fully secure functional encryption for regular languages, and more[END_REF] employing dual system groups ([CW13,CGW15]), thus implying constructions for predicate encryption in both composite-order and prime-order bilinear group settings. This work also considers a relaxation of the information theoretic security property used in [START_REF] Attrapadung | Dual system encryption via doubly selective security: Framework, fully secure functional encryption for regular languages, and more[END_REF][START_REF] Attrapadung | Dual system encryption framework in prime-order groups[END_REF] that allows covering a larger class of encodings. On the other hand, the efficiency tradeoffs for the constructions in [START_REF] Chen | Improved dual system ABE in prime-order groups via predicate encodings[END_REF] and [START_REF] Agrawal | A study of pair encodings: Predicate encryption in prime order groups[END_REF] are directly related to the underlying dual system groups (DSG) instantiation. The DSG realisation in [START_REF] Chen | Improved dual system ABE in prime-order groups via predicate encodings[END_REF] leads to very efficient constructions in the prime-order setting for several predicates. Apart from translations from composite-order groups, there have been attempts at direct constructions of certain simple primitives such as IBE and HIBE. The approach of [START_REF] Jutla | Shorter quasi-adaptive NIZK proofs for linear subspaces[END_REF] is via QA-NIZK proofs. This was later extended to HIBE in [START_REF] Somindu | Efficient (anonymous) compact HIBE from standard assumptions[END_REF] and IBBE [START_REF] Somindu | Efficient adaptively secure IBBE from standard assumptions[END_REF]. Another interesting approach was to construct (H)IBE from message authentica-tion codes (which is a symmetric primitive), examined in [START_REF] Blazy | hierarchical) identity-based encryption from affine message authentication[END_REF]. But it is not known whether or not the last method extends to attribute-based encryption.

Preliminaries

This section introduces some notation followed by a review of pairings and related hardness assumptions. Also provided are definitions related to innerproduct encryption.

Notation

The notation x 1 , . . . , x k R ←-X indicates that elements x 1 , . . . , x k are sampled independently from the set X according to some distribution R. We use U to denote the uniform distribution. For a (probabilistic) algorithm A, y R ←-A(x) means that y is chosen according to the output distribution of A on input x. A(x; r) denotes that A is run on input x with its internal random coins set to r. For two integers a < b, the notation [a, b] represents the set {x ∈ Z : a ≤ x ≤ b}. If G is a finite cyclic group, then G × denotes the set of generators of G.

We denote vectors in Z n p by bold upright characters (e.g. x). Inner product of two Z n p -vectors x = (x 1 , . . . , x n ) and y = (y 1 , . . . , y n ) is given by x, y = n i=1 x i y i .

Asymmetric Pairings and Hardness Assumptions

A bilinear pairing ensemble is a 7-tuple G = (p, G 1 , G 2 , G T , e, P 1 , P 2 ) where G 1 = P 1 , G 2 = P 2 are written additively and G T is a multiplicatively written group, all having the same order p and e : G 1 × G 2 → G T (the pairing) is a bilinear, non-degenerate and efficiently computable map. In a Type-3 pairing, G 1 = G 2 and no efficiently computable isomorphisms between G 1 and G 2 are known. The constructions we provide are based on such pairings. The assumptions based on which the security of our constructions is proven are the decision Diffie-Hellman (DDH) assumptions in groups G 1 and G 2 , called DDH1 and DDH2 respectively. Below, we describe these two assumptions. Technically speaking, the two assumptions are not in the standard form but can be shown to be equivalent. The reason we use the alternate forms is that they suit the requirements of our reductions and also to be in sync with the notation in [START_REF] Jutla | Shorter quasi-adaptive NIZK proofs for linear subspaces[END_REF].

Let G = (p, G 1 , G 2 , G T , e, P 1 , P 2 ) be an asymmetric pairing ensemble and A , a probabilistic polynomial time (PPT) algorithm A that outputs 0 or 1. Assumption DDH1. Define a distribution D as follows:

P 1 U ←-G × 1 ; b, s U ←- Z p , µ U ←-Z p ; D = (G, P 1 , bP 1 , bsP 1
). The advantage of A in solving the DDH1 problem is given by

Adv DDH1 G (A ) = | Pr[A (D, sP 1 ) = 1] -Pr[A (D, (s + µ)P 1 ) = 1]|.
Essentially, A has to decide whether µ = 0 or µ ∈ U Z p given (D, (s + µ)P 1 ). The (ε, t)-DDH1 assumption holds in G if for any adversary A running in time at most t, Adv DDH1 G (A ) ≤ ε.

Assumption DDH2. Let a distribution D be defined as follows:

P 2 U ←-G × 2 , r, c U ←-Z p , γ U ←-Z p ; D = (G, P 2 , rP 2 , cP 2 ).
A 's advantage in solving the DDH2 problem is given by

Adv DDH2 G (A ) = | Pr[A (D, rcP 2 ) = 1] -Pr[A (D, (rc + γ)P 2 ) = 1]|.
The (ε, t)-DDH2 assumption is that, for any t-time algorithm A , Adv DDH2 G (A ) ≤ ε.

Inner Product Encryption (IPE)

Definition 1 (IPE). Let V denote a vector space of dimension n over a field F and M denote the message space. An IPE scheme for inner products over V , is defined by four probabilistic algorithms -Setup, Encrypt, KeyGen and Decrypt.

Setup(κ, n) Takes as input a security parameter κ and the dimension of V . It outputs the public parameters PP and the master secret MSK. KeyGen(MSK, y) On input a vector y ∈ V and the master secret MSK; this algorithm outputs a secret key SK y for y. Encrypt(PP, m, x) Takes as input a message m and an attribute vector x ∈ V and outputs a ciphertext C. Decrypt(PP, C, SK y ) If x, y = 0, this algorithm returns the message m and ⊥ otherwise.

Correctness. The IPE scheme is said to satisfy the correctness condition if for all vectors x, y ∈ V with x, y = 0 and for all m ∈ M, if (PP, MSK)

R ←- Setup(κ, n), SK y R ←-KeyGen(MSK, y), C R ←-Encrypt(PP, m, x), then Pr[m = Decrypt(PP, C, SK y )] = 1.
Definition 2 (Security). The security definition for inner product encryption scheme that we consider is weak attribute hiding and adaptive security against chosen plaintext attacks. It is formalised in terms of the following game ind-wah-cpa between an adversary A and a challenger. Setup: The challenger runs the Setup algorithm of the IPE and gives the public parameters to A . Key Extraction Phase 1: A makes a number of key extraction queries adaptively. For a query on a vector y, the challenger responds with a key SK y . Challenge: A provides two pairs of messages and attribute vectors m 0 , x 0 and m 1 , x 1 with the restriction that if y is queried in the key extraction phase 1, then x 0 , y = 0 and x 1 , y = 0. The challenger chooses a bit β uniformly at random from {0, 1}, encrypts m β to x β and returns the resulting ciphertext C to A .

Key Extraction Phase 2:

A makes more key extraction queries with the restriction that it cannot query a key for any vector y with x 0 , y = 0 or x 1 , y = 0. Guess: A outputs a bit β .

If β = β , then A wins the game. The advantage of A in winning the ind-wah-cpa is given by

Adv ind-wah-cpa IPE (A ) = Pr[β = β ] - 1 2 .
The IPE scheme is said to be (ε, t, q)-IND-WAH-CPA secure if every t-time adversary making at most q key extraction queries has Adv ind-wah-cpa IPE (A ) ≤ ε. We also consider a slightly weaker form of adaptive security denoted IND-CPA-security where attribute hiding property is not achieved. In the corresponding security game, denoted ind-cpa, x 1 = x 2 that is, there is only one challenge attribute vector x.

Variant of Jutla-Roy Split-CRS NIZK Proof and IBE

In this section, we suggest a small modification to QA-NIZK proofs of Jutla and Roy [START_REF] Jutla | Shorter quasi-adaptive NIZK proofs for linear subspaces[END_REF] and describe an IBE derived from it. We denote the IBE as JR -IBE-D, the 'd' signifying a sort of 'dual' of the original scheme. JR -IBE-D forms the basis of our IPE construction with short ciphertexts. Since the QA-NIZK construction only points a way to the IBE construction, we provide an informal description of the modification required without delving into details of the construction or proof. For definitions and more details related to QA-NIZK proofs we refer to [START_REF] Jutla | Shorter quasi-adaptive NIZK proofs for linear subspaces[END_REF].

We are mainly interested in NIZK proofs for languages that are linear subspaces of vectors of G 2 -elements. [START_REF] Jutla | Shorter quasi-adaptive NIZK proofs for linear subspaces[END_REF] actually considers vectors over G 1 . Since G 1 has shorter representation compared to G 2 , we prefer the ciphertext components to live in G 1 and hence reverse the roles of G 1 and G 2 in our presentation. A linear subspace language is parameterised by an t×m matrix A of G 2 -elements and defined as

L A = {x T A | x ∈ Z t p }. A NIZK proof
system for this language is a collection of 4 algorithms (K 0 , K 1 , P, V) where K 0 generates the common parameters (group descriptions for a pairing), K 1 generates CRS p and CRS v , the prover and verifier CRS's respectively, P generates a proof given a witness x for a candidate Q ∈ L A and V verifies that the proof is valid. Quasi-adaptiveness refers to the CRS being allowed to depend on the parameter, (A in the above case). Three notionscompleteness, soundness and zero-knowledge -formalise the security requirements of a NIZK proof system. [START_REF] Jutla | Shorter quasi-adaptive NIZK proofs for linear subspaces[END_REF] starts with an efficient construction for this language and then extends it to what they call the split-CRS QA-NIZK system. The languages supported by such systems are characterised as

L A, A1, A2 = {x T • [A| A 1 + ctag • A 2 ] | x ∈ Z t p , ctag ∈ Z p }, with A ∈ G t×m 2 , A 1 , A 2 ∈ G t 2 are parameters defining the language. Writing A as [A l |A r ] with A l ∈ G t×t 2 and A r ∈ G (m-t)×t 2
and assuming that the number (m -t) of equations in excess of the number of unknowns can be verified by just making additional randomised copies of the CRS [JR13], we only consider A l in our descriptions. The algorithms of the split-CRS NIZK system are described below.

K 0 : Generates the bilinear pairing parameters G = (p, G 1 , G 2 , G T , e, P 1 , P 2 ). K 1 : Generates CRS as CRS p,0 = A l | A 1 u 1 b -1 CRS p,1 = A l | A 2 u 2 b -1 CRS v,0 =   bu 1 1 -b   P 1 CRS v,1 =   bu 2 0 0   P 1 , where u 1 , u 2 U ←-Z t p and b U ←-Z × p . Note that CRS v,0 , CRS v,1 ∈ G t+2 1 . P: Suppose the candidate is Q = x T • [A| A 1 + ctag • A 2 ]. The proof is given by R = x T (CRS p,0 + ctag • CRS p,1 ). V: Given a proof R for a candidate Q , the verifier checks whether e [ R | Q], CRS v,0 + ctag • CRS v,1
equals 1 T , the identity of G T or not indicating validity of the proof or otherwise, respectively. Here the pairing function e evaluated on vectors is nothing but the product of the component-wise evaluations.

Our modification. We are now ready to propose our tweak to this split-CRS NIZK system. Instead of combining the verifier CRS's during verification, consider providing only one verifier CRS defined as

CRS v = CRS v,0 + ktagCRS v,1 where ktag U ←-Z p is chosen in K 1 . Verification is now done by testing whether e [ R | Q], CRS v 1 (ctag-ktag)
is 1 T only if ctag = ktag. Verification fails unconditionally if the two tags are equal. The modification weakens the quasi-adaptive soundness criterion since there is a probability that the verification algorithm fails. However, we make this modification only to make a transition to attribute-based encryption. Whether this NIZK system is actually useful for other purposes is beyond the scope of this work.

IBE.

We now present the identity-based encryption scheme obtained from the above mentioned NIZK system.

Setup(κ): Let G = (p, G 1 , G 2 , G T , e, F 1 , F
2 ) be a Type-3 pairing ensemble generated based on the security parameter κ.

Choose P 1 U ←-G × 1 , P 2 U ←-G × 2 , b U ←-Z × p , α 1 , α 2 , u 1 , u 2 , v 1 , v 2 , w 1 , w 2 U ←-Z p and set U 1 = (u 1 +bu 2 )P 1 , V 1 = (v 1 + bv 2 )P 1 , W 1 = (w 1 + bw 2 )P 1 , g T = e(P 1 , P 2 ) α1+bα2
. The parameters are given by

PP : (P 1 , bP 1 , U 1 , V 1 , W 1 , g T ) MSK : (P 2 , α 1 , α 2 , u 1 , u 2 , v 1 , v 2 , w 1 , w 2 ) Encrypt(PP, m, id): The ciphertext is given by C = (C 0 , C 1 , C 2 , C 3 , ctag) where ctag, s U ←-Z p , C 0 = m • (g T ) s , C 1 = sP 1 , C 2 = sbP 1 , C 3 = s(U 1 + idV 1 + ctagW 1 ). KeyGen(MSK, id) Compute the secret key SK id = (K 1 , K 2 , K 3 , K 4 , K 5 , ktag) as follows. r, ktag U ←-Z p , K 1 = rP 2 , K 2 = (α 1 + rw 1 ) P 2 , K 3 = (α 2 + rw 2 ) P 2 K 4 = r(u 1 + idv 1 + ktagw 1 )P 2 , K 5 = r(u 2 + idv 2 + ktagw 2 )P 2 . Decrypt(C, SK id ): If ctag = ktag, return ⊥. Otherwise compute A = e(C 3 , K 1 ) e(C 1 , K 4 )e(C 2 , K 5 ) 1 ctag-ktag
and recover the message as

m = C 0 • A e(C 1 , K 2 )e(C 2 , K 3 ) .
The message m can be recovered in a single step involving 3 pairing operations.

Decryption involves the two-equation revocation technique of Sahai and Waters [START_REF] Lewko | Revocation systems with very small private keys[END_REF] that was also used in Waters IBE [START_REF] Waters | Dual System Encryption: Realizing Fully Secure IBE and HIBE under Simple Assumptions[END_REF]. The scheme is adaptively secure under the SXDH assumption. Since JR -IBE-D is a special case of IPE 1 , its security is implied by that of IPE 1 . Hence we omit the proof.

IPE with Short Ciphertexts

In this section, we define our first IPE construction IPE 1 with constant-size ciphertexts and show that it is adaptively secure. As mentioned earlier, we use the n-equation revocation technique of Attrapadung and Libert [START_REF] Attrapadung | Functional encryption for inner product: Achieving constant-size ciphertexts with adaptive security or support for negation[END_REF] to extend JR -IBE-D to support inner product encryption. Below is the description of the algorithms of

IPE 1 = (IPE 1 .Setup, IPE 1 .Encrypt, IPE 1 .KeyGen, IPE 1 .Decrypt). IPE 1 .Setup(κ, n): Generate a Type-3 pairing G = (p, G 1 , G 2 , G T , e, F 1 , F 2 ) based on the security parameter κ. Choose P 1 U ←-G × 1 , P 2 U ←-G × 2 , b U ←-Z × p , α 1 , α 2 , w 1 , w 2 U ←-Z p , u 1 = (u 1,1 , . . . , u 1,n ), u 2 = (u 2,1 , . . . , u 2,n ) U ←-Z n p
and set u = (u 1 + bu 2 )P 1 , w = (w 1 + bw 2 ), g T = e(P 1 , P 2 ) α1+bα2 . The parameters are given by

PP : (P 1 , bP 1 , uP 1 , wP 1 , g T ) MSK : (P 2 , α 1 , α 2 , u 1 , u 2 , w 1 , w 2 ) IPE 1 .Encrypt(PP, m, x = (x 1 , . . . , x n )): Components of the ciphertext are com- puted as follows. ctag, s U ←-Z p , C 0 = m • (g T ) s , C 1 = sP 1 , C 2 = sbP 1 , C 3 = s( x, u + ctag • w)P 1 .
Note that C 3 can be computed from uP 1 , wP 1 and ctag using n + 1 scalar multiplications. The ciphertext is given by C = (x, C 0 , C 1 , C 2 , C 3 , ctag). IPE 1 .KeyGen(MSK, y = (y 1 , . . . , y n )): The secret key for y is given by SK

y = (K 1 , K 2 , K 3 , (K 4,i , K 5,i , ktag i ) n i=2 ) where r, (ktag i ) n i=2 U ←-Z p , K 1 = rP 2 , K 2 = (α 1 + rw 1 )P 2 , K 3 = (α 2 + rw 2 )P 2 For i = 2, . . . , n, K 4,i = r(-u 1,1 yi y1 + u 1,i + ktag i w 1 )P 2 , K 5,i = r(-u 2,1 yi y1 + u 2,i + ktag i w 2 )P 2 . IPE 1 .Decrypt(C, SK y ): Compute ktag = n i=2 x i ktag i . If ctag = ktag, return ⊥. Otherwise let A = e(C 3 , K 1 )e(C 1 , n i=2 x i K 4,i ) -1 e(C 2 , n i=2 x i K 5 ) -1 1 ctag-ktag .
Recover the message as m = C0•A e(C1,K2)e(C2,K3) . As in the IBE, decryption can be done in a single step involving 3 pairings.

Correctness: Let C ←-IPE 1 .Encrypt(PP, m, x = (x 1 , . . . , x n ); s) where C = (x, C 0 , C 1 , C 2 , C 3 , ctag) and let SK y ←-IPE 1 .KeyGen(MSK, y = (y 1 , . . . , y n ); r) with SK y = (K 1 , K 2 , K 3 , (K 4,i , K 5,i , ktag i ) n i=2
). Suppose x, y = 0 and ktag = n i=2 x i ktag i = ctag. First, we look at the computation of A. We have

n i=2 x i K 4,i = n i=2 x i r(-u 1,1 y i y 1 + u 1,i + ktag i w 1 )P 2 = r - u 1,1 y 1 n i=2 x i y i + n i=2 x i u 1,i + w 1 n i=2 x i ktag i P 2 = r - u 1,1 y 1 ( x, y -x 1 y 1 ) + x, u 1 -x 1 u 1,1 + ktag • w 1 P 2 = r ( x, u 1 + ktag • w 1 ) P 2 . Similarly, n i=2 x i K 5,i = r ( x, u 2 + ktag • w 1 ) P 2 .
Combining the two, we get

e(C 1 , n i=2 x i K 4,i )e(C 2 , n i=2
x i K 5 ) = e(P 1 , P 2 ) rs( x,u +ktag•w)

implying that

A = e(C 3 , K 1 )e(C 1 , n i=2 x i K 4,i ) -1 e(C 2 , n i=2 x i K 5 ) -1 1 ctag-ktag = e(P 1 , P 2 ) rsw .
The second stage of decryption recovers the message as shown below.

C 0 • A e(C 1 , K 2 )e(C 2 , K 3 ) = m • g s T • A e(sP 1 , (α 1 + rw 1 )P 2 )e(sbP 1 , (α 2 + rw 2 )P 2 ) =
m • e(P 1 , P 2 ) (α1+bα2)s • e(P 1 , P 2 ) rsw e(P 1 , P 2 ) (α1+bα2)s e(P 1 , P 2 ) rsw = m Before proving security, we describe algorithms that generate the necessary semi-functional objects for a dual system proof. These are required only in the proof.

IPE 1 .SFEncrypt(PP, MSK, m, x): Generate (C = (x, C 0 , C 1 , C 2 , C 3 , ctag)) R ←- IPE 1 .Encrypt(PP, m, x). Choose µ U ←-Z p
and generate the semi-functional ciphertext components as follows.

C 0 ←-C 0 • e(P 1 , P 2 ) µα1 , C 1 ←-C 1 + µP 1 , C 3 ←-C 3 + µ( x, u 1 + ctag • w 1 ).
Return C = (x, C 0 , C 1 , C 2 , C 3 , ctag) as the resulting semi-functional ciphertext. IPE 1 .SFKeyGen(PP, MSK, y): Let SK y = (K 1 , K 2 , K 3 , (K 4,i , K 5,i , ktag i ) n i=2 ) be obtained by running IPE 1 .KeyGen(MSK, y). Pick γ U ←-Z p and modify the components of SK y as follows:

K 2 ←-K 2 + γP 2 , K 3 ←-K 3 -γ b P 2 . The semi-functional key given by SK y = (K 1 , K 2 , K 3 , (K 4,i , K 5,i , ktag i ) n i=2 ) is returned as output.
For a given pair of ciphertext and key satisfying (ktag = n i=2 x i ktag i ) = ctag and x, y = 0, decryption fails only when both are semi-functional since the message will be blinded by e(P 1 , P 2 ) µγ . It is easy to see that the rest of the semi-functional components get canceled.

We now prove that scheme IPE 1 is adaptively secure, formalised in the theorem below.

Theorem 1. Scheme IPE 1 is (q, ε, t)-IND-CPA-secure if the (ε DDH1 , t 1 )-DDH1 and (ε DDH2 , t 2 )-DDH2 assumptions hold in the underlying pairing description G where ε ≤ ε DDH1 + q • ε DDH2 + (1/p) and t = max(t 1 , t 2 ) -O(qρ), ρ being the maximum cost of scalar multiplication in either G 1 or G 2 .

Proof Sketch. Let G 0 denote the real security game ind-cpa (defined in Section 2.3). The proof proceeds though a sequence of games where we gradually change the distribution of the keys and challenge ciphertext provided to the adversary. At the end is the game where the attacker receives semi-functional encryption of a random message. We first change the ciphertext to semi-functional form and then the q keys provided as answers to the q queries to semi-functional form. There are essentially three main parts in the reduction.

Distinguishing normal and semi-functional ciphertexts: We show that an attacker's ability to distinguish between normal and semi-functional ciphertexts can be leveraged to solve the DDH1 problem. This is clear from the definition of semi-functional ciphertexts. P 1 , bP 1 and sbP 1 come from the instance and are sufficient to simulate the correct environment. The DDH1 challenge is embedded in C 1 which is either normal or semi-functional according as the instance is real or random. Since no encoding of b is known in G 2 , the simulator itself cannot create a semi-functional key and detect the type of the challenge ciphertext. Detecting the change of k-th key from normal to semi-functional:

This is the most crucial stage of the security reduction. Denote by y 1 , . . . , y q the queries made by the attacker. The first k -1 keys returned are semifunctional and the last q -k -1 keys are normal. The simulator is designed in a way that it can create both normal and semi-functional keys. The DDH2 challenge is embedded in the k-th key and particularly in component K 2 .

However, for the k-th key the simulator can only create a semi-functional ciphertext with ctag = n i=2 x i ktag i . This ensures that the simulator itself cannot detect the type of k-th key and trivially solve DDH2. Furthermore, the tags in the ciphertext and keys need to be uniformly and independently distributed in the attacker's view. This is achieved by setting them as

     ctag ktag 2 . . . ktag n      =        -x 1 -x 2 -x 3 • • • -x n y 2 /y 1 -1 0 • • • 0 y 3 /y 1 0 -1 • • • 0 . . . . . . . . . . . . . . . y n /y 1 0 0 • • • -1             v 2,1 v 2,2 . . . v 2,n     
where ctag is the tag associated with the challenge ciphertext for the challenge vector x = ( x 1 , . . . , x n ) and ktag 2 , . . . , ktag n are the tags associated with the secret key for y k . The matrix has determinant (-1) n x, y k /y 1 which is non-zero because all of A 's queries are such that x, y k = 0.

(Here y 1 is the first coordinate of y k ). Hence all we need to do is choose v 2 = (v 2,1 , . . . , v 2,n ) uniformly from Z n p and also hide v 2 information theoretically from the attacker. v 2 is in fact embedded in the master secret key (and as a result in the public parameters) but masked by other additive terms. The argument repeated q times for each query gives a degradation of q in DDH2. Distinguishing the real message from a random one: The last important step is an information theoretic argument to show that the message encrypted is random that is, the bit β is statistically hidden form the attacker. This is done by changing the setup and semi-functional key generation algorithms in such a way that all information provided to the attacker are independent of α 1 . The only component that depends on α 1 is C 0 of the challenge ciphertext where the message has a blinding factor of e(P 1 , P 2 ) µα1 . Since all other information is independent of α 1 , m β •e(P 1 , P 2 ) µα1 is uniformly distributed in G T and thus provides no hint to about β unless µ = 0 which happens with probability 1/p.

Refer to Appendix A for details of the proof.

Weakly Attribute-Hiding IPE

In this section, we present our second IPE construction IPE 2 for inner products over Z n p . Unlike IPE 1 , this construction is based on JR -IBE. While the n-equation revocation technique was used in [START_REF] Attrapadung | Functional encryption for inner product: Achieving constant-size ciphertexts with adaptive security or support for negation[END_REF] to obtain constantsize ciphertexts forgoing attribute-hiding, we use it here to anonymise ciphertexts by incorporating the technique into the encryption algorithm. We split the ciphertext component of JR -IBE containing the identity hash into n -1 components corresponding to the entries of the attribute vector x. For decryption, the relation R(x, y) can be verified by combining the ciphertext components using the secret vector y without knowing x. Let IPE 2 = (IPE 2 .Setup, IPE 2 .Encrypt, IPE 2 .KeyGen, IPE 2 .Decrypt) with the algorithms described as below.

IPE 2 .Setup(κ, n): Generate a Type-3 pairing G = (p, G 1 , G 2 , G T , e, F 1 , F 2 ) based
on the security parameter κ.

Choose P 1 U ←-G × 1 , P 2 U ←-G × 2 , b U ←-Z × p , α 1 , α 2 , w 1 , w 2 U ←-Z p , u 1 , u 2 U ←-Z n
p and set u = u 1 + bu 2 , w = w 1 + bw 2 and g T = e(P 1 , P 2 ) α1+bα2 . The parameters are given by

PP : (P 1 , bP 1 , uP 1 , wP 1 , g T ) MSK : (P 2 , α 1 , α 2 , u 1 , u 2 , w 1 , w 2 ) IPE 2 .Encrypt(PP, m, x = (x 1 , . . . , x n )): The ciphertext is given by the tuple C = (C 0 , C 1 , C 2 , (C 3,i , ctag i ) n i=2 )
where

(ctag i ) n i=2 , s U ←-Z p , C 0 = m • (g T ) s , C 1 = sP 1 , C 2 = sbP 1 , C 3,i = s -xi x1 u 1 + u i + ctag i w P 1 for i = 2, . . . , n.
Since (u i P 1 ) i∈[1,n] and wP 1 are provided in PP, each C 3,i can be computed using 3 scalar multiplications. IPE 2 .KeyGen(MSK, y = (y 1 , . . . , y n )): Secret key

SK y = (K 1 , K 2 , K 3 , K 4 , K 5 ) is computed as follows. r U ←-Z p , K 1 = rP 2 , K 2 = (α 1 + r y, u 1 ) P 2 , K 3 = (α 2 + r y, u 2 ) P 2 K 4 = rw 1 P 2 , K 5 = rw 2 P 2 .
IPE 2 .Decrypt(C, SK y , y): Compute ctag = n i=2 y i ctag i . Recover the message as follows. thus implying that A 2 /A 1 = (g T ) s , as desired.

m = C 0 • e( n i=2 y i C 3,i , K 1 ) e(C 1 , K 2 + ctagK 4 )e(C 2 , K 3 + ctagK 5 ) . Correctness. Let C R ←-IPE 2 .Encrypt(PP, m, x = (x 1 , . . . , x n ); s) and let SK y R ←-IPE 2 .KeyGen(MSK, y = (y 1 , . . . , y n ); r) where C, SK y are given by (C 0 , C 1 , C 2 , (C 3,i , ctag i ) n i=2 ), SK y = (K 1 , K 2 , K 3 , K 4 , K 5 ) respectively. Suppose x, y = 0 and ctag = n i=2 y i ctag i . Let A 1 = e( n i=2 y i C 3,i , K 1 ) and A 2 = e(C 1 , K 2 + ctagK 4 )e(C 2 , K 3 + ctagK 5 ). Decryption is correct if A 2 /A 1 = (g T ) s . We have A 1 = e n i=2 y i C 3,i , K 1 = e n i=2 y i s - x i u 1 x 1 + u i + ctag i w P 1 , rP 2 = e -( y, x -x 1 y 1 ) u 1 x 1 + y, u -y 1 u 1 + ctag • w
Security. The theorem below summarises the security guarantee we obtain for IPE 2 .

Theorem 2. Scheme IPE 2 is (q, ε, t)-IND-WAH-CPA-secure if the (ε DDH1 , t 1 )-DDH1 and (ε DDH2 , t 2 )-DDH2 assumptions hold in the underlying pairing description G where ε ≤ ε DDH1 + q • ε DDH2 + (1/p) and t = max(t 1 , t 2 ) -O(qρ), ρ being the maximum cost of scalar multiplication in either G 1 or G 2 .

The proof is more or less similar to the proof of Theorem 1 except for the information theoretic argument in the last step. In addition to showing that the blinding factor on the message is uniformly random in the attacker's view, we also need to prove that the attribute vector is hidden from the adversary. The solution is to simulate the key extraction queries in such a way that all information the attacker sees is independent of u 1 . Observe that u 1 is part of the master secret and would also be used to define the semi-functional components for C 3,i . With all keys and parameters being independent of u 1 , one can argue that C 3,i components are uniform and independent elements of G 1 thus providing no hint about which attribute vector the challenge ciphertext is encrypted to. (This makes sense as the only ciphertext components determined by the attribute vector are C 3,i for i = 2, . . . , n). A detailed proof is provided in Appendix B.

A Proof of Theorem 1

The proof is a hybrid argument over a sequence of q + 6 games G 0 , G 1 , G 2 ,G 3,0 , . . . , G 3,q , G 4 , G 5 where G 0 is the real ind-cpa attack game defined in Section Let X denote the event that the adversary A wins (i.e., β = β ) in G . The rest of the games are described below.

Game G 1 : This game is similar to G 0 except for a modification to the Encrypt algorithm. Elements from the master secret key MSK are used instead of the public parameters. The challenge ciphertext is generated as follows.

ctag, s U ←-Z p , C 1 = sP 1 , C 2 = sbP 1 , C 3 = ( x, u 1 + ctag • w 1 )C 1 + ( x, u 2 + ctag • w 2 )C 2 . C 0 = m β • (C 1 , P 2 ) α1 e(C 2 , P 2 ) α2 ,
It is straightforward to verify that C 0 and C 3 are well-formed. The change we have made is only conceptual and hence G 1 is identical to G 0 . Therefore, we have

Pr[X 0 ] = Pr[X 1 ].
(1)

Game G 2 : The challenge ciphertext generation in G 1 is further modified to obtain game G 2 . Component C 1 is generated as C 1 U ←-G 1 .
The rest of the steps remain the same. We show that the ability of the adversary to detect this change can be used to construct a DDH1-solver. More precisely we have the following.

Lemma 1. | Pr[X 1 ] -Pr[X 2 ]| ≤ ε DDH1 .
Game G 3,0 : We arrive at G 3,0 by modifying the setup, key generation and encryption procedures in G 2 as follows.

Setup: The public parameters are generated as follows. Choose P

1 U ←- G × 1 , P 2 U ←-G × 2 , α, α 1 , w, w 1 U ←-Z p , b U ←-Z × p , u, u 1 U ←-Z n p , implicitly setting u 2 = b -1 (u -u 1 ), w 2 = b -1 (w -w 1 ) and α 2 = b -1 (α -α 1 )
. Set g T = e(P 1 , P 2 ) α and PP = (P 1 , bP 1 , uP 1 , wP 1 , g T ). Key Generation: On input a vector y, the KeyGen algorithm is modified to create the components of SK y as shown below.

r,

(ktag i ) n i=2 U ←-Z p , K 1 = rP 2 , K 2 = (α 1 + rw 1 )P 2 , K 3 = b -1 ((α + rw)P 2 -K 2 ) For i = 2, . . . , n, K 4,i = r(-u 1,1 yi y1 + u 1,i + ktag i w 1 )P 2 , K 5,i = b -1 r(-u 1 yi y1 + u i + ktag i w)P 2 -K 4,i .
Encryption: The Encrypt algorithm is modified to use public parameters instead of elements from the master secret (as in the construction). Further, the challenge ciphertext is generated by a call to the SFEncrypt algorithm.

Essentially, the components of C are generated as follows.

ctag, s, µ

U ←-Z p , C 0 = m β • (g T ) s e(P 1 , P 2 ) µα1 , C 1 = sP 1 + µP 1 , C 2 = sbP 1 , C 3 = s( x, u + • w)P 1 + µ( x, u 1 + ctag • w 1 )P 1 .
It can be shown that the keys and C have the right form via simple calculations. The changes we have made are only conceptual. Therefore, game G 3,0 is identical to G 2 and we have

Pr[X 2 ] = Pr[X 3,0 ]. ( 2
)
Game G 3,k (for k = 1, . . . , q): Let y 1 , . . . , y q be the vectors queried by A . This game is identical to G 3,k-1 except for the following two modifications. The (k -1)-st key is generated according to the SFKeyGen algorithm and SK y k for the k-th vector y k is generated differently -component K 2 of SK y k is now chosen uniformly at random from G 2 . The first change is purely conceptual and hence does not affect the adversary's behaviour in any way. We show that if the adversary can detect the second modification, then the DDH2 problem can be solved. We have the following lemma.

Lemma 2. | Pr[X 3,k-1 ] -Pr[X 3,k ]| ≤ ε DDH2 for all k ∈ [1, q].
Game G 4 : Proceeds identical to G 3,q but for one difference -the secret key corresponding to y q is computed using the SFKeyGen algorithm. Since this is only a conceptual change, we have

Pr[X 3,q ] = Pr[X 4 ]. ( 3
)
Game G 5 : This game is similar to G 4 except for a modification of the SFKeyGen algorithm. The setup remains same as defined in G 3,0 . Let y be the input to SFKeyGen.

r, γ U ←-Z p , K 1 = rP 2 , K 2 = (γ + rw 1 )P 2 , K 3 = b -1 ((α + rw)P 2 -K 2 )
The rest of the secret key components are generated as in G 3,0 . This implicitly sets γ = α 1 + γ and induces a uniform distribution on γ. Furthermore, all keys are computed independent of α 1 and so are the public parameters. As a result, in the adversary's view, e(P 1 , P 2 ) µα1 is randomly distributed in G T as long as µ = 0 which happens with probability at most 1/p. Hence

| Pr[X 4 ] -Pr[X 5 ]| ≤ (1/p). ( 4
)
The probability that A wins in G 5 , where m β is masked by e(P 1 , P 2 ) µα1 , is exactly 1/2 as the bit b is information theoretically hidden from the attacker. Therefore, from Lemmas 1, 2 and equations (1), (2), (3) and (4), we have

ε = Pr[X 0 ] - 1 2 = | Pr[X 0 ] -Pr[X 5 ]| ≤ | Pr[X 0 ] -Pr[X 1 ]| + | Pr[X 1 ] -Pr[X 2 ]| + | Pr[X 2 ] Pr[X 3 , 0]| + q k=1 | Pr[X 3,k-1 ] -Pr[X 3,k ]| + | Pr[X 3,q ] -Pr[X 4 ]| + | Pr[X 4 ] -Pr[X 5 ]| ≤ ε DDH1 + q • ε DDH2 + (1/p)
Proof (of Lemma 1). We build an algorithm B that can solve DDH1 if the adversary A is able to distinguish between games G 1 and G 2 . Let (G, P 1 , bP 1 , sbP 1 , (s+ µ)P 1 ) be a DDH1 instance given to B. The task here is to decide whether µ = 0 or µ U ←-Z p . B simulates different phases of the game for A as follows.

Setup: The group description is same as G of the instance. Pick

p 2 U ←-G × 2 , u 1 , u 2 U ←-Z n p , α 1 , α 2 , w 1 , w 2 U ←-Z n
p and generate the public parameters as: uP 1 = u 1 P 1 + u 2 (bP 1 ), wP 1 = w 1 P 1 + w 2 (bP 1 ), g T = e(P 1 , P 2 ) α1 e(bP 1 , P 2 ) α2 , where bP 1 comes from the DDH1 instance. Key Generation: Keys are generated normally via the KeyGen algorithm. B does not know an encoding of b in G 2 and hence cannot create a semi-functional key and trivially win the game. Challenge: A sends two messages m 0 , m 1 and attribute vector x to B. Pick

β U ←-{0, 1} and generate C = (C 0 , C 1 , C 2 , C 3 , ctag) as: ctag U ←-Z p , C 0 = m β • e(C 1 , P 2 ) α1 • e(C 2 , P 2 ) α2 , C 1 = (s + µ)P 1 , C 2 = sbP 1 , C 3 = ( x, u 1 + ctagw 1 )C 1 + ( x, u 2 + ctagw 2 )C 2 ,
where sbP 1 comes from the DDH1 instance. C is distributed normally if µ = 0 and as a ciphertext in G 2 in case µ

U ←-Z p . This is because C 1 is uniformly distributed in group G 1 if µ U ←-Z p .
A returns a bit β as its guess of β to B. If A wins (i.e., β = β ) B returns 1 and otherwise it returns 0. We have,

| Pr[X 1 ] -Pr[X 2 ]| = | Pr[β = β in G 1 ] -Pr[β = β in G 2 ]| = | Pr[β = β |µ = 0] -Pr[β = β |µ U ←-Z p ]| = | Pr[B returns 1|µ = 0] -Pr[B returns 1|µ U ←-Z p ]| = Adv DDH1 G (A ) ≤ ε DDH1
Proof (of Lemma 2). If the attacker can distinguish between the two games G 3,k-1 and G 3,k , then we show how to build an algorithm B that solves the DDH2 problem. Let (G, P 2 , rP 2 , w 1 P 2 , (rw 1 γ)P 2 ) be an instance of DDH2 provided to B whose task is to determine whether γ = 0 or γ U ←-Z p . The different phases of the game are simulated as follows.

Setup: Choose P 1 U ←-G × 1 , v 1 , v 2 U ←-Z n p and implicitly set u 1 = v 1 + w 1 v 2 .
Observe that no encoding of u 1 is available in G 1 . Nevertheless, the public parameters can be generated without using u 1 or w 1 , as described in G 3,0 . Key Generation: Denote by y 1 , . . . , y q the vectors queried by A . Normal keys can be generated as in G 3,0 . Note that B knows w 1 P 2 and hence can compute u 1 P 2 which is required for generating components of a normal key. For j = 1, . . . , q, key SK yj is generated as follows.

Case j < k: Use SFKeyGen to generate SK yj . This is possible since b is known to B.

Case j = k: Create the key SK y k = (K 1 , K 2 , K 3 , (K 4,i , K 5,i , ktag i ) n i=2 ) as fol- lows. Let y k = (y 1 , . . . , y n ). For i = 2, . . . , n, set ktag i = (y i /y 1 )v 2,1 -v 2,i ; pick r U ←-Z p , K 1 = rP 2 , K 2 = α 1 P 2 + (rw 1 + γ)P 2 , K 3 = b -1 ((α -α 1 )P 2 + wrP 2 -(rw 1 + γ)P 2 ), for i = 2, . . . , n, K 4,i = -yi y1 v 1,1 + v 1,i rP 2 , K 5,i = b -1 -yi y1 u 1 + u i P 2 -K 4,i .
Case j > k: B computes a normal key according to the KeyGen algorithm.

The following calculation shows that K 4,i is well-formed.

K 4,i = - y i y 1 u 1,1 + u 1,i + ktag i w 1 rP 2 = - y i y 1 (v 1,1 + w 1 v 2,1 ) + (v 1,i + w 1 v 2,i ) + y i y 1 v 2,1 -v 2,i w 1 rP 2 = - y i y 1 v 1,1 + v 1,i rP 2
Also, for a vector x that is orthogonal to y k , we have

ktag = n i=2 x i ktag i = n i=2 x i ((y i /y 1 )v 2,1 -v 2,i ) = (v 2,1 /y 1 ) n i=2 x i y i - n i=2 x i v 2,i = (v 2,1 /y 1 )( x, y -x 1 y 1 ) -( v 2 , x -v 2,1 x 1 ) = -v 2 , x .
Challenge Phase: A provides two messages m 0 , m 1 and a challenge vector

x = ( x 1 , . . . , x n ). B picks β U ←-{0, 1} and generates the challenge ciphertext C = (C 0 , C 1 , C 2 , C 3 , as follows. s, µ U ←-Z p , ctag = -v 2 , x C 0 = m β • e(P 1 , P 2 ) sα • e(P 1 , P 2 ) µα1 , C 1 = sP 1 + µP 1 , C 2 = sbP 1 , C 3 = s( u, x + ctag • w)P 1 + µ( v 1 , x )P 2 .
The semi-functional component of C 3 is given by

µ( u 1 , x + ctag • w 1 )P 2 = µ( v 1 + w 1 v 2 , x -ctag • w 1 )P 2 = µ( v 1 , x + w 1 v 2 , x -v 2 , x w 1 )P 2 = µ( v 1 , x )P 2 ,
and hence C 3 has the correct distribution. Another point to note is the following -B does not know an encoding of w 1 in G 1 . In order to generate a semifuntional ciphertext for a vector x. the only choice for ctag is -v 2 , x . This helps in cancelling out the w 1 P 1 component with the w 1 -portion of the hash created using

u 1 = v 1 + w 1 v 2 . If γ = 0, k-th key is distributed as in G 3,k-1 ; otherwise γ U ←-Z p
and SK y k is distributed as a semi-functional key. Furthermore, if B tries to create a ciphertext for a vector x that is orthogonal to y k , it can only do so by setting ctag = -v 2 , x = ktag. In this case decryption would fail unconditionally and provide no information to B about the key for y k . What remains is to show that all the information provided to A are properly distributed. The public parameters are distributed as in the real scheme. Randomisers for the keys and ciphertexts including their semi-functional components have the correct distribution. We only need to show that all the n tags -ctag of the challenge ciphertext and ktag 2 , . . . , ktag n for the k-th secret key -generated using v 2 , are randomly distributed in Z p . The tags are defined in the reduction as follows.

     ctag ktag 2 . . . ktag n      =        -x 1 -x 2 -x 3 • • • -x n y 2 /y 1 -1 0 • • • 0 y 3 /y 1 0 -1 • • • 0 . . . . . . . . . . . . . . . y n /y 1 0 0 • • • -1             v 2,1 v 2,2 . . . v 2,n     
All information provided to the adversary, including public parameters are computed independent of v 2 . Since v 2 is chosen uniformly from Z n p , the tags are uniformly distributed in the adversary's view if the determinant of the matrix above is non-zero. It is easy to observe that determinant is (-1) n x, y k /y 1 which is non-zero because all of A 's queries are such that x, y k = 0. Therefore, the simulation is perfect.

B Proof of Theorem 2

We first describe the semi-functional ciphertext and key generation algorithms required for the proof.

IPE 2 .SFEncrypt(PP, MSK, m, x): Generate (C = (C 0 , C 1 , C 2 , (C 3,i , ctag i ) n i=2 )) R ←-IPE 2 .
Encrypt(PP, m, x). Choose µ U ←-Z p and generate the semi-functional ciphertext components as follows.

0 ←-C 0 • e(P 1 , P 2 ) µα1 , C 1 ←-C 1 + µP 1 , C 3,i ←-C 3,i + µ -xi x1 u 1,1 + u 1,i + ctag i w 1 P 1 for i = 2, . . . , n. Return C = (C 0 , C 1 , C 2 , C 3 , (C 3,i , ctag i ) n i=2
)) as the resulting semi-functional ciphertext. IPE 2 .SFKeyGen(PP, MSK, y): Let SK y = (K 1 , K 2 , K 3 , K 4 , K 5 ) be obtained by running IPE 2 .KeyGen(MSK, y). Pick γ, π U ←-Z p and modify the components of SK y as follows:

K 2 ←-K 2 + γπP 2 , K 3 ←-K 3 -γπ b P 2 , K 4 ←-K 4 + γP 2 , K 5 ←-K 5 -γ b P 2 .
The semi-functional key given by SK y = (K 1 , K 2 , K 3 , K 4 , K 5 ) is returned as output.

When a semi-functional ciphertext is decrypted with a semi-functional key, the message is blinded by a factor e(P 1 , P 2 ) µγ(π+ctag) as a result of pairing C 1 with K 2 + ctagK 4 , the rest of the semi-functional terms being canceled. If the relation π = -ctag holds, then decryption succeeds. In this case, we call the ciphertext and key nominally semi-functional.

The proof is a hybrid argument over a sequence of q + 6 games G 0 , G 1 , G 2 , G 3,0 , . . . , G 3,q , G 4 , G 5 where G 0 is the real ind-wah-cpa attack game defined in Section 2.3. Let X denote the event that the adversary A wins (i.e., β = β ) in G . The rest of the games are described below.

Game G 1 : Defined similar to G 0 except for a modification to the Encrypt algorithm. Elements from the master secret key MSK are used instead of the public parameters to generate the challenge ciphertext.

( ctag i ) n i=2 , s U ←-Z p , C 1 = sP 1 , C 2 = sbP 1 , C 0 = m β • (C 1 , P 2 ) α1 e(C 2 , P 2 ) α2 , for i = 2, . . . , n, C 3,i = - x β,i x β,1 u 1,1 + u 1,i + ctag i w 1 C 1 + - x β,i x β,1 u 2,1 + u 2,i + ctag i w 2 C 2 .
It is not hard to see that C 0 and C 3 are well-formed. The change we have made is only conceptual and hence G 1 is identical to G 0 . We have

Pr[X 0 ] = Pr[X 1 ]. (5) Game G 2 : The challenge ciphertext generation in G 1 is changed to generate C 1 as C 1 U ←-G 1 .
We can show that an adversary capable of detecting this change can be used to solve DDH1. In other words, we have the following lemma.

Lemma 3. | Pr[X ] -Pr[X 2 ]| ≤ ε DDH1 .
It is a rather straightforward reduction wherein we embed the DDH1 challenge in C 1 . The proof is similar to that of Lemma 1 and hence we skip it.

Game G 3,0 : We arrive at G 3,0 by modifying the setup, key generation and encryption procedures in G 2 as follows.

Setup: The public parameters are generated as follows. Choose P

1 U ←-G × 1 , P 2 U ←-G × 2 , α, α 1 , w, w 1 U ←-Z p , b U ←-Z × p , u, v 1 , v 2 U ←-Z n p and compute u 1 = v 1 +w 1 v 2 ,
g T = e(P 1 , P 2 ) α . The algorithm implicitly sets u 2 = b -1 (uu 1 ), w 2 = b -1 (w -w 1 ) and α 2 = b -1 (α -α 1 ). The parameters are given by PP = (P 1 , bP 1 , uP 1 , wP 1 , g T ). Key Generation: On input a vector y, the KeyGen algorithm is modified to create the components of SK y as shown below.

r U ←-Z p , K 1 = rP 2 , K 2 = (α 1 + r y, v 1 ) P 2 + y, v 2 K 4 , K 3 = b -1 ((α + r y, u )P 2 -K 2 ) K 4 = rw 1 P 2 , K 5 = b -1 (rwP 2 -K 4 ).
Encryption: The Encrypt algorithm is modified to use public parameters instead of elements from the master secret (as in the construction). The challenge ciphertext is generated by a call to the SFEncrypt algorithm. Essentially, the components of C are generated as follows.

( ctag i ) n i=2 , s, µ U ←-Z p , C 0 = m β • (g T ) s e(P 1 , P 2 ) µα1 , C 1 = sP 1 + µP 1 , C 2 = sbP 1 , for i = 2, . . . , n, C 3,i = s - x β,i x β,1 u 1 + u i + ctag i w P 1 + µ - x β,i x β,1 u 1,1 + u 1,i + ctag i w 1 P 1 .
The modifications are purely conceptual and so game G 3,0 is identical to G 2 . We have Pr

[X 2 ] = Pr[X 3,0 ]. ( 6
)
Game G 3,k (for k = 1, . . . , q): Let y 1 , . . . , y q be the vectors queried by A . This game is identical to G 3,k-1 except for the following two modifications. The (k -1)-st key is generated according to the SFKeyGen algorithm and SK y k for the k-th vector y k is generated differently -component K 2 of SK y k is now chosen uniformly at random from G 2 . The first change is purely conceptual and hence does not affect the adversary's behaviour in any way. We show that if the adversary can detect the second modification, then the DDH2 problem can be solved. We have the following lemma.

Lemma 4. | Pr[X 3,k-1 ] -Pr[X 3,k ]| ≤ ε DDH2 for all k ∈ [1, q].
G 4 : Proceeds identical to G 3,q but for one difference -the secret key corresponding to y q is computed using the SFKeyGen algorithm. Since this is only a conceptual change, we have

Pr[X 3,q ] = Pr[X 4 ]. (7)
Game G 5 : We arrive at this game from G by modifying the setup and semifunctional key generation algorithms.

Setup: The public parameters are generated as follows. Choose P

1 U ←-G × 1 , P 2 U ←-G × 2 , α, α 1 , w, w 1 U ←-Z p , b U ←-Z × p , u, u 1 U ←-Z n
p and compute g T = e(P 1 , P 2 ) α . The algorithm implicitly sets u 2 = b -1 (u-u 1 ), w 2 = b -1 (w-w 1 ) and α 2 = b -1 (α -α 1 ) and outputs PP = (P 1 , bP 1 , uP 1 , wP 1 , g T ). Key Generation: Let y be the input to SFKeyGen.

r, π , γ U ←-Z p , K 1 = rP 2 , K 2 = π P 2 , K 3 = b -1 ((α + r y, u )P 2 -K 2 ), K 4 = γ P 2 , K 5 = b -1 ((α + rw)P 2 -K 4 )
The rest of the secret key components are generated as in G 3,0 .

The reduction implicitly sets γ = α 1 + r y, u 1 P 2 + πγ, thus fixing π. The rest of the components are consistent with K 2 . If γ = 0, π is uniformly distributed in Z p by the choice of γ . Note that even if γ = 0, π can take any value from Z p uniformly at random. Hence the keys are correctly distributed.

Since the change is only conceptual, we have,

| Pr[X 4 ] -Pr[X 5 ]| ≤ (1/p). (8)
Now consider the challenge ciphertext. All keys are computed independent of α 1 , u 1 , w 1 and so are the public parameters. As a result, in the adversary's view, e(P 1 , P 2 ) µα1 is randomly distributed in G T as long as µ = 0 which happens with probability at most 1/p. The semi-functional components of C 3,i , i ∈ [2, n] are determined by the following matrix-vector product.

     x β,2 / x β,1 1 0 • • • 0 x β,3 / x β,1 0 1 • • • 0 . . . . . . . . . . . . . . . x β,n / x β,1 0 0 • • • 1           u 1,1 u 1,2 . . . u 1,n      .
The rank of the matrix is n -1 and hence the semi-functional components are uniformly distributed in the adversary's view (given that u 1 U ←-Z n p and µ = 0). Based on the discussion above we can say that in game G 5 , all components involving the message m β and the attribute vector xx β are randomly distributed. Hence the bit β is information theoretically hidden from the adversary. The probability that A wins in G 5 is exactly 1/2. Therefore, from Lemmas 3, 4 and equations ( 5), ( 6), ( 7) and (8), we have

ε = Pr[X 0 ] - 1 2 = | Pr[X 0 ] -Pr[X 5 ]| ≤ | Pr[X 0 ] -Pr[X 1 ]| + | Pr[X 1 ] Pr[X 2 ]| + | Pr[X 2 ] -Pr[X 3 , 0]| + q k=1 | Pr[X 3,k-1 ] -Pr[X 3,k ]| + | Pr[X 3,q ] -Pr[X 4 ]| + | Pr[X 4 ] -Pr[X 5 ]| ≤ ε DDH1 + q • ε DDH2 + (1/p)
Proof (of Lemma 4). If the attacker can distinguish between the two games G 3,k-1 and G 3,k , then we show how to build an algorithm B that solves the DDH2 problem. Let (G, P 2 , rP 2 , w 1 P 2 , (rw 1 + γ)P 2 ) be an instance of DDH2 provided to B whose task is to determine whether γ = 0 or γ U ←-Z p . The different phases of the game are simulated as follows.

Setup: Choose P 1 U ←-G × 1 , α, α 1 , w, w 1 U ←-Z p , b U ←-Z × p , u, v 1 , v 2 U ←-Z n p and compute u 1 P 2 = v 1 P 2 + v 2 (w 1 P 2 ), g T = e(P 1 , P 2 ) α . The algorithm implicitly sets u 2 = b -1 (u -u 1 ), w 2 = b -1 (w -w 1 ) and α 2 = b -1 (α -α 1 )
. The parameters are given by PP = (P 1 , bP 1 , uP 1 , wP 1 , g T ). Note that PP can be generated without the knowledge of u 1 or w 1 . Key Generation: Denote by y 1 , . . . , y q the vectors queried by A . Normal keys can be generated as in G 3,0 . For j = 1, . . . , q, key SK yj is generated as follows.

Case j < k: Use SFKeyGen to generate SK yj . This is possible since b is known to B. Case j = k: Create the key SK y

k = (K 1 , K 2 , K 3 , K 4 , K 5 ) as follows. Let y k = (y 1 , . . . , y n ). Pick r U ←-Z p and set, K 1 = rP 2 , K 2 = (α 1 + r y, v 1 ) P 2 + y, v 2 K 4 , K 3 = b -1 ((α + r y, u )P 2 -K 2 ) K 4 = (rw 1 + γ)P 2 , K 5 = b -1 (rwP 2 -K 4 ).
Components of SK y k are generated exactly as in game G 3,0 except that the DDH2 challenge is embedded in K 4 . Case j > k: B computes a normal key according to the KeyGen algorithm.

Challenge Phase: A provides two messages m 0 , m 1 and two vectors x 0 = ( x 0,1 , . . . , x 0,n ),

x 1 = ( x 1,1 , . . . , x 1,n ). B picks β U ←-{0, 1} and generates the challenge ciphertext C = (C 0 , C 1 , C 2 , (C 3,i , ctag i ) n i=2 ) as follows. Pick s, µ U ←-Z p and set, ctag i = x β,i x β,1 v 2,1 -v 2,i , C 0 = m β • (g T ) s e(P 1 , P 2 ) µα1 , C 1 = sP 1 + µP 1 , C 2 = sbP 1 , for i = 2, . . . , n, C 3,i = s - x β,i x β,1 u 1 + u + ctag i w P 1 + µ - x β,i x β,1 v 1,1 + v 1,i P 1 .
The choice of tags above enables us to create the semi-functional component without the knowledge of w 1 . Essentially we cancel out the v 2 component of hash (computed using u 1 = v 1 + w 1 v 2 ) by choosing the corresponding tag for w 1 -component appropriately. We stress that this is the only way to create a semi-functional ciphertext.

If γ = 0, k-th key is distributed as in G 3,k-1 ; otherwise γ U ←-Z p and SK y k is distributed as a semi-functional key with randomiser γ coming from the DDH2 challenge and π = x, v 2 . Now, suppose that B tries to create a ciphertext for a vector x that is orthogonal to y k , it can only do so by setting

ctag i = xi x1 v 2,1 -v 2,i . This implies that ctag = n i=2 y i ctag i = n i=2 y i ((x i /x 1 )v 2,1 -v 2,i ) = (v 2,1 /x 1 ) n i=2 x i y i - n i=2 y i v 2,i = (v 2,1 /x 1 )( x, y -x 1 y 1 ) -( v 2 , y -v 2,1 y 1 ) = -v 2 , y ,
which is equal to -π, which is precisely the requirement for the ciphertext and key to be nominally semi-functional. Decryption succeeds and B obtains no information about whether or not SK y k is semi-functional.

We now show that the view of the adversary is perfectly simulated by B. The public parameters are distributed as in the real scheme. Randomisers for the keys and ciphertexts including their semi-functional components have the correct distribution. We only need to show that all the n -1 tags, ( ctag i ) n i=2 of the challenge ciphertext and π for the k-th secret key -generated using v 2 , are randomly distributed in Z p .

     π ctag 2 . . . ctag n      =        y 1 y 2 y 3 • • • y n x β,2 / x β,1 -1 0 • • • 0 x β,3 / x β,1 0 -1 • • • 0 . . . . . . . . . . . . . . . x β,n / x β,1 0 0 • • • -1             v 2,1 v 2,2 . . . v 2,n     
From the above equation, one can say that the tags and π have uniform and independent distributions over Z p in A 's view iff -v 2 is information theoretically hidden in A 's view and uniformly distributed in Z n p , the matrix is invertible.

The first condition is naturally satisfied as no encodings of v 2 in either G 1 or G 2 are revealed in the public parameters. The second condition also holds since determinant of the matrix is (-1) n x, y k / x β,1 which is clearly non-zero due to the restriction on A 's queries requiring x, y k = 0. Therefore, the simulation is perfect.

C Application to Identity-Based Broadcast Encryption

We explain how to derive an identity-based encryption scheme (IBBE) that has sub-linear sized ciphertexts and keys. In an IBBE scheme, each user is associated with an identity id ∈ I (I denotes the domain of identities). There is a central authority called the private key generator (PKG) that generates and distributes keys for all users securely. The secret key corresponding to a user with identity id is denoted SK id . A sender can broadcast an encrypted message (as in IPE, the parameters of the PKG are used for encryption) to all users of the system. The message however is only intended for a subset S = {id 1 , . . . , id } of users that we refer to as privileged. Naturally, this requires the ciphertext to be constructed in a manner that allows only a legitimate/privileged user to decrypt. In other words, only a user with identity id with id ∈ S can decrypt the ciphertext using SK id .

An IBBE can be expressed as a special case of inner product encryption. We only provide the top-level idea and skip the details. As our constructions are based on bilinear groups of prime order p, let the domain of attributes and identities to be Z p . We now show that an IPE scheme supporting inner products over Z n+1 p can be specialised to an IBBE scheme where the number of intended recipients of a broadcast is upper bounded by n. Consider a particular set S = {id 1 , . . . , id } with ≤ n. Define the polynomial p S (z) = i=1 (z -id i ) ∈ Z p [z] and compute x = (x 0 , . . . , x n ), the vector of coefficients of 1, z, z 2 , . . . , z n in p S (z). Since the degree of the polynomial is , x j = 0 for all j > . The ciphertext is encrypted to the attribute vector x as in the Encrypt alrogithm of the IPE. The secret key for an identity id is constructed as follows: let y = (1, id, id 2 , . . . , id n ); create a key for the vector y using the IPE KeyGen algorithm. If id ∈ S, then clearly id is a root of p S (z) and hence y, x = x 0 + idx 1 + id 2 x 2 + • • • + id n x n = 0. The converse also holds.

Following the method outlined above, we can derive a constant-size ciphertext IBBE from IPE 1 with ciphertext size being 3|G 1 | + |Z p | + |G T | (recall that |G| is the size of representation of an element from G). Size of a key would be (2n + 3)|G 2 | + n|Z p |. Similarly, the scheme IPE 2 leads to an IBBE with constantsize keys (of size 5|G 2 |) and ciphertext of size (n + 2)|G 1 | + n|Z p | + |G T |. In addition this scheme is anonymous i.e., decryption can be performed without knowing the set for which the ciphertext was encrypted to. Furthermore, unlike many anonymous broadcast encryption schemes, decryption time is constant (independent of and n).

In the IBBE obtained from IPE 1 , the linear dependence of key size on n is rather impractical in certain scenarios, for instance, when the user keys are actually stored in smartcards. On the other hand, ciphertext size also contributes the communication overhead and longer ciphertexts consume larger bandwidth. So, IPE 2 ciphertexts indeed eat up larger bandwidth. Also, these ciphertexts grow linearly in n, unlike the construction in [START_REF] Somindu | Efficient adaptively secure IBBE from standard assumptions[END_REF] where the ciphertext size varies with (≤ n). In order to strike a balance between the two, we propose simple scheme built upon IPE 1 that achieves a reasonable trade-off. Note that we no longer aim for ciphertext anonymity. A high-level overview of this construction is provided below.

As earlier, let n denote the maximum number of privileged recipients of a broadcast and assume for simplicity that n = n 1 n 2 . Setup IPE 1 for inner products over Z n1+1 p . The encryption algorithm partitions the input set S = {id 1 , . . . , id } into 2 (≤ n 2 ) subsets S 1 , . . . , S 2 with

|S 1 | = |S 2 | = • • • = |S 2-1 | = n 1 and |S 2 | = 1 (≤ n 1
). Then perform separate IPE 2 -encryptions of the message for each of the sets. Secret keys are generated as in IPE 2 . Let p Si (z) denote the polynomial corresponding to set S i (for i ∈ [1, 2 ]) and x i the corresponding coefficient vector. Let y denote the vector associated to the secret key for id. Now, any id ∈ S is present exactly in one of the subsets, say S j implying that x j , y = 0 and x i , y = 0 for i ∈ [1, 2 ]\{j}. The decryption algorithm can simply choose the subset to which id belongs and decrypt the IPE 2 -ciphertext corresponding to that set. On evaluating the efficiency of this scheme, we find that ciphertexts are of size 2 (3|G 1 | + |Z p | + |G T |) and the key size is (2n 1 + 3)|G 1 | + n 1 |Z p |. This provides a nice trade-off among the public parameters, ciphertext and key sizes.

Choosing n 1 and n 2 to be about sqrtn, we obtain an IBBE scheme with public parameters, ciphertexts and keys, all with O( √ n)-size, which is sublinear in n.

Acknowledgements

I would like to thank Benoit Libert and Palash Sarkar for helpful discussions as well as the reviewers of ACNS'16 for their valuable comments. This research was funded by the "Programme Avenir Lyon Saint-Etienne de l'Universite de Lyon" in the framework of the programme "Investissements d'Avenir" (ANR-11-IDEX-0007).