Michel Abdalla
email: michel.abdalla@ens.fr

Dario Catalano
email: catalano@dmi.unict.it

Romain Gay
email: romain.rgay@gmail.com

Bogdan Ursu
email: bogdan.ursu@inf.ethz.ch

Inner-Product Functional Encryption with Fine-Grained Access Control

We construct new functional encryption schemes that combine the access control functionality of attributebased encryption with the possibility of performing linear operations on the encrypted data. While such a primitive could be easily realized from fully fledged functional encryption schemes, what makes our result interesting is the fact that our schemes simultaneously achieve all the following properties. They are public-key, efficient and can be proved secure under standard and well established assumptions (such as LWE or pairings). Furthermore, security is guaranteed in the setting where adversaries are allowed to get functional keys that decrypt the challenge ciphertext. Our first results are two functional encryption schemes for the family of functions that allow users to embed policies (expressed by monotone span programs) in the encrypted data, so that one can generate functional keys to compute weighted sums on the latter. Both schemes are pairing-based and quite generic: they combine the ALS functional encryption scheme for inner products from Crypto 2016 with any attribute-based encryption schemes relying on the dual-system encryption methodology. As an additional bonus, they yield simple and elegant multi-input extensions essentially for free, thereby broadening the set of applications for such schemes. Multi-input is a particularly desirable feature in our setting, since it gives a finer access control over the encrypted data, by allowing users to associate different access policies to different parts of the encrypted data. Our second result builds identity-based functional encryption for inner products from lattices. This is achieved by carefully combining existing IBE schemes from lattices with adapted, LWE-based, variants of ALS. We point out to intrinsic technical bottlenecks to obtain richer forms of access control from lattices. From a conceptual point of view, all our results can be seen as further evidence that more expressive forms of functional encryption can be realized under standard assumptions and with little computational overhead.

Introduction

Public-key encryption allows the owner of a secret key sk to decrypt any ciphertext created with respect to a corresponding public key pk. At the same time, without sk, one should not be able to extract any information whatsoever about the encrypted plaintext. This all-or-nothing feature is becoming restrictive nowadays as, in many applications, a much more fine grained access control to data is required. Functional encryption addresses this need by providing an encryption mechanism where decryption keys are associated with functions. Specifically, given a ciphertext Enc(m) and a secret key sk f associated to some function f , the holder of sk f learns f (m) and nothing else.

Security for functional encryption is formalized via a variant of the standard indistinguishability notion. In a nutshell, this notion states that an adversary who is allowed to see secret keys corresponding to functions f 1 , . . . f n should not be able to say which of the challenge messages m 0 or m 1 has been encrypted, as long as f i (m 0 ) = f i (m 1 ), for all i. This indistinguishability notion has been proposed in [BSW11, O'N10] and shown inadequate for certain, somewhat complex, functionalities. These authors also suggested an alternative, simulation based, security notion that however turns out to be impossible to achieve for general functionalities without introducing additional restrictions. See [BSW11, O'N10] for details.

Since its introduction, functional encryption has attracted a lot of interest. Known results can be broadly categorized as focusing on (1) feasibility results for general functionalities, and on (2) concrete, efficient realizations for restricted functionalities of practical interest. Constructions of the first type are all horrendously inefficient. Also, they either rely on quite unstable assumptions (e.g. indistinguishability obfuscation) or impose severe restrictions on the number of secret keys that can be issued. Constructions of the second type, on the other hand, are known only for the case of linear functions and quadratic functions. Over the last few years, significant research efforts have been devoted to the quest of improving these constructions along different directions. For the case of the inner-product functionality (IPFE) [ABDP15], this meant, for instance, improved security guarantees (e.g. [ALS16, ABDP16, BBL17, CLT18]), function hiding realizations (e.g. [BJK15, DDM16, DOT18]), multi-input extensions (e.g. [AGRW17, ACF + 18]), decentralized schemes (e.g. [CDG + 18,ABKW19,LT19,ABG19]), unbounded-size vectors (e.g. [TT18,DP19]) and specialized variants (e.g. [BCSW19]). For the case of quadratic functions, current schemes are limited to [BCFG17,Gay20] in the public-key setting. Note that FE for inner products, which is the focus of this work, can be used a building block to obtain FE for quadratic functions. This fact, implicit in [BCFG17], is made explicit in [Gay20] and in the private-key variants [AS17,Lin17].

In spite of these efforts, only a few convincing practical applications of the primitive have been proposed so far. Notable examples include the recent non interactive protocol for hidden-weight coin flips from [CS19], a practical construction of function-hiding inner product FE with applications such as in biometric authentication, nearest-neighbor search on encrypted data in [KLM + 18], an application of functional encryption for quadratic functions for performing private inference on encrypted data in [RPB + 19].

A possible explanation for this is that, behind its charming theoretical appearance, functional encryption hides a fragile and potentially dangerous nature: each new released secret key inherently leaks information. This becomes particularly painful for the case of inner products, as, when encrypting plaintexts of length, say, n, holding n secret keys allows, in general, to recover the full plaintext completely. While this might seem inherent in the nature of IPFE, one might wonder if additional measures might be put in place to reduce leakage and make the primitive more appealing for applications. Think for instance of the case of a medical database. To preserve privacy while maintaining the possibility of performing simple descriptive statistics (such as the weighted mean) on the data, one might decide to encrypt the database using IPFE. A drawback of this solution, however, is that the confidentiality of the whole database is compromised if a sufficiently large number of different keys is released. This is problematic since this threshold might be easy to reach when many users access the database.

A natural way to limit the inherent information leakage of existing IPFE schemes would be to use FE primitives with more sophisticated functionalities. Ideally, this primitive should allow to embed access policies in the (encrypted) data while allowing to compute weighted sums on the latter. More precisely, each key should allow to obtain the desired inner product only when some appropriate access policy is satisfied. Going back to our medical example, this means that the confidentiality of a particular database entry would be compromised only if sufficiently many different keys satisfying the ciphertext policy associated with that entry are released.

Another way to look at the question, is providing additional security guarantees with respect to basic identity or attribute based encryption schemes. These typically control who is authorized to decrypt the data. Still, once the data is accessed, no additional control is possible: authorized users get the full information, while others get nothing. In this sense, it is natural to consider encryption primitives that, beyond access control, also permit to more carefully tune the information leakage.

Notice that the mechanisms above are easy to realize if one is willing to resort to functional encryption schemes for general functionalities. The trouble with this is that such a solution would be of little (if any) practical interest. Our goal, on the other hand, is to develop a scheme that implements the features above while retaining as much as possible all the nice properties of currently known IPFEs.

This motivates the following question.

Is it possible to develop an efficient, public-key, functional encryption scheme that allows users both to embed access policies in the encrypted data and to generate decryption keys to compute inner products on the data?

A trivial generic approach. Since ABE and IPFE are both well-studied primitives, the first natural question is whether we can easily combine existing schemes to achieve our target notion. In the target scheme, each ciphertext is associated with a predicate P and encrypts a vector x. Each functional decryption key sk y,att is associated with an attribute att and a vector y. Decryption recovers x, y if P(att) = 1. If it is not the case, no information about x should be revealed. Now, consider the approach of encrypting a plaintext via an IPFE and then encrypting the resulting ciphertext via the ABE. This is not secure against collusions as, once the outer ciphertext is decrypted, the inner one becomes completely independent from the ABE. To see why, assume we have keys for sk y0,att0 and sk y1,att0 and a ciphertext ct, encrypting a vector x under the predicate P such that P(att 0 ) = 1 and P(att 1 ) = 0. The trivial solution allows to use sk y0,att0 to obtain the original IPFE ciphertext, which can then be used with sk y1,att1 to obtain x, y 1 (even though we should only have been able to compute x, y 0 ). This means that mix-and-match attacks are possible. In fact, there seems to be no trivial solution to this problem.

Another trivial generic approach. One other approach to limit the leakage is by encrypting various databases under a different IPFE public key for every recipient. Apart from the fact that this leads to a prohibitive blow-up in size, it would not be possible to agregate data between different databases. Our solution has neither of these limitations and ensures that the ciphertext size is independent of the number of potential recipients.

Our contributions. In this paper, we construct schemes for inner-product functional encryption with fine-grained access control. Our realizations are both efficient and provably secure under standard and well-established assumptions.

The key distinguishing feature of our constructions is that they can be proved secure in the, technically more challenging, setting where the adversary is allowed to (get keys to) decrypt the challenge ciphertext. Let us explain this more in detail. Popular specializations of functional encryption (such as identity-based encryption (IBE) [Sha84,BF01] and attribute-based encryption [SW05, GPSW06]) are ones where the message is interpreted as a pair (I, m), where m is the actual message (often called the "payload") and I is a string, referred to as the index (or in the context of ciphertext-policy ABE [BSW07], a predicate), that can be either public or private. For these schemes, confidentiality of the payload is guaranteed as long as no decryption keys associated with attributes that satisfy the predicate are issued. In our case, we still guarantee a meaningful security notion when keys which allow users to decrypt the payload are issued.

Private-index schemes also provide meaningful security guarantees when keys that decrypt are leaked, namely, they still hide the index in that case. However, as opposed to public-index schemes, for which we have constructions for all circuits from standard assumptions [GVW13, BGG + 14], such schemes can only handle restrictive policies, that are expressed by orthogonality testing (also referred to as inner-product encryption [KSW08]), or assume a weaker security property, called weak attribute hiding, which limits the set of keys that the adversary can get. Namely, this property dictates that the adversary is only allowed to ask secret keys corresponding to functions that cannot be used to decrypt the challenge ciphertext. As observed in [GVW15], a fully attribute-hiding predicate encryption for circuits would bring us tantalizing close to getting indistinguishability obfuscation, which explains why they are much harder to realize in practice.

We consider both public-index schemes where policies are expressive (they can be expressed by monotone span programs, which capture Boolean formulas), and private-index schemes for orthogonality testing (which captures constant depth Boolean formulas). In both settings, we permit a fine-tuned access to the payload, which, from a technical point of view, involve providing security even when the adversary obtains keys that decrypt the challenge ciphertext (even in the public-index case).

IP-FE WITH FINE-GRAINED ACCESS CONTROL FROM PAIRINGS. Our first main result is the construction of functional encryption schemes for the family of functions that allows users to embed policies on the encrypted data, so that one can generate decryption keys that computes weighted sums on the latter. More precisely, in our schemes, each ciphertext is associated with a predicate P and encrypts a (small norm) vector x. Each functional decryption key is associated with an attribute att and a (small norm) vector y. Decryption recovers x, y if att satisfies P. If this is not the case, security guarantees that no information about x is revealed.

Our constructions are quite generic and show that it is possible to combine existing pairing-based attribute-based encryption with the IPFE from [ALS16]. Our construction relies on any attribute-based encryption that uses the dualsystem encryption methodology [Wat09]. In particular, we provide a modular framework that turns any ABE that supports the class of predicates P into a functional encryption scheme for the functions described by an attribute att ∈ U and a vector y, that given as input a vector x and a predicate P ∈ P, outputs x, y if P(att) = 1 and ⊥ otherwise. For correctness to hold we require that both x and y are vectors of polynomially-bounded dimension and norm. We consider both the case where the policy P associated with a ciphertext is public, or at the contrary, remains hidden. As explained previously, leveraging state of the art pairing-based ABE, we obtain an FE for P described by monotone span programs, and an FE for P for any constant depth formula, where the formula itself remains hidden.

From a technical point of view, our first realization combines the IPFE from [ALS16] with any predicate encoding for prime-order pairing groups. In a nutshell, predicate encodings [Wee14,Att14] are a one-time secure, private key, statistical variant of ABE that are much simpler to construct and to deal with. The resulting construction achieves simulation security, but only in a selective sense, and unfortunately this happens to be the case even if the underlying building blocks achieve adaptive security. Informally, this comes from the fact that our security model explicitly allows the adversary to (get keys to) decrypt the challenge ciphertext. Technically, this means that, throughout the security proof, only functional decryption keys associated with pairs (att, y) for which P * (att) = 0 can be turned into semifunctional ones (here P * denotes the predicate chosen by the adversary for the challenge ciphertext). Following the dual-system encryption methodology, semi-functional keys refer to keys that cannot decrypt successfully the challenge ciphertext, but can decrypt correctly any other honestly generated ciphertext. Keys for which P * (att) = 1 cannot be turned semi-functional as otherwise they would fail to (correctly) decrypt the challenge ciphertext. Such a decryption issue does not arise in typical ABE settings, as their security model explicitly prevents the adversary to decrypt the challenge ciphertext.

Our second construction circumvents this difficulty and obtains adaptive security by generalizing the techniques introduced in [OT12], later improved in [CGW18] in the context of fully-hiding predicate encryption for inner product testing. Indeed, in fully-hiding predicate encryption, the proof also has to explicitly deal with the decryption issue sketched above. To do so, we introduce the notion of function encoding, which is the analogue of predicate encoding for functional encryption. Recall that predicate encodings, introduced in [Att14,Wee14], are a "dumbed-down" version of ABE, and provide a framework to extend the dual system encryption methodology introduced by [Wat09] in the context of adaptively-secure IBE to a broad class of ABE, including inner product testing, or Boolean formulas. In our case, we use the abstraction of function encoding to generalize the information-theoretic argument from [CGW18] to capture a broad class of functional encryption, including inner-product FE with access control expressed by innerproduct testing, Boolean formulas, and more.

Similarly to predicate encoding, which has received significant interest (particularly as its more general form referred to as Conditional-Disclosure of Secret, e.g. [GIKM00, GKW15, AARV17, LVW17]), we believe the notion of function encoding could be interesting on its own. In a nutshell, functional encodings enhance a more sophisticated information theoretic argument than traditional Dual System Encryption, where secret keys are switched to a semi-functional mode that still allows them to decrypt the challenge ciphertext, but yield different information than normally generated secret keys. Indeed, in the security proof, the ciphertext will encode the original message x 0 , but also the message x 1 , where the pair ( x 0 , x 1 ) is chosen by the adversary during the indistinguishability game. Normal keys will decrypt with respect to the message x 0 , whereas the semi-functional keys will decrypt with respect to the message x 1 , thereby successfully proving security.

IDENTITY-BASED INNER-PRODUCT FE FROM LATTICES. Our second main result is the construction of two identitybased inner-product FE (IB-IPFE) from the LWE assumption6 . Both schemes combine existing LWE-based IBE with the LWE-based inner-product FE from [ALS16]. The first one uses the IBE from [GPV08], where the public key described a trapdoor function for which it is hard to sample short preimage. Given the trapdoor-the master key of the IBE-it is possible to efficiently compute a short preimage of any target image. Each identity id yielding a different image, the corresponding preimage, a matrix of short coefficients M id , defines the user secret key for id. As it turns out, to produce functional decryption keys associated with identity id and vector y, we can simply give a projection M id y. We prove this remarkably simple scheme adaptively-secure in the random oracle model using the security argument of [GPV08] to handle all functional decryption keys that do not decrypt the challenge ciphertext, whereas we use the proof techniques of [ALS16] to take care of all keys that decrypt the challenge ciphertexts.

Our second constructions relies on the IBE from [ABB10], where the public key can be used to derive an identitybased public key pk id for any identity id. The public key pk id describes a trapdoor function, for which, as in [GPV08], it is hard to compute short preimages. A fixed target image, which belongs to the range of all the trapdoor functions pk id is made public. The user secret key for id is a short preimage of the fixed target image, for the function pk id . Once again, user secret keys happen to be matrices, which can be projected to obtain functional decryption keys sk id, y and get an IB-IPFE.

As a bonus, our schemes inherit the anonymity property of the underlying IBE, that is, the identity associated with a ciphertext remains hidden as long as no functional decryption key that decrypts is issued.

RICHER ACCESS CONTROL FROM LATTICES. The puncturing technique that is used in the security proof of [ABB10] has been generalized to obtain ABE for all circuits in [BGG + 14]. However, there are intrinsic technical limitations in our proof strategy which prevent from extending our scheme to the ABE case. In particular, to use the security argument of the IPFE from [ALS16] as part of our own security proof, we rely on a lazy sampling argument: to obtain a functional decryption key sk id , y where id is the identity of the challenge ciphertext, we first sample a matrix with short coefficients M id and set the fixed public target image such that this short matrix is a preimage of the target image by the function described by the public key pk id . Concretely, the target image is a matrix T , the public key pk id = A id is also a matrix, and we want A id M id = T , where the matrices have matching dimensions. We can first sample T , then use the trapdoor to compute M id satisfying the previous equation, but we can also first sample a short M id , and then set T = A id M id . This produces identically distributed matrices, and in the latter case, we can produce M id without knowing the trapdoor, which is necessary in the security proof. The matrix M id will actually correspond to the master secret key of the IPFE of [ALS16]. The key sk id , y is M id y, as described above, which corresponds to a functional decryption key for y in the scheme from [ALS16]. However, this lazy sampling argument is inherently limited to the case where only one attribute (here, identity) satisfies the predicate (here, identity) of the challenge ciphertext. In the case of ABE, there can be multiple such attributes for a given predicate. We leave combining ABE for circuits with inner-product FE as a challenging open problem. MULTI-INPUT EXTENSIONS. As a final contribution, we show how to generalize our pairing-based IP-FE scheme to the multi input setting. Our realization is rather generic in the sense that it converts any single input construction of the primitive, satisfying few additional properties, into a multi input scheme supporting the same class of functionalities. Specifically, the required properties are that (1) the underlying IP-FE is pairings-based (2) its encryption and key generation algorithms can take as input large norm vectors and (3) its encryption algorithm enjoys linearly homomorphic properties. Recall that, to guarantee efficient decryption, our parings based constructions require that both the plaintext vectors x and the function vector y have small norm. What we require now is that, if one is willing to give up efficient decryption, the small norm condition can be relaxed (i.e. decryption returns an encoding of the output rather than the output itself).

On a technical level the transformation follows very closely the generic single-input to multi-input IP-FE transform by Abdalla et al. [ACF + 18, AGRW17]. In this sense, we believe that the interesting contribution is the primitive itself. Indeed, information leakage is even more problematic in the multi input setting, as here users can combine their inputs with many different ciphertexts coming from other users. In the case of n users this easily leads to an information leakage that completely destroys security. While countermeasures could be put in place to limit the encryption and key queries that the adversary is allowed to ask, by resorting for instance, to the notion of multi-client IPFE, where ciphertexts are associated with time-stamps, and only ciphertext with matching time-stamps can be combined (e.g. [CDG + 18]) we believe that our proposed primitive provides a more general and versatile solution to the problem.

Our construction allows users to compute weighted sums on encrypted vectors each associated with a possibly different access structure. In our medical example above, this might be used to add even more granularity to the access control of data. That is, some users may obtain keys that can compute statistics on some, but not all, the encrypted data. For instance, doctors in a hospital may be able to compute on a different set of encrypted data then employees of a health insurance company. Moreover, multi-input allows users to aggregate data coming from different sources.

Related Work. We emphasize that the primitive considered in this paper is natural, and as such, it has also been considered in previous works, either implicitly or explicitly.

In [DP19], Dufour-Sans and Pointcheval describe an identity-based functional encryption scheme for inner products as a byproduct of their realization of unbounded IPFE with succinct keys. Their construction is proven selectively secure in the random-oracle model based on the standard decisional bilinear Diffie-Hellman assumption. Compared to their construction, our pairing-based schemes provide support for significantly richer functionalities and are proven secure in the standard model.

