Functional Encryption for Inner Product: Achieving Constant-Size Ciphertexts with Adaptive Security or Support for Negation

From Bauman National Library
This page was last modified on 5 December 2015, at 07:38.
Functional Encryption for Inner Product: Achieving Constant-Size Ciphertexts with Adaptive Security or Support for Negation
Functional Encryption for Inner Product.png
Authors Nuttapong Attrapadung[@: 1],
Benoît Libert[@: 2]
Published 2010 г.
Web site Homepage of The International Association for Cryptologic Research
Download Original article

Abstract. In functional encryption (FE) schemes, ciphertexts and private keys are associated with attributes and decryption is possible whenever key and ciphertext attributes are suitably related. It is known that expressive realizations can be obtained from a simple FE favor called inner product encryption (IPE), where decryption is allowed whenever ciphertext and key attributes form orthogonal vectors. In this paper, we construct (non-anonymous) IPE systems with constant-size ciphertexts for the zero and non-zero evaluations of inner products. These schemes respectively imply an adaptively secure identity-based broadcast encryption scheme and an identity-based revocation mechanism that both feature short ciphertexts and rely on simple assumptions in prime order groups. We also introduce the notion of negated spatial encryption, which subsumes non-zero-mode IPE and can be seen as the revocation analogue of the spatial encryption primitive of Boneh and Hamburg.

Keywords. Functional encryption, identity-based broadcast encryption, revocation, efficiency.


Ordinary encryption schemes usually provide coarse-grained access control since, given a ciphertext, only the holder of the private key can obtain the plaintext. In many applications such as distributed file systems, the need for fine-grained and more complex access control policies frequently arises. To address these concerns, several kinds of functional public key encryption schemes have been studied.

Functional encryption can be seen as a generalization of identity-based encryption (IBE) [1], [2]. In IBE schemes, the receiver's ability to decrypt is merely contingent on his knowledge of a private key associated with an identity that matches a string chosen by the sender. In contrast, functional encryption (FE) systems make it possible to decrypt using a private key corresponding to a set of atomic elements, called attributes, that is suitably related — according to some well-defined relation — to another attribute set specified by the sender.

The goal of this paper is to describe new (pairing-based) functional encryption constructions providing short ciphertexts (ideally, their length should not depend on the size of attribute sets) while providing security against adaptive adversaries or supporting negation (e.g. decryption should be disallowed to holders of private keys for which ).

Related Work. The first flavor of functional encryption traces back to the work of Sahai and Waters [3] that was subsequently extended in [4], [5]. Their concept, called attribute-based encryption (ABE), allows a sender to encrypt data under a set of attributes ω while an authority generates private keys for access control policies . Decryption rights are granted to anyone holding a private key for a policy such that . Identity-based broadcast encryption (IBBE) [6], [7], [8], [9] and revocation (IBR) [10] schemes can also be thought of as functional encryption systems where ciphertexts are encrypted for a set of identities : in IBBE (resp. IBR) systems, decryption requires to hold a private key for which (resp. ).

The above kinds of functional encryption systems are only payload hiding in that they keep encrypted messages back from unauthorized parties but ciphertexts do not hide their underlying attribute set. Predicate encryption schemes [11], [12], [13], [14] additionally provide anonymity as ciphertexts also conceal the attribute set they are associated with, which enables [15], [16] efficient searches over encrypted data. In [12], Katz, Sahai and Waters devised a predicate encryption scheme for inner products: a ciphertext encrypted for the attribute vector can be opened by any key such that . As shown in [12], inner product encryption (IPE) suffices to give functional encryption for a number of relations corresponding to the evaluation of polynomials or CNF/DNF formulae.

