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

 Functional Encryption for Inner Product: Achieving Constant-Size Ciphertexts with Adaptive Security or Support for Negation 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.

## Introduction

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 ${\displaystyle sk_{x}}$ corresponding to a set ${\displaystyle x~\,\!}$ of atomic elements, called attributes, that is suitably related — according to some well-defined relation ${\displaystyle R~\,\!}$ — to another attribute set ${\displaystyle y~\,\!}$ 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 ${\displaystyle sk_{x}}$ for which ${\displaystyle R(x,y)=1}$ ).

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 ${\displaystyle \tau }$. Decryption rights are granted to anyone holding a private key for a policy ${\displaystyle \tau }$ such that ${\displaystyle \tau (\omega )=1}$. 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 ${\displaystyle S={ID_{1},...,ID_{n}}}$: in IBBE (resp. IBR) systems, decryption requires to hold a private key ${\displaystyle sk_{ID}}$ for which ${\displaystyle ID\in S}$ (resp. ${\displaystyle ID\notin S}$).

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 ${\displaystyle {\overrightarrow {Y}}}$ can be opened by any key ${\displaystyle sk_{\bar {X}}}$ such that ${\displaystyle {\overrightarrow {X}}\cdot {\overrightarrow {Y}}=0}$. 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 ${\displaystyle \mathrm {O} (n)}$-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 ${\displaystyle y~\,\!}$ on a server and we want to decrypt only those for which ${\displaystyle R(x,y)=1}$. Anonymous ciphertexts require to decrypt all of them whereas public attributes ${\displaystyle y~\,\!}$ make it possible to test whether ${\displaystyle R(x,y)}$ (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 ${\displaystyle \mathrm {O} (1)}$ 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 ${\displaystyle \mathrm {O} (n)}$, 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 ${\displaystyle {\overrightarrow {Y}}}$ 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 ${\displaystyle \mathrm {O} (1)}$-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 ${\displaystyle {\overrightarrow {Y}}}$ can only be decrypted using ${\displaystyle sk_{\bar {X}}}$ if ${\displaystyle {\overrightarrow {X}}\cdot {\overrightarrow {Y}}\neq 0}$ 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 ${\displaystyle \mathrm {O} (1)}$-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)
${\displaystyle \blacktriangleright }$ Setup: lets ${\displaystyle (\mathbb {G} ,\mathbb {G} _{T})}$ be bilinear groups of prime order ${\displaystyle p~\,\!}$ and picks ${\displaystyle g{\overset {\}{\leftarrow }}\mathbb {G} ,\alpha ,\alpha _{1},\alpha _{2}{\overset {\}{\leftarrow }}\mathbb {Z} _{p}}$. The public key is ${\displaystyle (g,g^{\alpha _{1}},g^{\alpha _{2}},e(g,g)^{\alpha })}$. The master key is ${\displaystyle g^{\alpha }}$.
${\displaystyle \blacktriangleright }$ KeyGen: chooses ${\displaystyle t{\overset {\}{\leftarrow }}\mathbb {Z} _{p}}$ and outputs a private key for an identity ${\displaystyle ID\in \mathbb {Z} _{p}}$ as ${\displaystyle (K_{0}=g^{t},K_{1}=g^{\alpha +\alpha _{1}t},K_{2}=g^{t(\alpha _{1}ID+\alpha _{2})})}$.
${\displaystyle \blacktriangleright }$ Encrypt: encrypts M and specifies a revoked ${\displaystyle ID'}$ by choosing ${\displaystyle s{\overset {\}{\leftarrow }}\mathbb {Z} _{p}}$ and computing ${\displaystyle (E_{0}=M\cdot e(g,g)^{\alpha s},E_{1}=g^{s(\alpha _{1}ID'+\alpha _{2})},E_{2}=g^{S})}$.
${\displaystyle \blacktriangleright }$ Decrypt: decryption computes ${\displaystyle e(K_{2},E_{2})^{\tfrac {1}{ID-ID'}}e(E_{1},K_{0})^{\tfrac {-1}{ID-ID'}}=e(g,g)^{\alpha _{1}ts}}$ if ${\displaystyle ID\neq ID'}$. It then computes ${\displaystyle e(g,g)^{\alpha s}}$ as ${\displaystyle e(K_{1},E_{2})/{e(g,g)^{\alpha _{1}ts}}=e(g,g)^{\alpha s}}$.

The scheme can be explained by viewing a key and a ciphertext as forming alinear system of 2 equations in the exponent of ${\displaystyle e(g,g)}$ with variables ${\displaystyle \alpha _{1}ts,\alpha _{2}ts}$.

${\displaystyle M_{ID,ID'}{\begin{pmatrix}\alpha _{1}ts\\\alpha _{2}ts\end{pmatrix}}:={\begin{pmatrix}ID1\\ID'1\end{pmatrix}}{\begin{pmatrix}\alpha _{1}ts\\\alpha _{2}ts\end{pmatrix}}={\begin{pmatrix}log(e(K_{2},E_{2}))\\log(e(E_{1},K_{0}))\end{pmatrix}}}$ .

Computing ${\displaystyle e(g,g)^{\alpha _{1}ts}}$ amounts to solve the system, which is possible when ${\displaystyle det(M_{ID,ID'})\neq 0}$ (and thus ${\displaystyle ID\neq ID'}$, as required). In particular, decryption computes a linear combination (in the exponent) with coefficients from the first row of ${\displaystyle M_{ID,ID'}^{-1}}$ which is ${\displaystyle ({\tfrac {1}{ID-ID'}},{\tfrac {-1}{ID-ID'}})}$. In [10], this is called "2-equation technique". The scheme is extended to n-dimension, i.e., the revocation of n users ${\displaystyle \left\{ID'_{1},...,ID'_{n}\right\}}$, by utilizing n local independent systems of two equations

${\displaystyle M_{ID,ID'_{j}}(\alpha _{1}ts_{j},\alpha _{2}ts_{j})^{\top }={\Big (}log(e(K_{2},E_{2,j})),log(e(E_{1,j},K_{0})){\Big )}^{\top }}$ for ${\displaystyle j\in [1,n]}$,

that yield 2n ciphertext components ${\displaystyle (E_{1,j},E_{2,j})}$, each one of which corresponds to a share ${\displaystyle s_{j}}$ of ${\displaystyle s~\,\!}$ such that ${\displaystyle s=\textstyle \sum _{1}^{n}s_{j}}$. The decryption at j-th system returns ${\displaystyle e(g,g)^{\alpha _{1}ts_{i}}}$ if ${\displaystyle ID\neq ID'_{j}}$. Combining these results finally gives ${\displaystyle e(g,g)^{\alpha _{1}ts}}$.

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 ${\displaystyle {\overrightarrow {X}}\cdot {\overrightarrow {Y}}\neq 0}$ cannot be decomposed as simply as that of the revocation scheme, which is decomposable as the conjunction of ${\displaystyle ID\neq ID'_{j}}$ for ${\displaystyle j\in [1,n]}$. Second, the ciphertext size was ${\displaystyle \mathrm {O} (n)}$.

Towards solving these, we introduce a technique called “n-equation technique”. First, we utilize n secret exponents ${\displaystyle {\overrightarrow {\alpha }}=(\alpha _{1},\ldots ,\alpha _{n})^{\top }}$ and let ${\displaystyle \alpha _{1}}$ function as the “master” exponent while ${\displaystyle \alpha _{2},...,\alpha _{n}}$ serve as the “perturbed” factors. Intuitively, we will set up a system of n linear equations of the form:

   ${\displaystyle M_{{\bar {X}},{\bar {Y}}}(\alpha _{1}ts,\ldots ,\alpha _{n}ts)^{\top }=(log(e(K_{i_{1}},E_{j_{1}})),\ldots ,log(e(K_{i_{n}},E_{j_{n}})))^{\top }\qquad (1)}$


where ${\displaystyle {K_{i_{k}}}}$ and ${\displaystyle \{E_{j_{k}}\}}$ are elements of G defined for a key for ${\displaystyle {\overrightarrow {X}}}$ and a ciphertext for ${\displaystyle {\overrightarrow {Y}}}$ respectively. At first, this generalized system seems to require linear-size ciphertexts ${\displaystyle (E_{j_{1}},...,E_{j_{n}})}$. A trick to resolve this is to reuse ciphertext elements throughout the system: we let ${\displaystyle E_{j_{k}}=E_{2}=g^{s}}$ for ${\displaystyle k\in [1,n-1]}$. This effectively yields a constraint ${\displaystyle M_{{\bar {X}},{\bar {Y}}}=(Q_{\bar {X}}^{\top }R^{\top })^{\top }}$, where ${\displaystyle Q_{\bar {X}}}$ is a ${\displaystyle (n-1)\times n}$ matrix parameterized only by ${\displaystyle {\overrightarrow {X}}}$ and ${\displaystyle R}$ is a ${\displaystyle 1\times n}$ matrix. The remaining problem is then to choose ${\displaystyle M_{{\bar {X}},{\bar {Y}}}}$ in such a way that the system has a solution if ${\displaystyle {\overrightarrow {X}}\cdot {\overrightarrow {Y}}\neq 0}$ (the decryptability condition). To this end, we define

   ${\displaystyle M_{{\bar {X}},{\bar {Y}}}:={\begin{pmatrix}-{\dfrac {x_{2}}{x_{1}}}&1&&&\\-{\dfrac {x_{3}}{x_{1}}}&&1&\\\vdots &&&\ddots &\\-{\dfrac {x_{n}}{x_{1}}}&&&&1\\y_{1}&y_{2}&y_{3}&\cdots &y_{n}\end{pmatrix}},\qquad (2)}$


where it holds that det${\displaystyle (M_{{\bar {X}},{\bar {Y}}})=(-1)^{n+1}{\overrightarrow {X}}\cdot {\overrightarrow {Y}}/x_{1}}$. 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.

## Definitions

### Syntax and Security Definition for Functional Encryption

Let ${\displaystyle R:\Sigma _{k}\times \Sigma _{e}\rightarrow {0,1}}$ be a boolean function where ${\displaystyle \Sigma _{k}}$ and ${\displaystyle \Sigma _{k}}$ denote "key attribute" and "ciphertext attribute" spaces. A functional encryption (FE) scheme for R consists of the following algorithms.

• ${\displaystyle Setup(1^{\lambda },des)\rightarrow (pk,msk):}$ takes as input a security parameter ${\displaystyle 1^{\lambda }}$ and a scheme description des (which usually describes the dimension n), and outputs a master public key pk and a master secret key msk.
• ${\displaystyle KeyGen(x,msk)\rightarrow sk_{x}:}$ takes as input a key attribute ${\displaystyle x\in \Sigma _{k}}$ and the master key msk. It outputs a private decryption key ${\displaystyle sk_{x}}$.
• ${\displaystyle Encrypt(y,M,pk)\rightarrow C:}$ takes as input a ciphertext attribute ${\displaystyle y\in \Sigma _{e}}$, a message ${\displaystyle M\in {\mathcal {M}}}$, and public key pk. It outputs a ciphertext C.
• ${\displaystyle Decrypt(C,y,sk_{x},x)\rightarrow M:}$ given a ciphertext C with its attribute y and the decryption key ${\displaystyle sk_{x}}$ with its attribute ${\displaystyle x~\,\!}$, it outputs a message M or ${\displaystyle \bot }$.

We require the standard correctness of decryption, that is, for all ${\displaystyle \lambda }$, all ${\displaystyle (pk,msk)\leftarrow Setup(1^{\lambda })}$, all ${\displaystyle x\in \Sigma _{k}}$, all ${\displaystyle sk_{x}\leftarrow KeyGen(x,msk)}$, and all ${\displaystyle y\in \Sigma _{e}}$,

• If ${\displaystyle R(x,y)=1}$, then ${\displaystyle Decrypt(Encrypt(y,M,pk),sk_{x})=M}$.
• If R(x,y) = 0, Decrypt(Encrypt(y,M,pk),sk_x)= \bot [/itex] 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 ${\displaystyle R^{A}:\Sigma _{k}^{A}\times \Sigma _{e}^{A}\rightarrow \{0,1\}.}$ For a FE primitive A, we can define two variants:

• Dual Variant, denoted by Dual(A), is defined by setting ${\displaystyle \Sigma _{k}^{Dual(A)}:=\Sigma _{e}^{A}}$ and

${\displaystyle \Sigma _{e}^{Dual(A)}:=\Sigma _{k}^{A}}$ and ${\displaystyle R^{A}(\mathbf {x} ,\mathbf {y} )=R^{Dual(A)}(\mathbf {y} ,\mathbf {x} )}$. In a dual variant, the roles of key and ciphertext attributes are swapped from those of its original primitive.

• Negated Variant, denoted by ${\displaystyle Neg(A)}$, is defined by using the same domains as A and setting ${\displaystyle R^{Neg(A)}(\mathbf {x} ,\mathbf {y} )=1\Leftrightarrow R^{A}(\mathbf {x} ,\mathbf {y} )=0}$. The condition is thus the opposite of the original primitive.

Security Definition. A FE scheme for a function ${\displaystyle R:\Sigma _{k}\times \Sigma _{e}\rightarrow \{0,1\}}$ is fully secure if no PPT adversary ${\displaystyle {\mathcal {A}}}$ has non-negligible advantage in this game.

Setup. The challenger runs Setup(n) and hands the public key pk to ${\displaystyle {\mathcal {A}}}$.

Query Phase 1. The challenger answers private key queries for ${\displaystyle x\in \Sigma _{k}}$ by returning ${\displaystyle sk_{x}\leftarrow KeyGen(x,msk)}$.

Challenge. ${\displaystyle {\mathcal {A}}}$ submits messages ${\displaystyle M_{0},M_{1}}$ and a target ciphertext attribute vector ${\displaystyle y^{*}\in \Sigma _{e}}$ such that ${\displaystyle R(\mathbf {x} ,\mathbf {y^{*}} )=0}$ for all key attributes ${\displaystyle x~\,\!}$ that have been queried so far. The challenger then flips a bit ${\displaystyle \beta {\xleftarrow {\}}\{0,1\}}$ and computes the challenge ciphertext ${\displaystyle C^{*}\leftarrow Encrypt(\mathbf {y} ,\mathbf {M_{\beta }} ,\mathbf {pk} )}$ which is given to ${\displaystyle {\mathcal {A}}}$.

Query Phase 2. The adversary is allowed to make further private key queries ${\displaystyle x\in \Sigma _{k}}$ under the same restriction as above, i.e., ${\displaystyle R(\mathbf {x} ,\mathbf {y^{*}} )=0}$.

'Guess. The adversary ${\displaystyle {\mathcal {A}}}$ outputs a guess ${\displaystyle \beta '\in \{0,1\}}$ and wins if ${\displaystyle \beta '=\beta }$. In the game, ${\displaystyle {\mathcal {A}}}$'s advantage is typically defined as ${\displaystyle \mathbf {Adv} _{\mathcal {A}}(\lambda )=|Pr[\beta =beta']-{\dfrac {1}{2}}|}$.

(Co-)Selective Security. We also consider the notion of selective security [23][24], where ${\displaystyle {\mathcal {A}}}$ has to choose the challenge attribute ${\displaystyle \mathbf {y^{*}} }$ before the setup phase, but can adaptively choose the key queries for ${\displaystyle \mathbf {x_{1}} ,\cdots ,\mathbf {x_{q}} }$. One can consider its "dual" notion where ${\displaystyle {\mathcal {A}}}$ must output the q key queries for attribute vectors ${\displaystyle \mathbf {x_{1}} ,\cdots ,\mathbf {x_{q}} }$ before the setup phase, but can adaptively choose the target challenge attribute ${\displaystyle \mathbf {y^{*}} }$. 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 ${\displaystyle R^{A},R^{B}}$, respectively. Suppose there exists efficient injective mappings ${\displaystyle f_{k}:\Sigma _{k}^{A}\rightarrow \Sigma _{k}^{B}}$ and ${\displaystyle f_{e}:\Sigma _{e}^{A}\rightarrow \Sigma _{e}^{B}}$ such that ${\displaystyle R^{B}(f_{k}(\mathbf {x} ),f_{e}(\mathbf {y} ))=1\Leftrightarrow R^{A}(\mathbf {x,y} )=1}$. Let ${\displaystyle \Pi _{B}}$ be a construction for primitive B. We then construct ${\displaystyle \Pi _{A}}$ for primitive A from ${\displaystyle \Pi _{B}}$ by applying mappings ${\displaystyle f_{k},f_{e}}$ 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 ${\displaystyle \Pi _{A}.KeyGen(x,msk):=\Pi _{B}.KeyGen(f_{k}(x),msk)}$ and ${\displaystyle \Pi _{A}.Encrypt(y,M,pk):=\Pi _{B}.Encrypt(f_{e}(y),M,pk)}$, respectively. Then, if ${\displaystyle \Pi _{B}}$ is secure, so is ${\displaystyle \Pi _{A}}$. This holds for adaptive, selective, co-selective security models.

We denote this primitive implication by ${\displaystyle B{\xrightarrow {f_{k},f_{e}}}A}$.

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
${\displaystyle B{\xrightarrow {f_{k},f_{e}}}A}$ implies ${\displaystyle Dual(B){\xrightarrow {f_{e},f_{k}}}Dual(A)}$ and ${\displaystyle Neg(B){\xrightarrow {f_{k},f_{e}}}Neg(A)}$.

### Complexity Assumptions in bilinear Groups

We consider groups ${\displaystyle (\mathbb {G} ,\mathbb {G} _{T})}$ of prime order p with an efficiently computable map ${\displaystyle e:\mathbb {G} \times \mathbb {G} \rightarrow \mathbb {G} _{T}}$ such that ${\displaystyle e(g^{a},h^{b})=e(g,h)^{a}b}$ for any ${\displaystyle (g,h)\in \mathbb {G} \times \mathbb {G} }$ and ${\displaystyle a,b\in \mathbb {Z} }$ and ${\displaystyle e(g,h)\neq 1_{\mathbb {G} _{T}}}$ whenever ${\displaystyle g,h\neq 1_{\mathbb {G} }}$. 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 ${\displaystyle (\mathbb {G} ,\mathbb {G} _{T})}$ is, given elements ${\displaystyle (g^{0},g^{\theta _{1}},g^{\theta _{2}},g^{\theta _{3}},\eta )\in \mathbb {G} ^{4}\times \mathbb {G} _{T}}$ with ${\displaystyle \theta _{1},\theta _{2},\theta _{3}{\xleftarrow {\}}\mathbb {Z} _{p}}$, to decide whether ${\displaystyle \eta =e(g,g)^{\theta _{1}\theta _{2}\theta _{3}}}$ or ${\displaystyle \eta \in _{R}\mathbb {G} _{T}}$.

Definition 2: Decision Linear Problem
The Decision Linear Problem (DLIN) in ${\displaystyle \mathbb {G} }$ consists in, given a tuple ${\displaystyle (g,f,\nu ,g^{\theta _{1}},f^{\theta _{2}},\eta )\in \mathbb {G} ^{6}}$ with ${\displaystyle \theta _{1},\theta _{2}{\xleftarrow {\}}\mathbb {Z} _{p}}$ and ${\displaystyle f,g,\nu {\xleftarrow {\}}\mathbb {G} }$, deciding whether ${\displaystyle \eta =\nu ^{\theta _{1}+\theta _{2}}}$ or ${\displaystyle \nu \in _{R}\mathbb {G} }$.

## 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 ${\displaystyle R~\,\!}$. 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 ${\displaystyle \mathbb {Z} _{p}^{n}}$, for some prime p, is defined as follows. Both attribute domains are ${\displaystyle \Sigma _{k}^{IPE_{n}}=\Sigma _{e}^{IPE_{n}}=\mathbb {Z} _{p}^{n}}$.

We consider two distinct IPE modes here. The first one is zero-mode IPE where ${\displaystyle R^{ZIPE_{n}}({\overrightarrow {X}},{\overrightarrow {Y}})=1\quad iff\quad {\overrightarrow {X}}\cdot {\overrightarrow {Y}}=0}$. The other one is its negated primitive, which we call the non-zero-mode IPE, where ${\displaystyle R^{NIPE_{n}}({\overrightarrow {X}},{\overrightarrow {Y}})=1\quad iff\quad {\overrightarrow {X}}\cdot {\overrightarrow {Y}}\neq 0}$.

Polynomial Evaluation. Functional encryption for the zero evaluation of polynomials of degree ${\displaystyle \leq n}$ is defined as follows. The ciphertext and key attribute domains are defined as ${\displaystyle \Sigma _{e}^{ZPoly_{\leq n}}=\mathbb {Z} _{p}}$ and ${\displaystyle \Sigma _{k}^{ZPoly_{\leq n}}=\{P\in \mathbb {Z} _{p}[x][deg(P)\leq n]\}}$, respectively. The relation is defined by ${\displaystyle R^{ZPoly_{\leq n}}(P,x)=1\quad iff\quad P(x)=0}$. The non-zero evaluation mode can be defined as its negated primitive ${\displaystyle Neg(ZPoly_{\leq n})}$.

Given an IPE scheme over ${\displaystyle \mathbb {Z} _{p}^{n+1}}$, one obtain a functional encryption system for polynomial evaluation via the following embedding. For the key attribute, we map the polynomial ${\displaystyle P[X]=\rho _{0}+\rho _{1}X+\cdots +\rho _{n}X^{n}}$ to ${\displaystyle {\overrightarrow {X}}_{p}=(\rho _{0},\cdots ,\rho _{n})}$. Regarding ciphertext attributes, each element ${\displaystyle \omega \in \mathbb {Z} _{p}}$ is mapped onto a vector ${\displaystyle {\overrightarrow {Y}}_{\omega }=(1,\omega ,\omega ^{2},\cdots ,\omega ^{n})}$. Correctness and security hold since ${\displaystyle P(\omega )=0}$ whenever ${\displaystyle {\overrightarrow {X}}_{p}\cdot {\overrightarrow {Y}}_{\omega }=0}$. 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 ${\displaystyle R^{OR\leq n}:\mathbb {Z} _{n}^{\leq n}\times \mathbb {Z} _{n}\rightarrow \{0,1\}}$ can be defined by ${\displaystyle R^{OR\leq n}((I_{1},\cdots ,I_{k}),z)\mapsto 1(\quad for\quad k\leq n)\quad iff\quad (z=I_{1})\quad or\cdots or\quad (z=I_{k})}$. 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 ${\displaystyle f_{OR,I_{1},\cdots ,I_{k}}(z)=(z-I_{1})\cdots (z-I_{k})}$, and letting senders encrypting to ${\displaystyle z~\,\!}$.

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, ${\displaystyle r{\xleftarrow {\}}\mathbb {Z} _{p}}$ is chosen by ${\displaystyle KeyGen}$.[not.: 2]

${\displaystyle {\begin{array}{c c}{\text{Policy}}&{\text{Implementation}}\\\hline (z=I_{1})\ or\ (z=I_{2})&f_{OR,I_{1},I_{2}}(z)=(z-I_{1})(z-I_{2})=0\\(z_{1}=I_{1})\ or\ (z_{2}=I_{2})&f_{{\overline {OR}},I_{1},I_{2}}(z_{1},z_{2})=(z_{1}-I_{1})(z_{2}-I_{2})=0\\(z_{1}=I_{1})\ and\ (z_{2}=I_{2})&f_{AND,I_{1},I_{2}}(z_{1},z_{2})=(z_{1}-I_{1})r+(z_{2}-I_{2})=0\\(z_{1}\neq I_{1})\ or\ (z_{2}\neq I_{2})&f_{NOR,I_{1},I_{2}}(z_{1},z_{2})=(z_{1}-I_{1})r+(z_{2}-I_{2})\neq 0\\(z\neq I_{1})\ and\ (z\neq I_{2})&f_{NAND,I_{1},I_{2}}(z)=(z-I_{1})(z-I_{2})\neq 0\\(z_{1}\neq I_{1})\ and\ (z_{2}\neq I_{2})&f_{{\overline {NAND}},I_{1},I_{2}}(z_{1},z_{2})=(z_{1}-I_{1})(z_{2}-I_{2})\neq 0\\\end{array}}}$

ID-based Broadcast Encryption and Revocation. Let ${\displaystyle {\mathcal {I}}}$ be an identity space. An ID-based broadcast encryption scheme (IBBE) for maximum n receivers per ciphertext is a functional encryption for ${\displaystyle R^{IBBE_{\leq n}}:{\mathcal {I}}\times 2^{\mathcal {I}}\rightarrow \{0,1\}}$ defined by ${\displaystyle R^{IBBE_{\leq n}}:(ID,S)\mapsto 1\ iff\ ID\in S}$. An IBBE system can be constructed by a functional encryption for ${\displaystyle R^{Dual(OR_{\leq n})}}$. To encrypt a message for the receiver set ${\displaystyle S=\{ID_{1},\cdots ,ID_{k}\}}$, one encrypts using the policy ${\displaystyle (z=ID_{1})\ or\cdots or\ (z=ID_{k})}$.

Likewise, identity-based revocation (IBR) [10] for at most n revocations per ciphertext can be casted as a negated IBBE, i.e., ${\displaystyle R^{IBR_{\leq n}}:(ID,R)\mapsto 1\ iff\ ID\notin R}$.

### Spatial Encryption

We now recall the concept of spatial encryption [9]. For a ${\displaystyle n\times d}$ matrix M of which elements are in ${\displaystyle \mathbb {Z} _{p}}$ and a vector ${\displaystyle {\vec {c}}\in \mathbb {Z} _{p}^{n}}$, we define its corresponding affine space as ${\displaystyle Aff(M,{\vec {c}})=\{M{\vec {\omega }}+{\vec {c}}\ {\big |}\ {\vec {\omega }}\in \mathbb {Z} _{p}^{d}\}}$. Let ${\displaystyle \mathrm {N} _{n}\subseteq 2^{\mathbb {Z} _{p}^{n}}}$ be the collection of all afiine spaces inside ${\displaystyle \mathbb {Z} _{p}^{n}}$. That is,${\displaystyle \mathrm {N} _{n}=\{Aff(M,{\vec {c}})\ {\big |}\ M\in \mathbb {M} _{n\times d},c\in \mathbb {Z} _{p}^{n},d\leq n\}}$, where ${\displaystyle \mathbb {M} _{n\times d}}$ is the set of all ${\displaystyle n\times d}$ matrices in ${\displaystyle \mathbb {Z} _{p}}$.

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 ${\displaystyle R^{Neg(Spatial)}:(V,{\vec {y}})\mapsto 1\quad iff\quad {\vec {y}}\notin V)}$ 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 ${\displaystyle {\vec {X}}=(x_{1},\cdot ,x_{n})^{\top }\in \mathbb {Z} _{p}^{n}}$ to an ${\displaystyle (n-1)}$- dimension affline space ${\displaystyle V_{\bar {X}}=Aff(M_{\bar {X}},{\vec {0}}_{n})=\{M_{\bar {X}}{\vec {\omega }}+{\vec {0}}_{n}{\big |}{\vec {\omega }}\in \mathbb {Z} _{p}^{n-1}\}}$ with the matrix ${\displaystyle M_{\bar {X}}\in \mathbb {Z} _{p}^{n\times (n-1)}}$

${\displaystyle M_{\bar {X}}={\begin{pmatrix}-{\frac {x_{2}}{x_{1}}},&-{\frac {x_{3}}{x_{1}}},&\cdots ,&{\frac {x_{n}}{x_{1}}}\\&\quad I_{n-1}&&\end{pmatrix}}.\qquad {\text{(3)}}}$


For any ${\displaystyle {\vec {Y}}=(y_{1},\cdots ,y_{n})^{\top }\in \mathbb {Z} _{p}^{n}}$, we then have ${\displaystyle {\vec {X}}\cdot {\vec {Y}}=0\Leftrightarrow {\vec {Y}}=M_{\bar {X}}\cdot (y_{2},\cdots ,y_{n})^{\top }\Leftrightarrow {\vec {Y}}\in V_{\bar {X}}}$. 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 ${\displaystyle {\vec {a}}=(a_{1},\cdots ,a_{n})^{\top }\in \mathbb {Z} _{p}^{n}}$, we write ${\displaystyle g^{\bar {a}}}$ to denote ${\displaystyle (g^{a_{1}},\cdots ,g^{a_{n}})^{\top }}$. Given ${\displaystyle g^{\bar {a}},{\vec {z}}}$, one can easily compute ${\displaystyle (g^{\bar {a}})^{\bar {z}}:=g^{({\bar {a}},{\bar {z}})}}$ where ${\displaystyle \langle {\vec {a}},{\vec {z}}\rangle }$ denotes the inner product ${\displaystyle {\vec {a}}\cdot {\vec {z}}={\vec {a}}^{\top }{\vec {z}}}$.

Construction 2. (Selectively secure zero IPE)
${\displaystyle \blacktriangleright }$${\displaystyle {\text{Setup}}(1^{\lambda ,n})}$: chooses bilinear groups ${\displaystyle (\mathbb {G} ,\mathbb {G} _{T})}$ of prime order ${\displaystyle p>2^{\lambda }}$ with a generator ${\displaystyle g{\xleftarrow {\}}\mathbb {G} }$. It chooses ${\displaystyle (\alpha ,\alpha _{0},\cdots ,\alpha _{n}){\xleftarrow {\}}\mathbb {Z} _{p}}$.Let ${\displaystyle {\vec {\alpha }}=(\alpha _{1},\cdots ,\alpha _{n})}$. The public key is ${\displaystyle {\text{pk}}=(g,g^{\alpha _{0}},{\vec {H}}=g^{\bar {\alpha }},Z=e(g,g)^{\alpha })}$. The master key is ${\displaystyle {\text{msk}}=g^{\alpha }}$.
${\displaystyle \blacktriangleright }$${\displaystyle {\text{KeyGen}}({\vec {X}},{\text{msk}},{\text{pk}})}$: chooses ${\displaystyle t{\xleftarrow {\}}\mathbb {Z} _{p}}$ and parces ${\displaystyle {\vec {X}}\ {\text{as}}\ (x_{1},\cdots ,x_{n})}$ and returns ${\displaystyle \bot \ {\text{if}}\ x_{1}=0}$. It outputs the private key as ${\displaystyle sk_{\bar {X}}=(D_{0},D_{1},K_{2},\cdots ,K_{n})}$ where

${\displaystyle \qquad D_{0}=g^{t},\qquad D_{1}=g^{\alpha +\alpha _{0}t},\qquad \{K_{i}=(g^{-\alpha _{1}{\frac {x_{i}}{x_{1}}}}g^{\alpha _{i}})^{t}\}_{i=2,\cdots ,n}}$.

${\displaystyle \blacktriangleright }$${\displaystyle {\text{Encrypt}}({\vec {Y}},{\text{pk}})}$: the encryption algorithm first picks ${\displaystyle s{\xleftarrow {\}}\mathbb {Z} _{p}}$. It parses ${\displaystyle {\vec {Y}}\ {\text{as}}\ (y_{1},\cdots ,y_{n})}$ and computes the ciphertext as

${\displaystyle E_{0}=M\cdot e(g,g)^{\alpha s},\qquad E_{1}=(g^{\alpha _{0}}g^{\langle {\bar {\alpha }},{\bar {Y}}\rangle })^{s},\qquad E_{2}=g^{s}}$.

${\displaystyle \blacktriangleright }$${\displaystyle {\text{Decrypt}}(C,{\vec {Y}},{\text{sk}}_{\bar {X}},{\vec {X}},{\text{pk}})}$: to decrypt, the algorithm computes the message blinding factor as ${\displaystyle {\frac {e(D_{1}K_{2}^{y_{2}}\cdots K_{n}^{y_{n}},E_{2})}{e(E_{1},D_{0})}}=e(g,g)^{\alpha s}}$.

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).
Proof
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 ${\displaystyle E_{1}}$ while each key contains ${\displaystyle n-1}$ tags (${\displaystyle {\text{tagk}}_{i}}$ for each ${\displaystyle K_{i}}$ element) that are aggregated into ${\displaystyle {\text{tagk}}=\textstyle \sum _{i=2}^{n}{\text{tagk}}_{i}y_{i}}$ upon decryption of a ciphertext intended for ${\displaystyle {\vec {Y}}}$. The receiver can decrypt if ${\displaystyle {\text{tagk}}\neq {\text{tagc}}}$ (and ${\displaystyle {\overrightarrow {X}}\cdot {\overrightarrow {Y}}=0}$.

${\displaystyle \blacktriangleright }$${\displaystyle {\text{Setup}}(1^{\lambda ,n})}$: chooses bilinear groups ${\displaystyle (\mathbb {G} ,\mathbb {G} _{T})}$ of prime order ${\displaystyle p>2^{\lambda }}$. It then picks generators ${\displaystyle g,v,v_{1},v_{2}{\xleftarrow {\}}\mathbb {G} }$ and chooses ${\displaystyle \alpha ,\alpha _{1},\cdots ,\alpha _{n},a_{1},a_{2},b{\xleftarrow {\}}\mathbb {Z} _{p}}$. Let ${\displaystyle {\vec {\alpha }}=(\alpha _{1},\cdots ,\alpha _{n})}$ and ${\displaystyle {\vec {H}}=(h_{1},\cdots ,h_{n})=g^{\bar {\alpha }}}$. The public key consist of

${\displaystyle {\text{pk}}={\begin{pmatrix}g,\ \omega =g^{\alpha _{0}},\ Z=e(g,g)^{\alpha \cdot a_{1}\cdot b},\ {\vec {H}}=g^{\bar {\alpha }},\ A_{1}=g^{a_{1}},\ A_{2}=g^{a_{2}},\ B=g^{b},\\B_{1}=g^{b\cdot a_{1}},\ B_{2}=g^{b\cdot a_{2}},\ \tau _{1}=v\cdot v_{1}^{a_{1}},\ \tau _{1}=v\cdot v_{2}^{a_{2}},\ T_{1}=\tau _{1}^{b},\ T_{2}=\tau _{2}^{b}\end{pmatrix}}}$ The master key is defined to be ${\displaystyle {\text{msk}}=(g^{\alpha },g^{\alpha a_{1}},v,v_{1},v_{2}).}$

${\displaystyle \blacktriangleright }$${\displaystyle {\text{KeyGen}}({\vec {X}},{\text{msk}},{\text{pk}})}$: parces ${\displaystyle {\vec {X}}\ {\text{as}}\ (x_{1},\cdots ,x_{n})}$ and returns ${\displaystyle \bot \ {\text{if}}\ x_{1}=0}$. Otherwise, it picks ${\displaystyle r_{1},r_{2}{\xleftarrow {\}}\mathbb {Z} _{p},{\text{tagk}}_{2},\cdots ,{\text{tagk}}_{n}{\xleftarrow {\}}\mathbb {Z} _{p}}$, sets ${\displaystyle r=r_{1}+r_{2}}$ and generates ${\displaystyle sk_{\bar {X}}=(D_{1},\cdots ,D_{7},K_{2},\cdots ,K_{n},tagk_{2},\cdots ,tagk_{n})}$ by computing

${\displaystyle {\text{sk}}_{\text{core}}=\{K_{i}=(g^{-\alpha _{1}{\frac {x_{i}}{x_{1}}}}\cdot g^{\alpha _{i}}\cdot g^{\alpha _{0}\cdot {\text{tagk}}_{i}})^{r_{1}}\}_{i=2,\cdots ,n'}}$

${\displaystyle {\text{sk}}_{\text{adapt}}={\begin{pmatrix}D_{1}=g^{\alpha a_{1}}\cdot v^{r},&D_{2}=g^{-\alpha }\cdot v_{1}^{r}\cdot g^{z_{1}},&D_{3}=B^{-z_{1}},&D_{4}=v_{2}^{r}\cdot g^{z_{2}},\\D_{5}=B^{-z_{2}},&D_{6}=B^{r_{2}},&D_{7}=g^{r_{1}}&\end{pmatrix}}.}$

${\displaystyle \blacktriangleright }$${\displaystyle {\text{Encrypt}}({\vec {Y}},M,{\text{pk}})}$: to encrypt ${\displaystyle M\in \mathbb {G} _{T}{\text{under}}(y_{1},\cdots ,y_{n})\in (\mathbb {Z} _{p})^{n}}$, pick ${\displaystyle s_{1},s_{2},t,{\text{tagc}}{\xleftarrow {\}}\mathbb {Z} _{p}}$ and compute ${\displaystyle C=(C_{1},\cdots ,C_{7},E_{0},E_{1},E_{2},{\text{tagc}})}$ where

${\displaystyle C_{\text{core}}=(E_{0}=M\cdot Z^{s_{2}},\ E_{1}=(g^{\alpha _{0}\cdot {\text{tagc}}}\cdot g^{\langle {\bar {\alpha }},{\bar {Y}}\rangle })^{t},\ E_{2}=g^{t}}$

${\displaystyle C_{\text{adapt}}={\begin{pmatrix}C_{1}=B^{s_{1}+s_{2}},&C_{2}=B_{1}^{s_{1}},&C_{3}=A_{1}^{s_{1}},&C_{4}=B_{2}^{s_{2}},\\C_{5}=A_{2}^{s_{2}},&C_{6}=\tau _{1}^{s_{1}}\cdot \tau _{2}^{s_{2}},&C_{7}=T_{1}^{s_{1}}\cdot T_{2}^{s_{2}}\cdot \omega ^{-t}&\end{pmatrix}}.}$

${\displaystyle \blacktriangleright }$${\displaystyle {\text{Decrypt}}(C,{\vec {Y}},{\text{sk}}_{\bar {X}},{\vec {X}},{\text{pk}})}$: computes ${\displaystyle {\text{tagk}}={\text{tagk}}_{2}y_{2}+\cdots +{\text{tagk}}_{n}y_{n}}$ and then ${\displaystyle W_{1}=\textstyle \prod _{j=1}^{5}e(C_{j},D_{j})\cdot (\textstyle \prod _{j=1}^{7}e(C_{j},D_{j}))^{-1}=e(g,g)^{\alpha \cdot a_{1}\cdot b\cdot s_{2}}\cdot e(g,w)^{r_{1}t}}$, as well as ${\displaystyle W_{2}={\Bigg (}{\frac {e(K_{2}^{y_{2}}\cdots K_{n}^{y_{n}},E_{2})}{e(E_{1},D_{7})}}{\Bigg )}^{\frac {1}{{\text{tagk}}-{\text{tagc}}}}=e(g,w)^{r_{1}t}}$. It finally recovers the plaintext as ${\displaystyle M=E_{0}/Z^{s_{2}}=E_{0}/e(g,g)^{\alpha \cdot a_{1}\cdot b\cdot s_{2}}\leftarrow E_{0}\cdot W_{2}\cdot W_{1}^{-1}}$.

The correctness of ${\displaystyle W_{2}}$ 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 ${\displaystyle {\vec {Y}}}$ is. Also, decryption entails a constant number of pairing evaluations (whereas ciphertexts cost ${\displaystyle \mathrm {O} (n)}$ pairings to decrypt in [12]).

Theorem 2
Construction 3 is adaptively secure under the DLIN and DBDH assumptions.
Proof
The proof uses the dual system methodology similar to [19], which involves ciphertexts and private keys that can be normal or semi-functional.
${\displaystyle \circ }$ Semi-functional ciphertexts are generated by first computing a normal ciphertext ${\displaystyle (C_{0}',C_{1}','cdots,C_{7}',E_{1}',E_{7}',{\text{tagc}}')}$ and then choosing ${\displaystyle \chi {\xleftarrow {\}}\mathbb {Z} _{p}}$ before replacing ${\displaystyle (C_{4}',C_{5}',C_{6}',C_{7}',E_{1}',E_{7}',{\text{tagc}}')}$, respectively, by

${\displaystyle C_{4}=C_{4}'\cdot g^{ba_{2}\chi },\ C_{5}=C_{5}'\cdot g^{a_{2}\chi },\ C_{6}=C_{6}'\cdot v^{a_{2}\chi },\ C_{7}=C_{7}'\cdot v_{2}^{a_{2}b\chi }.\ {\text{(4)}}}$

${\displaystyle \circ }$ From a normal key ${\displaystyle (D_{1}',\cdots ,D_{7}',K_{2}',\cdots ,K'_{n},{\text{tagk}}_{2}',\cdots ,{\text{tagk}}_{n}')}$, semi-functional keys are obtained by choosing ${\displaystyle \gamma {\xleftarrow {\}}\mathbb {Z} _{p}}$ and replacing ${\displaystyle (D_{1}',D_{2}',D_{4}')}$ by

${\displaystyle D_{1}=D_{1}'\cdot g^{-a_{1}a_{2}\gamma },\ D_{2}=D_{2}'\cdot g^{a_{2}\gamma },\ D_{4}=D_{4}'\cdot g^{a_{1}\gamma }.\ (5)}$

The proof proceeds with a game sequence starting from ${\displaystyle {\text{Game}}_{\text{Real}}}$, which is the actual attack game. The following games are defined below.

${\displaystyle {\text{Game}}_{0}}$ is the real attack game but the challenge ciphertext is semi-functional.

${\displaystyle {\text{Game}}_{k}}$ (for ${\displaystyle 1\leq k\leq q}$) is identical to ${\displaystyle {\text{Game}}_{0}}$ except that the first i private key generation queries are answered by returning a semi-functional key.

${\displaystyle {\text{Game}}_{q+1}}$ is as Game q but the challenge ciphertext is a semi-functional encryption of a random element of ${\displaystyle \mathbb {G} _{T}}$ instead of the actual plaintext.

We prove the indistinguishability between two consecutive games under some assumptions. The sequence ends in ${\displaystyle {\text{Game}}_{q+1}}$, where the challenge ciphertext is independent of the challenger's bit ${\displaystyle \beta }$, hence any adversary has no advantage.

The indistinguishability of ${\displaystyle {\text{Game}}_{\text{Real}}}$ and ${\displaystyle {\text{Game}}_{0}}$ as well as that of ${\displaystyle {\text{Game}}_{q}}$ and ${\displaystyle {\text{Game}}_{q+1}}$ 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, ${\displaystyle {\text{Game}}_{0}}$ is indistinguishable from ${\displaystyle {\text{Game}}_{\text{Real}}}$.

Lemma 2
For any ${\displaystyle 1\leq k\leq q}$, if an adversary ${\displaystyle {\mathcal {A}}}$ can distinguish ${\displaystyle {\text{Game}}_{k}}$ from ${\displaystyle {\text{Game}}_{k-1}}$, 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 ${\displaystyle {\mathcal {B}}}$ can create semi-functional keys for any vector ${\displaystyle {\vec {X}}}$, including those for which ${\displaystyle {\vec {X}}\cdot {\vec {Y}}^{*}=0}$. However, the crucial point is that we must prevent ${\displaystyle {\mathcal {B}}}$ from directly deciding whether the ${\displaystyle k^{\text{th}}}$ queried private key is normal or semi-functional by generating a semi-functional ciphertext for itself. Indeed, if this were possible, the reduction from ${\displaystyle {\mathcal {A}}}$ would not be established.

To resolve this, we use a secret exponent vector ${\displaystyle {\vec {\zeta }}\in \mathbb {Z} _{p}^{n}}$ and embed the DLIN instance so that ${\displaystyle {\mathcal {B}}}$ can simulate only the key at ${\displaystyle k^{\text{th}}}$ query for ${\displaystyle {\vec {X}}}$ with tags ${\displaystyle ({\text{tagk}}_{2},\cdots ,{\text{tagk}}_{n})}$ and the challenge ciphertext for ${\displaystyle {\vec {Y}}^{*}}$ with ${\displaystyle {\text{tagc}}^{*}}$ that obey the relation: ${\displaystyle ({\text{tagk}}_{2},\cdots ,{\text{tagk}}_{n},{\text{tagc}}^{*})^{\top }=-M_{{\bar {X}},{\bar {Y}}^{*}}{\vec {\zeta }}}$ where ${\displaystyle M_{{\bar {X}},{\bar {Y}}}}$ is the ${\displaystyle n\times n}$ matrix defined in Eq.(2). We thereby conceptually use the n-equation technique here. A particular consequence is that if we have ${\displaystyle {\vec {X}}\cdot {\vec {Y}}^{*}=0}$ then it holds that

${\displaystyle {\text{tagk}}=\sum _{i=2}^{n}{\text{tagk}}_{i}y_{i}^{*}=\zeta _{1}\sum _{i=2}^{n}{\frac {x_{i}}{x_{1}}}y_{i}^{*}-\sum _{i=2}^{n}\zeta _{i}y_{i}^{*}=\zeta _{1}\cdot (-y_{1}^{*})-\sum _{i=2}^{n}\zeta _{i}y_{i}^{*}={\text{tagc}}^{*},}$


which is the exact condition that hampers the decryption, thus ${\displaystyle {\mathcal {B}}}$ cannot test by itself, as desired. We are now ready to describe the proof of Lemma 2.

Proof. The distinguisher ${\displaystyle {\mathcal {B}}}$ receives ${\displaystyle (g,f,\nu ,g^{\theta _{1}},f^{\theta _{2}},\eta )}$ and decides if ${\displaystyle \eta =\nu ^{\theta _{1}+\theta _{2}}}$.

Setup. Algorithm ${\displaystyle {\mathcal {B}}}$ picks ${\displaystyle \alpha ,a_{1},a_{2},\delta _{v_{1}},\delta _{v_{2}}{\xleftarrow {\}}\mathbb {Z} _{p}}$ and sets ${\displaystyle g=g,Z=e(f,g)^{\alpha a_{1}},}$

${\displaystyle {\begin{matrix}A_{1}=g^{a_{1}},&A_{2}=g^{a_{2}},&B=g^{b}=f,&v_{1}=\nu ^{a_{2}}\cdot g^{\delta _{v_{1}}},\\B_{1}=g^{ba_{1}}=f^{a_{1}},&B_{2}=g^{ba_{2}}=f^{a_{2}},&v=\nu ^{-a_{1}a_{2}},&v_{2}=\nu ^{a_{1}}\cdot g^{\delta _{v_{2}}},\\\tau _{1}=vv_{1}^{a_{1}}=g^{\delta _{v_{1}}a_{1}},&\tau _{2}=vv_{2}^{a_{2}}=g^{\delta _{v_{2}}a_{2}},&\tau _{1}^{b}=f^{\delta _{v_{1}}a_{1}},&\tau _{2}^{b}=f^{\delta _{v_{2}}a_{2}}.\end{matrix}}}$

Next, ${\displaystyle {\mathcal {B}}}$ chooses ${\displaystyle \delta _{w}{\xleftarrow {\}}\mathbb {Z} _{p},{\vec {\zeta }}=(\zeta _{1},\cdots ,\zeta _{n}){\xleftarrow {\}}\mathbb {Z} _{p}^{n},{\vec {\delta }}=(\delta _{1}\cdots \delta _{2}){\xleftarrow {\}}\mathbb {Z} _{p}^{n}}$, then defines ${\displaystyle w=g^{a_{0}}=f\cdot g^{\delta _{w}}}$, and ${\displaystyle h_{i}=g^{\alpha _{i}}=f^{\zeta _{i}}\cdot g^{\delta _{i}}}$ for ${\displaystyle i=1,\cdots ,n}$. Note that, as in the proof of lemma 2 in [19] , ${\displaystyle {\mathcal {B}}}$ knows ${\displaystyle {\text{msk}}=(g^{\alpha },g^{\alpha a_{1}},v,v_{1},v_{2})}$.

Key Queries. When ${\displaystyle {\mathcal {A}}}$ makes the ${\displaystyle j^{\text{th}}}$ private key query, ${\displaystyle {\mathcal {B}}}$ does as follows.

[Case ${\displaystyle j>k}$] It generates a normal key, using the master secret key ${\displaystyle {\text{msk}}}$.

[Case ${\displaystyle j] It creates a semi-functional key, which it can do using ${\displaystyle g^{a_{1}a_{2}}}$.

[Case ${\displaystyle j>k}$] It defines ${\displaystyle {\text{tagk}}_{2},\cdots ,{\text{tagk}}_{n}}$ as ${\displaystyle {\text{tagk}}_{i}=\zeta _{1}\cdot {\frac {x_{i}}{x_{1}}}-\zeta _{i}}$ for ${\displaystyle i=2\cdots ,n}$,

which implies that ${\displaystyle (h_{1}^{-x_{i}/x_{1}}\cdot h_{i}\cdot w^{{\text{tagk}}_{i}})=g^{-\delta _{1}(x_{i}/x_{1})+\delta _{i}+\delta _{w}{\text{tagk}}_{i}}}$, for ${\displaystyle i=2\cdots ,n}$.

Using these tags, it generates a normal private key ${\displaystyle (D'_{1},\cdots ,D'_{7},K'_{2},\cdots ,K'_{n})}$ using random exponents ${\displaystyle r'_{1},r'_{2},z'_{2}{\xleftarrow {\}}\mathbb {Z} _{p}}$. Then, it sets ${\displaystyle {\begin{matrix}D_{1}=D'_{1}\cdot \eta ^{-a_{1}a_{2}},&D_{2}=D'_{2}\cdot \eta ^{a_{2}}\cdot (g^{\theta _{1}})^{\delta _{v_{1}}},&D_{3}=D'_{3}\cdot (f^{\theta _{2}})^{\delta _{v_{1}}},\\D_{4}=D'_{4}\cdot \eta ^{a_{1}}\cdot (g^{\theta _{1}})^{\delta _{v_{2}}},&D_{5}=D'_{5}\cdot (f^{\theta _{2}})^{\delta _{v_{2}}},&D_{6}=D'_{6}\cdot f^{\theta _{2}},\end{matrix}}}$

as well as ${\displaystyle D_{7}=D'_{7}\cdot (g^{\theta _{1}})}$ and ${\displaystyle K_{i}=K'_{i}\cdot (g^{\theta _{1}})^{-\delta _{1}(x_{i}/x_{1})+\delta _{i}+\delta _{w}{\text{tagk}}_{i}}}$ for ${\displaystyle i=2\cdots ,n}$.

If ${\displaystyle \eta =\nu ^{\theta _{1}+\theta _{2}},sk_{\bar {X}}=(D_{1},\cdots ,D_{7},K_{2},\cdots ,K_{n},{\text{tagk}}_{2},\cdots ,{\text{tagk}}_{n})}$ is easily seen to form a normal key where ${\displaystyle r_{1}=r'_{1}+\theta _{1},r_{2}=r'_{2}+\theta _{2},z_{1}=z'_{1}-\delta _{v_{1}}\theta _{2},z_{2}=z'_{2}-\delta _{v_{2}}\theta _{2}}$ are the underlying random exponents. If ${\displaystyle \eta \in _{R}\mathbb {G} }$, it can be written ${\displaystyle \eta =\nu ^{\theta _{1}+\theta _{2}}\cdot g^{\gamma }}$ for some ${\displaystyle \gamma \in _{R}\mathbb {Z} _{p}}$, so that ${\displaystyle sk_{\bar {X}}}$ is distributed as a semi-functional key. We note that ${\displaystyle {\text{tagk}}_{2},\cdots ,{\text{tagk}}_{n}}$ are independent and uniformly distributed since ${\displaystyle \zeta _{1}\cdots \zeta _{n}}$ (which are the solutions of a system of ${\displaystyle n-1}$ equations with ${\displaystyle n~\,\!}$ unknowns) are uniformly random and perfectly hidden from ${\displaystyle {\mathcal {A}}}$'s view.

Challenge. ${\displaystyle {\mathcal {A}}}$ outputs ${\displaystyle M_{0},M_{1}\in \mathbb {G} _{T}}$ along with a vector ${\displaystyle {\vec {Y}}^{*}=(y_{1}^{*},\cdots ,y_{n}^{*})}$. ${\displaystyle {\mathcal {B}}}$ flips a coin ${\displaystyle {\mathcal {B}}{\xleftarrow {\}}\{0,1\}}$ and computes the tag ${\displaystyle {\text{tagc}}*=-\langle {\vec {Y}}^{*},{\vec {zeta}}\rangle }$ for which ${\displaystyle {\mathcal {B}}}$ will be able to prepare the semi-functional ciphertext. To this end, ${\displaystyle {\mathcal {B}}}$ first computes a normal encryption ${\displaystyle (C'_{0},C;_{1},\cdots ,C'_{7},E_{1}',E_{2}',{\text{tagc}}*)}$ of ${\displaystyle M_{\beta }}$ using exponents ${\displaystyle s'_{1},s'_{2},t'}$. It then chooses ${\displaystyle \chi {\xleftarrow {\mathbb {Z} }}_{p}}$ and computes

${\displaystyle {\begin{matrix}C_{4}=C'_{4}\cdot f^{a_{2}\cdot \chi },&C_{5}=C'_{5}\cdot g^{a_{2}\cdot \chi },&C_{7}=C'_{7}\cdot \nu ^{-\delta _{w}\cdot a_{1}\cdot a_{2}\cdot \chi }\cdot f^{\delta _{v_{2}}\cdot a_{2}\cdot \chi },\\C_{6}=C'_{6}\cdot v^{a_{2}\cdot \chi },&E_{2}=E'_{2}\cdot v^{a_{1}\cdot a_{2}\cdot \chi },&E_{1}=E'_{1}\cdot (\nu ^{\delta _{w}\cdot {\text{tagc}}^{*}+\langle {\bar {Y}}^{*},{\bar {\delta }}\rangle })^{a_{1}\cdot a_{2}\cdot \chi }.\end{matrix}}}$

We claim that ${\displaystyle (C_{0}',C_{1}',C_{2}',C_{3}',C_{4},C_{5},C_{6},C_{7},E_{1},E_{2},{\text{tagc}}^{*})}$ is a semi-functional ciphertext with underlying exponents ${\displaystyle \chi ,s_{1}=s'_{1},s_{2}=s'_{2}}$ and ${\displaystyle t=t'+log_{g}(\nu )a_{1}a_{2}\chi }$. To prove this, we observe that

{\displaystyle {\begin{alignedat}{2}C_{7}&=T_{1}^{s_{1}}\cdot T_{2}^{s_{2}}\cdot w^{-t}\cdot v_{2}^{a_{2}b\chi }=T_{1}^{s_{1}}\cdot T_{2}^{s_{2}}\cdot w^{-t'-\log _{g}(\nu )a_{1}a_{2}\chi }\cdot (\nu ^{a_{1}}\cdot g^{\delta _{v_{2}}})^{a_{2}b\chi }\\&=T_{1}^{s_{1}}\cdot T_{2}^{s_{2}}\cdot w^{-t'}\cdot (f\cdot g^{\delta _{w}})^{-\log _{g}(\nu )a_{1}a_{2}\chi }\cdot (\nu ^{a_{1}}\cdot g^{\delta _{v_{2}}})^{a_{2}b\chi }\\&=C'_{7}\cdot \nu ^{-\delta _{w}a_{1}a_{2}\chi }\cdot f^{\delta _{v_{2}}a_{2}\chi },\end{alignedat}}}

where the unknown term in ${\displaystyle v_{2}^{a_{2}b_{\chi }}}$ is canceled out by ${\displaystyle w^{-t}}$. Also,

{\displaystyle {\begin{alignedat}{2}E_{1}&=E'_{1}\cdot (h_{1}^{y_{1}^{*}}\cdots h_{n}^{y_{n}^{*}}\cdot w^{{\text{tagc}}^{*}})^{\log _{g}(\nu )a_{1}a_{2}\chi }\\&=E'_{1}\cdot {\Big (}(f^{\zeta _{1}}g^{\delta _{1}})^{y_{1}^{*}}\cdots (f^{\zeta _{n}}g^{\delta _{n}})^{y_{n}^{*}}\cdot (fg^{\delta _{w}})^{-\langle {\bar {Y}}^{*},{\bar {\zeta }}\rangle }{\Big )}^{\log _{g}(\nu )a_{1}a_{2}\chi }\\&=E'_{1}\cdot (\nu ^{\langle {\bar {Y}}^{*},{\bar {\zeta }}\rangle +\delta _{w}\cdot {\text{tagc}}^{*}})^{a_{1}a_{2}\chi },\end{alignedat}}}

where the unknown ${\displaystyle f^{\log _{g}(\nu )}}$ vanishes due to our definition of ${\displaystyle {\text{tagc}}^{*}}$. It then remains to show that ${\displaystyle {\text{tagc}}^{*},{\text{tagk}}_{2},\cdots ,{\text{tagk}}_{n}}$ are still ${\displaystyle n~\,\!}$-wise independent. But this holds since their relations form a system

${\displaystyle M\cdot {\vec {\zeta }}:={\begin{pmatrix}-{\frac {x_{2}}{x_{1}}}&1&&&\\-{\frac {x_{3}}{x_{1}}}&&1&&\\\vdots &&&\ddots &\\-{\frac {x_{n}}{x_{1}}}&&&&1\\y_{1}^{*}&y_{2}^{*}&y_{3}^{*}&\cdots &y_{n}^{*}\end{pmatrix}}{\begin{pmatrix}\zeta _{1}\\\zeta _{2}\\\vdots \\\\\zeta _{n}\end{pmatrix}}=-{\begin{pmatrix}{\text{tagk}}_{2}\\{\text{tagk}}_{3}\\\vdots \\{\text{tagk}}_{n}\\{\text{tagc}}^{*}\end{pmatrix}},}$

which has a solution in ${\displaystyle {\vec {\zeta }}}$ whenever ${\displaystyle \det(M)=(-1)^{n+1}{\vec {X}}\cdot {\vec {Y}}^{*}/x_{1}\neq 0}$.

Eventually, ${\displaystyle {\mathcal {A}}}$ outputs a bit ${\displaystyle \beta '}$ and ${\displaystyle {\mathcal {B}}}$ outputs 0 if ${\displaystyle \beta =\beta '}$. As in [19], we see that ${\displaystyle {\mathcal {A}}}$ is playing ${\displaystyle {\text{Game}}_{k-1}}$ if ${\displaystyle \eta =\nu ^{\theta _{1}+\theta _{2}}}$ and ${\displaystyle {\text{Game}}_{k}}$ otherwise.

Lemma 3
If DBDH is hard, ${\displaystyle {\text{Game}}_{q}}$ and ${\displaystyle {\text{Game}}_{q+1}}$ 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 ${\displaystyle R^{{\text{Neg}}({\text{Spatial}})}:{\mathcal {W}}_{n}\times \mathbb {Z} _{p}^{n}\leftarrow {0,1}}$, where we define a collection ${\displaystyle {\mathcal {W}}\subseteq {\mathcal {V}}_{n}}$ of vector subspaces in ${\displaystyle \mathbb {Z} _{p}^{n}}$ as ${\displaystyle {\mathcal {W}}_{n}=\{{\text{Aff}}(M,{\vec {0}})\in {\mathcal {V}}_{n}{\big |}{\text{rank}}(M_{(-1)})=n-1\}}$, where we denote ${\displaystyle M_{(-1)}}$ as the matrix obtained by deleting the first row ${\displaystyle M_{1}\in \mathbb {Z} _{p}^{1\times d}\ {\text{of}}\ M}$.

Construction 4. (Co-selectively secure negated spatial encryption)
${\displaystyle \blacktriangleright }$${\displaystyle {\text{Setup}}(1^{\lambda ,n})}$: chooses bilinear groups ${\displaystyle \mathbb {G} }$ of prime order ${\displaystyle p>2^{\lambda }}$ with a random generator ${\displaystyle g{\xleftarrow {\}}\mathbb {G} _{p}}$. It randomly chooses ${\displaystyle \alpha _{1},\cdots ,\alpha _{n}{\xleftarrow {\}}\mathbb {Z} _{p}}$ Let ${\displaystyle {\vec {\alpha }}=(\alpha _{1},\cdots ,\alpha _{n})}$. The public key is ${\displaystyle {\text{pk}}=(g,g^{\bar {\alpha }},g^{\alpha _{1}{\bar {\alpha }}},e(g,g)^{\alpha })}$. The master key is ${\displaystyle {\text{msk}}=(\alpha ,{\vec {\alpha }})}$.
${\displaystyle \blacktriangleright }$${\displaystyle {\text{KeyGen}}(V,{\text{msk}},{\text{pk}})}$: suppose that ${\displaystyle V={\text{Aff}}(M,{\vec {0}})}$, from a matrix ${\displaystyle M\in (\mathbb {Z} _{p})^{n\times d}}$. The algorithm picks ${\displaystyle t{\xleftarrow {\}}\mathbb {Z} _{p}}$ and outputs ${\displaystyle sk_{V}=(D_{0},D_{1},{\vec {K}})\in \mathbb {G} ^{d+2}}$ where

${\displaystyle \qquad D_{0}=g^{t},\qquad D_{1}=g^{\alpha +t\alpha _{1}^{2}},\qquad {\vec {K}}=g^{tM^{\top }{\vec {\alpha }}}}$.

${\displaystyle \blacktriangleright }$${\displaystyle {\text{Encrypt}}({\vec {y}},M,{\text{pk}})}$: picks ${\displaystyle s{\xleftarrow {\}}\mathbb {Z} _{p}}$ and computes ${\displaystyle (C_{0},C_{1},C_{2},C_{3})}$ as

${\displaystyle C_{0}=M\cdot e(g,g)^{\alpha s},\qquad C_{1}=g^{s\alpha _{1}\langle {\bar {y}},{\bar {\alpha }}\rangle },\qquad C_{2}=g^{s}\qquad C_{3}=g^{\alpha _{1}s}}$.

${\displaystyle \blacktriangleright }$${\displaystyle {\text{Decrypt}}(C,{\vec {y}},{\text{sk}}_{V},V,{\text{pk}})}$: the algorithm first obtains ${\displaystyle M~\,\!}$ from ${\displaystyle V~\,\!}$. We also recall the the notation of ${\displaystyle M_{1}}$, which is the vector of the first row of ${\displaystyle M~\,\!}$. It first solves the system of equations in ${\displaystyle {\vec {\omega }}}$ from ${\displaystyle M_{(-1)}{\vec {\omega }}=(y_{2},\cdots ,y_{n})^{top}}$, which it can do since ${\displaystyle V\in {\mathcal {W}}_{n}}$. It computes the message blinding factor ${\displaystyle e(g,g)^{\alpha s}}$ as
${\displaystyle e(D_{1},C_{2})\cdot {\Bigg (}{\frac {e(C_{1},D_{0})}{e({\vec {K}}^{\vec {\omega }},C_{3})}}{\Bigg )}^{\frac {1}{M_{1}{\bar {w}}-y_{1}}}=e(g^{\alpha +t\alpha _{1}^{2}},g^{s})\cdot {\Bigg (}{\frac {e(g^{s\alpha _{1}\langle {\bar {y}},{\bar {\alpha }}\rangle },g^{t})}{g^{t{\bar {\omega }}^{\top }M^{\top }{\vec {\alpha }}},g^{\alpha _{1}s}}}{\Bigg )}^{\frac {1}{M_{1}{\vec {w}}-y_{1}}}}$.

Computability. We claim that the decryption can be computed if ${\displaystyle y\notin V}$. Indeed, we prove that if ${\displaystyle y\notin V}$ then ${\displaystyle M_{1}{\vec {\omega }}-y_{1}\neq 0}$ (and the above equation is well-defined). To prove the contrapositive, suppose that ${\displaystyle M_{1}{\vec {\omega }}-y_{1}=0}$ Then, we must have ${\displaystyle {\vec {y}}\in V}$ since ${\displaystyle M{\vec {\omega }}={\begin{bmatrix}M_{1}\\M_{(-1)}\end{bmatrix}}{\vec {\omega }}={\begin{bmatrix}M_{1}{\vec {\omega }}\\M_{(-1)}{\vec {\omega }}\end{bmatrix}}={\vec {y}}}$.

Correctness. We verify that decryption is correct as follows. First, we note that due to our definition of ${\displaystyle {\vec {\omega }}}$, we have ${\displaystyle \langle M{\vec {w}}-{\vec {y}},{\vec {\alpha }}\rangle =(M_{1}{\vec {\omega }}-y_{1})\alpha _{1}}$. Therefore, the correctness follows from the fact that

 ${\displaystyle {\Bigg (}{\frac {e(g^{s\alpha _{1}\langle {\bar {y}},{\bar {\alpha }}\rangle },g^{t})}{g^{t{\bar {\omega }}^{\top }M^{\top }{\vec {\alpha }}},g^{\alpha _{1}s}}}{\Bigg )}^{\frac {1}{M_{1}{\vec {w}}-y_{1}}}={\Bigg (}{\frac {1}{e(g,g)^{ts\alpha _{1}\langle M{\bar {\omega }}-{\bar {y}},{\bar {\alpha }}\rangle }}}{\Bigg )}^{\frac {1}{M_{1}{\bar {\omega }}-y_{1}}}=e(g,g)^{-st\alpha _{1}^{2}}}$

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)
Proof
Without proof

Implications. For a vector ${\displaystyle {\vec {X}}\in \mathbb {Z} _{p}^{n}}$, the embedding ${\displaystyle V_{\bar {X}}={\text{Aff}}(M_{\bar {X}},{\vec {0}}_{n})}$ defined in Eq.(3) is easily seen to be in the limited domain ${\displaystyle {\mathcal {W}}_{n}}$ since ${\displaystyle (M_{\bar {X}})_{(-1)}}$ is an identity matrix of size ${\displaystyle n-1}$ and bence ${\displaystyle {\text{rank}}((M_{\bar {X}})_{(-1)})=n-1}$. 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)
${\displaystyle \blacktriangleright }$${\displaystyle {\text{Setup}}(1^{\lambda ,n})}$: outputs pk exactly as in the construction 3 except that we define ${\displaystyle \omega =g^{\alpha _{1}}(=h_{1})}$ in this scheme, instead of ${\displaystyle g^{\alpha _{0}}}$.
${\displaystyle \blacktriangleright }$${\displaystyle {\text{KeyGen}}({\vec {X}},{\text{msk}},{\text{pk}})}$: outputs ${\displaystyle {\text{sk}}_{\bar {X}}=({\text{sk}}_{\text{adapt}},{\text{sk}}_{\text{core}})}$ where ${\displaystyle {\text{sk}}_{\text{adapt}}}$ is the same as in the construction 3 (with ${\displaystyle \omega =g^{\alpha _{1}})}$ and ${\displaystyle {\text{sk}}_{\text{core}}=\{K_{i}=(g^{-\alpha _{1}{\frac {x_{i}}{x_{1}}}}\cdot g^{\alpha _{i}})^{r_{1}}\}_{i=2,\cdots ,n}}$.
${\displaystyle \blacktriangleright }$${\displaystyle {\text{Encrypt}}({\vec {Y}},M,{\text{pk}})}$: outputs ${\displaystyle C=(C_{\text{adapt}},C_{\text{core}})}$ where ${\displaystyle C_{\text{adapt}}}$ is as in the construction 3 (with ${\displaystyle \omega =g^{\alpha _{1}}}$) and ${\displaystyle C_{\text{core}}=(E_{0}=M\cdot Z^{s_{2}},E_{1}=(g^{\langle {\bar {\alpha }},{\bar {Y}}\rangle })^{t},E_{2}=g^{t}).}$
${\displaystyle \blacktriangleright }$${\displaystyle {\text{Decrypt}}(C,{\vec {Y}},{\text{sk}}_{\bar {X}},{\vec {X}},{\text{pk}})}$: computes ${\displaystyle W_{1}}$ as in the construction 3 and ${\displaystyle W_{2}}$ as ${\displaystyle W_{2}={\Bigg (}{\frac {e(K_{2}^{y_{2}}\cdots K_{n}^{y_{n}},E_{2})}{e(E_{1},D_{7})}}{\Bigg )}^{-{\frac {x_{1}}{{\bar {X}}\cdot {\bar {Y}}}}}=e(g,\omega )^{r_{1}t}}$. (See appendix A.2).

Theorem 4
Construction 5 is co-selectively secure under the DLIN and DBDH assumptions.
Proof
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 ${\displaystyle R^{{\text{NIPE}}_{n}}:\mathbb {Z} _{p}^{n}\times \mathbb {Z} _{p}^{n}\rightarrow \{0,1\}}$ can be extended so as to support relations of the form ${\displaystyle R^{{\text{NIPE}}_{n}^{*}}:\mathbb {Z} _{p}^{n}\times (\mathbb {Z} _{p}^{n})^{d}\rightarrow \{0,1\}}$, for some ${\displaystyle d\in {\text{poly}}(\lambda )}$, and defined as ${\displaystyle R^{{\text{NIPE}}_{n}^{*}}({\vec {X}},({\vec {Y}}_{1},\cdots ,{\vec {Y}}_{d}))=1\ {\text{iff for all}}\ i=1,\cdots ,d:{\vec {X}}\cdot {\vec {Y}}_{i}\neq 0}$.

We construct this extended system by setting up exactly the same public and private keys (for ${\displaystyle {\vec {X}}}$) as in the original scheme. To encrypt to ${\displaystyle ({\vec {Y}}_{1},\cdots ,{\vec {Y}}_{d})}$, the scheme generates ${\displaystyle C_{0},\cdots ,C_{7}}$ as usual with the underlying exponents ${\displaystyle s_{1},s_{2},t}$. Then, it chooses ${\displaystyle t_{1},\cdots ,t_{d}\in \mathbb {Z} _{p}}$ so that ${\displaystyle t=t_{1}+\cdots +t_{d}}$ and for ${\displaystyle i=1,\cdots ,d}$, parses ${\displaystyle {\vec {Y}}_{i}=(y_{i,1},\cdots ,y_{i,n})}$ and computes ${\displaystyle E_{1,i}=(g^{\langle {\vec {\alpha }},{\vec {Y}}_{i}\rangle })^{t_{i}}=(h_{1}^{y_{i},1}\cdots h_{n}^{y_{i},n})^{t_{i}}}$ and ${\displaystyle E_{2,i}=g^{t_{i}}}$, in such a way that the ciphertext is ${\displaystyle (C_{0},\cdots ,C_{7},\{E_{1,i},E_{2,i}\}_{i=1,\cdots ,d})}$. Decryption requires to first compute

${\displaystyle W_{2,i}={\Bigg (}{\frac {e(K_{2}^{y_{2}}\cdots K_{n}^{y_{n}},E_{2,i})}{e(E_{1,i},D_{7})}}{\Bigg )}^{-{\frac {x_{1}}{{\bar {X}}\cdot {\bar {Y}}_{i}}}}=e(g,\omega )^{r_{1}t_{i}},}$

for ${\displaystyle i=1,\cdots ,d,}$ from which the receiver obtains ${\displaystyle W_{2}=W_{2,1}\cdots W_{2,d}=e(g,\omega )^{r_{1}t}}$. 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 ${\displaystyle (IBR_{\leq n})}$ from our non-zero inner-product system ${\displaystyle {\text{NIPE}}_{n+1}}$ yields a construction with ${\displaystyle \mathrm {O} (1)}$-size ciphertexts and ${\displaystyle \mathrm {O} (n)}$-size private keys, where n denotes the maximal number of revoked users.

From our extended scheme ${\displaystyle {\text{NIPE}}_{n+1}^{*},}$ we can obtain an ID-based revocation scheme ${\displaystyle {\text{IBR}}_{{\text{poly}}(\lambda )}}$, without a fixed maximal number of revoked users. To revoke the set ${\displaystyle R~\,\!}$ where ${\displaystyle |R|=r}$, we divide it into a disjointed union ${\displaystyle R=R_{1}\cup \cdots \cup R_{r/n}}$, where ${\displaystyle |R_{i}|=n}$ for all ${\displaystyle i~\,\!}$ (we assume that ${\displaystyle n~\,\!}$ divides ${\displaystyle r~\,\!}$). We then simply construct the vector ${\displaystyle {\vec {Y}}_{i}}$ from the revocation subset ${\displaystyle R_{i}}$ for each ${\displaystyle i\in [1,r/n]}$, in the same way as we use ${\displaystyle {\text{NIPE}}_{n+1}}$ to instantiate ${\displaystyle IBR_{\leq n}}$. We then finally encrypt using the set of vectors ${\displaystyle ({\vec {Y}}_{1},\cdots ,{\vec {Y}}_{r/n})}$. The correctness and security properties hold since ${\displaystyle R^{IBR_{\leq n}}({\text{ID}},R)=1\Leftrightarrow R^{IBR_{{\text{poly}}(\lambda )}}({\text{ID}},(R_{1},\cdots ,R_{r/n}))=1}$. The construction has ${\displaystyle \mathrm {O} (r/n)}$-size ciphertexts and ${\displaystyle \mathrm {O} (n)}$-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 ${\displaystyle n=1}$.

## A Verifying Correctness in Decryption

### A.1 For the Zero IPE Scheme of Section 4.2

{\displaystyle {\begin{alignedat}{2}W_{2}&={\Bigg (}{\frac {e(\textstyle \prod _{i=2}^{n}K_{i}^{y_{i}},E_{2})}{e(E_{1},D_{7})}}{\Bigg )}^{\frac {1}{{\text{tagk}}-{\text{tagc}}}}={\Bigg (}{\frac {e(\textstyle \prod _{i=2}^{n}(g^{-\alpha _{1}{\frac {x_{i}}{x_{1}}}}g^{\alpha _{i}}w^{{\text{tagk}}_{i}})^{r_{1}y_{i}},g^{t})}{e{\Big (}(g^{\langle {\bar {\alpha }},{\bar {Y}}\rangle }\cdot w^{\text{tagc}})^{t},g^{r_{1}}{\Big )}}}{\Bigg )}^{\frac {1}{{\text{tagk}}-{\text{tagc}}}}\\&={\Bigg (}{\frac {e{\Big (}(g^{-\alpha _{1}{\frac {x_{2}y_{2}+\cdots +x_{n}y_{n}}{x_{1}}}}g^{\alpha _{2}y_{2}+\cdots +\alpha _{n}y_{n}}w^{{\text{tagk}}_{2}y_{2}+\cdots +{\text{tagk}}_{n}y_{n}})^{r_{1}},g^{t}{\Big )}}{e{\Big (}(g^{\alpha _{1}y_{1}+\alpha _{2}y_{2}+\cdots +\alpha _{n}y_{n}}\cdot w^{\text{tagc}})^{t},g^{r_{1}}{\Big )}}}{\Bigg )}^{\frac {1}{{\text{tagk}}-{\text{tagc}}}}\\&={\Bigg (}e{\Big (}g^{-\alpha _{1}{\frac {x_{2}y_{2}+\cdots +x_{n}y_{n}}{x_{1}}}}w^{{\text{tagk}}-{\text{tagc}}},g{\Big )}^{\frac {r_{1}t}{{\text{tagk}}-{\text{tagc}}}}\\&=e{\Big (}g^{-\alpha _{1}{\frac {{\bar {X}}\cdot {\bar {Y}}}{x_{1}}}}w^{{\text{tagk}}-{\text{tagc}}},g{\Big )}^{\frac {r_{1}t}{{\text{tagk}}-{\text{tagc}}}}=e(g,w)^{r_{1}t}.\end{alignedat}}}

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

{\displaystyle {\begin{alignedat}{2}W_{2}&={\Bigg (}{\frac {e(\textstyle \prod _{i=2}^{n}K_{i}^{y_{i}},E_{2})}{e(E_{1},D_{7})}}{\Bigg )}^{-{\frac {x_{1}}{{\vec {X}}\cdot {\vec {Y}}}}}={\Bigg (}{\frac {e(\textstyle \prod _{i=2}^{n}(g^{-\alpha _{1}{\frac {x_{i}}{x_{1}}}}g^{\alpha _{i}})^{r_{1}y_{i}},g^{t})}{e{\Big (}(g^{\alpha _{1}y_{1}+\cdots +\alpha _{n}y_{n}})^{t},g^{r_{1}}{\Big )}}}{\Bigg )}^{-{\frac {x_{1}}{{\vec {X}}\cdot {\vec {Y}}}}}\\&={\Bigg (}{\frac {e{\Big (}(w^{-{\frac {x_{2}y_{2}+\cdots +x_{n}y_{n}}{x_{1}}}}g^{\alpha _{2}y_{2}+\cdots +\alpha _{n}y_{n}})^{r_{1}},g^{t}{\Big )}}{e{\Big (}(w^{y_{1}}\cdot g^{\alpha _{2}y_{2}+\alpha _{2}y_{2}+\cdots +\alpha _{n}y_{n}})^{t},g^{r_{1}}{\Big )}}}{\Bigg )}^{-{\frac {x_{1}}{{\vec {X}}\cdot {\vec {Y}}}}}\\&=e{\Big (}w^{\frac {{\bar {X}}\cdot {\bar {Y}}}{x_{1}}},g{\Big )}^{r_{1}t\cdot {\frac {x_{1}}{{\vec {X}}\cdot {\vec {Y}}}}}=e(g,w)^{r_{1}t}.\end{alignedat}}}

## Authors

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

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

## Notations

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

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

## References

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. 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. R. Sakai, J. Furukawa. Identity-Based Broadcast Encryption. In Cryptology ePrint Archive: Report 2007/217, http://eprint.iacr.org/2007/217, 2007.
8. C. Delerablee. Identity-Based Broadcast Encryption with Constant Size Ciphertexts and Private Keys. In Asiacrypt'07, LNCS 4833, pp. 200-215, 2007.
9. D. Boneh, M. Hamburg. Generalized Identity Based and Broadcast Encryption Schemes. In Asiacrypt'08, LNCS 5350, pp. 455-470, 2008.
10. 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. 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. 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. 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. 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. 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. 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