In prior works [AJS18,JLMS19], the authors define a so-called partially-hiding FE allowing for the computation on two inputs (x, y), where the input x is seen as a public attribute and the other one, y, remains hidden. The construction of [AJS18] supports degree-2 computation on the private input y, and degree-1 computation on the public input x. Its security rely on the generic bilinear group model. In [JLMS19], functional secret keys support the computation of degree-2 polynomials on the private input, as in [AJS18], but it supports NC 0 computation on the public input. As an additional benefit, the security of their construction rely on a standard assumption on pairing groups (namely, SXDH). In [JLS19], Jain, Lin, and Sahai provided a partially-hiding FE allowing for degree-2 computation on the private input, and NC 1 computation on the public inputs; relying on the SXDH assumption. All of these schemes are in the secretkey setting. Our scheme has the advantage to be public-key, although our techniques inherently rely on the linearity of the inner-product functionality. All of those works focus on simulation, selective security, and use partially-hiding FE in the context of providing indistinguishability obfuscation.

In [CZY19], Chen, Zang, and Yiu propose a construction of attribute-based functional encryption for inner products. Like ours, their construction is pairing-based, but it is less generic, and relies on three decisional assumptions on bilinear groups of composite order N = p 1 p 2 p 3 (p 1 , p 2 , p 3 distinct primes), which are less efficient than prime-order groups. Our realizations, on the other hand, build generically from any dual system encryption-based ABE. In terms of security, their construction guarantees indistinguishability against adaptive adversaries in the standard model, but only in the weaker setting discussed above, where keys that decrypt cannot be leaked to the adversary, which does not capture the essence of the notion that we achieve, since it does not offer any additional security guarantees with respect to standard ABE schemes. We recall that all our schemes explicitly allow the adversary to get functional keys to decrypt the challenge ciphertext. Also, while our first scheme is only selectively secure, it achieves this in the stronger simulation setting. Finally, no extensions to the multi-input case are considered in [CZY19].

In [Wee17], Wee builds partially hiding predicate encryption schemes which simultaneously generalize existing attribute-based and inner-product predicate encryption schemes. Although his constructions support a larger class of policies than our constructions, the decryptor still has access to the payload message (a KEM key in this case) once the access policy is satisfied or to a uniformly random value otherwise. We see it as an interesting open problem to extend his work to also permit selective computations over the payload message when the access policy is satisfied.

Subsequent work. In [AGW20], Abdalla, Gong, and Wee present functional encryption schemes for attributeweighted sums, where encryption takes as input N attribute-value pairs (x i , z i ) where x i is public and z i is private; secret keys are associated with arithmetic branching programs f , and decryption returns the weighted sum N i=1 f (x i )z i while leaking no additional information about the z i 's. The functionalities being introduced in this paper can be seen as a particular case of the new functionality in [AGW20] by setting N = 1. We note, however, that our adaptively secure construction in Section 3 also allows for private attributes.

In [GJLS20], Gay, Jain, Lin, and Sahai extend the partially-hiding FE scheme in [JLS19] to the public-key setting. Their new functionality also encompasses the ones being introduced in this paper since it supports the computation of degree-2 polynomials on the private input.

Publication note. An abridged version of this paper appears in the proceedings of ASIACRYPT 2020 [ACGU20]. In addition to including complete proofs of security, this version also describes a lattice-based standard-model construction of identity-based functional encryption and a multi-input extension of our schemes. Moreover, it also provides concrete function encodings that correspond to identity-based encryption, inner-product predicate encryption, fullyhiding inner-product predicate encryption and monotone span programs.

Organization. Section 2 recalls some standard notation together with the syntax and security definitions for functional encryption schemes. Section 3 presents our constructions of inner-product FE with fine-grained access control from pairings. Section 4 describes our first lattice-based construction of identity-based functional encryption in the random-oracle model. Section 5 describes the lattice-based standard-model construction of identity-based functional encryption and Section 6 presents a multi-input extension of our schemes.

Preliminaries

Notation. We denote with λ ∈ N a security parameter. A probabilistic polynomial time (PPT) algorithm A is a randomized algorithm for which there exists a polynomial p(•) such that for every input x the running time of A(x) is bounded by p(|x|). We say that a function ε : N → R + is negligible if for every positive polynomial p(λ) there exists λ 0 ∈ N such that for all λ > λ 0 : ε(λ) < 1/p(λ). If S is a set, x ← R S denotes the process of selecting x uniformly at random in S. If A is a probabilistic algorithm, y ← R A(•) denotes the process of running A on some appropriate input and assigning its output to y. For a positive integer n, we denote by [n] the set {1, . . . , n}. We denote vectors x = (x i ) and matrices A = (a i,j ) in bold. For a set S (resp. vector x) |S| (resp. | x|) denotes its cardinality (resp. number of entries). Also, given two vectors x and x we denote by x x their concatenation. By ≡, we denote the equality of statistical distributions, and for any ε > 0, we denote by ≈ ε the ε-statistical difference of two distributions. For any x ∈ R, we denote by x the largest integer less than or equal to x, while for any z ∈ [0, 1], we denote by z the closest integer to z. For all a i ∈ Z ni p for i ∈ [n], we denote by ( a 1 , . . . , a n ) ∈ Z i∈ [n] ni p a column vector, and by

( a 1 | • • • | a n ) ∈ Z 1× i∈[n] ni p
a row vector.

Pairing groups

Let PGGen be a PPT algorithm that on input the security parameter 1 λ , returns a description PG = (G 1 , G 2 , G T , p, P 1 , P 2 , e) where for all s ∈ {1, 2, T }, G s is an additive cyclic group of order p for a 2λ-bit prime p. G 1 and G 2 are generated by P 1 and P 2 respectively, and e : G 1 × G 2 → G T is an efficiently computable (non-degenerate) bilinear map. Define P T := e(P 1 , P 2 ), which is a generator of G T , of order p. We use implicit representation of group elements. For s ∈ {1, 2, T } and a ∈ Z p , define [a] s = a • P s ∈ G s as the implicit representation of a in G s . More generally, for a matrix A = (a ij ) ∈ Z n×m p we define [A] s as the implicit representation of A in G s :

[A] s :=   a 11 • P s ... a 1m • P s a n1 • P s ... a nm • P s   ∈ G n×m s . Given [a] 1 and [b] 2 , one can efficiently compute [a • b] T using the pairing e. For matrices A and B of matching dimensions, define e([A] 1 , [B] 2 ) := [AB] T . For any matrix A, B ∈ Z n×m p , any group s ∈ {1, 2, T }, we denote by [A] s + [B] s = [A + B] s .
For any prime p, we define the following distributions. The DDH distribution over

Z 2 p : a ← R Z p , outputs a := 1 a . The DLIN distribution over Z 3×2 p : a, b ← R Z p , outputs A :=   a 0 0 b 1 1   .
Definition 2.1 (DDH assumption). For any adversary A, any group s ∈ {1, 2, T } and any security parameter λ, let

Adv DDH Gs,A (λ) := | Pr[1 ← A(PG, [ a] s , [ ar] s )] -Pr[1 ← A(PG, [ a] s , [ u] s )]|, where the probabilities are taken over PG ← R GGen(1 λ , d), a ← R DDH, r ← R Z p , u ← R Z 2
p , and the random coins of A. We say DDH holds in G s if for all PPT adversaries A, Adv DDH Gs,A (λ) is a negligible function of λ. Definition 2.2 (SXDH assumption). For any security parameter λ and any pairing group

PG = (G 1 , G 2 , G T , p, P 1 , P 2 , e) ← R PGGen(1 λ ), we say SXDH holds in PG if DDH holds in G 1 and G 2 .

Functional Encryption Definition 2.3 (Functional Encryption [BSW11, O'N10]

). Let F be a family of functions, with f ∈ F defined as f : X → Y. A functional encryption scheme for F consists of the following algorithms:

-Setup(1 λ , F): takes as input the security parameter λ and a description of the function family F, and outputs a master public key mpk and a master secret key msk. The master public key mpk is assumed to be part of the input of all the remaining algorithms. -Enc(x ∈ X ): takes as input the master public key mpk and a message x ∈ X , and it outputs a ciphertext ct.

-KeyGen(msk, f ∈ F): takes as input the master secret key msk, a function f ∈ F, and it outputs a decryption key sk f . -Dec(sk f , ct): takes as input a decryption key sk f along with a ciphertext ct, and it outputs a value y ∈ Y or the special symbol ⊥ if it fails.

A scheme as defined above is correct if for all security parameter λ, x ∈ X , and f ∈ F, we have:

Pr[Dec(sk f , ct x ) = f (x)] = 1]
where the probability is taken over

(mpk, msk) ← Setup(1 λ , F), sk f ← KeyGen(msk, f ), ct x ← Enc(x).
Partial information. For the rest of this paper, it is convenient to split the output of the function in two parts:

(f (x), part(x))
, where part(x) is some partial information on x that is independent from f . For instance, we will consider the case of x := (P, x), where P is a predicate, and x ∈ Z d is a vector of dimension d; each function is described by a pair (att, y) where att is an attribute, and y ∈ Z d . The output f (x) reveals x y and P if P(att) = 1; only P otherwise. Note that the information P is always revealed, no matter the function. Considering this part of the input separately will be helpful later.

Security notions. We first recall the selective indistinguishability variant for the security of functional encryption here.

Definition 2.4 (SEL-IND security). For every functional encryption FE, every security parameter λ, every stateful adversary A, we define the following experiments for β ∈ {0, 1}:

Experiment SEL-IND F E β (1 λ , A): (x 0 , x 1 ) ← A(1 λ , F) (mpk, msk) ← Setup(1 λ , F) ct ← Enc(x β ) β ← A OKeyGen(•) (mpk, ct ) Output: β
where OKeyGen(•) is an oracle that on input f ∈ F, outputs KeyGen(msk, f ). Additionally, if A ever calls the oracle KeyGen on an input f ∈ F, the challenge queries x 0 , x 1 must satisfy: f (x 0 ) = f (x 1 ) and part(x 0 ) = part(x 1 ).

A functional encryption scheme FE is SEL-IND-secure if for every PPT adversary A, the following advantage is a negligible function of λ:

Adv SEL-IND F E,A (λ) = Pr SEL-IND F E 0 (1 λ , A) = 1 -Pr SEL-IND F E 1 (1 λ , A) = 1
Now we give the adaptive, indinstinguishability based variant of security for FE. It is the same as the previous definition, except the challenge (x 0 , x 1 ) can be chosen adaptively, after seeing the public key and querying functional decryption keys.

Definition 2.5 (AD-IND security).

For every functional encryption FE, every security parameter λ, every stateful adversary A, we define the following experiments for β ∈ {0, 1}:

Experiment AD-IND F E β (1 λ , A): (mpk, msk) ← Setup(1 λ , F) (x 0 , x 1 ) ← A OKeyGen(•) (1 λ , F) ct ← Enc(x β ) β ← A OKeyGen(•) (mpk, ct ) Output: β
where OKeyGen(•) is an oracle that on input f ∈ F, outputs KeyGen(msk, f ). Additionally, if A ever calls the oracle KeyGen on an input f ∈ F, the challenge queries x 0 , x 1 must satisfy: f (x 0 ) = f (x 1 ) and part(x 0 ) = part(x 1 ).

A functional encryption scheme FE is AD-IND-secure if for every PPT adversary A, the following advantage is a negligible function of λ:

Adv AD-IND F E,A (λ) = Pr AD-IND F E 0 (1 λ , A) = 1 -Pr AD-IND F E 1 (1 λ , A) = 1
We now give the simulation-based, selective security. Note that simulation security straightforwardly implies indistinguishable security.

Definition 2.6 (SEL-SIM security). For any FE scheme FE for functionality F, any security parameter λ, any PPT stateful adversary A, and any PPT simulator S := ( Setup, Enc, KeyGen), we define the following two experiments.

Real F E A (1 λ ): x ← A(1 λ ) (mpk, msk) ← Setup(1 λ , F) ct ← Enc(x ) α ← A OKeyGen(•) (mpk, ct ) Ideal F E A,S (1 λ ): x ← A(1 λ ) ( mpk, msk) ← Setup(1 λ , F) ct ← Enc( msk, part(x )) α ← A OKeyGen(•) ( mpk, ct )
In the real experiment, the key generation oracle OKeyGen, when given as input f ∈ F, returns KeyGen(msk, f ). In the ideal experiment, the key generation oracle OKeyGen, when given as input f ∈ F, computes f (x ), and returns KeyGen( msk, part(x ), f, f (x )), where part(x ) denotes the partial information on x .

We say an FE scheme is SEL-SIM secure if for all PPT adversaries A, there exists a PPT simulator S := ( Setup, Enc, KeyGen) such that

Adv SEL-SIM F E,A (λ) := | Pr[1 ← Real F E A (1 λ )] -Pr[1 ← Ideal F E A,S (1 λ )]| = negl(λ).
3 Inner-Product FE with Fine-grained Access Control

In this section, we present functional encryption schemes for the family of functions that allows users to embed access policies in the encrypted data, and generate functional decryption keys that compute weighted sum on the latter. Namely, each ciphertext is associated with a predicate P, and encrypts a vector x ∈ [0, B] d for some dimension d and some bound B. Each functional decryption key is associated with an attribute att and a vector y ∈ [0, B] d . Decryption recovers the inner product x y ∈ [0, dB 2 ] together with P if the attribute att satisfies the predicate P. Otherwise, it only recovers the predicate P, but no information about the encrypted vector x is revealed. We show it is possible to combine existing pairing-based ABE together with the inner-product FE from [ALS16]. Our generic construction works on any ABE that relies on the dual system encryption methodology, originally put forth by [Wat09]. Namely, any such ABE that supports the class of predicates P, can be turned into an FE scheme for the family F ipfe(d,B),P := U × [0, B] d of functions described by an attribute att ∈ U and a vector y ∈ [0, B] d , that given as input a predicate P ∈ P where P : U → {0, 1} and a vector x ∈ [0, B] d , returns x y ∈ [0, dB 2 ] if P(att) = 1, 0 otherwise. Note that this can be compactly written as P(att) • x y. We will consider the case where the partial information that is leaked about (P, x) is P, which corresponds to the case of ABE with public indices, but also the case where the predicate itself is hidden, which corresponding to the case of predicate encryption, also referred to as ABE with private indices. For correctness, we require the bound B and the dimension d to be polynomially bounded.

We first give a scheme that builds upon any predicate encoding, a one-time secure, private-key, statistical variant of ABE, introduced in [Wee14, Att14], later refined in [Att16, AC16, AC17, ABS17] for prime-order pairing groups. Building a predicate encoding is much easier than directly building an attribute based encryption, since the heavy machinery that is being used to prove security of the resulting ABE is taken care of by these modular frameworks. We follow this line of work by giving a definition of predicate encoding which is essentially that of [CGW15]. For simplicity, we leave the question of using more general predicate encodings, such as those from [AC17], which capture a larger class of ABE, as future work. Our modular construction is general enough to capture identity-based encryption, inner-product predicate encryption, and monotone span programs, whose concrete predicate encodings are given in Appendix B.

FE with simulation, selective security

First, we recall the definition of predicate encodings.

Definition 3.1 (predicate encoding). Let P be a family of predicates and p be a prime. A predicate encoding for (P, Z p ) is given by the following polynomial-time deterministic algorithms:

-Param(P): takes as input the family of predicates P, and returns the parameters (n, |ct|, |sk|) ∈ N 3 .

-EncCt(P): takes as input a predicate P ∈ P, and returns a matrix C ∈ Z n×|ct| p .

-EncKey(att): takes as input an attribute att ∈ U, and returns a matrix K ∈ Z .

Security. If P ∈ P and att ∈ U such that P(att) = 0, then the following are identically distributed:

(α|v 1 | • • • |v n ) 0 C K and (0|v 1 | • • • |v n ) 0 C K , where α, v 1 , . . . , v n ← R Z p .
Example: Identity-Based Encryption.

-Param(IBE): takes as input the family of predicates I, where each predicate is described by an identity id ∈ I, and returns 1 when given as an input an identity id such that id = id, returns 0 otherwise. It returns the parameters

(n = 2, |ct| = 1, |sk| = 1) ∈ N 3 . -EncCt(id): given id ∈ I, returns a matrix C = (1, id) ∈ Z 2×1 p such that (v 1 |v 2 )C = v 1 + idv 2 ∈ Z p . -EncKey(id): given id ∈ I, returns a matrix K = (1, 1, id) ∈ Z 3×1 p such that (α|v 1 |v 2 )K = α + v 1 + idv 2 ∈ Z p . -Decode(id, id ): if id = id , it returns the vector d := -1 1 ∈ Z 2 p .
Our simulation, selectively secure FE is described in Fig. 1.

Correctness.

Observe that for all predicates P ∈ P, the vector

[(W 1 c 1 | . . . |W n c 1 )] 1 ∈ G 2×n
1 can be computed from mpk and the randomness s ← R Z p used by the encryption algorithm to compute [ c 1 ] 1 := [ as] 1 . Then, the encryption algorithm multiplies the resulting vector by the matrix

C := EncCt(P) ∈ Z n×|ct| p to obtain [C 2 ] 1 ∈ G 2×|ct| 1
. Similarly, for all attributes att ∈ U, the vector

[(U y|W 1 k 1 | . . . |W n k 1 )] 2 ∈ G 2×(n+1) 2
can be computed from mpk, msk, and the randomness r ← R Z p used by the key generation algorithm to compute [ k 1 ] 2 := [ br] 2 . Then, the key generation algorithm multiplies the resulting vector by the matrix KeyGen(msk, att, y). The values computed by the decryption algorithm are such that

K := EncKey(att) ∈ Z (n+1)×|sk| p to obtain [K 2 ] 1 ∈ G 2×|sk| 2 . Let P ∈ P and att ∈ U such that P(att) = 1, x, y ∈ [0, B] d , (P, [ c 1 ] 1 , [C 2 ] 1 , [ c 3 ] 1 ) ← R Enc(mpk, P, x), and (att, y, [ k 1 ] 2 , [K 2 ] 2 ) ← R
[ d 1 ] T := [( c 1 W 1 k 1 | . . . | c 1 W n k 1 )C] T ∈ G 1×|ct| T
, where C := EncCt(P) ∈ Z n×|ct| p , and

[ d 2 ] T := [( c 1 U y| c 1 W 1 k 1 | . . . | c 1 W n k 1 )K] T ∈ G 1×|sk| T
, where K := EncKey(att) ∈ Z (n+1)×|sk| p . Thus, by correctness of the predicate encoding (Param, EncCt, EncKey, Decode), we have [γ] T := [ c 1 U y] T ∈ G T . To see why, please note that, since

d 1 = ( c 1 W 1 k 1 | . . . | c 1 W n k 1 )C = ( c 1 U y| c 1 W 1 k 1 | . . . | c 1 W n k 1 ) 0 C , γ = ( d 1 | d 2 ) d = ( c 1 U y| c 1 W 1 k 1 | . . . | c 1 W n k 1 ) 0 C K d = ( c 1 U y| c 1 W 1 k 1 | . . . | c 1 W n k 1 ) • (1|0| . . . |0]) = c 1 U y. Therefore, [out] T = [ x y] T .
Finally, assuming the value B 2 d is polynomial in the security parameter, the decryption can efficiently recover the discrete logarithm out from [out] T .