Our Contributions. While quite useful, the IPE scheme of [12] strives to anonymize ciphertexts, which makes it difficult to break through the linear complexity barrier (in the vector length n in terms of ciphertext size. It indeed seems very hard to avoid such a dependency as long as anonymity is required: for instance, anonymous FE constructions [11], [17] suffer from the same overhead. A similar problem appears in the context of broadcast encryption, where the only known scheme [18] that conceals the receiver set also has -size ciphertexts.

This paper focuses on applications of IPE schemes, such as identity-based broadcast encryption and revocation systems, where the anonymity property is not fundamental. Assuming public ciphertext attributes rather than anonymity may be useful in other contexts. For instance, suppose that a number of ciphertexts are stored with varying attributes on a server and we want to decrypt only those for which . Anonymous ciphertexts require to decrypt all of them whereas public attributes make it possible to test whether (which is usually faster than decrypting) and only decrypt appropriate ones.

At the expense of sacrificing anonymity, we thus describe IPE schemes where the ciphertext overhead reduces to as long as the description of the ciphertext attribute vector is not considered as being part of the ciphertext, which is a common assumption in the broadcast encryption/revocation applications. In addition, the number of pairing evaluations to decrypt is also constant, which significantly improves upon , since pairings calculations still remain costly.

Our first IPE system achieves adaptive security, as opposed to the selective model, used in [12], where the adversary has to choose the target ciphertext vector upfront. To acquire adaptive security, we basically utilize the method used in the Waters' fully secure IBE [19], albeit we also have to introduce a new trick called "n-equation technique" so as to deal with the richer structure of IPE. Our system directly yields the first adaptively secure identity-based broadcast encryption scheme with constant-size ciphertexts in the standard model. Previous IBBE with -size ciphertexts were either only selective-ID secure [6], [8][9], [7] or in the random oracle model [20]. Among IBBE systems featuring compact ciphertexts (including selective-ID secure ones), ours is also the first one relying on simple assumptions (i.e., no q-type assumption) in prime order groups.

It is worth mentioning that techniques developed by Lewko and Waters [21] can be applied to the construction of Boneh and Hamburg [9] to give fully secure IBBE with short ciphertexts in composite order groups. However, it was not previously known how to obtain such a scheme in prime order groups (at least without relying on the absence of computable isomorphism in asymmetric pairing configurations). Indeed, despite recent progress [22], there is still no black-box way to translate pairing-based cryptosystems from composite to prime order groups. In particular, Freeman's framework [22] does not apply to [21].

Our second contribution is an IPE system for non-zero inner products: ciphertexts encrypted for vector can only be decrypted using if which — without retaining anonymity — solves a question left open by Katz, Sahai and Waters [12][Section 5.4]. The scheme implies the first identity-based revocation (IBR) mechanism [10] with -size ciphertexts. Like the schemes of Lewko, Sahai and Waters [10], its security is analyzed in a non-adaptive model where the adversary has to choose which users to corrupt at the outset of the game [not.: 1]. In comparison with [10] where ciphertexts grow linearly with the number of revoked users and public/private keys have constant size, our basic IBR construction performs in the dual way since key sizes depend on the maximal number of revoked users. Depending on the application, one may prefer one scheme over the other one. We actually show how to generalize both implementations and obtain a tradeoff between ciphertext and key sizes (and without assuming a maximal number of revoked users): the second scheme of [10] and ours can be seen as lying at opposite extremities of the spectrum.

On a theoretical side, our non-zero IPE realization turns out to be a particular case of a more general primitive, that we call negated spatial encryption, which we define as a negated mode for the spatial encryption primitive of Boneh and Hamburg [9]. Namely, keys correspond to subspaces and can decrypt ciphertexts encrypted under points that lie outside the subspace. This generalized primitive turns out to be non-trivial to implement and we had to use a fully generalized form of our new "n-equation" technique. The proposed scheme is proven secure under a non-standard assumption defined in [10].

Our Techniques. The core technique of our non-zero IPE scheme will be used throughout the paper, including in our adaptively secure zero IPE scheme. This can be viewed analogously to fact that Waters' fully secure IBE [19] uses the revocation technique of [10]. Our non-zero IPE also builds on [10]. However, the fact that non-zero IPE has much richer structure than revocation scheme and the pursued goal of achieving constant ciphertext size together prevent us from using their techniques directly. To describe the difficulties that arise, we first outline the Lewko-Sahai-Waters revocation scheme in its simplified form where security proof is not provided and where only one user is revoked.

Construction 1. (A simplified revocation scheme)
Setup: lets be bilinear groups of prime order and picks . The public key is . The master key is .
KeyGen: chooses and outputs a private key for an identity as .
Encrypt: encrypts M and specifies a revoked by choosing and computing .
Decrypt: decryption computes if . It then computes as .

The scheme can be explained by viewing a key and a ciphertext as forming alinear system of 2 equations in the exponent of with variables .


Computing amounts to solve the system, which is possible when (and thus , as required). In particular, decryption computes a linear combination (in the exponent) with coefficients from the first row of which is . In [10], this is called "2-equation technique". The scheme is extended to n-dimension, i.e., the revocation of n users , by utilizing n local independent systems of two equations

for ,

that yield 2n ciphertext components , each one of which corresponds to a share of such that . The decryption at j-th system returns if . Combining these results finally gives .

We aim at constant-size ciphertexts for non-zero IPE schemes of dimension n. When trying to use the 2-equation technique with n dimensions, the following difficulties arise. First, the "decryptability" condition cannot be decomposed as simply as that of the revocation scheme, which is decomposable as the conjunction of for . Second, the ciphertext size was .

Towards solving these, we introduce a technique called “n-equation technique”. First, we utilize n secret exponents and let function as the “master” exponent while serve as the “perturbed” factors. Intuitively, we will set up a system of n linear equations of the form:


where and are elements of G defined for a key for and a ciphertext for respectively. At first, this generalized system seems to require linear-size ciphertexts . A trick to resolve this is to reuse ciphertext elements throughout the system: we let for . This effectively yields a constraint , where is a matrix parameterized only by and is a matrix. The remaining problem is then to choose in such a way that the system has a solution if (the decryptability condition). To this end, we define


where it holds that det. By translating this conceptual view back into algorithms, we obtain a basic non-zero IPE scheme. From this, we propose two schemes for non-zero IPE: the first one is a special case of negated spatial encryption scheme in section 5.1, while the second one is proven secure under simple assumptions and given in section 5.2.

Organization. In the forthcoming sections, the syntax and the applications of functional encryption are explained in sections 2 and 3. We describe our zero mode IPE system in section 4. Our negated schemes are detailed in section 5.


Syntax and Security Definition for Functional Encryption

Let be a boolean function where and denote "key attribute" and "ciphertext attribute" spaces. A functional encryption (FE) scheme for R consists of the following algorithms.

  • takes as input a security parameter and a scheme description des (which usually describes the dimension n), and outputs a master public key pk and a master secret key msk.
  • takes as input a key attribute and the master key msk. It outputs a private decryption key .
  • takes as input a ciphertext attribute , a message , and public key pk. It outputs a ciphertext C.
  • given a ciphertext C with its attribute y and the decryption key with its attribute , it outputs a message M or .

We require the standard correctness of decryption, that is, for all , all , all , all , and all ,

  • If , then .
  • If R(x,y) = 0, Decrypt(Encrypt(y,M,pk),sk_x)= \bot </math> with probality nearly 1.

Terminology and Variants. We refer to any encryption primitive A that can be casted as a functional encryption by specifying its corresponding function For a FE primitive A, we can define two variants:

  • Dual Variant, denoted by Dual(A), is defined by setting and

and . In a dual variant, the roles of key and ciphertext attributes are swapped from those of its original primitive.

  • Negated Variant, denoted by , is defined by using the same domains as A and setting . The condition is thus the opposite of the original primitive.

Security Definition. A FE scheme for a function is fully secure if no PPT adversary has non-negligible advantage in this game.

Setup. The challenger runs Setup(n) and hands the public key pk to .

Query Phase 1. The challenger answers private key queries for by returning .

Challenge. submits messages and a target ciphertext attribute vector such that for all key attributes that have been queried so far. The challenger then flips a bit and computes the challenge ciphertext which is given to .

Query Phase 2. The adversary is allowed to make further private key queries under the same restriction as above, i.e., .

'Guess. The adversary outputs a guess and wins if . In the game, 's advantage is typically defined as .

(Co-)Selective Security. We also consider the notion of selective security [23][24], where has to choose the challenge attribute before the setup phase, but can adaptively choose the key queries for . One can consider its "dual" notion where must output the q key queries for attribute vectors before the setup phase, but can adaptively choose the target challenge attribute . We refer to this scenario as the co-selective security model, which is useful in some applications such as revocation. By definition, both notions are incomparable in general and we do not know about their relation yet.

We shall show how one FE primitive can be obtained from another. The following useful lemma from [9] describes a sufficient criterion for implication.

Proposition 1 (Embedding Lemma [9]).
Consider encryption primitives A,B that can be casted as functional encryption for functions , respectively. Suppose there exists efficient injective mappings and such that . Let be a construction for primitive B. We then construct for primitive A from by applying mappings to all key attributes and ciphertext attributes, respectively. More precisely, we use exactly the same setup algorithm and define key generation and encryption procedures as and , respectively. Then, if is secure, so is . This holds for adaptive, selective, co-selective security models.

We denote this primitive implication by .

We immediately obtain the next corollary stating that the implication applies to the negated (resp. dual) variant with the same (resp. swapped) mappings.

Corollary 1
implies and .

Complexity Assumptions in bilinear Groups

We consider groups of prime order p with an efficiently computable map such that for any and and whenever . In these groups, we assume the hardness of the Decision Bilinear Diffie-Hellman and Decision Linear [25] problems.

Definition 1: Decision Bilinear Diffie-Hellman Problem
The Decision Bilinear Diffie-Hellman Problem (DBDH) in is, given elements with , to decide whether or .

Definition 2: Decision Linear Problem
The Decision Linear Problem (DLIN) in consists in, given a tuple with and , deciding whether or .

Functional Encryption Instances and Their Implications

Inner Product Encryption and Its Consequences

We underline the power of IPE by showing its implications in this section. Each primitive is defined by describing the corresponding boolean function . We then show how to construct one primitive from another by explicitly describing attribute mappings. In this way, correctness and security are consequences of the embedding lemma. Basically, the approach follows exactly the same way as [12]. A new contribution is that we also consider the negated variant of primitives, which will be useful for non-zero polynomial evaluation and revocation schemes. The implication for negated variants follows from Corollary 1.

Inner Product. An inner product encryption (IPE) scheme over , for some prime p, is defined as follows. Both attribute domains are .

We consider two distinct IPE modes here. The first one is zero-mode IPE where . The other one is its negated primitive, which we call the non-zero-mode IPE, where .

Polynomial Evaluation. Functional encryption for the zero evaluation of polynomials of degree is defined as follows. The ciphertext and key attribute domains are defined as and , respectively. The relation is defined by . The non-zero evaluation mode can be defined as its negated primitive .

Given an IPE scheme over , one obtain a functional encryption system for polynomial evaluation via the following embedding. For the key attribute, we map the polynomial to . Regarding ciphertext attributes, each element is mapped onto a vector . Correctness and security hold since whenever . The non-zero evaluation case can be analogously derived from the non-zero-mode IPE using the same mappings, due to Corollary 1.

We can also consider other variants such as a scheme that supports multivariate polynomials and a dual variant, where the key attribute corresponds to a fixed point and the ciphertext attribute corresponds to a polynomial, as in [12].

OR, AND, DNF, CNF Formulae. We now consider a FE scheme for some boolean formulae that evaluate disjunctions, conjunctions, and their extensions to disjunctive or conjunctive normal forms. As an example, a functional encryption scheme for boolean formula can be defined by . This can be obtained from a functional encryption for the zero evaluation of a univariate polynomial of degree smaller than n by generating a private key for , and letting senders encrypting to .

Other fundamental cases can be considered similarly as in [12] and are shown below. In [12] only non-negated policies (the first three cases below and their extensions) were considered. Schemes supporting negated policies (the latter three cases below and their extensions) are introduced in this paper. The negated case can be implemented by IPE for non-zero evaluation. One can combine these cases to obtain DNF, CNF formulae. Below, is chosen by .[not.: 2]

ID-based Broadcast Encryption and Revocation. Let be an identity space. An ID-based broadcast encryption scheme (IBBE) for maximum n receivers per ciphertext is a functional encryption for defined by . An IBBE system can be constructed by a functional encryption for . To encrypt a message for the receiver set , one encrypts using the policy .

Likewise, identity-based revocation (IBR) [10] for at most n revocations per ciphertext can be casted as a negated IBBE, i.e., .

Spatial Encryption

We now recall the concept of spatial encryption [9]. For a matrix M of which elements are in and a vector , we define its corresponding affine space as . Let be the collection of all afiine spaces inside . That is,, where is the set of all matrices in .

The notion of spatial encryption was motivated by Boneh and Hamburg [9]. It has many applications as it notably implies broadcast HIBE and multi-authority schemes. Nevertheless, its connection to inner-product encryption has not been investigated so far. In section 4.1, we prove that spatial encryption implies inner product encryption by providing a simple attribute mapping.

As a result of independent interest, we also consider the negated spatial encryption primitive (namely, FE that is defined by and provide a construction in section 5.1. From this scheme and Corollary 1 together with our implication result of zero-mode IPE from spatial encryption, we then obtain a non-zero-mode IPE construction.

Functional Encryption for Zero Inner-Product

Warm-up: Selectively Secure Zero IPE from Spatial Encryption

We first show that spatial encryption implies zero IPE. For the key attribute, we map to an - dimension affline space with the matrix

For any , we then have . By the embedding lemma, we can therefore conclude its implication.

In [9], Boneh and Hamburg described a selectively secure construction of spatial encryption that achieves constant-size ciphertexts (by generalizing the Boneh-Boyen-Goh HIBE [26]). We thus immediately obtain a selectively secure zero IPE scheme with constant-size ciphertext as shown below.

We give some notations here. For a vector , we write to denote . Given , one can easily compute where denotes the inner product .

Construction 2. (Selectively secure zero IPE)
: chooses bilinear groups of prime order with a generator . It chooses .Let . The public key is . The master key is .
: chooses and parces and returns . It outputs the private key as where


: the encryption algorithm first picks . It parses and computes the ciphertext as


: to decrypt, the algorithm computes the message blinding factor as .

The selective security of this scheme is a consequence of a result given in [9].

Theorem 1
Construction 2 is selectively secure under the n-Decisional Bilinear Diffie-Hellman Exponent assumption (see [9] for a description of the latter).
Without proof

Adaptively Secure Zero IPE under Simple Assumptions

We extend the above selectively secure zero IPE to acquire adaptive security by applying the Waters' dual system method [19]. However, we have to use our "n-equation technique" as opposed to 2-equation technique used for IBE in [19]. The reason is that we have to deal with the difficulties arising from the richer structure of IPE and the aggregation of ciphertexts into a constant number of elements, analogously to what we described in section 1.

The scheme basically goes as follows. A ciphertext contains a random tag tagc in the element while each key contains tags ( for each element) that are aggregated into upon decryption of a ciphertext intended for . The receiver can decrypt if (and .

Construction 3.(Adaptively secure zero IPE)
: chooses bilinear groups of prime order . It then picks generators and chooses . Let and . The public key consist of

The master key is defined to be

: parces and returns . Otherwise, it picks , sets and generates by computing

: to encrypt , pick and compute where

: computes and then , as well as . It finally recovers the plaintext as .

The correctness of is shown in appendix A.1, while the rest follows from [19]. As we can see, ciphertexts have the same size as in the IBE scheme of [19], no matter how large the vector is. Also, decryption entails a constant number of pairing evaluations (whereas ciphertexts cost pairings to decrypt in [12]).

Theorem 2
Construction 3 is adaptively secure under the DLIN and DBDH assumptions.
The proof uses the dual system methodology similar to [19], which involves ciphertexts and private keys that can be normal or semi-functional.
Semi-functional ciphertexts are generated by first computing a normal ciphertext and then choosing before replacing , respectively, by

From a normal key , semi-functional keys are obtained by choosing and replacing by

The proof proceeds with a game sequence starting from , which is the actual attack game. The following games are defined below.

is the real attack game but the challenge ciphertext is semi-functional.

(for ) is identical to except that the first i private key generation queries are answered by returning a semi-functional key.

is as Game q but the challenge ciphertext is a semi-functional encryption of a random element of instead of the actual plaintext.

We prove the indistinguishability between two consecutive games under some assumptions. The sequence ends in , where the challenge ciphertext is independent of the challenger's bit , hence any adversary has no advantage.

The indistinguishability of and as well as that of and can be proved exactly in the same way as in [19] and the details are given in the full version of the paper.

Lemma 1
If DLIN is hard, is indistinguishable from .

Lemma 2
For any , if an adversary can distinguish from , we can build a distinguisher for the DLIN problem.

This lemma is the most non-trivial part in the theorem. The main issue is that, in order to enable adaptive security, the reduction must be done in such a way that the simulator can create semi-functional keys for any vector , including those for which . However, the crucial point is that we must prevent from directly deciding whether the queried private key is normal or semi-functional by generating a semi-functional ciphertext for itself. Indeed, if this were possible, the reduction from would not be established.

To resolve this, we use a secret exponent vector and embed the DLIN instance so that can simulate only the key at query for with tags and the challenge ciphertext for with that obey the relation: where is the matrix defined in Eq.(2). We thereby conceptually use the n-equation technique here. A particular consequence is that if we have then it holds that

which is the exact condition that hampers the decryption, thus cannot test by itself, as desired. We are now ready to describe the proof of Lemma 2.

Proof. The distinguisher receives and decides if .

Setup. Algorithm picks and sets

Next, chooses , then defines , and for . Note that, as in the proof of lemma 2 in [19] , knows .

Key Queries. When makes the private key query, does as follows.

[Case ] It generates a normal key, using the master secret key .

[Case ] It creates a semi-functional key, which it can do using .

[Case ] It defines as for ,

which implies that , for .

Using these tags, it generates a normal private key using random exponents . Then, it sets

as well as and for .

If is easily seen to form a normal key where are the underlying random exponents. If , it can be written for some , so that is distributed as a semi-functional key. We note that are independent and uniformly distributed since (which are the solutions of a system of equations with unknowns) are uniformly random and perfectly hidden from 's view.

Challenge. outputs along with a vector . flips a coin and computes the tag for which will be able to prepare the semi-functional ciphertext. To this end, first computes a normal encryption of using exponents . It then chooses and computes

We claim that is a semi-functional ciphertext with underlying exponents and . To prove this, we observe that

where the unknown term in is canceled out by . Also,

where the unknown vanishes due to our definition of . It then remains to show that are still -wise independent. But this holds since their relations form a system

which has a solution in whenever .

Eventually, outputs a bit and outputs 0 if . As in [19], we see that is playing if and otherwise.

Lemma 3
If DBDH is hard, and are indistinguishable.

Functional Encryption for Non-Zero Inner-Product

Negated Spatial Encryption

We begin this section by providing a co-selectively-secure construction of negated spatial encryption, which is motivated by its implication of non-zero IPE. At a high-level, our scheme can be viewed as a "negative" analogue of the Boneh-Hamburg spatial encryption [9], in very much the same way as the Lewko-Sahai-Waters revocation scheme [10] is a negative analogue of the Boneh-Boyen IBE [24]. The intuition follows exactly from section 1, where we have to use "n-equation technique". In spatial encryption, we have to deal with, in general, how we can set up a system of n equations similarly to Eq.(1). To this end, we confine the vector subspaces that we can use as follows. Our construction is a FE for , where we define a collection of vector subspaces in as , where we denote as the matrix obtained by deleting the first row .

Construction 4. (Co-selectively secure negated spatial encryption)
: chooses bilinear groups of prime order with a random generator . It randomly chooses Let . The public key is . The master key is .
: suppose that , from a matrix . The algorithm picks and outputs where


: picks and computes as


: the algorithm first obtains from . We also recall the the notation of , which is the vector of the first row of . It first solves the system of equations in from , which it can do since . It computes the message blinding factor as

Computability. We claim that the decryption can be computed if . Indeed, we prove that if then (and the above equation is well-defined). To prove the contrapositive, suppose that Then, we must have since .

Correctness. We verify that decryption is correct as follows. First, we note that due to our definition of , we have . Therefore, the correctness follows from the fact that

Theorem 3
Construction 4 is co-selectively secure under the q-Decisional Multi-Exponent Bilinear Diffie-Hellman assumption (q is the number of key queries). (The proof is given in the full paper where the assumption [10] is also recalled)
Without proof

Implications. For a vector , the embedding defined in Eq.(3) is easily seen to be in the limited domain since is an identity matrix of size and bence . Therefore, from Corollary 1, the above scheme implies non-zero IPE.

Non-Zero IPE under Simple Assumptions

We prove the co-selective security of our negated spatial encryption scheme under a non-standard q-type assumption introduced in [12]. Here, we show that the dual system technique [19] makes it possible to rest on simple assumptions such as DBDH and DLIN. The scheme is very similar to the zero IPE scheme of section 4.2 and we only state the differences. The intuition again follows exactly from section 1 and the security proof uses similar techniques as in [10].

Construction 5. (Co-selectively secure non-zero IPE)
: outputs pk exactly as in the construction 3 except that we define in this scheme, instead of .
: outputs where is the same as in the construction 3 (with and .
: outputs where is as in the construction 3 (with ) and
: computes as in the construction 3 and as . (See appendix A.2).

Theorem 4
Construction 5 is co-selectively secure under the DLIN and DBDH assumptions.
The proof is deferred to the full version of the paper.

A Generalization of the Scheme and Its Application

Extended Ciphertext Attribute Domain. The above scheme for the relation can be extended so as to support relations of the form , for some , and defined as .

We construct this extended system by setting up exactly the same public and private keys (for ) as in the original scheme. To encrypt to , the scheme generates as usual with the underlying exponents . Then, it chooses so that and for , parses and computes and , in such a way that the ciphertext is . Decryption requires to first compute

for from which the receiver obtains . The rest is then done as usual and we explain in the full version of the paper how the security proof must be adapted.

Applications. We can obtain an identity-based revocation scheme with parameter tradeoff from the aforementioned extension. The instantiation of ID-based revocation scheme from our non-zero inner-product system yields a construction with -size ciphertexts and -size private keys, where n denotes the maximal number of revoked users.

From our extended scheme we can obtain an ID-based revocation scheme , without a fixed maximal number of revoked users. To revoke the set where , we divide it into a disjointed union , where for all (we assume that divides ). We then simply construct the vector from the revocation subset for each , in the same way as we use to instantiate . We then finally encrypt using the set of vectors . The correctness and security properties hold since . The construction has -size ciphertexts and -size private keys. Interestingly, we note that the second scheme described by Lewko, Sahai and Waters [10] (which indeed inspires ours) can be viewed as a special case of our scheme where .

A Verifying Correctness in Decryption

A.1 For the Zero IPE Scheme of Section 4.2

A.2 For the Non-Zero IPE Scheme of Section 5.2


Cite error: Invalid <references> tag; parameter "group" is allowed only.

Use <references />, or <references group="..." />


Cite error: Invalid <references> tag; parameter "group" is allowed only.

Use <references />, or <references group="..." />


Cite error: Invalid <references> tag; parameter "group" is allowed only.

Use <references />, or <references group="..." />
27. R. Canetti, S. Halevi, J. Katz. Chosen-Ciphertext Security from Identity-Based Encryption. In Eurocrypt'04, LNCS 3027, pp. 207-222, 2004.

Cite error: <ref> tags exist for a group named "@:", but no corresponding <references group="@:"/> tag was found, or a closing </ref> is missing
  1. Lindell, Y., Pinkas, B.: An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 52–78. Springer, Heidelberg (2007)
  2. D. Boneh, M. Franklin. Identity-Based Encryption from the Weil Pairing. In SIAM Journal of Computing 32(3), pp. 586-615, 2003, earlier version in Crypto'01, LNCS 2139, pp. 213-229, 2001.
  3. A. Sahai, B. Waters. Fuzzy Identity-Based Encryption In Eurocrypt'05, LNCS 3494, pp. 457-473, 2005.
  4. V. Goyal, O. Pandey, A. Sahai, B. Waters. Attribute-based encryption for fine-grained access control of encrypted data. In ACM CCS'06, pp. 89-98, 2006.
  5. R. Ostrovsky, A. Sahai, B. Waters. Attribute-based encryption with non-monotonic access structures. In ACM CCS'07, pp. 195-203, 2007.
  6. 6.0 6.1 M. Abdalla, E. Kiltz, G. Neven. Generalized Key Delegation for Hierarchical Identity-Based Encryption. In ESORICS'07, LNCS 4734, pp. 139-154. Springer, 2007.
  7. 7.0 7.1 R. Sakai, J. Furukawa. Identity-Based Broadcast Encryption. In Cryptology ePrint Archive: Report 2007/217,, 2007.
  8. 8.0 8.1 C. Delerablee. Identity-Based Broadcast Encryption with Constant Size Ciphertexts and Private Keys. In Asiacrypt'07, LNCS 4833, pp. 200-215, 2007.
  9. 9.00 9.01 9.02 9.03 9.04 9.05 9.06 9.07 9.08 9.09 9.10 9.11 D. Boneh, M. Hamburg. Generalized Identity Based and Broadcast Encryption Schemes. In Asiacrypt'08, LNCS 5350, pp. 455-470, 2008.
  10. 10.00 10.01 10.02 10.03 10.04 10.05 10.06 10.07 10.08 10.09 10.10 10.11 10.12 10.13 A. Lewko, A. Sahai, B. Waters. Revocation Systems with Very Small Private Keys. In IEEE Symposium on Security and Privacy (S&P) 2010, to appear.
  11. 11.0 11.1 D. Boneh, B. Waters. Conjunctive, Subset, and Range Queries on Encrypted Data. In 4th Theory of Cryptography Conference (TCC 2007), LNCS 4392, pp. 535-554, 2007.
  12. 12.00 12.01 12.02 12.03 12.04 12.05 12.06 12.07 12.08 12.09 12.10 12.11 J. Katz, A. Sahai, B. Waters. Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products. In Eurocrypt'08, LNCS 4965, pp. 146-162, 2008.
  13. E. Shi, B. Waters. Delegating Capabilities in Predicate Encryption Systems. In ICALP'08, LNCS 5126, pp. 560-578, 2008.
  14. E. Shen, E. Shi, B. Waters. Predicate Privacy in Encryption Systems. In TCC'09, LNCS 5444, pp. 457-473, 2009
  15. D. Boneh, G. Di Crescenzo, R. Ostrovsky, G. Persiano. Public Key Encryption with Keyword Search. In Eurocrypt'04, LNCS 3027, pp. 506-522, 2004.
  16. M. Abdalla, M. Bellare, D. Catalano, E. Kiltz, T. Kohno, T. Lange, J. Malone-Lee, G. Neven, P. Paillier, H. Shi. Searchable Encryption Revisited: Consistency Properties, Relation to Anonymous IBE, and Extensions. In Crypto'05, LNCS 3621, pp. 205-222, 2005.
  17. V. Iovino, G. Persiano. Hidden-Vector Encryption with Groups of Prime Order. In Pairing'08, LNCS 5209, pp. 75-88, 2008.
  18. A. Barth, D. Boneh, B. Waters. Privacy in Encrypted Content Distribution Using Private Broadcast Encryption. In Financial Cryptography 2006, LNCS 4107, pp. 52-64, 2006.
  19. 19.00 19.01 19.02 19.03 19.04 19.05 19.06 19.07 19.08 19.09 19.10 B. Waters. Dual System Encryption: Realizing Fully Secure IBE and HIBE under Simple Assumptions. In Crypto'09, LNCS series, 2009.
  20. C. Gentry, B. Waters. Adaptive Security in Broadcast Encryption Systems (with Short Ciphertexts). In Eurocrypt'09, LNCS 5479, pp. 171-188, 2009.
  21. 21.0 21.1 A. Lewko, B. Waters. New Techniques for Dual System Encryption and Fully Secure HIBE with Short Ciphertexts. In TCC 2010, LNCS 5978, pp. 455-479, Springer, 2010.
  22. 22.0 22.1 D. Freeman. Converting Pairing-Based Cryptosystems from Composite-Order Groups to Prime-Order Groups. In Eurocrypt'10, LNCS series, to appear, 2010.
  23. R. Canetti, S. Halevi, J. Katz. A Forward-Secure Public-Key Encryption Scheme. In Eurocrypt'03, LNCS 2656, pp. 254-271, 2003.
  24. 24.0 24.1 D. Boneh, X. Boyen. Efficient Selective-ID Secure Identity-Based Encryption Without Random Oracles. In Eurocrypt'04, LNCS 3027, pp. 223-238, 2004.
  25. D. Boneh, X. Boyen, and H. Shacham. Short Group Signatures. In Crypto'04, LNCS 3152, pp. 41-55, 2004.
  26. D. Boneh, X. Boyen, E.-J. Goh. Hierarchical Identity-Based encryption with Constant Size Ciphertext. In Eurocrypt'05, LNCS 3494, pp. 440-456, 2005.

Cite error: <ref> tags exist for a group named "not.:", but no corresponding <references group="not.:"/> tag was found, or a closing </ref> is missing