Setup(1 λ , F ipfe(d,B),P ):

PG = (G1, G2, GT , p, P1, P2, e) ← PGGen(1 λ ), a, b ←R DDH, U ←R Z 2×d p , (n, |ct|, |sk|) ← Param(P), for all i ∈ [n], Wi ←R Z 2×2 p , mpk := [ a]1, [ b]2, [U a]1, {[W i a]1, [Wi b]2} i∈[n] , msk := U. Return (mpk, msk).
Enc(mpk, P, x): Theorem 3.2 (SEL-SIM security). If the underlying predicate encoding is secure, then the FE scheme from Fig. 1 is SEL-SIM secure. Namely, for any PPT adversary A, there exist PPT adversaries B 1 and B 2 such that:

s ←R Zp, [ c1]1 := [ as]1, C := EncCt(P) ∈ Z n×|ct| p , [C2]1 := [(W 1 c1| . . . |W n c1)C]1, [ c3]1 := [ x + U c1]1. Return (P, [ c1]1, [C2]1, [ c3]1) ∈ P × G 2 1 × G 2×|ct| 1 × G d 1 KeyGen(msk, att, y): r ←R Zp, [ k1]2 := [ br]2, K := EncKey(att) ∈ Z (n+1)×|sk| p , [K2]2 := [(U y|W1 k1| . . . |Wn k1)K]2, Return (att, y, [ k1]2, [K2]2) ∈ U × [0, B] d × G2 × G 2×|sk| 2 Dec (P, [ c1]1, [C2]1, [ c3]1), (att, y, [ k1]2, [K2]2) : [ d1]T := e([C2] 1 , [ k1]2) ∈ G |ct| T , [ d 2 ]T := e([ c1] 1 , [K2]2) ∈ G 1×|sk| T , d := Decode(P, att), [γ]T := [( d 1 | d 2 ) d]T ∈ GT , [out]T := e([ c3] 1 , [ y]2) -[γ]T . Return out.
Adv SEL-IND F E,A (λ) ≤ Adv DDH G1,B1 (λ) + 2Q • Adv DDH G2,B2 (λ) + 1 p ,
where Q denotes the number of queries to OKeyGen.

Proof. The proof goes over a series of hybrid games, defined in Fig. 4. Let A be a PPT adversary. For any such game G, we denote by Adv G (A) the probability Pr[1 ← R G(A)], that is, the probability that the game outputs 1 when interacting with A. The probability is taken over the random coins of A and the game G itself. For an overview of the ciphertext and key distributions in the proof, see Figs. 2 and3.

Game G 0 : is the same as Real F E A (1 λ ) from Definition 2.6. Game G 1 : in this game, the challenge ciphertext is switched to the semi-functional distribution (see Fig. 2). Namely, the vector [ c 1 ] 1 contained in the challenge ciphertext is switched to uniformly random over G 2 1 , using the DDH assumption. The game is described fully in Fig. 4 and is indistinguishable from G 0 by Lemma 3.3.

Ciphertext [ c1]1 [C2]1 [ c3]1 Hybrid Normal [ as]1, s ←R Zp [(W 1 c1| . . . |W n c1)C]1 [ x + U c1]1 G0 SF [ c1]1 ←R G 2 1 [(W 1 c1| . . . |W n c1)C]1 [ x + U c1]1 G1 Simulated c1 ←R Z 2 p \ span( a) [(W 1 c1| • • • |W n c1)C]1 [U c1]1 Ideal F E A,S (1 λ )
Fig. 2. Overview of ciphertext distributions appearing in the proof of Theorem 3.2, with changes between hybrids highlighted with a gray background. SF stands for semi-functional. Here, C := EncCt(P ).

Type of j th Key Remark [ k1]2 [K2]2 Hybrid Normal r ←R Zp [ br]2 [(U y|W1 k1| • • • |Wn k1)K]2 G0 Pseudo if P (att) = 0 [ k1]2 ←R G 2 1 [(U y|W1 k1| • • • |Wn k1)K]2 Hj-1.2 Pseudo SF if P (att) = 0 [ k1]2 ←R G 2 1 [( U y|W1 k1| • • • |Wn k1)K]2 Hj-1.7 SF if P (att) = 0 [ br]2 [( U y|W1 k1| • • • |Wn k1)K]2 Hj+1 Simulated if P (att)=0 [ br]2 [( U y|W1 k1| • • • |Wn k1)K]2 Ideal F E A,S (1 λ ) Simulated if P (att)=1 [ br]2 [(-y x • a ⊥ + U y|W1 k1| • • • |Wn k1)K]2 Ideal F E A,S (1 λ )
Fig. 3. Overview of key distributions appearing in the proof of Theorem 3.2, with changes between hybrids highlighted with a gray background. SF stands for semi-functional. Throughout the figure, K = EncKey(att).

Lemma 3.3. There exists a PPT adversary B 1 , such that:

|Adv G1 (A) -Adv G0 (A)| ≤ Adv DDH G1,B1 (λ).
Proof. The PPT adversary B 1 receives the DDH challenge

([ a] 1 , [ z] 1 ) where a ← R DDH, [ z] 1 := [ as] 1 with s ← R Z p or [ z] 1 ← R G 2 1 , then samples W i ← R Z 2×2 p , U ← R Z 2×d p
, b ← R DDH and simulates the experiment for A in the following way:

Simulation of the master public key: Since B 1 samples U and W i himself, he can use the encoding

[ a] 1 to compute [U a] 1 and {[W i a] 1 } i∈[n] ). Then B 1 , computes [W i b] 2 } i∈[n] and outputs mpk := [ a] 1 , [ b] 2 , [U a] 1 , {[W i a] 1 , [W i b] 2 } i∈[n] .
Simulation of the encryption challenge:

Adversary B 1 sets [ c 1 ] 1 := [ z] 1 , C := EncCt(P), [C 2 ] 1 := [(W 1 z| . . . |W n z)C] 1 , [ c 3 ] 1 := [ x + U z] 1 , and returns (P, [ c 1 ] 1 , [C 2 ] 1 , [ c 3 ] 1 ). When B 1 gets a DDH challenge of the form [ z] 1 := [ as] 1 with s ← R Z p , it simulates G 1 , whereas it simulates G 2 when [ z] 1 is uniformly random over G 1 .
Simulation of the functional keys: B 1 generates the keys straightforwardly as described in G 0 , using the matrix U, {W i } i∈[n] , and b.

Game G 2 : in this game, all the functional decryption keys associated with an attribute att such that P (att) = 0 are switched to semi-functional (see Fig. 3). That is, for these keys, the matrix U (defined in Fig. 4) is used in place of the master secret key U. Note that the matrix U, as opposed to the master secret key U, can be computed (information theoretically) from mpk only. These semi-functional keys decrypt successfully normal ciphertexts (which can be produced from mpk), but fail to decrypt semi-functional ciphertexts.

To switch keys from normal to semi-functional, we use a hybrid argument across keys, where each key is first switched to a high entropy distribution, typically referred to as pseudo mode in the dual system methodology [Wat09], where the vector [ k 1 ] 2 contained in the key is switched to uniformly random over G 2 2 , using the DDH assumption. At this point, the proof relies on the security of the predicate encoding to switch the key a semifunctional distribution. After this statistical transition, the vector [ k 1 ] 2 is switched back to its original distribution, and the proof proceeds to the next key. Details of the transition from game G 1 to game G 2 are given in Lemma 3.4. G0, G1, G2 :

(P , x ) ← A(1 λ ) PG ← PGGen(1 λ ), a, b ←R DDH, U ←R Z 2×d p , (n, |ct|, |sk|) ← Param(P), for all i ∈ [n], Wi ←R Z 2×2 p , mpk := [ a]1, [ b]2, [U a]1, {[W i a]1, [Wi b]2} i∈[n] u0 := U a a 2 2 ∈ Z d p , U := a u 0 ∈ Z 2×d p ct ← OEnc(P , x ) b ← A OKeyGen(•) (mpk, ct )
OEnc(P , x ): Even though the hybrid argument used here is standard in the context of dual system encryption, the crucial difference is that only the keys associated with att such that P (att) = 0 can be switched to semi-functional. The other keys should actually decrypt the challenge ciphertext properly. This is the reason the experiment needs to know in advance the value P , so as to determine which key can be switched. For the keys that cannot be switched, we use a security argument similar to that used in [ALS16] instead.

s ←R Zp, [ c1]1 := [ as]1, [ c1]1 ←R G 2 1 , C := EncCt(P ), [C2]1 := [(W 1 c1| . . . |W n c1)C]1, [ c3]1 := [ x + U c1]1. Return (P , [ c1]1, [C2]1, [ c3]1) OKeyGen(att, y): r ←R Zp, [ k1]2 := [ br]2, K := EncKey(att), [K2]2 := [(U y|W1 k1| • • • |Wn k1)K]2, If P (att) = 0, then [K2]2 := [( U y|W1 k1| • • • |Wn k1)K]2 . Return (att, y, [ k1]2, [K2]2)
Lemma 3.4 (From Game G 1 to game G 2 ). There exists a PPT adversary B 2 such that:

|Adv G1 (A) -Adv G2 (A)| ≤ 2Q • Adv DDH G2,B2 (λ) + 3Q
p , where Q denotes the number of queries to OKeyGen.

Proof. The proof goes over a series of hybrid games, defined in Fig. 5. Let A be a PPT adversary. For any such game H, we denote by Adv H (A) the probability Pr[1 ← R H(A)], that is, the probability that the experiment outputs 1 when interacting with A. Game H j-1 : this game is the same as G 1 , except that the first j -1 queries to OKeyGen are answered as in G 2 .

Thus, the game H 0 is the same as G 1 and H Q is the same as G 2 , where Q denotes the number of queries to OKeyGen. We show that for all j ∈ [1, Q], the games H j-1 and H j are computationally indistinguishable, using the intermediate hybrid games H j-1.1 and H j-1.2 , defined in Fig. 5. Game H j-1.1 : this game is the same as H j-1 , except that the j-th functional decryption key is switched to a high entropy distribution, where the vector [ k 1 ] 2 is switched to uniformly random over G 2 2 . This is referred to as the pseudo distribution in Fig. 3. Recall that the key is associated to attributes att. The functional key is changed only if P (att) = 0, where P is the predicate of the challenge ciphertext. If the j-th functional decryption key is associated with an attribute att such that P (att) = 1, then we make no changes and move on to H j.1 . Let's consider now the case P (att) = 0. We build an adversary B j.1 such that:

|Adv Hj-1 (A) -Adv Hj-1.1 (A)| ≤ Adv DDH G2,Bj.1 (λ).
Upon receiving the DDH challenge

([ b] 2 , [ z] 2 ) where b ← R DDH, [ z] 2 := [ br] 2 with r ← R Z p or [ z] 2 ← R G 2 2 , B j.1 samples W i ← R Z 2×2 p for all i ∈ [n], U ← R Z 2×d p , upon which it can simulate the experiment for A straightforwardly. When [ z] 2 := [ br] 2 , B j.1 simulates H j-1 , whereas it simulates H j-1.1 when [ z] 2 is uniformly random over G 2 2 .
Game H j-1.2 : In this game, we change the distribution of the vector [ k 1 ] used in the j-th functional decryption key from uniformly random over G 2 2 to uniformly random over G 2 2 \ span ([ b] 2 ). Since the size of span ([ b] 2 ) is at most p, while the size of G 2 2 is p 2 , this change only induces a statistical change of 1/p. Namely, we obtain:

|Adv Hj-1.1 (A) -Adv Hj-1.2 (A)| ≤ 1 p . Game H j-1.3 : Consider first orthogonal vectors a ⊥ , b ⊥ , such that a ⊥ ← R Z 2 p \ {0}, b ⊥ ← R Z 2 p \ {0}
with a a ⊥ = 0 and b b ⊥ = 0. In this game, we change for every i ∈ [n], the distribution of matrices W i to

W i + v i • a ⊥ ( b ⊥ ) , with v i ← R Z p .
We use the fact that for all a ⊥ , b ⊥ ∈ Z 2 p , the following distributions are identical:

{W i } i∈[n] and {W i + v i • a ⊥ ( b ⊥ ) } i∈[n] ,
where for all i ∈

[n], W i ← R Z 2×2 p , v i ← R Z p . This is because each W i is uniformly random over Z 2×2 p .
The leftmost distribution corresponds to H j-1.2 , whereas the rightmost distribution corresponds to H j-1.3 . Namely, in the latter case, we can write the challenge ciphertext as:

(P , [ c 1 ] 1 , [C 2 ] 1 , [ c 3 ] 1 ), with [ c 1 ] 1 ← R G 2 1 , [ c 3 ] 1 = [ x + U c 1 ] 1 ,
and:

[C 2 ] 1 := [(W 1 c 1 + v 1 • b ⊥ ( a ⊥ ) c 1 | • • • |W n c 1 + v n • b ⊥ ( a ⊥ ) c 1 )C] 1 = [(W 1 c 1 | • • • |W n c 1 )C] 1 + b ⊥ ( a ⊥ ) c 1 • (v 1 | • • • |v n )C 1
where C := EncCt(P ). For all keys of index i = j, the corresponding k 1 is in the span of b (i.e. k 1 ∈ span( b)), thus, we have that ( b ⊥ ) k 1 = 0, and the fine-dotted factors from the j-th key below vanish in all keys, except for the j-th one. The j-th key is of the following form:

[K 2 ] 2 := [(U y|W 1 k 1 + v 1 • a ⊥ ( b ⊥ ) k 1 | • • • |W n k 1 + v n • a ⊥ ( b ⊥ ) k 1 )K] 2 = [(U y|W 1 k 1 | • • • |W n k 1 )K] 2 + [ a ⊥ ( b ⊥ ) k 1 ( 0|v 1 | • • • |v n )K] 2 ,
Finally, because of the orthogonality constraints imposed on a ⊥ and b ⊥ , the extra terms (highlighted in finedotted boxes) also do not appear in mpk. We thus have:

Adv Hj-1.2 (A) = Adv Hj-1.3 (A).
Game H j-1.4 : In this game, the value α used to generate the j-th functional decryption key (see Fig. 5) is switched to uniformly random over Z p . Using the security of the underlying predicate encoding, we can argue that the following are identically distributed:

(v 1 | • • • |v n )C, (α|v 1 | • • • |v n )K and (v 1 | • • • |v n )C, (0|v 1 | • • • |v n )K .
The leftmost value corresponds to H j-1.3 , whereas the rightmost value corresponds to H j-1.4 . Thus, we have:

Adv Hj-1.3 (A) = Adv Hj-1.4 (A).
Game H j-1.5 : In this game, the vector v used to generate the j-th functional decryption key (see Fig. 5) is switched to U y instead of U y. We show that H j-1.4 and H j-1.5 are identically distributed. Using the basis ( a, a ⊥ ) of Z 2 p , we can write U = a u 0 + a ⊥ u 1 , where u 0 = U a a 2 2 , and

u 1 ← R Z 2 p .
Thus, we can write the j-th key as (att, y,

[ k 1 ] 2 , [K 2 ] 2 ), with [ k 1 ] 2 ← R G 2 2 \ span([ b]
2 ), and:

[K 2 ] 2 := ( U y + a ⊥ u 1 y |W 1 k 1 | • • • |W n k 1 )K + a ⊥ ( b ⊥ ) k 1 (α|v 1 | • • • |v n )K 2 = ( U y|W 1 k 1 | • • • |W n k 1 )K + a ⊥ ( b ⊥ ) k 1 (0|v 1 | • • • |v n )K + a ⊥ α • ( b ⊥ ) k 1 + u 1 y 0 • • • 0 K 2 ,
where K := EncKey(att).

We conclude using the fact that for all vectors a ⊥ , b ⊥ , k 1 ∈ Z 2 p such that k 1 b ⊥ = 0, the following are identically distributed:

k 1 b ⊥ • α + u 1 y and k 1 b ⊥ • α,
where α ← R Z p . The leftmost distribution corresponds to H j-1.4 , whereas the rightmost distribution corresponds to H j-1.5 . Thus, we have:

Adv Hj-1.4 (A) = Adv Hj-1.5 (A).
Game H j-1.6 : In this game, the value α used to generate the j-th functional decryption key (see Fig. 5) is switched back to 0. This transition is the reverse than the transition from H j-1.3 to H j-1.4 . Similarly, we use the security of the underlying predicate encoding to argue that the following are identically distributed:

(v 1 | • • • |v n )C, (α|v 1 | • • • |v n )K and (v 1 | • • • |v n )C, (0|v 1 | • • • |v n )K .
The leftmost value corresponds to H j-1.6 , whereas the rightmost value corresponds to H j-1.5 . Thus, we have:

Adv Hj-1.5 (A) = Adv Hj-1.6 (A).
Game H j-1.7 : Switching back from

W i + v i • a ⊥ ( b ⊥ ) to W i for all i ∈ [n],
we can write the matrix [C 2 ] 1 in the challenge ciphertext as:

[C 2 ] 1 = [(W 1 c 1 | • • • |W n c 1 )C] 1
and the matrix [K 2 ] 2 in the j-th key as:

[K 2 ] 2 := [( U y|W 1 k 1 | • • • |W n k 1 )K] 2
Similarly to the transition between H j-1.2 and H j-1.3 , it holds that:

Adv Hj-1.6 (A) = Adv Hj-1.7 (A).

Game H j-1.8 : we switch the distribution of the vector

[ k 1 ] 2 contained in the j-th from uniform over G 2 2 \ span([ b] 2 ) back to uniform over G 2
2 . This is the reverse transition than from H j-1.1 to H j-1.2 . We have:

|Adv Hj-1.7 (A) -Adv Hj-1.8 (A)| ≤ 1 p .
Game H j : we switch the distribution of the vector

[ k 1 ] 2 contained in the j-th key back to [ k 1 ] 2 := [ br] 2 for r ← R Z p .
This transition is similar to the transition between game H j-1 and H j-1.1 . Thus, we obtain a PPT adversary B j.2 such that: |Adv Hj-1.8 (A) -Adv Hj (A)| ≤ Adv DDH G2,Bj.2 (λ). Summing up for all j ∈ [Q], we obtain the lemma. Hj, Hj.1 , Hj.2, Hj.3, Hj.4, Hj.5 , Hj.6 , Hj.7 , Hj.8 ,Hj.9 :

(P , x ) ←R A(1 λ ) PG ←R PGGen(1 λ ), a, b ←R DDH, U ←R Z 2×d p , (n, |ct|, |sk|) ←R Param(P), for all i ∈ [n], Wi ←R Z 2×2 p a ⊥ , b ⊥ ←R Z 2 p \ {0} s.t. a a ⊥ = b b ⊥ = 0, ∀i ∈ [n] : vi ←R Zp mpk := [ a]1, [ b]2, [U a]1, {[W i a]1, [Wi b]2} i∈[n] u0 := U a a 2 2 ∈ Z d p , U := a u 0 ∈ Z 2×d p ct ←R OEnc(P , x ) b ←R A OKeyGen(•) (mpk, ct ) OEnc(P , x ): [ c1]1 ←R G 2 1 , C := EncCt(P), [C2]1 := [(W 1 c1| • • • |W n c1)C]1 [C2]1 = [(W 1 c1| • • • |W n c1)C]1 + b ⊥ ( a ⊥ ) c1 • (v1| • • • |vn)C 1 [C2]1 = [(W 1 c1| • • • |W n c1)C]1 [ c3]1 := [ x + U c1]1. Return (P , [ c1]1, [C2]1, [ c3]1)
OKeyGen(att, y): On the the ρ-th query:

r ←R Zp, [ k1]2 := [ br]1, K := EncKey(att). If ρ = j + 1 and P (att) = 0, then [ k1]2 ←R G 2 2 . If ρ = j + 1 and P (att) = 0, then [ k1]2 ←R G 2 2 \ span([ b]2) . If ρ ≤ j and P (att) = 0, then: [K2]2 := [( U y|W1 k1| • • • |Wn k1)K]2 If ρ > j or P (att) = 1, then: [K2]2 := [(U y|W1 k1| • • • |Wn k1)K]2
If ρ = j + 1 and P (att) = 0, then:

u = U y, α = 0, α ←R Zp , u = U y , [K2]2 := [ u|W1 k1| • • • |Wn k1)K + ( a ⊥ ( b ⊥ ) k1)(α|v1| . . . |vn)K]2 if ρ = j + 1 and P (att) = 0, then:[K2]2 := [( U y|W1 k1| • • • |Wn k1)K]2 Return (att, y, [ k1]2, [K2]2)

Game Ideal F E

A,S (1 λ ): we show this game is statistically close to G 2 . The simulator S := ( Setup, Enc, KeyGen) is described in Fig. 6. First, we use the fact that for all a ∈ Z 2 p , the following distributions are within 1/p statistical distance:

c 1 ← R Z 2 p and c 1 ← R Z 2 p \ span( a)
. The leftmost distribution corresponds to G 2 , whereas the rightmost distribution corresponds to Ideal F E A,S (1 λ ). Then, we use the fact that for all x ∈ Z d , the following distributions are identical:

( a, c 1 , U, U) and ( a, c 1 , U, U -a ⊥ ( x ) ), where a ← R DDH, c 1 ← R Z 2 p \ span( a), U ← R Z 2×d p , u 0 := U a a 2 2
, U := a u 0 , and a ⊥ ∈ Z 2 p such that a a ⊥ = 0 and c 1 a ⊥ = 1. This is because U is a uniformly random matrix, so adding an offset -a ⊥ ( x ) does not change its distribution. This extra offset doesn't appear in U since a a ⊥ = 0. The leftmost distribution corresponds to G 2 , whereas the rightmost distribution corresponds to Ideal F E A,S (1 λ ). Putting everything together, we obtain:

|Adv G2 (A) -Pr[1 ← R Ideal F E A,S (1 λ )]| ≤ 1 p .
Setup(1 λ , F ipfe(d,B),P ):

PG ← GGen(1 λ ), a, b ←R DDH, c1 ←R Z 2 p \ span( a), a ⊥ ←R Z 2 p such that c 1 a ⊥ = 1 and a a ⊥ = 0, U ←R Z 2×d p , u0 := U a a 2 2 , U := a u 0 , (n, |ct|, |sk|) ← Param(P), for all i ∈ [n], Wi ←R Z 2×2 p Return pk := [ a]1, [ b]2, [U a]1, {[W i a]1, [Wi b]2} i∈[n] , msk := U, U, a ⊥
Enc( msk, P ):

C := EncCt(P), [C2]1 := [(W 1 c1| • • • |W n c1)C]1, [ c3]1 := [U c1]1. Return (P , [ c1]1, [C2]1, [ c3]1)
KeyGen( msk, P , y, att, P (att) • y x ):

r ←R Zp, [ k1]2 := [ br]2, K := EncKey(att). If P (att) = 0, then [K2]2 := [( U y|W1 k1| • • • |Wn k1)K]2. If P (att) = 1, then [K2]2 := [(-y x • a ⊥ + U y|W1 k1| • • • |Wn k1)K]2. Return (att, y, [ k1]2, [K2]2)

FE with adaptive, indistinguishability based security

In this section, we build FE schemes for the family of functions F ipfe(d,B),P , where P corresponds to identity-based encryption, inner-product predicate encryption, or even monotone span programs. Similarly to the selective construction in Section 3.1, we give a modular construction that builds upon a simple, information-theoretic, one-time secure object, that generalizes the notion of predicate encoding to functions, hence called function encoding. Namely, a function encoding is a private-key version of functional encryption that only satisfies a one-time security notion.

Recall that our construction from Section 3.1 fails to achieve adaptive security, even if the underlying building blocks are adaptively secure. The reason is that, throughout the security proof, only the functional decryption keys associated with a pair (att, y) such that P (att) = 0 can be turned to semi-functional, where P is the predicate chosen by the adversary for the challenge ciphertext. In fact, the other keys cannot be turned semi-functional, since they must decrypt correctly the challenge ciphertext, and not just ciphertexts that can be generated from the public key. This challenge does not arise in the typical dual system encryption methodology used for ABE, since none of the queried keys can decrypt.

A similar situation arose in the context of fully-hiding predicate encryption for inner products, where ciphertexts are associated with a vector x ∈ Z n p , functional decryption keys are associated with y ∈ Z n p , and decryption successfully recovers the plaintext if x y = 0, whereas no information about that plaintext is revealed otherwise. As opposed to regular inner-product encryption, the vector x is also hidden, the only bit of information that leaks is whether x y = 0 or not. In this context, the adversary can query functional decryption keys that decrypt the challenge ciphertext. This is still a meaningful security notion since x remains hidden even when such keys are queried.

We show that the techniques introduced by [OT12], later improved in [CGW18] for adaptively secure fully-hiding predicate encryption for inner products are also relevant to obtain adaptively secure inner-product FE with fine-grained access control (even when the predicate is not hidden). In fact, using function encodings, a new notion we introduce that subsumes the notion of predicate encoding introduced in [Att14, Wee14] in the context of adaptively-secure ABE, we generalize the approach of [OT12,CGW18] to a large class of functional encryption schemes, whereas their scheme corresponds to the special case of inner-product encryption. Namely, we compile any function encoding for the function family F into an adaptively secure FE for the same class of functions from the SXDH assumption in asymmetric pairings. In Appendix C, we give concrete function encodings that correspond to identity-based encryption, innerproduct predicate encryption, fully-hiding inner-product predicate encryption and monotone span programs. Definition 3.5 (function encoding). Let F be a family of functions where each function f ∈ F is of the form f : X → Z p , and p be a prime. A function encoding for (F, Z p ) is given by the following polynomial-time deterministic algorithms:

-Param(F): takes as input the family of functions F, and returns the parameters (n, |ct|, |sk|) ∈ N 3 .

-EncCt(x): takes as input x ∈ X , and returns a matrix C ∈ Z . (See Section 2.2 for a discussion on the partial information).

We require the following properties.

Correctness. For all x ∈ X and f ∈ F,

C := EncCt(x) ∈ Z (n+1)×|ct| p , K := EncKey(f ) ∈ Z (n+1)×|sk| p , d := Decode(f, part(x)), we have: (C|K) d = (f (x), 0, . . . , 0) ∈ Z n+1 p .
Security. For any x 0 , x 1 ∈ X and f ∈ F such that f (x 0 ) = f (x 1 ) and part(x 0 ) = part(x 1 ), the following are identically distributed: Example: Identity-Based Encryption. Each function is described by an identity id ∈ Z p and a vector y ∈ [0, B] d , takes as input another identity id ∈ Z p and a vector x ∈ [0, B] d , and outputs x y if id = id , 0 otherwise. The partial information part( x, id) = id.

-Param: returns the parameters (2d, |ct| = d, |sk| = n + 1).

-EncCt( x, id): given x ∈ Z n p and id ∈ Z p , returns a matrix C ∈ Z (2d+1)×d p such that C (w 0 , w 1 , w 2 ) = (w 0 x + w 1 + id w 2 ) ∈ Z d p .

-EncKey( y, id ): given y ∈ Z n p and id ∈ Z p , returns a matrix K ∈ Z (2d+1)×1 p such that K (w 0 , w 1 , w 2 ) = y ( w 1 + id w 2 ) ∈ Z p .

-Decode(id, id , y): if x y = 0, it returns the vector d := ( y, -1) ∈ Z d+1 p .

Our modular construction is presented in Fig. 7. Proofs of correctness and security are given below.

Setup(1 λ , F ipfe(d,B),P ): Correctness. Observe that for all predicates P ∈ P and vectors x ∈ [0, B] d , the vector

PG = (G1, G2, GT , p, P1, P2, e) ← PGGen(1 λ ), a ←R DDH, b ←R Z 3 p , (n, |ct|, |sk|) ← Param(F ipfe(d,B),P ), for all i ∈ [0, n], Wi ←R Z 2×3 p , mpk := [ a]1, {[W i a]1} i∈[n] , msk := [ b]2, {[Wi b]2} i∈[n] . Return (mpk, msk) Enc(mpk, P, x): s ←R Zp, [ c1]1 := [ as]1 ∈ G 2 1 , C := EncCt(P, x) ∈ Z (n+1)×|ct| p , [C2]1 := [(W 0 c1| . . . |W n c1)C]1 ∈ G 3×|ct| 1 . Return (part(P, x), [ c1]1, [C2]1). KeyGen(msk, att, y): r ←R Zp, [ k1]2 := [ br]2 ∈ G 3 2 , K := EncKey(att, y) ∈ Z (n+1)×|sk| p , [K2]2 := [(W0 k1| . . . |Wn k1)K]2 ∈ G 2×|sk| 2 , [ k3]2 := [W0 k1]2 ∈ G 2 2 . Return (att, y, [ k1]2, [K2]2, [ k3]2). Dec part(P, x), [ c1]1, [C2]1, y, [ k1]2, [K2]2, [ k3]2): [ d1]T := e([C2] 1 , [ k1]2) ∈ G |ct| T , [ d 2 ]T := e([ c1] 1 , [K2]2) ∈ G
[(W 0 c 1 |W 1 c 1 | . . . | W n c 1 )] 1 ∈ G 3×n
1 can be computed from mpk and the randomness s ← R Z p used by the encryption algorithm to compute [ c 1 ] 1 := [ as] 1 . Then, the encryption algorithm multiplies by the matrix

C := EncCt(P, x) ∈ Z (n+1)×|ct| p to obtain [C 2 ] 1 ∈ G 3×|ct| 1
. Similarly, for all attributes att ∈ U, the vector

[(W 0 k 1 |W 1 k 1 | . . . |W n k 1 )] 2 ∈ G 2×n
2 can be computed from mpk, msk, and the randomness r ← R Z p used by the key generation algorithm to compute [ k 1 ] 2 := [ br] 2 . Then, the key generation algorithm multiplies by the matrix KeyGen(msk, att, y). The values computed by the decryption algorithm are such

K := EncKey(att, y) ∈ Z (n+1)×|sk| p to obtain [K 2 ] 1 ∈ G 2×|sk| 2 . Let P ∈ P and att ∈ U such that P(att) = 1, x, y ∈ [0, B] d , (part(P, x), [ c 1 ] 1 , [C 2 ] 1 ) ← R Enc(mpk, P, x), and (att, y, [ k 1 ] 2 , [K 2 ] 2 , [ k 3 ] 2 ) ← R
that [ d 1 ] T :=   C    c 1 W 0 k 1 . . . c 1 W n k 1       T , which implies that [ d 1 ] T = [( c 1 W 0 k 1 | c 1 W 1 k 1 | . . . | c 1 W n k 1 )C] T ∈ G 1×|ct| T
, where C := EncCt(P, x) ∈ Z (n+1)×|ct| p

, and the second equality holds because

c 1 W i k 1 ∈ Z p , for every i ∈ {0 . . . n}. Also, [ d 2 ] T := [( c 1 W 0 k 1 | c 1 W 1 k 1 | . . . | c 1 W n k 1 )K] T ∈ G 1×|sk| T
, where K := EncKey(att, y) ∈ Z (n+1)×|sk| p . Thus, by correctness of the function encoding (Param, EncCt, EncKey, Decode), we have

[γ] T := [ c 1 W 0 k 1 • x y] T = [ c 1 k 3 • x y] ∈ G T .
Therefore, assuming the value B 2 d is polynomial in the security parameter, the decryption can efficiently recover out = x y ∈ [0, B 2 d].

G0, G1, G2 :

β ←R {0, 1}, PG ← PGGen(1 λ ), a ←R DDH, b ←R Z 3 p , (n, |ct|, |sk|) ← Param(F ipfe(d,B) , P), for all i ∈ [0, n], Wi ←R Z 2×3 p , mpk := [ a]1, {[W i a]1, } i∈[n] (P 0 , x 0 ), (P 1 , x 1 ) ← A OKeyGen(•) (1 λ , mpk) ct ←R OEnc (P 0 , x 0 ), (P 1 , x 1 ) β ← A OKeyGen(•) (mpk, ct ) Return 1 if β = β, 0 otherwise.
OEnc (P 0 , x 0 ), (P 1 , x 1 ) :

s ←R Zp, [ c1]1 := [ as]1, [ c1]1 ←R G 2 1 C := EncCt(P β , x β ), C := EncCt(P 0 , x 0 ) , [C2]1 := [(W 0 c1|W 1 c1| . . . |W n c1)C]T , Return ct := (part(P β , x β ), [ c1]1, [C2]1)
OKeyGen(att, y):

r ←R Zp, [ k1]2 := [ br]1, K := EncKey(att, y), [K2]2 := [(W0 k1|W1 k1| • • • |W k1)K]2, [ k3]2 := [W0 k1]2. Return (att, y, [ k1]2, [K2]2, [ k3]2)
Fig. 8. Hybrid games for the proof of Theorem 3.6.

Theorem 3.6 (AD-IND security). If the underlying function encoding is secure, then the FE scheme from Fig. 7 is AD-IND secure. Namely, for any PPT adversary A, there exist PPT adversaries B 1 and B 2 such that:

Adv AD-IND F E,A (λ) ≤ Adv DDH G1,B1 (λ) + 4QAdv DDH G2,B2 (λ),
where Q denotes the number of queries to OKeyGen.

Proof. The proof uses a series of hybrid games, described in Fig. 8. For each game G, we define by Adv G (A) the advantage of A in G, that is:

2 • | Pr[1 ← R G(A)] -1/2|. Game G 0 : is defined such that Adv G0 (A) = Adv AD-IND F E,A (λ).
Game G 1 : here we change the distribution of the vector [ c 1 ] 1 that is part of the challenge ciphertext to uniformly random over G 2 1 , using the DDH assumption in G 1 . Namely, we build a PPT adversary B 1 such that:

|Adv G0 (A) -Adv G1 (A)| ≤ Adv DDH G1,B1 (λ). Upon receiving a challenge (PG, [ a] 1 , [ z] 1 ), where [ z] 1 := [ as] 1 for s ← R Z p , or [ z] 1 ← R G 2 1 , the adversary B 1 samples (n, |ct|, |sk|) ← Param(F ipfe(d,B) , P), for all i ∈ [0, n], W i ← R Z 2×3 p
, and simulate A's view in a straightforward way, setting

[ c 1 ] 1 := [ z] 1 in the challenge ciphertext.
Game G 2 : here we change the distribution of the challenge ciphertext so that it doesn't depend on the random bit β ← R {0, 1} anymore. Clearly, Adv G2 (A) = 0.

We show that G 1 and G 2 are computationally indistinguishable using the security of a private-key variant of our scheme. Namely, we exhibit a PPT adversary B 2 such that:

|Adv G1 (A) -Adv G2 (A)| ≤ Adv H0 (B 2 ),
where Adv H0 (B 2 ) denotes the advantage of B 2 in game H 0 , which is the private-key analogue of game G 0 (see Fig. 10). We use the fact that for any i ∈ [0, n]:

(W i a, W i c 1 ) with W i ← R Z 2×3 p , a ← R DDH, c 1 ← R Z 3 p , is within negligible statistical distance from (W i a, w i ) with w i ← R Z 3 p .
Roughly speaking, the vectors w i can be used as a fresh private-key, independent of the public key {[W i a] 1 }. Note that when a ← R DDH and a ⊥ ← R Z 2 p \ {0} such that a a ⊥ = 0, we have that the vectors ( a| a ⊥ ) form a basis of Z 2 p . Thus we can write W i := w i a + w i ( a ⊥ ) , where w i , w i ← R Z 3 p , and a ⊥ ∈ Z 2 p is such that a a ⊥ = 0 and c 1 a ⊥ = 1. This way, the public key can be written as:

mpk := [ a] 1 , {[ w i a a] 1 } i∈[n] ,
the challenge ciphertext can be written as:

(part(P β , x β ), [ c 1 ] 1 , [C 2 ] 1 ), with [ c 1 ] 1 ← R G 2 1 , C := EncCt(P β , x β ), [C 2 ] 1 := [( w 0 | w 1 | . . . | w n )C] 1 ,
which corresponds exactly to game H 0 . The functional decryption keys can be written as:

r ← R Z p , [ k 1 ] 2 := [ br] 1 , K := EncKey(att, y), [K 2 ] 2 := [( a w 0 + a ⊥ w 0 ) k 1 | • • • |( a w n + a ⊥ w n ) k 1 )K] 2 , [ k 3 ] 2 := [( a w 0 + a ⊥ w 0 ) k 1 ] 2 . The adversary B 2 samples w i ← R Z 3 p for all i ∈ [0, n] and a ← R DDH, a ⊥ ← R Z 2
p such that a a ⊥ = 0, thanks to which it can simulate the public key to A. To generate the challenge ciphertext, B 2 forwards the query (P 0 , x 0 ), (P 1 , x 1 ) to its own encryption oracle, and forwards its challenge ciphertext to A. When A queries OKeyGen(att, y), B 2 queries its own oracle to get sk att, y := (att, y,

[ k 1 ] 2 , [ k 2 ] 2 , [k 3 ] 2 ), where [ k 2 ] 2 := [( w 0 k 1 | . . . | w n k 1 )K] 2 for K := EncKey(att, y), and [k 3 ] 2 := [ w 0 k 1 ] 2 . B 2 computes [K 2 ] 2 := [ a ⊥ k 2 ] 2 + [ a( w 0 | . . . | w n )K] 2 , and [ k 3 ] 2 := [ a ⊥ k 3 ] 2 + [ a w 0 k 1 ] 2 , and returns ([ k 1 ] 2 , [K 2 ] 2 , [ k 3 ] 2 ) to A.
In Lemma 3.7, we show that Adv H0 (B 2 ) is negligible.

Lemma 3.7. For any PPT adversary A, there exists a PPT adversary B such that:

Adv H0 (A) ≤ 4Q • Adv DDH G2,B (λ),
where Q denotes the number of queries to OKeyGen.

Proof. The proof uses a series of hybrid games, described in Figs. 9 and 10. For any game H, we denote by Adv H (A) the advantage of A in H, that is, the probability Pr[1 ← R H(A)] that the game H returns 1 when interacting with A, where the probability is taken over the random coins of A and the game H itself. Game H 0 : is described in Fig. 10. We use the basis

( b * | b * 2 | b * 3 ) of Z 3 p to write w i ← R Z 3 p as w i := w 1 i b * + w 2 i b * 1 + w 3 i b * 3 , with w 1 i , w 2 i , w 3 i ← R Z p , for all i ∈ [0, n]. This basis is dual to the random basis ( b| b 2 | b 3 ), that is: b 2 b * = b 3 b * = 0, b b * = 1, b b * 2 = b 3 b * 2 = 0, b 2 b * 2 = 1, b b * 3 = b 2 b * 3 = 0, b 3 b * 3 = 1.
Game H 1 : we change the component of the ciphertext along the vector b * 3 , using the one-time security of the function encoding. Namely, we use the fact that (w 3 0 | . . .

|w 3 n )C β is identically distributed to (w 3 0 | . . . |w 3 n )C 0 , where w 3 0 , . . . , w 3 n ← R Z p , C β := EncCt(P β , x β
), and C 0 := EncCt(P 0 , x 0 ), by security of the function encoding (see Definition 3.5). Note that we rely on the fact that the values (w 3 0 | . . . |w 3 n ) do not appear in the functional decryption keys, since all of these keys contain vectors [ k 1 ] 2 such that k 1 b * 3 = 0. Game H 1.q : is defined in Fig. 9 for all q ∈ [Q] where Q denotes the number of queries to OKeyGen. Note that H 1.0 is the same as game H 1 . To show that H 1.q-1 is computationally indistinguishable from H 1.q for all q ∈ [Q], we use intermediate hybrid games H 1.q-1.1 ,H 1.q-1.2 , and H 1.q-1.3 , also defined in Fig. 9.

Game H 1.q-1.1 : in this game, we switch the distribution of the output to the q-th query to OKeyGen. Namely, the vector

[ k 1 ] 2 is sampled uniformly in span([ b 2 ] 2 ) instead of span([ b]
2 ). This is done using the DDH assumption in G 2 . The reduction from DDH must not know the vectors b * and b * 2 , which are trapdoors for the DDH assumption (they permit to test membership in span ([ b] 2 ) or span([ b 2 ] 2 ) respectively). Indeed, it is possible to sample the vectors w

1 i b * + w 2 i b * 2 with w 1 i , w 2 i ← R Z p for all i ∈ [0, n],
without knowing explicitly the vectors b * and b * 2 . We consider an intermediate game H 1.q-1.1 which is like H 1.q-1.1 except that the vector [ k 1 ] 2 from the q-th key is sampled uniformly over span ([ b] 2 , [ b 2 ] 2 ). We build PPT adversaries B 1.q-1 and B 1.q-1.1 such that: |Adv H1.q-1 (A) -Adv H 1.q-1.1 (A)| ≤ Adv As-1 PG,B 1.q-1 (λ), and |Adv H 1.q-1.1 (A) -Adv H1.q-1.1 (A)| ≤ Adv As-2 PG,B 1.q-1.1 (λ). By Lemma 3.8, this implies the existence of a PPT adversary B 1.q-1 such that

|Adv H1.q-1 (A) -Adv H1.q-1.1 (A)| ≤ 2 • Adv DDH G2,B1.q-1 (λ). Upon receiving ( u 1 , u 2 , b * 3 , [ b] 2 , [ b 3 ] 2 , [ z] 2 ), B 1.q-1 computes the challenge ciphertext as c β 2 + c 0 2 with c β 2 := ( u 1 w 1 0 + u 2 w 2 0 | . . . | u 1 w 1 n + u 2 w 2 n )C β and c 0 2 := ( b * 3 w 3 0 | . . . | b * 3 w 3 n )C 0 with w 1 i , w 2 i , w 3 i ← R Z p for all i ∈ [0, n], C β := EncCt(P β , x β
) and C 0 := EncCt(P 0 , x 0 ). It computes the keys as follows. For the q-1 first keys, it samples

[ k 1 ] 2 ← R span([ b 3 ] 2 ); for the q-th key, it uses [ k 1 ] 2 := [ z] 2 , and for the last Q -q -1 keys it computes [ k 1 ] 2 ← R span([ b] 2 ). The rest of the keys are computed as [ k 2 ] 2 := [( w 0 k 1 | w 1 k 1 | • • • | w n k 1 )K] T , [k 3 ] 2 := [ w 0 k 1 ] 2 , with w i := u 1 w 1 i + u 2 w 2 i + b * 3 w 3 i for all i ∈ [0, n].
The adversary B 1.q-1.1 works similarly. Game H 1.q-1.2 : Here we switch the distribution of the challenge ciphertext, using the fact that the following distributions are identical:

(w 2 0 | . . . |w 2 0 ) C β , (w 2 0 | . . . |w 2 0 ) K and (w 2 0 | . . . |w 2 0 ) C 0 , (w 2 0 | . . . |w 2 0 ) K,
where w 2 0 , . . . , w 2 n ← R Z p , C β := EncCt(P β , x β ), C 0 := EncCt(P 0 , x 0 ), and K := EncKey(att, y). This holds by security of the function encoding (see Definition 3.5), since by definition of the security game, we have P 0 (att) • y x 0 = P 1 (att) • y x 1 for all queries (att, y) to OKeyGen. The leftmost distribution corresponds to game H 1.q-1.1 , whereas the rightmost distribution corresponds to the game H 1.q-1.2 . Thus, we have:

Adv H1.q-1.1 (A) = Adv H1.q-1.2 (A).

Game H 1.q-1.3 : in this game, we switch the distribution of the output to the q-th query to OKeyGen. Namely, the vector

[ k 1 ] 2 is sampled uniformly in span([ b 3 ] 2 ) instead of span([ b 2 ] 2 )
. This is done using the DDH assumption in G 2 . As for the transition between games H 1.q-1.1 and H 1.q-1.2 , we consider an intermediate game H 1.q-1.2 which is like H 1.q-1.2 except the vector [ k 1 ] 2 from the q-th key is sampled uniformly over span([ b 2 ] 2 , [ b 3 ] 2 ). We build PPT adversaries B 1.q-1.2 and B 1.q-1.3 such that: λ). By Lemma 3.8, this implies the existence of a PPT adversary B 1.q-1.2 such that

|Adv H1.q-1.2 (A)-Adv H 1.q-1.2 (A)| ≤ Adv As-3 PG,B 1.q-1.2 (λ), and |Adv H 1.q-1.2 (A)-Adv H1.q-1.3 (A)| ≤ Adv As-4 PG,B 1.q-1.3 (
|Adv H1.q-1.2 (A) -Adv H1.q-1.3 (A)| ≤ 2 • Adv DDH G2,B1.q-1.2 (λ). Upon receiving ( u 1 , u 2 , b * , [ b] 2 , [ b 3 ] 2 , [ z] 2 ), B 1.q-1 computes the challenge ciphertext as c β 2 + c 0 2 with c β 2 := ( b * w 1 0 | . . . | b * w 1 n )C β and c 0 2 := ( u 1 w 2 0 + u 2 w 3 0 | . . . | u 1 w 2 n + u 2 w 3 n )C 0 with w 1 i , w 2 i , w 3 i ← R Z p for all i ∈ [0, n].
It computes the keys as follows. For the q-1 first keys, it samples

[ k 1 ] 2 ← R span([ b 3 ] 2 ); for the q-th key, it uses [ k 1 ] 2 := [ z] 2 , and for the last Q -q -1 keys it computes [ k 1 ] 2 ← R span([ b] 2 ). The rest of the keys are computed as [ k 2 ] 2 := [( w 0 k 1 | w 1 k 1 | • • • | w n k 1 )K] T , [k 3 ] 2 := [ w 0 k 1 ] 2 , with w i := b * w 1 i + u 1 w 2 i + u 2 w 3 i for all i ∈ [0, n].
The adversary B 1.q-1.3 works similarly. Game H 1.q : the transition between games H 1.q-1.3 and H 1.q is similar to the transition between games H 0 and H 1 .

Namely,we switch the distribution of the challenge ciphertext, using the fact that the following distributions are identical:

(w 2 0 | . . . |w 2 0 ) C β and (w 2 0 | . . . |w 2 0 ) C 0 ,
where w 2 0 , . . . , w 2 n ← R Z p , C β := EncCt(P β , x β ), and C 0 := EncCt(P 0 , x 0 ). The leftmost distribution corresponds to game H 1.q , whereas the rightmost distribution corresponds to the game H 1.q-1.3 . Thus, we have:

Adv H1.q-1.3 (A) = Adv H1.q (A).

Game H 2 : the transition between games H 1.Q and H 2 is also similar to the transition between games H 0 and H 1 . Namely, we switch the distribution of the challenge ciphertext, using the fact that the following distributions are identical:

(w 1 0 | . . . |w 1 0 ) C β and (w 1 0 | . . . |w 1 0 ) C 0 ,
where w 1 0 , . . . , w 1 n ← R Z p , C β := EncCt(P β , x β ), and C 0 := EncCt(P 0 , x 0 ). The leftmost distribution corresponds to game H 1.Q , whereas the rightmost distribution corresponds to the game H 2 . Thus, we have:

Adv H 1.Q (A) = Adv H2 (A).
H1.q, H1.q.1,H1.q.2, H1.q.3, H2:

β ←R {0, 1}, PG ← PGGen(1 λ ), (n, |ct|, |sk|) ← Param(F), let ( b| b2| b3) and ( b * | b * 2 | b * 3 ) be two random dual basis of Z 3 p . For all i ∈ [0, n], j ∈ [3], wi ←R Z 3 p . We write wi := w 1 i b * + w 2 i b * 1 + w 3 i b * 3 (P 0 , x 0 ), (P 1 , x 1 ) ← A(1 λ ) ct ←R OEnc (P 0 , x 0 ), (P 1 , x 1 ) β ← A OKeyGen(•) (ct ) Return 1 if β = β, 0 otherwise.
OEnc (P 0 , x 0 ), (P 1 , x 1 ) : H1.q, H1.q.1, H1.q.2, H1.q.3 , H2

C β := EncCt(P β , x β ), C 0 := EncCt(P 0 , x 0 ) c β 2 := ( b * w 1 0 + b * 2 w 2 0 | . . . | b * w 1 n + b * 2 w 2 n )C β c β 2 := ( b * w 1 0 | . . . | b * w 1 n )C β c β 2 := 0 c 0 2 := ( b * 3 w 3 0 | . . . | b * 3 w 3 n )C 0 c 0 2 := ( b * 2 w 2 0 + b * 3 w 3 0 | . . . | b * 2 w 2 n + b * 3 w 3 n )C 0 c 0 2 := ( w 0 | . . . | w n )C 0 c2 := c β 2 + c 0 2 Return ct := (part(P β , x β ), c2)
OKeyGen(att, y): H1.q, H1.q.1,H1.q.2 , H1.q.3 , H2

On the ρ-th query if ρ ≤ q, then k1 ←R span( b3). If ρ > q, then k1 ←R span( b).

If ρ = q + 1, then k1 ←R span( b2). If ρ = q + 1, then k1 ←R span( b3).
For all ρ, k1 ←R span( b3)

K := EncKey(att, y), [ k 2 ]2 := [( w 0 k1| w 1 k1| • • • | w n k1)K]T , [k3]2 := [ w 0 k1]2. Return (att, y, [ k1]2, [ k 2 ]2, [k3]2)
Fig. 9. Hybrid games for the proof of Lemma 3.7, where q ∈ [Q], and Q denotes the number of queries to OKeyGen.

Proof. Let A be a PPT adversary. For each assumption i, we build a PPT adversary B i that has a greater advantage in breaking DDH in G 2 that the advantage of A in breaking Assumption i. Upon receiving

(PG, [ a] 2 , [ t] 2 ), where PG ← R PGGen(1 λ ), a ← R DDH, [ t] 2 := [ as] 2 with s ← R Z p , or [ t] 2 ← R G 2 2
, adversary B i does the following:

Assumption 1: B 1 samples u 1 , u 2 , b * 3 ← R Z 3 p , compute [ a] 2 such that a a b * 3 = 0. Writing b * 3 :=   α β γ   and
assuming γ = 0, this can be done efficiently by setting

[ a] 2 := -[ a] 2 ( α β ) γ . Similarly, compute [ t] 2 := -[ t] 2 ( α β ) γ . Set [ b] 2 := a a 2 , [ z] 2 := z z 2 sample b 3 ← R Z 3 p such that b 3 b * 3 = 0 and return u 1 , u 2 , b * 3 , [ b] 2 , [ b 3 ] 2 , [ z] 2 to A. Assumption 2: B 2 samples u 1 , u 2 , b * 3 ← R Z 3 p , compute [ z] 2 as B 1 . Set [ z] 2 := z z 2 , sample b, b 3 ← R Z 3 p such that b b * 3 = b 3 b * 3 = 0, and return u 1 , u 2 , b * 3 , [ b] 2 , [ b 3 ] 2 , [ z] 2 to A. Assumption 3: B 3 samples b * , u 1 , u 2 ← R Z 3 p , compute [ z] 2 such that z z b * = 0, which can be done efficiently, as B 1 (replacing b * 3 with b * ). Set [ z] 2 := z z 2 , sample b, b 3 ← R Z 3 p such that b 3 b * 3 = 0 and b b * = 1, and return b * , u 1 , u 2 , [ b] 2 , [ b 3 ] 2 , [ z] 2 to A. Assumption 4: B 4 samples b * , u 1 , u 2 ← R Z 3 p , compute [ a] 2 and [ z] 2 such that a a b * = 0 and z z b * = 0, re- spectively. Set [ b 3 ] 2 := a a 2 , [ z] 2 := z z 2 , sample b ← R Z 3 p such that b b * = 1, and return b * , u 1 , u 2 , [ b] 2 , [ b 3 ] 2 , [ z] 2 to A. H0, H1 : β ←R {0, 1}, PG ← PGGen(1 λ ), (n, |ct|, |sk|) ← Param(F ipfe(d,B) , P), let ( b| b2| b3) and ( b * | b * 2 | b * 3 ) be two random dual basis of Z 3 p . For all i ∈ [0, n], wi ←R Z 3 p . We write wi := w 1 i b * + w 2 i b * 1 + w 3 i b * 3 , with w 1 i , w 2 i , w 3 i ←R Zp (P 0 , x 0 ), (P 1 , x 1 ) ← A(1 λ ) ct ←R OEnc (P 0 , x 0 ), (P 1 , x 1 ) β ← A OKeyGen(•) (ct ) Return 1 if β = β, 0 otherwise.
OEnc (P 0 , x 0 ), (P 1 , x 1 ) :

C β := EncCt(P β , x β ), C 0 := EncCt(P 0 , x 0 ), c β 2 := ( w 0 | . . . | w n )C β , c β 2 := ( b * w 1 0 + b * 2 w 2 0 | . . . | b * w 1 n + b * 2 w 2 n )C β , c 0 2 := 0 , c 0 2 := ( b * 3 w 3 0 | . . . | b * 3 w 3 n )C 0 , c2 := c β 2 + c 0 2 . Return ct := (part(P β , x β ), c2) OKeyGen(att, y): k1 ←R span( b), K := EncKey(att, y), [ k 2 ]2 := [( w 0 k1| w 1 k1| • • • | w n k1)K]2, [k3]2 := [ w 0 k1]2. Return (att, y, [ k1]2, [ k2]2, [k3]2)
Fig. 10. Hybrid games for the proofs of Theorem 3.6 and Lemma 3.7.

A Lattice-Based Identity-Based Functional Encryption in the Random-Oracle Model

In this section, we build an identity-based functional encryption (IFE) for the inner-product functionality from LWE in the random-oracle model. In Section 5, we provide a lattice-based scheme that is proven secure in the standard model.

Lattice Preliminaries

Matrix norms For a vector u, u denotes its 2 norm. For a matrix R, by R we denote the result of applying Gram Schmidt orthogonalization on the columns of R. In addition:

-R denotes the 2 norm of the longest column of R.

-R 2 denotes the operator norm of R, where R 2 = sup x =1 R x , with x ∈ Z m s 1 (R) denotes the spectral norm (the largest singular value of R).

Known facts are that R ≤ R ≤ R 2 ≤ √ k R .
We will also need the fact that concatenating two matrices R, S yields s 1 (R|S) ≤ s 1 (R) 2 + s 1 (S 2 ). For bounding the spectral norm, we will require the following lemma: Lemma 4.1. [DM14] Let X ∈ R n×m be a subgaussian random matrix with parameter s. There exists a universal constant C ≈ 1 √ 2π such that for any t ≥ 0, we have s

1 (X) ≤ C • s • ( √ m + √ n + t) except with probability at most 2 e πt 2 .
Lattices. For any matrix A ∈ Z n×m q and any vector p ∈ Z n q , we define the orthogonal q-ary lattice of A: Λ ⊥ q (A) := { u ∈ Z m : A u = 0 mod q} and the shifted lattice: Λ p q (A) := { u ∈ Z m : A u = p mod q}. Similarly, for any matrix P ∈ Z n× q , we define: Λ P q (A) := {U ∈ Z m× : AU = P mod q}.

Probability distributions Consider a lattice Λ ⊆ Z m . The normal Gaussian distribution of mean 0 and variance σ 2 is the distribution on R with probability density function

1 σ• √ 2π 1 e x 2 /(2σ 2 )
. The lattice gaussian distribution with support Λ ⊆ R n , standard deviation σ and centered at c is defined as: for all y ∈ Λ : D Λ,σ, c ( y) = e -π y-c 2 /σ 2 x∈Λ e -π x-c 2 /σ 2 Lemma 4.2 (Bounding Gaussian Noise). [MR04] For any n-dimensional lattice Λ, c ∈ span(Λ), real ∈ (0, 1), and s ≥ η (Λ), Pr

x←RD Λ,s,c [ x -c > s √ n] ≤ 1+ 1- 1 2 n .
Also from [MR04, Lemma 3.2], for any n-dimensional lattice Λ, η (Λ) ≤ √ n/λ 1 (Λ * ), where = 1 2 n . This was improved by [GPV08] to obtain that for any ω(

√ log n) function, there is a negligible (n) such that: η (Z) ≤ ω( √ log n).
In particular, when sampling integers, we have that for any ∈ (0, 1 2 ) any s ≥ η (Z), and any t ≥ ω(

√ log n): Pr x←RD Z,s,c [|x -c| > s • t] ≤ negl(n).
Learning with errors (LWE) [Reg05] Let q be a prime, χ be a public distribution over Z q and s be uniformly random over Z n q . Moreover, s is constant across calls to oracles O ∫ or O $ , defined below: -Oracle O s outputs samples ( a, a s + x), where a ← R Z n q and x ← R χ are fresh and independently sampled. -Oracle O $ outputs uniformly random elements of Z n q × Z q . Define another oracle O, which across all calls, is either O s or O $ . The learning with errors LWE q,χ,n problem is to distinguish with non-negligible probability, given access to oracle O, whether it corresponds to O s or O $ .

Proposition 4.3 ([Reg05]

). Let α = α(n) ∈ (0, 1) and let q = q(n) be a prime such that α • q > 2 √ n. If there exists an efficient (possibly quantum) algorithm that solves LWE q, ψα , then there exists an efficient quantum algorithm for approximating SIVP and GapSVP in the 2 norm, in the worst case, to within O(n/α) factors.

In [Pei07], this result has been generalized for any p norm, with 2 ≤ p ≤ ∞ and for similar O(n/α) approximation factors.

Theorem 4.4. [GPV08, Theorem 4.1] There is a probabilistic polynomial-time algorithm SampleD that, given a basis B of an n-dimensional lattice ∆ = L(B), a parameter s ≥ B • ω( √ log n), and a center c ∈ R, outputs a sample from a distribution that is statistically close to D Λ,s, c . Proposition 4.5. [Ajt99] For any prime q = poly(n) and any m ≥ 5n lg q, there is a probabilistic polynomial-time algorithm SampleMat that, on input 1 n , outputs a matrix A ∈ Z n×m q and a full-rank set S ⊂ Λ ⊥ q (A), where the distribution of A is statistically close to uniform over Z n×m q and the length S ≤ L = m 2.5 . Also, by [MG02, Lemma 7.1, page 129], S can be converted efficiently to a "good" basis T of Λ ⊥ q (A) such that T ≤ S ≤ L.

Lemma 4.6 ([GPV08]Preimage Samplable Functions). For any prime q = poly(n), any m ≥ 5n lg q, and any s ≥ L • ω( √ log m), it holds that there exist PPT algorithms TrapGen, SampleD, SamplePre such that:

1. TrapGen computes (A, T) ← R TrapGen(1 n , 1 m ), where A ∈ Z m×n q
is statistically close to uniform and T ⊂ Λ ⊥ q (A) is a good basis with T ≤ L. The matrix A (and q) are public, while the good basis T is the trapdoor. 2. SampleD samples vectors e from D Z ×m ,s . 3. The trapdoor inversion algorithm SamplePre(A, T, s, U) outputs a matrix Z ∈ Z ×m such that U = ZA.

In addition, it holds that the following distributions D 1 , D 2 are statistically close:

D 1 := (A, Z, U), s.t. (A, T) ← R TrapGen(1 n , 1 m ), U ← R Z ×n , Z ← R SamplePre(A, T, s, U) D 2 := (A, Z, ZA), where A ← R Z m×n q , Z ← R D Z ×m ,s : z i ≤ s √ m, i ∈ {1 . . . m}
where z i denotes the i-th row of Z.

Setup(1 λ , X , Y):

(A, T) ←R TrapGen(1 n , 1 m ) mpk ← A, msk ← T Enc(mpk, id, x): U id ← H(id) s ←R Z n q f1 ←R D Z m ,σ f2 ←R D Z ,σ ct1 ← A s + f1 ct2 = U id s + f2 + q K • x Return (ct1, ct2) KeyGen(id, y): U id ← H(id) Z id ←R SamplePre(A, T, ρ, U id ) Return ( y, sk id, y := ( y • Z id ))
Dec ct1, ct2, sk id, y , y):

µ = y • ct2 -sk id, y • ct1 µ = arg min µ ∈{0...K+1} q K • µ -µ Return µ

Our Construction

In this section, we describe how to obtain an identity-based inner-product funtional encryption scheme based on the hardness of LWE in the random-oracle model. Our idea is to start with a modification of the ALS functional encryption scheme for inner-products [ALS16], proposed by [WFL19] and which we recall in Appendix A. We modify the identity-based encryption scheme of [GPV08] in such a way as to support functional key generation queries, as in ALS. Our construction is described in Fig. 11. Ciphertexts encode vectors x ∈ X := {0, . . . , P -1} under an identity id. Secret keys correspond to an identity id and a vector y ∈ Y := {0, . . . , V -1} . When the identities match, our scheme decrypts the bounded inner-product x, y ∈ {0, . . . , K -1} where K = P V .

Since our construction achieves anonymity and the size of input vectors x are fixed, no partial information about the input is leaked. That is, part( x, id) =⊥.

Lemma 4.8 (Correctness). For q ≥ 2K √ V ω(log 2 n), σ = 2Cαq( √ m+ √ n+ √ ), ρ ≥ ω( √ log
n), m = 2n log q, the scheme from Fig. 11 is correct.

Proof. When identities match, observe that decryption yields y U s + y f 2 + y ZA s + y Z f 1 + q K x, y , which is equal to:

y f 2 + y Z f 1 error terms + q K x, y
This decrypts correctly as long as the error terms are small. From Lemma 4.2, we know that every entry of Z is with overwhelming probability bounded by ω(log n), so Z ≤ √

• ω(log n), as long as ρ ≥ ω( √ log n). We use Lemma 4.2 once again and we bound y Z e 1 ≤ √

V ω(log 2 n) and y e 2 ≤ V ω( √ log n), as long as

Finally, when id = id * , we need to argue that ALS public keys are distributed statistically close to honestly generated keys in Game 0 . Note that in ALS, the second matrix D ALS is not uniformly random like in Game 0 , but instead is of the form D ALS = Z ALS A ALS (in fact in can be proven that U is not statistically close to uniformly random). However, this is not an issue in our case, as the distribution of U id * is in fact uniform conditioned on it being of the form Z id * A. Therefore, we can apply Lemma 4.6 once again, and conclude that (A, Z id * , U id * ) with trapdoored A and uniform U id * is statistically close to (A, Z id * , Z id * A).

Case 2, id * 0 = id * 1 In this case, we make the following observation: if the adversary was allowed to obtain secret keys for either id * 0 y or id * 1 y, for any y, then it could trivially distinguish between encryptions of x 0 under id * 0 and encryptions of x 1 under id * 1 . This type of trivial attack is excluded by the AD-IND definition, therefore we conclude that the adversary cannot obtain decryption key queries for neither id * 0 or id * 1 . With this limitation, we can perform a reduction directly to LWE for matrix

B =   A U id * 0 U id * 1   ∈ Z (m+2 )×n q
, where B is uniformly random. We obtain a ciphertext c = ( c 1 , c 2 , c 3 ) from the LWE oracle. To simulate the view of A, we set H(id * 0 ) = U id * 0 and H(U id * 1 ). For all the other keys, we proceed as in the previous case:

1. For every id / ∈ {id * 0 , id * 1 } query to the random oracle H, we draw a matrix Z id ← R D Z ×m ,ρ . We program the random oracle H(id) = U id , where U id is now computed as U id = Z id A. 2. For every id / ∈ {id * 0 , id * 1 }, key queries of the form id y are answered by returning y Z id .

Challenge queries to answer a challenge encryption for x 0 under id * 0 or x 1 under id * 1 , we pick uniformly at random a bit β and reply with:

( c 0 , c 1 + q K • x 0 ), if β = 0 and ( c 0 , c 2 + q K • x 1 ), if β = 1
If the LWE oracle outputs a uniformly random element, then Adv Game1 (A) ≤ Adv LWEq,α,n (A) and the view is identical to Game 1 . When the LWE oracle outputs an element of the form c = B d + g, with d ← R Z n q and g ← R D Z m+2 , the split into ( c 0 , c 1 , c 2 ) ∈ Z m q × (Z q ) 2 produces ciphertexts formed exactly as in Game 0 . We are left to argue that (A, U id * 0 , U id * 1 ) in Game 1 is distributed statistically close as in Game 2 , which is the case by Lemma 4.6.

We have thus proven that:

Adv IND-FE-CPA (A) ≤ 1 Q 2 max(Adv LWEq,α,n (A), Adv LWE q,σ/q,n (A)) ≤ 1 Q 2 Adv LWEq,α,n (A),
where Q is the number of random-oracle queries.

A Lattice-Based Identity-Based Functional Encryption in the Standard Model

In this section, we present a lattice-based IFE construction for the inner-product functionality in the standard model. However, before doing so, we first recall some known results that we are going to use in our construction and security proofs.

Preliminaries

Lemma 5.1 ([BGG + 14]). Let n, m, q > 0 be integers, where q prime. There exist polynomial time algorithms, such that:

Definition 5.9 (Indistinguishability from Random). This security notion for IBE implies both indistinguishability and receiver anonymity (meaning that for every id, without sk id , one is not able to determine whether any ciphertext is encrypted under id). Moreover, any ciphertext should be indistinguishable from a uniformly random element from the ciphertext space. More formally, consider the following security game for any stateful PPT adversary A, and every security parameter λ, and β ∈ {0, 1}:

Experiment INDr-sID-CPA β (1 λ , A): id * ← A(1 λ ) (pk, mk) ← Setup(1 λ ) x * ← A Extract(•) (pk) ct ← R C if β = 0 then ct ← Enc(pk, id * , x * ) β ← A Extract(•) (pk, ct ) Output: β
where C is the ciphertext space. Extract(•) is an oracle that on input id, outputs Extract(mk, id), only if id = id * . An identity encryption scheme is INDr-sID-CPA-secure if for every PPT adversary A, the following advantage is a negligible function of λ:

Adv INDr-sID-CPA A (λ) = Pr INDr-sID-CPA 0 (1 λ , A) = 1 - Pr INDr-sID-CPA 1 (1 λ , A) = 1

Our Construction

In this section, we combine the construction idea showcased in Section 4 with the standard-model IBE of [ABB10]. Similarly to the random-oracle model, we prove the resulting scheme anonymous, a property inherited by the underlying IBE scheme [ABB10] we build on. What we obtain is a scheme which is selectively secure with respect to the identities id * 0 , id * 1 used for the challenges x 0 and x 1 . Since the scheme will make use once again of ALS as a building block, the security will be adaptive with respect to the challenge vectors x 0 , x 1 themselves. The construction is described in Fig. 12. From our choice of q, this error is small enough to allow correct decryption.

Parameters Recall that plaintext vectors x ∈ X = {0, . . . , P -1}, decryption key vectors y ∈ Y = {0, . . . , V -1} and when identities match, we recover x, y ∈ {0, . . . , K -1} with K = P V . A first-time reader may want to skip this paragraph, as it references steps of the proof. Combining the ALS requirements from Appendix A with the parameters from [ABB10]. our scheme parameters must satisfy the following:

-We start with ALS parameters n ALS (the security parameter), q ALS , σ ALS , ρ ALS , m ALS = 2n ALS log q, n = n ALS , α ALS , chosen as in Appendix A. -From the ALS reduction in Game 5 , σ = σ ALS , q = q ALS , n = n ALS . m = m ALS , ρ = ρ ALS .

-SampleLeft and SampleRight, we require that ρ > m • ω( √ log m). -TrapGen requires that m > 6n log q.

-Leftover hash lemma, this carries over from ALS parameters.

-Guessing T A step: ρ > n • ω( √ n).
Notice that increasing ρ ALS can be done without invalidating LWE security. We only need to increase q ALS to satisfy correctness.

-Hardness of LWE: αq > 2 √ n.

-NoiseGen: The spectral norm of S * can be upper-bounded (by using the Frobenius norm) by s 1 (S * ) ≤ m. Using Lemma 4.1,

s 1 (Z 2 ) ≤ C • ρ(2 √ n + √ m), which implies that τ ≥ C • mρ(2 √ n + √ m). -Correctness: q > 2K V (σ + τ ) + C σρ4m √
nmV . Therefore, we choose ALS parameters, and then modify the following to satisfy our additional constraints:

• m ≥ 6n log q.

• q is now q > 2K V (σ + τ ) + C σρ4m √ nmV .

-Decryption keys for id = id * : Using SampleRight as in previous games.

-Challenge ciphertext upon receiving x 0 , x 1 from the adversary, we forward them to the ALS challenger and receive (ct ALS 1 , ct ALS 2 ). Then, compute and return:

ct 1 = ct ALS 1 + (S * ) ct ALS 1 ct 2 = ct ALS 2 + Z 2 (S * ) ct ALS 1 + NoiseGen(Z 2 (S * ) , s)
In this game the advantage of the adversary is upper bounded by the advantage of breaking the ALS scheme. It remains to show that Game 5 is indistinguishable from Game 4 . We start by spliting R id * := Z 1 Z 2 . Then the fact that

(A AS * )R id * = D translates to the fact that AZ 1 + AS * Z 2 = D.
The second matrix Z 2 we can simply sample from D Z n×m ,ρ,c , while S * is known and D is programmable (since Game 2 ). Now we set A = A ALS and implicitly Z 1 A = D ALS (Recall that Z 1 is the master secret key of ALS, so we do not have access to it). Notice that:

ct 1 = (I m |S * ) (A s + e 1 ) = (A|AS * ) s + (I m |S * ) e 1 ct 2 = D s + q K • x + e 2 = Z 1 A s + Z 2 (S * ) A s + q K • x β
, Let e 1 be the noise of the first ALS ciphertext. Then we can rewrite to:

ct 1 = ct ALS 1 + (S * ) ct ALS 1 ct 2 = D s + q K • x + e 2 + e 3 = ct ALS 2 + Z 2 (S * ) ct ALS 1 + NoiseGen(Z 2 (S * ) , s)
As already explained in our parameter section, we can upper-bound s 1 (Z 2 (S * )) and we let s > s 1 (Z 2 (S * )). To conclude, by the properties of NoiseGen(Z 2 (S * ) , s), we know that the noise in ct 2 will be statistically close to e 2 + e 3 , therefore Game 5 is statistically close to Game 4 .

6 Multi-Input Inner-Product Functional Encryption with Rich Access Control

In this section, we build a multi-input FE scheme for the family of functions F multi ipfe(d,B),P1,...,Pn for a dimension d ∈ N, a bound B ∈ N, and n predicates P 1 , . . . , P n ∈ P, where each predicate takes as input an attribute in the universe U, and returns a bit. Each function is described by a set of indices S ⊆ [n], and for each index ∈ S, an associated pair

(att i ∈ U, y i ∈ [0, B] d ). It takes as input n vectors x 1 , . . . , x n ∈ [0, B] d , and outputs i∈S x i y i ∈ [0, ndB 2 ] if P i (att i ) = 1 for all i ∈ S.
Note that to each input slot corresponds to a different predicate P i , which represents a different policy access to the encrypted data. For instance, some medical data can be considered very sensitive, and should only be computed on by doctors, whereas other records might be slightly less sensitive, and could pertain to the output of a computation performed by a user with lower credentials, say, a health insurance company. Each functional secret key permits to compute a weighted sum on some part of the data for which it has credentials (this is represented by the set S). That is, a key decrypts successfully provided it is associated with attributes that satisfy the predicates associated with the encrypted data on which it computes.

Our construction generically transforms any single-input FE for the family of functions F ipfe(d+1,B),P (described in Section 3) satisfying some structural properties into an MIFE for the family of functions F multi ipfe(d,B),P1,...,Pn . We first recall the definition of multi-input FE and then describe our construction.

Definitions

Definition 6.1 (Multi-Input Functional Encryption [GGG + 14]). Let F be a family of n-ary functions, with f ∈ F defined as f : X n → Y. A functional encryption scheme for F consists of the following algorithms:

-Setup(1 λ , F): takes as input the security parameter λ and a description of the function family F, and outputs a master public key mpk (which is implicitly part of the inputs of all other algorithms), a master secret key msk, and n encryption keys ek 1 , . . . , ek n . -Enc(ek i , x i ): takes as input an encryption key ek i , a message x i ∈ X , and outputs a ciphertext ct i .

-KeyGen(msk, f ): takes as input the master secret key msk, a function f ∈ F. It outputs a functional decryption key sk f .

-Dec sk f , (ct 1 , . . . , ct n ) : takes as input the functional decryption key sk f along with ciphertexts (ct 1 , . . . , ct n ).

It outputs a value y ∈ Y or the special symbol ⊥ if it fails.

A scheme as defined above is correct if for all security parameter λ, f ∈ F, x 1 , . . . , x n ∈ X , we have:

Pr Dec sk f , (ct 1 , . . . , ct n ) = f (x 1 , . . . , x n ) = 1
where the probability is taken over (mpk, msk, (ek 1 , . . . ,

ek n )) ← Setup(1 λ , F), ct i ← Enc(ek i , x i ) for all i ∈ [n], sk f ← KeyGen(msk, f ).
Definition 6.2 (AD-IND security). For every functional encryption MIFE, every security parameter λ, every stateful adversary A, we define the following experiments for β ∈ {0, 1}:

Experiment AD-IND F E β (1 λ , A): (mpk, msk, (ek 1 , . . . , ek n )) ← Setup(1 λ , F) β ← A OCorrupt(•),OKeyGen(•),OEnc(•,•,•) (mpk) Output: β
where n is the number of users; on input i ∈ [n], the oracle OCorrupt(i) returns ek i and adds i to the set Corr of corrupted users; on input tuples of the form (i, x 0 , x 1 ) where i ∈ [n], x 0 , x 1 ∈ X , the oracle OEnc(i, x 0 , x 1 ) returns Enc(ek i , x β ) and adds (i, x 0 , x 1 ) to the list of queries, denoted by Q; on input a function f ∈ F of arity n, the oracle OKeyGen(f ) returns the functional decryption key sk f ← KeyGen(msk, f ).

We denote by I the set of pairs (x 0 1 , . . . , x 0 ), (x 1 1 , . . . , x 1 ) where for all i ∈ Hon, (i, x 0 i , x 1 i ) ∈ Q and for all i ∈ Corr, x 0 i = x 1 i ∈ X . We require that for all functions f queried to OKeyGen, we have: f (x 0 1 , . . . , x 0 ) = f (x 1 1 , . . . , x 1 ) for all pairs (x 0 1 , . . . , x 0 ), (x 1 1 , . . . , x 1 ) ∈ I. Moreover, we require that for all users i that are corrupted during the game, all the queries of the form (i, x 0 , x 1 ) ∈ Q are such that x 0 = x 1 .

Using generic transformations from [ABKW19, Gay19], which build upon [AGRW17, DOT18], we can assume without loss of generality that, if i ∈ Hon, then there exists a query (i, x 0 i , x 1 i ) ∈ Q. A multi-input functional encryption scheme FE is AD-IND-secure if for every PPT adversary A, the following advantage is a negligible function of λ:

Adv AD-IND F E,A (λ) = Pr AD-IND F E 0 (1 λ , A) = 1 -Pr AD-IND F E 1 (1 λ , A) = 1
We define one-time security with its associated games ONE

-AD-IND F E b and advantage Adv ONE-AD-IND F E,A (
λ) similarly, except the adversary can make at most one query of the form (i, x 0 i , x 1 i ) for each slot i ∈ [n]. There are weaker security notions, where the set of corrupted users Corr, or the set of queries Q is chosen beforehand by the adversary. The former restriction is referred to as static corruptions, whereas the second restriction is referred to as selective security.

The proof, as in [ACF + 18, AGRW17], proceeds in two steps, where we first prove perfect one-time security, then boost it to many-time security using the many-time security of the underlying single-input FE. The adaptive and selective settings have very similar proofs, thus, we only give the proof in the adaptive setting, which is the most technical. Proof. First, in Lemma 6.4, we show that for any adversary A, we have:

Adv ONE-AD-IND MIF E,A (λ) = 0.
Next, for all PPT adversaries A, we show there exist PPT adversaries B 1 and B 2 such that:

Adv AD-IND MIF E,A (λ) ≤ Adv ONE-AD-IND MIF E,B1 (λ) + n • Adv AD-IND F E ,B2 (
λ) + negl(λ). The proof uses a series of hybrid games, described in Fig. 14. For game G j for all j ∈ [1, 3], we denote by Adv j (A) the probability that game G j outputs 1 when interacting with A. Here, for any input slot i ∈ [n], we denote by (i, x j,0 i , x j,1 i ) the j-th query for slot i ∈ [n] (note that there can be many such queries for each slot). It is clear that games G 1 and G 3 correspond to AD-IND F E 0 (1 λ , A) and AD-IND F E 1 (1 λ , A), respectively. We show in Lemma 6.5 that there exists a PPT adversary B 1 such that

|Adv 1 (A) -Adv 2 (A)| ≤ Adv ONE-AD-IND MIF E,B1 (λ)
. We show in Lemma 6.6 that there exists a PPT adversary B 2 such that

|Adv 2 (A) -Adv 3 (A)| ≤ n • Adv AD-IND F E ,B2 (λ) + negl(λ).
Lemma 6.4. For any adversary A, we have:

Adv ONE-AD-IND MIF E,A (λ) = 0.
Proof. We first define a game G 0 , which samples a random bit β ← R {0, 1}, and a guess of all the queries ( w

0 i , w 1 i ) ← R ([0, B] d ) 2 for all i ∈ [n]. Then the experiment behaves as AD-IND F E β (1 λ , A).
At the end of the experiment, the adversary A outputs a bit β . If the guess was successful, that is, the queries made by A were predicted correctly, with w 0 i = x 0 i and w 1 i = x 1 i , then the experiment outputs β . Otherwise, it outputs a random bit β ← R {0, 1}. We define the advantage Adv G0 (λ) :

= 2 • |1/2 -Pr[β = β|β ← G 0 ]|. We have: Adv G0 (λ) = B 2dn • Adv ONE-AD-IND MIF E,A (λ). Now, we show that Adv G0 (λ) = 0, which implies that Adv ONE-AD-IND MIF E,A (λ) = 0. We use the fact that { u i } i∈[n] , is identically distributed to { u i + w 1 i -w 0 i } i∈[n]
, where u i , w 0 i , w 1 i ← R Z d p . When the guess is successful, that is, when w 0 i = x 0 i and w 1 i = x 1 i for all i ∈ [n], the first distribution corresponds to case where b = 0 in the experiment G 0 , with challenge ciphertexts of the form Enc (mpk i , P i , x 0 i + u i mod p) and keys of the form {KeyGen (msk i , att i , y i )} i∈[n] , i∈[n] u i y i , whereas the second distribution corresponds to the case where b = 1 in the experiment G 0 , with challenge ciphertexts of the form Enc (mpk i , P i , x 0 i + ( u i + x 1 ix 0 i ) mod p) = Enc (mpk i , P i , x 1 i + u i mod p) and keys of the form (S, {KeyGen (msk i , att i , y i )} i∈S , i∈S ( u i + x 1 i -x 0 i ) y i = i∈S u i y i ), where the last equality uses the fact that i∈S y i x 0 i = i∈S y i x 1 i , by definition of the security game. Lemma 6.5 (From Game G 1 to G 2 ). There exists a PPT adversary B 1 such that

|Adv 1 (A) -Adv 2 (A)| ≤ Adv ONE-AD-IND
MIF E,B1 (λ). Proof. Adversary B 1 receives mpk which it forwards to A. When A queries OKeyGen or OCorrupt, B forwards the query to its own oracle and gives back the answer to A. When A queries OEnc(i, x 1,0 i , x 1,1 x ) on slot i ∈ [n] for the first time, B 1 forwards the query to its own oracle and gives back the answer to A, which is of the form ct i ← R Enc (mpk i , P i , x 1,b i + u i mod p). For any subsequent queries (i, x j,0 i , x j,1 x ) to OEnc, that is, for j > 1, B 1 uses the linear homomorphism to compute ct i ← R Add(ct i , x j,0 i -x 1,0 i ), which by property 3 is distributed as a fresh encryption of the form Enc (mpk i , P i , x j,0 i + x 1,b i -x 1,0 i ). Note that in the case b = 0, this corresponds to the game G 1 , whereas it corresponds to the game G 2 when b = 1. Lemma 6.6 (From Game G 2 to G 3 ). There exists a PPT adversary B 2 such that |Adv 2 (A) -Adv 3 (A)| ≤ n • Adv AD-IND F E ,B2 (λ) + negl(λ).

Proof. We switch the distribution of the challenge ciphertexts output by OEnc, one slot i ∈ [n] at a time, using a hybrid argument. To change the ciphertexts for slot i ∈ [n], we use the security of FE on (mpk i , msk i ). Namely, the reduction B 2 samples (mpk θ , msk θ ) ← R Setup (F ipfe(d,B),P ) for all θ = i and u i ← R Z d p for i ∈ [n], and it uses these values to simulate mpk and answer the queries (θ, x j,0 θ , x j,1 θ ) for all θ = i. B 2 can also answer queries to OCorrupt, since it knows ek i := u i for all i ∈ [n]. To answer A's queries to OKeyGen, it uses its own oracle to compute the sk i component of the secret key and its knowledge of msk θ for all θ = i and u i for i ∈ [n] to compute the remaining components, and forwards the answer to A. Upon receiving the queries (i, x j,0 i , x j,1 i ), B 2 sends the queries ( x j,0 i + x 1,1 i -x 1,0 i + u i mod p, x j,1 i + u i mod p) to its own experiment. The left challenge corresponds to the game G 2 , whereas the right challenge corresponds to the game G 3 . To use the AD-IND security of FE , we rely on the fact that ( x j,0 i -x 1,0 i ) y i = ( x j,1 i -x 1,1 i ) y i .

(1) This is required by definition of the security game, since this information is given by the ideal functionality (correctness of the scheme). For all i ∈ [n], any vector w i ∈ [-B, 2B] d , with probability at least 1 -3dB p over the choice of u i ← R Z d p , we have ( u i + w i ) mod p = ( u i mod p) + w i . Together with (1), this implies that: ( u i + x j,0 i + x 1,1 ix 1,0 i mod p) y i = ( x j,0 i + x 1,1 i -x 1,0 i ) y i + ( u i mod p) y i = x j,1 i y i + ( u i mod p) y i = ( x j,1 i + u i mod p) y i . That means the queries of B 2 to its experiment are valid.

G1, G2 , G3 :

(mpk, msk, (ek1, . . . , ekn)) ← Setup(1 λ , F multi ipfe(d,B),P 1 ,...,Pn ) β ← A OCorrupt(•),OKeyGen(•,•),OEnc(•,•,•) (mpk) OCorrupt(i): Return eki. OEnc(i, x j,0 i , x j,1 i ): cti ← Enc(eki, x j,0 i + x 1,1 i -x 1,0 i ) cti ← Enc(eki, x j,1 i ) Return cti.

OKeyGen(S, (attj, yj)j∈S ): sk att, y ← KeyGen(msk, S, (attj, yj)j∈S ). Return sk att, y . LWE q,α,n is reducible to lattice problems in dimension n when qα ≥ Ω( √ n). With this choice of parameters, we have the following theorem: Theorem A.2. [ALS16, WFL19] Let n be the security parameter, m ≥ 2n log q and q,σ, ρ, α ≤ σ 2Cαq( √ m+ √ n+ √ )

as described above. Then, the scheme from Fig. 15 is AD-IND-secure, assuming that LWE q,α,n is hard.

Proof. As mentioned previously, we recall the proof of the ALS scheme from [ALS16] in which Game 2 is modified with the idea described in [WFL19].

Game 1 This is the AD-IND game.

√ + √ m + √ λ)) 2 + 1
By computing c = V c + NoiseGen(V, σ ), we obtain c = V • c + f , where f ← R D Z m+ ,2rσ . Notice that we can split c into ct 1 ← A s + e 1 and ct 2 ← D s + e 2 , where e 1 ← D Z m ,2rσ and e 2 ← D Z ,2rσ . Now, to simulate ct 2 correctly, we need to compute ct 2 = ct 2 + q K • x β .

Game 3 By the LWE assumption, we change c = A s+ e into a uniformly random element u of Z m q . Now we argue that in this game, the probability the adversary has of winning is 1 2 . This step of the proof is identical to [ALS16, Theorem 2], which we recall here for completeness.

Consider y i the decryption key queries made by the adversary. Then, x 0 , y i = x 1 , y i over Z, for all i. Define x := 1 g ( x 1 -x 0 ) = 1 g (x 1 , . . . , x ), where g = 0 is the gcd of all coefficients of x 0 -x 1 . Since x, y i = 0, this means all decryption key queries must belong to the lattice { y ∈ Z : x, y = 0}. Assume without loss of generality that the first n 0 entries of x are zero, while the rest are non-zero.

Define matrix

Y top =          I n0 -x n0+2 -x n0+1 -x n0+3 . . . . . . -x x -1          ∈ Z -1×( )
Then they write Y bot = x ∈ Z 1× and define Y := Y top Y bot ∈ Z × q . By induction, they show that det(YY ) = ( -1 k=n0+2 x 2 k ) • x 4 . As long as q is large enough, this quantity is non-zero modulo q, which implies that Y is invertible modulo q. Observe that for ( g 1 , g 2 ) = NoiseGen(V, σ ) : ct 1 = u + g 1 and ct 2 = Z • u + g 2 + q K • x β , where u ← R Z m q . The proof strategy of [ALS16] is to show that the distribution of Y • ct 2 ∈ Z ×1 q is almost independent of β and therefore the probability of winning the game is almost 1 2 . Rewrite ct 2 = Y -1 • Y • (Z u + g 2 + q K • x β ) mod q.

Notice that Yct As long as the previous two lemmas hold, one can use the leftover hash lemma for the seed u and randomness Y bot Z to argue that given (A, ZA, Y top , Y top Z), the pair ( u, Y bot Z u) is 1/2 λ statistically close from the uniform distribution over Z m q × Z q , therefore hiding β. The variant of the leftover hash lemma used is the following: Lemma A.5 (Lemma 10 in [ALS16]). Let n, m, q ≥ 2 be positive integers. Assume that q = p k for p prime and k ≥ 1. Assume further that m ≥ 2n log 2 q. Let σ ≥ Ω( √ n + log m) and c ∈ Z m . Then for A ∈ Z m×n q sampled uniformly and e ∈ Z m sampled from D Z m ,σ,c , the distribution of the pair (A, e • A) is within statistical distance 2 -Ω(n) of uniform over Z m×n q × Z n q .

B Instantiations of Predicate Encodings B.1 Inner-product encryption with short ciphertexts [BBG05]

The predicate is described by a vector y ∈ Z n p , takes as input an attribute x ∈ Z n p , and outputs 1 if x y = 0, 0 otherwise. We recall the definition of read-once monotone span programs [KW93]. The predicate is described by a matrix M ∈ Z ×n p , takes as input an attribute x = (x 1 , . . . , x n ) ∈ {0, 1} n , and outputs 1 if the vector (1, 0, . . . , 0) ∈ Z n p is in the column span of M x , which denotes the collection of vectors {M j : x j = 1} where M j denotes the j'th column of M. That is, x satisfies M if there exists constants ω 1 , . . . , ω n ∈ Z p such that j:xj =1 ω j M j = (1, 0, . . . , 0)

(2)

Observe that the constants {ω j } j∈[n] can be computed in time polynomial in the size of the matrix M via Gaussian elimination.

-

  P, att): takes as input a predicate P ∈ P, an attribute att ∈ U, and returns a vector d ∈ Z |ct|+|sk| p . We require the following properties. Correctness. If P ∈ P and att ∈ U such that P(att) = 1, C := EncCt(P) ∈ Z n×|ct| p , K := EncKey(att) ∈ Z (n+1)×|sk| p , d := Decode(P, att), then 0 C K d = (1, 0, . . . , 0) ∈ Z n+1 p , where 0 ∈ Z 1×|ct| p

Fig. 1 .

 1 Fig. 1. A selectively-secure FE from pairings, for the function family F ipfe(d,B),P .

Fig. 4 .

 4 Fig. 4. Hybrid games for the proof of Theorem 3.2.

Fig. 5 .

 5 Fig. 5. Hybrid games for the proof of Lemma 3.4, where Hj is defined for all j ∈ [Q], and Hj.i are defined for all j ∈ [Q -1], i ∈ {1 . . . 9}. The six type of boxes denote which figure components belong to the hybrid.

Fig. 6 .

 6 Fig. 6. PPT simulator for the security proof of the FE scheme from Fig. 4.

  f ): takes as input a function f ∈ F, and returns a matrix K ∈ Z (n+1)×|sk| p . -Decode(f, part(x)): takes as input the partial information part(x) of x ∈ X and f ∈ F. It returns a vector d ∈ Z |ct|+|sk| p

v

  (C|K) with C := EncCt(x 0 ), K := EncKey(f ) and v (C|K) with C := EncCt(x 1 ), K := EncKey(f ), where v ← R Z n+1 p .

,

  d := Decode(part(P, x), att), [γ]T := [( d1, d2) d]T ∈ GT , Return out ∈ [0, dB 2 ] such that [γ]T = [ c 1 k3 • out]T . If there isn't such out, return ⊥.

Fig. 7 .

 7 Fig. 7. An adaptively-secure FE from pairings, for the function family F ipfe(d,B),P .

Fig. 11 .

 11 Fig. 11. An identity-based inner-product functional encryption scheme IFE in the random-oracle model, where H denotes the random oracle. Algorithms TrapGen and SamplePre are referenced in Lemma 4.6

Fig. 14 .

 14 Fig. 14. Hybrid games for the proof of Theorem 6.3.

Game 2

 2 Draw an error e ← R D Z m ,r and then compute c = A s + e. Let I m denote the m × m identity matrix. Now we apply Lemma 4.7 for V= I m Z ∈ Z (m+ )×m . Let σ > s 1 (V). By Lemma 4.1, we know that s 1 (Z) ≤ Cρ( with 1 e 2πλ probability and we use this to argue that s 1 (V) ≤ (Cρ(

  2 = Y top ct 2 Y bot ct 2 . Now Y top ct 2 does not depend on β because Y top • x 0 = Y top • x 1 ,from the functional encryption constraints. It remains to analyze Y bot ct 2 . Here, [ALS16] prove the following variant of the leftover hash lemma: Lemma A.3. [ALS16] Conditioned on (A, ZA, Y top , Y top Z), the min-entropy of Y bot Z is greater or equal than n log q + 2λ.This lemma can be applied as long as the following lemma due to [PR06] and adapted in [ALS16] holds for the standard deviation used to generate Z:Lemma A.4. [ALS16] Let Λ = k • Z be a 1-dimensional lattice. For any σ ≥ 10 • k, b ∈ λ and c ∈ R, we have that D Λ,σ,c (b) ≤ 3/4.In particular, we have H ∞ (D Λ,σ,c ) ≥ 0.4, where H ∞ () denotes the min-entropy.

-.-

  Param: returns the parameters (n + 2, |ct| = 1, |sk| = n + 1). -EncCt( x): given x ∈ Z n p returns a matrix C ∈ Z (n+2)×1 p such that C (v 1 , v 2 , w) = v 1 + x w ∈ Z p . -EncKey( y): given y ∈ Z n p returns a matrix K ∈ Z (n+3)×(n+1) p such that K (α, v 1 , v 2 , w) = (v 2 y + w, v 1 + α) ∈ Z n+1p Decode( x, y): if x y = 0, it returns the vector d := -policy ABE for monotone span programs[GPSW06]

  Param: returns the parameters (n + , |ct| = n, |sk| = n + 1).-EncCt(M): given M ∈ Z n× p returns a matrix C ∈ Z (n+2)×1 p such that C ( w, u, γ) = (w 1 + (γ, u) M 1 , . . . , w n + (γ, u) M n ) ∈ Z n p , where M j denotes the j'th column of M. -EncKey( x): given x ∈ {0, 1} n , returns a matrix K ∈ Z (n+3)×(n+1) p such that K (α, w, u, γ) = (γ+α, x 1 w 1 , . . . , x n w n ) ∈ Z n+1 p .-Decode( x, y): if x y = 0, it returns the vector d:= (x 1 ω 1 , . . . , x n ω n , 1, ω 1 , . . . , ω n ) ∈ Z 2n+1 p .More predicate encodings can be found in [CGW15], yielding inner-product encryption with short keys [BB04], non-zero inner-product encryption (introduced in [AL10]), spatial encryption [BH08, BBG05, LW10], ciphertextpolicy for arithmetic span programs [CGW15].

We stress that both schemes support exponentially large input domains, as for existing LWE-based inner-product FE schemes.

Acknowledgments. The first author was supported in part by the European Union's Horizon 2020 Research and Innovation Programme under grant agreement 780108 (FENTEC), by the ERC Project aSCEND (H2020 639554), and by the French FUI project ANBLIC. The third author was partially supported by a Google PhD Fellowship in Privacy and Security. The fourth author was partially supported by the ERC Project PREP-CRYPTO (H2020 724307). Part of this work was done while the third author was at École normale supérieure, Paris, France, at UC Berkeley, California, USA, and at Cornell Tech, NY, USA.

Assumptions. All assumptions are relative to a pairing group PG = (G 1 , G 2 , G T , p, P 1 , P 2 , e) ← PGGen( 1 For any assumption i and PPT adversary A, we define the advantage Adv As-i PG,A (λ) accordingly.

Assumption 1:

Lemma 3.8 (Reduction from DDH to the assumptions [OT09,Lew12]). For all the above assumptions, there is a reduction from DDH in G 2 .

σ ≥ ω( √ log n). For decryption to succeed, we want that the error terms are smaller than q 2K , which implies: q ≥ 2K √ V ω(log 2 n), which is the case for our choice of parameters.

Remark 4.9 (No smudging noise). We remark that in our setup, we rely on efficient lattice parameters and require no smudging or superpolynomial modulus.

Theorem 4.10 (Security). Let n be the security parameter, q ≥ 2K √ V ω(log 2 n), σ = 2Cαq(

) , then the scheme from Fig. 11 is AD-IND-secure in the random-oracle model, assuming that LWE q,α,n is hard.

Proof. We prove adaptive security in the random-oracle model, following the proof structure and techniques of [GPV08], while making several changes to adapt the proof techniques to functional encryption. First, without loss of generality, we assume that any adversary making key generation queries of the form id y will first query the random oracle on id (we can make this assumption because for every adversary A, we can compile it into an adversary A that exhibits this behavior). We proceed in a series of hybrids, consider A to be a PPT adversary, and n ∈ N to be the security parameter. We denote by Adv Gamei (A) the advantage of A in game i.

Game 0 This is the original AD-IND game.

Game 1 In this game, we guess what identities id * 0 and id * 1 will be used for the challenge messages. Guessing id * 0 , id * 1 themselves would incur an exponential security loss. Therefore, instead of guesssing the identities themselves, we guess the index of the random-oracle query in which the adversary queries the oracle H to get U id * 0 and U id * 1 . This will result in an 1 Q 2 security loss, where Q is the total number of queries to the random oracle. As explained above, we are guaranteed that the adversary will make this query.

Depending on whether id * 0 = id * 1 , we will either perform a reduction to the ALS scheme (see Appendix A) or directly to LWE.

Case 1, id * 0 = id * 1 We perform a reduction to the security of the ALS [ALS16] encryption scheme, which we recall in Appendix A. We reduce to the AD-IND security of ALS. We first obtain from the challenger public keys A ALS , D ALS . Now, equipped with the knowledge of id * , we define Game 1 to be the same as Game 0 , except for the following changes:

-Matrix A is not generated with TrapGen anymore, instead A is now replaced with A ALS .

-For every id = id * query to the random oracle H, we draw a matrix Z id ← R D Z ×m ,ρ . We program the random oracle H(id) = U id , where U id is now computed as U id = Z id A. Key queries of the form id y are answered by returning y Z id . -For id = id * , we program H(id) = D ALS .

-For key queries of the form id * y, we notice that we cannot answer them ourselves. However, we are allowed to forward y to the challenger of the AD-IND security of ALS, which replies with y Z ALS , where Z ALS is the master secret key of the ALS scheme. We set sk id * y := y Z ALS and forward it to the adversary. -When the adversary finally submits its challenge ( x 0 , x 1 ), we forward this to the ALS challenger, which replies with ct := (ct 1 , ct 2 ). We forward ct back to the adversary.

We therefore have that Adv Game1 (A) ≤ Adv ALS (A), now we only need to show that |Adv Game0 (A)-Adv Game1 (A)| ≤ negl(n). For this we use Lemma 4.6, which tells us that:

recall that z i denotes the i-th row of Z). Note that in ALS, matrix A ALS is indeed uniformly random, which corresponds to how A is chosen in Game 1 .

-TrapGen(1 n , 1 m , q) → (A, T A ) ([Ajt99, AP09, MP12]): a PPT algorithm that, for m = Θ(n log q), outputs a fullrank A ∈ Z n×m q and a basis T A ∈ Z m×m for Λ ⊥ q (A). In addition, A is negl(n)-close to uniform and T A = O( √ n log q), with overwhelming probability in n. -ExtendRight(A, T A , B) → T (A|B) ([CHKP10]): a deterministic algorithm that for full-rank A, B ∈ Z n×m q and a basis T A ∈ Z m×m of Λ ⊥ q (A), outputs a basis T (A|B) of Λ ⊥ q (A|B). In addition ([ABB10]): a deterministic algorithm that for full-rank A, G ∈ Z n×m q and a basis T G of Λ ⊥ q (G), outputs a basis T (A|G+AS) of Λ ⊥ q (A|G + AS). In addition

-For m = n, there exists a full-rank gadget matrix G ∈ Z n×m q for which Λ ⊥ q (G) has a publicly known basis T G , where

Then there exists PPT algorithm SampleLeft(A, T A , B, U, σ) that outputs a matrix X ∈ Z 2m× q , distributed statistically close to D Λ u q (A|B),σ .

Then there exists PPT algorithm SampleRight(A, S, y, U, σ) that outputs a matrix X ∈ Z 2m× q , distributed statistically close to D Λ u q (A|AS+yG),σ , where G is the gadget matrix from Lemma 5.1.

Lemma 5.4 (Bounding the Norm of a {±1} k×m Matrix [ABB10]). Let R be a matrix chosen uniformly at random from {±1} k×m . There exists a universal constant C , for which:

Lemma 5.5 ([Cai98] Gram-Schmidt Minimum). For any arbitrary integer lattice Λ, it holds that:

with the minimum is over all (ordered) bases B of lattice Λ.

Lemma 5.6 ([ABB10]). Let q prime and m > (n + 1) log q + ω(log n). Let S be chosen uniformly from {±1} m×k mod q, with k polynomial in n. Let A, B be chosen uniformly from Z n×m q and Z n×k q . Then, for every e ∈ Z m q , we have that the distributions (A, AS, S e) and (A, B, S e) are statistically close.

To encode identities, we need to recall the following definition from [ABB10]: Definition 5.7 ([ABB10] Encoding Identities as Matrices). Let q be a prime and n a positive integer. We say that a function H : Z n q → Z n×n q is an encoding with full-rank differences when:

for all distinct u, v ∈ Z n q , the matrix H(u) -H(v) ∈ Z n×n q has full-rank -H must also be computable in polynomial time in n log q.

A scheme for encodings with full-rank differences has been introduced by [ABB10].

Definition 5.8 (Identity-Based Encryption). An Identity-Based Encryption scheme is a tuple of four algorithms (Setup, Extract, Encrypt, Decrypt). The first algorithm, Setup produces some public parameters pk and a master secret key mk. Extract(mk, id) generates private keys sk id , associated to any given identity id. Encrypt produces encryptions under a target identity id using the public parameters pk, and Decrypt will take as input a key sk id and a ciphertext ct of some message x -it will recover the initial message x if ct = Enc(pk, id, x).

Enc(mpk, id, x):

12. An identity-based inner-product functional encryption scheme IFE. Function H is an encoding with full-rank difference, as in Definition 5.7. Algorithms TrapGen and SampleLeft are described in Lemma 5.1 and Theorem 5.2. Noise e3 is non-smudging and is of a different standard deviation τ , this is needed for the security proof.

Lemma 5.10 (Decryption correctness). For parameters n, m, q, σ, ρ, τ , chosen as in the previous paragraph, the scheme from Fig. 11 is correct.

. We know that H id R id = D, therefore the expression above can be rewritten as:

By Lemma 4.2, we now bound the error terms, by rewritting them as: y e 2 + y e 3 -y

√ nmV , where the last inequality is derived from Lemma 5.4. Therefore, the final error term is upper bounded by V (σ + τ ) + C σρ4m √ nmV .

Remark 5.11 (Inheriting Anonymity). Towards proving security, we recall the observation made during the proof of our random-oracle construction. Assume that id * 0 = id * 1 -if the adversary was allowed to obtain secret keys for either id * 0 y or id * 1 y, for any y, then it could trivially distinguish between encryptions of x 0 under id * 0 and encryptions of x 1 under id * 1 . This type of trivial attack is excluded by the SEL-IND definition, therefore we conclude that the adversary cannot obtain decryption key queries for neither id * 0 or id * 1 . Then, there are no functional keys and the adversary interacts with what is essentially an identity-based encryption scheme (in our case, exactly the scheme of [ABB10]). Therefore, since [ABB10] satisfies INDr-sID-CPA (see Definition 5.9), our scheme will trivially also satisfy the same security notion.

We can now state the following security theorem: Theorem 5.12 (SEL-IND Security). Let n be the security parameter and consider the ALS functional encryption scheme (Appendix A) with parameters q, σ, ρ, m, n, α. As long as ALS is secure under the LWE q,α,n and the ALS parameters satisfy in addition m ≥ 6n log q, q > 2K V (σ + τ ) + C σρ4m √ nmV , the scheme in Fig. 12 with

Proof. Since the case of id * 0 = id * 1 follows from Remark 5.11, we focus on the more difficult case when id * = id * 0 = id * 1 . The proof follows the outline of the original [ABB10]. The novelty is the adaptation for supporting functional decryption keys. An additional step we did not encounter in the random oracle construction is that here, when matrix A is switched from its trapdoored version to uniformly random, the simulator still needs to have access to a short basis in order to answer key decryption queries for the case id * . This is a difference from the proof of [ABB10], where they do not need to answer any queries for the punctured identity id * . Since our proof is selective with respect to the identity of the challenges, we assume that we have access to id * . We also make use of noise rerandomization and correction techniques from [KY16], which is why we require an additional non-smudging noise e 3 .

Game 0 This is the original SEL-IND game, the challenge plaintexts are ( x 0 , x 1 ).

Game 1 Instead of choosing (A, T) ← R TrapGen(1 n , 1 m ), choose A to be uniformly random. To compute decryption keys, we can enumerate all short possible basis T A of Λ ⊥ q (A) and use one of these short basis to generate decryption keys. This game is inefficient and indistinguishable from the previous one by the properties of TrapGen() (see Lemma 5.1). Since the indistinguishability is derived from a statistical argument, it is not problematic that this game is inefficient.

However, we need to ensure that the lattice spanned by A actually has a short basis. For this, we use Lemma 5.5, which says that: min B B ≤ O(n), which means that in order to use the SampleD algorithm, we need to set our standard deviation ρ > n • ω( √ n). This will require us to increase the standard deviation ρ used in SampleLeft, which in turn will lead to a larger modulus than in our random oracle scheme.

Game 2 In this game, we switch the computation of D to be programmed to D = H id * Z, where Z ← R D Z 2m×n ,ρ , using SampleD. We now justify that this change is (statistically) indistinguishable for the adversary. Recall that H id * = (A|B + H(id * )G). Since B and A are uniformly random, we can apply Lemma 4.6 and argue that H id * Z = (A|B + H(id * )G)Z is close to uniformly random over Z n× (which is how D was generated in Game 1 ).

The role of R id * is played by Z. Use Z to answer decryption key queries for id = id * , as sk id * y = Z • y. For all other decryption key queries, we still compute R id ← R SampleLeft(A, T A , B + H(id)G, D) and output R id * y Game 3 Matrix T A must still be found by enumeration. The matrix S * which will be chosen for the challenge ciphertext is now picked at ley generation, just as in [ABB10]. B is now chosen as B = AS * -H(id * )G. f := (I m |S) e 1 . By Lemma 5.6, we know that if A is uniform over Z n×m q and S uniform over {±1} m×m , the distribution (A, B, (S * ) e 1 ) is statistically close to (A, AS * , (S * ) e 1 ), where B is uniform over Z n×m q . Note that the distributions are close for any choice of e, so e can be known to a distinguishing adversary in this step.

Game 4 This game is now efficient. Use SampleRight(A, S, H(id) -H(id * ), D, ρ) with standard deviation ρ to generate R id , for id = id * . This is possible due to the identity encoding function (Definition 5.7), which ensures that H(id) -H(id * ) is non-zero, one of the requirements of the SampleRight algorithm. For id = id * , the decryption keys are generated using the secret matrix Z. This game is indistinguishable from the previous game due to Theorem 5.2, which says that the computed Z id is statistically close to D Λ U q (A|AS+(H(id)-H(id * )G),σ . This holds as long as the standard deviation ρ satisfies the constraints of Theorem 5.3.

Game 5 In this final game, we rely on the security of ALS to argue indistinguishability of ciphertexts. We interact with the AD-CPA challenger for ALS. We receive as public keys A ALS and D ALS . We simulate the view of the adversary in the following manner:

-Decryption keys for id * ỹ: Ask the ALS functional key oracle for key y, obtain sk y , return sk id * y = sk y Z 2 y , which

we can compute since we know Z 2 .

Generic Construction

We show that the techniques used in [ACF + 18, AGRW17] to generically transform any single-input FE for inner products into a multi-input FE for inner products are compatible with our single-input FE. Thus, we obtain an MIFE for the family of functions F multi ipfe(d,B),P1,...,Pn , described in Fig. 13, which relies on any single-input FE (Setup , Enc , KeyGen , Dec ) for the family of functions F ipfe(d+1,B),P , such as described in Section 3, satisfying the following properties:

1. Pairing-based: ciphertexts contain groups elements in G 1 and functional decryption keys contain groups elements in G 2 , for a pairing group PG = (G 1 , G 2 , G T , p, P 1 , P 2 , e) ← PGGen(1 λ ), with p B.

Large inputs:

The algorithms Enc and KeyGen can take as input arbitrary vectors in Z d p (as opposed to vectors in [0, B] d for a polynomial bound B) and the decryption returns [ x y] T ∈ G T .

Linear homomorphism:

There is a PPT algorithm Add such that for all x, x ∈ Z d p and P ∈ P, the following are identically distributed: (Enc (mpk, P, x), Enc (mpk, P, x+ x )) and (Enc (mpk, P, x), Add(Enc (mpk, P, x), x )). That is, Add can produce a fresh encryption of x + x from an encryption of x, for a given predicate P ∈ P.

It is not hard to verify that our scheme in Section 3.1 satisfies these properties.

Setup(1 λ , F multi ipfe(d,B),P 1 ,...,Pn ):

KeyGen(msk, S, (attj, yj)j∈S ):

If there exists j ∈ S such that Pj(attj) = 0, then return ⊥. Otherwise, for all j ∈ S, sk j ← KeyGen (mskj, attj, yj). Return sk att, y := S, {sk j }j∈S , j∈S y j uj .

Correctness. Let

such that for all j ∈ S, P j (att j ) = 1. We have, by correctness of the single-input FE, for all j ∈ S, [d j ] T := [ x j y j + u j y j ] T . Thus, [out] T := [ j∈S x j y j + u j y j ] T -[z] T = [ j∈S x j y j ] T , and the decryption can efficiently recover out, since the output belongs to [0, ndB 2 ], which is polynomially bounded.

Similarly, for any PPT adversary A, there exists a PPT adversary B such that:

Setup(1 λ , X , Y):

KeyGen(msk, y):

Return ( y, sk id, y := ( y Z))

A The ALS inner-product functional encryption scheme

In this appendix, we recall the inner-product functional encryption scheme from [ALS16], which we denote as ALS. The proof described here is the same as [ALS16], except for a small modification described in [WFL19]. The novelty of [WFL19] is that they described how a rerandomization technique due to [KY16] can be used to simplify the proof of the ALS scheme and improve its parameters. What is changed is that the matrix Z has a different distribution from [ALS16], which allows us to combine this scheme with the random-oracle based IBE of [GPV08] and the standard model IBE of [ABB10]. The construction is described in Fig. 15. This variant of ALS has the matrix Z ← R D Z ×m ,ρ , rather than the slightly more complicated distribution in the original description of the scheme.

Choice of Parameters

We first set X = {0, . . . , P -1} , Y = {0, . . . , V -1} , the output must belong to gs to {0, . . . , K -1} with K = P V . First we set the parameters for correctness:

-From Lemma 4.2, we know that every entry of D is with overwhelming probability bounded by ω(log n), so

-For decryption to suceed, we want that the error terms are smaller than q 2K , which implies:

We therefore have the following lemma:

The security reduction is with respect to LWE q,α,n , where the modulus will be much larger than K. Denote the standard deviation r := αq. To ensure security, we need to satisfy the following requirements:

-NoiseGen rerandomization: looking ahead in the security proof, we require that the singular value s 1 (V) of V is bounded by h := Ω(ρ(

(see the security proof for exact values and security parameter n). Then, in order for NoiseGen to provide security guarantees, we must set σ ≥ 2 • r • h. Since h depends on the gaussian parameter ρ of matrix Z, this establishes a relation between ρ and σ.

-Min-entropy requirement: since ρ > ω( √ log n), the min-entropy requirement is satisfied (as long as n > 2.303) and m ≥ (2n log q + 2n)/ log(4/3).

-Leftover hash lemma: this is satisfied as long as m is much larger than n (see [ALS16,Lemma 11]). For the purposes of this paper, we will choose m = 2n log q.

Putting all requirements together, we choose as parameters:

Each function is described by an identity id ∈ Z p and a vector y ∈ [0, B] d , takes as input another identity id ∈ Z p and a vector x ∈ [0, B] d , and outputs x y if id = id , 0 otherwise. The partial information part( x, id) = id.

-Param: returns the parameters (2d, |ct| = d, |sk| = n + 1).

-EncCt( x, id): given x ∈ Z n p and id ∈ Z p , returns a matrix

id , then it must be that y x 0 = y x 1 . In that case, security relies on the fact that the following are identically distributed: w 1 and w

If id 0 = id 1 = id , the security relies on the fact that the following are identically distributed: ( w 1 + id w 2 , w 1 + id w 2 ) and ( w 1 + id w 2 + x 1 -x 0 , w 1 + id w 2 ), where w 1 , w 2 ← R Z d p . The left most distribution corresponds to -EncKey( y, y): returns a matrix K ∈ Z (d +2)× p such that K (w 0 , u, w 1 , . . . , w ) = W y + u y ∈ Z p .

C.2 Orthogonality Testing with Inner-Product Functional Encryption

-Decode( x, y): if x y = 0, it returns the vector d := ( y, x) ∈ Z d+ p .

Correctness. Let x, y ∈ Z p such that x y = 0, x, y ∈ [0, B] d , C := EncCt( x, x), K := EncKey( y, y) and d := Decode( x, y, y). We have (w 0 , u, w 1 , . . . , w

where the last equality uses the fact that x y = 0. = 0, then it must be that y x 0 = y x 1 . In that case, security relies on the fact that the following are identically distributed: W and W + w 0 ( x 1 -x 0 ) v , where W ← R Z d× p , and v ∈ Z p is an arbitrary vector such that x v = 1 (such a vector exists since x = 0).

If y x

C.3 Fully-hiding Orthogonality Testing with Inner-Product Functional Encryption

Each function is described by a predicate vector y ∈ Z p and a message vector y ∈ [0, B] d , takes as input a pair

x ∈ Z p \ {0}, x ∈ [0, B] d , and returns x y if x y = 0. There is no partial information: part( x, x) = ∅.

-Param: returns the parameters (2d + d , |ct| = 1, |sk| = n + 1).

-EncCt( x, x): returns a matrix C ∈ Z

where the last equality uses the fact that x y = 0.

= 0, then it must be that y x 0 = y x 1 . In that case, security relies on the fact that the following are identically distributed: v and v + w 0 ( x 1 -x 0 ), where v ← R Z d p . If y x 0 = 0 and y x 1 = 0, then we show that (w 0 , u, v, vect(W)) (C b |K) is independent of b, using the fact that the following are identically distributed: (W, v) and

). If y = 0, then the gray term in the last distribution disappears, which means the distribution is independent of b. If y = 0, the value y u is uniformly random over Z p , and since the value y • x b is different from 0, that means the gray term itself is uniformly random over Z p , independent of b.

C.4 Ciphertext-policy ABE for Read-once Monotone Span Programs with Inner-Product Functional Encryption

Each function is described by a characteristic vector a = (a 1 , . . . , a n ) ∈ {0, 1} n , and a vector y ∈ [O, B] d . It takes as input an access structure, which is a matrix M ∈ Z n× p , and a vector x ∈ [0, B] d and outputs x y if the vector (1, 0, . . . , 0) ∈ Z 1× p is in the row span of M a , which denotes the collection of vectors {M j : a j = 1} where M j denotes the j'th row of M. That is, a satisfies M if there exists constants ω 1 , . . . , ω n ∈ Z p such that j:aj =1 ω j M j = (1, 0, . . . , 0)

(3)

Observe that the constants {ω j } j∈[n] can be computed in time polynomial in the size of the matrix M via Gaussian elimination.

The partial information is: part( a, x) = a. We have (w 0 , v, vect(U), w 1 , . . . , w n ) (C|K) d = j:aj =1 ω j ( y ( v|U)M j + y w j ) + w 0 x y + y v + y W y + j:aj =1 ω j y ( v|U)M j = w 0 x y, where the last equality uses (3).

Security. Let a ∈ {0, 1} n , x 0 , x 1 , y ∈ [0, B] d , M ∈ Z n× p , for all b ∈ {0, 1}, C b := EncCt( x b , M), K := EncKey( y, a). If a satisfies M, then x 0 = x 1 and there is nothing to prove.

If a doesn't satisfies M then we show that (w 0 , v, vect(U), w 1 , . . . , w n ) (C b |K) is independent of b, using the fact that for all a ∈ {0, 1} n , the following are identically distributed : { w i } i∈[n] and { w i + (a i -1)( v|U)M i } i∈ Since a does not satisfies M, we have: (a 1 ( v|U)M 1 , . . . , a n ( v|U)M n ) is independent of v, which can be used to mask w 0 x 0 . Formally, that means the following are identically distributed: (a 1 ( v|U)M 1 + w 1 , . . . , a n ( v|U)M n + w n , v + w 0 x 0 ) and (a 1 ( v|U)M 1 + w 1 , . . . , a n ( v|U)M n + w n , v + w 0 x 1 ).