Abstract
We give the first public-key functional encryption that supports the generation of functional decryption keys for degree-2 polynomials, with succinct ciphertexts, whose semi-adaptive simulation-based security is proven under standard assumptions. At the heart of our new paradigm lies a so-called partially function-hiding functional encryption scheme for inner products, which admits public-key instances, and that is sufficient to build functional encryption for degree-2 polynomials. Doing so, we improve upon prior works, such as the constructions from Lin (CRYPTO 17) or Ananth Sahai (EUROCRYPT 17), both of which rely on function-hiding inner product FE, that can only exist in the private-key setting. The simplicity of our construction yields the most efficient FE for quadratic functions from standard assumptions (even those satisfying a weaker security notion). The interest of our methodology is that the FE for quadratic functions that builds upon any partially function-hiding FE for inner products inherits the security properties of the latter. In particular, we build a partially function-hiding FE for inner products that enjoys simulation security, in the semi-adaptive setting, where the challenge sent from the adversary can be chosen adaptively after seeing the public key (but before corrupting functional decryption keys). This is in contrast from prior public-key FE for quadratic functions from Baltico et al. (CRYPTO 17), which only achieved an indistinguishability-based, selective security. As a bonus, we show that we can obtain security against Chosen-Ciphertext Attacks straightforwardly. Even though this is the de facto security notion for encryption, this was not achieved by prior functional encryption schemes for quadratic functions, where the generic Fujisaki Okamoto transformation (CRYPTO 99) does not apply.
R. Gay—Supported in part by NSF Award SATC-1704788 and in part by the Office of the Director of National Intelligence (ODNI), Intelligence Advanced Research Projects Activity (IARPA), via 2019-19-020700006. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies, either expressed or implied, of ODNI, IARPA, or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright annotation therein.
You have full access to this open access chapter, Download conference paper PDF
Similar content being viewed by others
1 Introduction
Functional Encryption [O’N10, BSW11](in short: FE) is a general paradigm where restricted decryption keys are generated, that let users learn specific functions of the encrypted data. Namely, each decryption key \({\mathsf {sk}_f}\) is associated with a function f, and the decryption of an encrypted message x with \({\mathsf {sk}_f}\) recovers f(x), and nothing else. The scheme must be resistant to any collusion of decryption keys \({\mathsf {sk}_f}\) for different functions f: such group of keys should not learn anything more than the information leaked by each key \({\mathsf {sk}_f}\), individually. This security property makes FE schemes both hard to build and extremely useful, provided the class of function they handle is large. In fact, it has been shown [BV15, AJ15] that general purpose functional encryption gives a construction of Indinstiguishability Obfuscation [BGI+01, GGG+14] (in short: iO) for all circuits, a powerful object that has been remarkably successful at providing an all-purpose tool for solving cryptographic problems [SW14]. Surprisingly, even FE for smaller classes of functions are powerful. Recently, [LT17] has shown that succinct FE supporting degree-3 functions is sufficient to build iO, together with additional assumptions on the existence of special kind of pseudo-random generatorsFootnote 1. However, there is no construction of such FE schemes from standard, well understood assumptions. All known constructions rely on either multilinear maps, or iO itself. Can we build FE for rich classes of functions from standard assumptions?
Beyond the case of predicate encryption [BW07, KSW08, GVW15], little is known about standard-based FE constructions. [ABDP15] gave the first construction of FE for inner products, where the encryption of a vector \({\mathbf {x}\in \mathbb {Z}^n}\), together with a decryption key associated with vector \({\mathbf {y}\in \mathbb {Z}^n}\), yields the inner product of \(\mathbf {x}\) and \(\mathbf {y}\). That is, their scheme can generate decryption keys that compute a weighted sum on encrypted data. They prove selective security, a useful but artificial security notion where the adversary has to commit to its challenge ciphertext beforehand. Later, [ALS16] gave constructions with full security (aka adaptive security, where the adversary can request decryption keys and the challenge ciphertext adaptively). Both constructions use standard assumptions (DDH, LWE, DCR). Note that inner products already capture constant depth circuits, by simply expressing circuits as polynomials, and encrypting all the monomials (of constant degree). However, for most applications, and in particular to obtain iO, one needs to recursively apply the FE scheme to itself. This bootstrapping requires the ciphertexts to be succinct, that is, their size should only depend on the underlying message, and not on the function to be evaluated. Following this quest for succinct FE for richer classes of functions, [BCFG17] (concurrently [AS17, Lin17] in the private-key setting), gave the first construction of succinct FE that supports the evaluation of quadratic functions on ciphertexts. All of these constructions are proven secure under an indistinguishability-based security definition, which is cumbersome to use, and is too weak to meaningful security for some functionality. Moreover, all these schemes either achieve only selective security, or assume the generic group model.
Our Contributions. We build the first simulation-secure FE in the semi-adaptive setting, whose security relies on a standard assumption, that supports a functionality beyond inner products, or predicate encryption. In our scheme, ciphertexts are associated with two vectors \({\mathbf {x}\in \mathbb {Z}^n}\) and \({\mathbf {y}\in \mathbb {Z}^m}\), and decryption keys are associated with a matrix \({\mathbf {F}\in \mathbb {Z}^{n \times m}}\). The decryption of a ciphertext \({\mathsf {ct}_{\mathbf {x},\mathbf {y}}}\) with a decryption key \({\mathsf {sk}_{\mathbf {F}}}\) recovers \({\mathbf {x}^\top \mathbf {F}\mathbf {y}\in \mathbb {Z}}\). The ciphertext size is \({O(n+m)}\) group elements, and security relies on pairings (DLIN) (Fig. 1).
To build our quadratic FE, we deploy a new paradigm that uses at its core a so-called partially function-hiding inner-product FE, where decryption keys partially hide their underlying function (in the case of inner product, their underlying vector). This approach allows us to obtain public-key FE, as opposed to prior work [AS17, Lin17] relying on full-fledged function-hiding inner-product FE, which is inherently private-key.
We then build a partially function-hiding inner-product FE with simulation security. This security notion implies its indistinguishability-based counterpart, and drastically simplifies the proof compared to previous works relying on indistinguishability-secure inner-product FE (for instance [Lin17]). This simplicity is illustrated by short ciphertexts and keys (see Fig. 2). We obtain simulation security in the semi-adaptive setting, where an adversary is restricted to choose its challenge before querying any secret keys. This is the best we can hope for: a simple extension of [BSW11, AGVW13] shows that adaptively simulation secure partially function-hiding inner-product FE are impossible to achieve from standard assumptions (note this impossibility result doesn’t apply to schemes proved in the generic group model, such as the inner-product FE from [KLM+18]). As shown in [BSW11], indistiguishability-based security is inadequate for some functionality. For instance, if a ciphertext encrypts the seed of a PRG, and each functional decryption key is associated with one position of the output of the PRG, simulation-based security ensure that only the output of the PRG is revealed, whereas indistinguishability-based security is essentially useless, since it only proves that an encryption of a seed is computationally indistinguishable from an encryption of seed’ if PRG(seed) = PRG(seed’). This example is relevant in the context of quadratic FE, since our construction is expressive enough to evaluate the output of a PRG (see Remark 1). This indicates that simulation security is qualitatively stronger than its indistinguisahbility-based counterpart.
Another benefit of our new approach is that many properties of the underlying partially function-hiding inner-product FE can be lifted to the overall quadratic FE. This is case of the semi-adaptive simulation-based security, but we also show that if the partially function-hiding inner-product FE is secure against Chosen-Ciphertext Attacks (CCA-security), then so is the resulting quadratic FE. CCA-security is the de facto security notion for encryption, as it captures active or man-in-the-middle attacks, as opposed to CPA security. However, previous quadratic FE only prove CPA security. Note that generic transformation, such as Fujisaki Okamoto transform [FO99], cannot be applied here, since it relies on hybrid encryption, which is incompatible with functional encryption, which permits selective computation on encrypted data, as opposed to the all-or-nothing access provided by typical encryption. The CHK transform [CHK04] has been extended in [GPSW06] to obtain CCA-security for Attribute-Based Encryption (ABE) with some delegatability property. This property has been relaxed in [YAHK11]. However, these techniques only apply to ABE, where a decryption secret key recovers the encrypted plaintext entirely, or not at all, which is different in nature from the Functional Encryption we are studying here, where only partial information about the plaintext is recovered. The only generic transformation that seems to apply in our case is the dual encryption methodology from [NY90], which has the disadvantage of doubling the size of ciphertexts, and relying on (simulation-sound) non-interactive zero knowledge proofs. [BBL17] avoids using the Naor Yung paradigm, and builds the first CCA-secure FE (beyond the case of ABE), which handles inner product, and is based on efficient hash-proof systems. Their security proof crucially relies on structural (linearly homomorphic) properties of hash proofs system, which is tailored to FE for inner products. Indeed, none of these techniques seem to be applicable to existing quadratic FE, such as [BCFG17]. Our construction strikes by its simplicity: it suffices to build a CCA-secure partially function-hiding inner-product FE, which can be simply obtained by adding an Quasi-Adaptive Non-Interactive Zero Knowledge argument for the simple language of DDH tuples, without doubling the size of the ciphertext as required by Naor Yung dual encryption methodology. Instantiating these with arguments from [KW15] only adds 2 group elements in the ciphertexts, and requires no extra assumption. Surely, this is made easy by the use of pairings, which are not used by [BBL17]. In fact, we do not consider CCA-security to be the main technical contribution of this paper, but rather an illustration of the interest of building quadratic FE from inner-product FE, as is done in our new paradigm.
Technical Overview
Quadratic FE. Our quadratic FE uses a pairing group \({\mathbb {G}_1 \times \mathbb {G}_2 \rightarrow \mathbb {G}_T}\), where the encryption of \({\mathbf {x},\mathbf {y}}\) contains an encryption \({\mathsf {Enc}_1(\mathbf {x};r)}\) of \(\mathbf {x}\) under randomness r, that consists of elements in \(\mathbb {G}_1\), and an encryption \({\mathsf {Enc}_2(\mathbf {y};s)}\) of \(\mathbf {y}\) under randomness s, which consists of elements in \(\mathbb {G}_2\). Thanks to the pairing \({e: \mathbb {G}_1 \times \mathbb {G}_2 \rightarrow \mathbb {G}_T}\), we can compute the product of \({\mathsf {Enc}_1(\mathbf {x},r)}\) and \({\mathsf {Enc}_2(\mathbf {y},s)}\) to obtain the output \({\mathbf {x}^\top \mathbf {F}\mathbf {y}}\) in the group \(\mathbb {G}_T\), masked by some extra terms, that can be expressed as the inner product of a vector that only depends on the input \({\mathbf {x}, \mathbf {y}}\), and the randomness r, s used by the encryption, together with another vector which only depends on the secret key of these encryptions, and the matrix \(\mathbf {F}\). Both vectors have a dimension that is linear in the dimension of the vectors \(\mathbf {x}\) and \(\mathbf {y}\). Thus, as in [AS17, Lin17], we can use an inner-product FE to compute the masking term. Such inner-product FE needs to be function-hiding, since revealing the secret key would compromise the security of the encryptions \(\mathsf {Enc}_1\) and \(\mathsf {Enc}_2\). However, function-hiding FE is an inherently private-key primitive, since a public encryption would allow to recover the function underlying each decryption key, simply by encrypting well-chosen vectors and decrypting them using the decryption key. To obtain a public key quadratic FE, we make the crucial observation that the underlying function-hiding FE for inner products is only used for vectors that lie in some specific subspace. Thus, we create, and make public, a restricted encryption key that can only generate ciphertexts for these vectors, while still providing some meaningful function-hiding. In particular, we obtain a public-key inner-product FE where decryption keys partially hide their underlying vector, which turns out to be sufficient for the security proof of the quadratic FE. Roughly speaking, the security of the inner-product FE proves that only the masking terms are revealed, along with some partial information on the secret keys that do not compromise security of the encryptions \(\mathsf {Enc}_1\), \(\mathsf {Enc}_2\). Thus, we obtain security of the quadratic FE using the security of the latter encryptions.
Partially Function-Hiding Inner-Product FE. We now highlight the construction of our new public-key, partially function-hiding inner-product FE. Our starting point is the FE for inner products from [ALS16], where decrypting an encryption \(\mathsf {Enc}(\mathbf {x})\) of a vector \(\mathbf {x}\) with a decryption key \({\mathsf {KeyGen}(\mathbf {y})}\) associated with vector \(\mathbf {y}\) yields the inner product \({\mathbf {x}^\top \mathbf {y}}\). Their scheme is not function-hiding since \(\mathbf {y}\) is part of the decryption key generated by \({\mathsf {KeyGen}(\mathbf {y})}\). As in [Lin17, Section 6.3], we use the fact that the decryption computes the inner product of \({\mathsf {Enc}(\mathbf {x})}\) and \({\mathsf {KeyGen}(\mathbf {y})}\) to obtain \({\mathbf {x}^\top \mathbf {y}}\). Namely, we replace the vector \(\mathbf {y}\) in each decryption key by an ALS encryption of \(\mathbf {y}\), and \(\mathbf {x}\) in each ciphertext is replaced by an ALS decryption key for \(\mathbf {x}\) (see Fig. 3). Function-Hiding (hiding \(\mathbf {y}\)) follows from the security of the inner ALS FE, whereas security (hiding \(\mathbf {x}\)) follows from the security of the outter ALS FE. [Lin17] uses a similar approach, where the entire decryption key is encrypted using an outter inner-product FE (see Fig. 3), and the underlying inner-product FE [ABDP15] are only selective indistinguishability secure.
To make our scheme public-key, we publish a restricted secret key for the inner layer FE that lets \({\mathsf {KeyGen}^{\mathsf {in}}(\mathbf {x})}\) run on vectors \(\mathbf {x}\) that lie in some subspace. To be of use in our quadratic FE scheme, our function-hiding FE needs to be simulation secure (this is stronger than the classical indistinguishability based security for FE). We prove simulation security using the simulation security of [ALS16], which was proved in [AGRW17, Wee17] in the selective setting.
CCA-Security. As a bonus, we show that we can easily obtain CCA-security for our partially function-hiding inner-product FE, and that security property is transferred to the overall quadratic FE. We use Quasi-Adaptive Non-Interactive arguments for the simple language of DDH tuples, which must fulfill one-time simulation-soundness, in order to boost the security of our partially function-hiding FE for inner products to handle Chosen Ciphertext Attacks. This QANIZK argument can be instantiated with [KW15, Section 3.3], which only adds two group elements in the ciphertexts (this is the case \(k=1\) in their paper) and rely on the Kernel assumption, implied by SXDH (this is competitive with Fiat Shamir NIZKs, and does not rely on the random oracle model). Recall that prior constructions fail to obtain CCA-security even in the random oracle model, since the Fujisaki Okamoto transform, which relies on hybrid encryption (that is incompatible with functional encryption, where only a partial information on the plaintext is recovered during decryption), is of no help here.
Conclusion, and Perspective. Summarizing, we exhibit a new paradigm to build quadratic FE from partially function-hiding FE for inner products, a newly introduced primitive that bypasses impossibility results of public-key function-hiding FE. This gives stronger, desirable security guarantees that were previously not achieved. Moreover, its simplicity is appealing, not only because it gives constructions that outperform previous standard-based schemes in terms of ciphertext size, but also because it transfers properties from inner-product FE to quadratic FE. An important exception is adaptive security. Even though there are adaptively-secure inner-product FE (in fact we claim, without proof, that our semi-adaptive partially function-hiding FE for inner products can be extended to the adaptive, indistinguishability-based setting, up to doubling the size of the ciphertexts, as done in [LV16]), our quadratic FE fails at achieving adaptive security. Despite this shortcomings, we are optimistic this new approach will shed light on the largely unexplored domain of building functional encryption for richer functionalities from standard assumptions.
Road-Map. The rest of this paper is organized as follows. After giving some relevant technical preliminaries in Sect. 2, we define partially function-hiding public-key FE for inner products, and generically use it to build a quadratic FE, in Sect. 3. Then, in Sect. 4, we give concrete instances of such partially function-hiding FE for inner products, using standard assumptions on pairing groups.
2 Preliminaries
2.1 Notations
For any set S, we denote by \({a \leftarrow _{\text {R}}S}\) a uniformly random element a in S. PPT stands for Probabilistic Polynomial Time. For any PPT algorithm \(\mathcal {A}\), we denote by \({x \leftarrow \mathcal {A}}\) a random output from \(\mathcal {A}\). We use \({\approx _c}\) to denote computational indistinguishability, and \(\equiv \) to denote equality between distributions.
2.2 Pairing Groups
Let \(\mathsf {PGGen}\) be a PPT algorithm that on input the security parameter \({1^\lambda }\), returns a description \({\mathcal {PG}=(\mathbb {G}_1,\mathbb {G}_2,\mathbb {G}_T,p,P_1,P_2,e)}\) where for all \({s\in \{1,2,T\}}\), \(\mathbb {G}_s\) is an additive cyclic group of order p for a \({2\lambda }\)-bit prime p. \(\mathbb {G}_1\) and \(\mathbb {G}_2\) are generated by \(P_1\) and \(P_2\) respectively, and \({e: \mathbb {G}_1 \times \mathbb {G}_2 \rightarrow \mathbb {G}_T}\) is an efficiently computable (non-degenerate) bilinear map. Define \({P_T := e(P_1, P_2)}\), which is a generator of \(\mathbb {G}_T\), of order p. We use implicit representation of group elements. For \({s \in \{1,2,T\}}\) and \({a \in \mathbb {Z}_p}\), define \({[a]_s = a \cdot P_s \in \mathbb {G}_s}\) as the implicit representation of a in \(G_s\). More generally, for a matrix \({\mathbf {A}= (a_{ij}) \in \mathbb {Z}_p^{n\times m}}\) we define \({[\mathbf {A}]_s}\) as the implicit representation of \(\mathbf {A}\) in \(\mathbb {G}_s\):
Given \({[a]_1}\) and \({[b]_2}\), one can efficiently compute \({[a \cdot b]_T}\) using the pairing e. For matrices \(\mathbf {A}\) and \(\mathbf {B}\) of matching dimensions, define \({e([\mathbf {A}]_1, [\mathbf {B}]_2) := \left[ \mathbf {A}\mathbf {B}\right] _T}\). For any matrix \({\mathbf {A}, \mathbf {B}\in \mathbb {Z}_p^{n \times m}}\), any group \({s \in \{1,2,T\}}\), we denote by \({[\mathbf {A}]_s + [\mathbf {B}]_s = [\mathbf {A}+\mathbf {B}]_s}\).
For any prime p, we define the following distributions. The \(\mathsf {DDH}\) distribution over \({\mathbb {Z}_p^2}\): \({a \leftarrow _{\text {R}}\mathbb {Z}_p}\), outputs \({\mathbf {a}:= {1 \atopwithdelims ()a}}\). The \(\mathsf {DLIN}\) distribution over \({\mathbb {Z}_p^{3 \times 2}}\): \({a,b \leftarrow _{\text {R}}\mathbb {Z}_p}\), outputs \(\mathbf {A}:= \begin{pmatrix} a &{} 0 \\ 0 &{} b \\ 1 &{} 1 \end{pmatrix}\).
Definition 1 (DDH assumption)
For any adversary \(\mathcal {A}\), any group \({s \in \{1,2,T\}}\) and any security parameter \(\lambda \), let
where the probabilities are taken over \({\mathcal {PG}\leftarrow _{\text {R}}\mathsf {GGen}(1^\lambda ,d)}\), \({\mathbf {a} \leftarrow _{\text {R}}\mathsf {DDH}}\), \({r \leftarrow _{\text {R}}\mathbb {Z}_p}\), \({\mathbf {u}\leftarrow _{\text {R}}\mathbb {Z}_p^2}\), and the random coins of \(\mathcal {A}\). We say DDH holds in \(\mathbb {G}_s\) if for all PPT adversaries \(\mathcal {A}\), \({\mathrm {Adv}^{\mathsf {DDH}}_{\mathbb {G}_s,\mathcal {A}}(\lambda )}\) is a negligible function of \(\lambda \).
Definition 2 (SXDH assumption)
For any security parameter \(\lambda \) and any pairing group \({\mathcal {PG}=(\mathbb {G}_1, \mathbb {G}_2,\mathbb {G}_T, p,P_1,P_2,e) \leftarrow _{\text {R}}\mathsf {PGGen}(1^\lambda )}\), we say SXDH holds in \(\mathcal {PG}\) if DDH holds in \(\mathbb {G}_1\) and \(\mathbb {G}_2\).
Definition 3 (bilateral DLIN)
For any adversary \(\mathcal {A}\), any security parameter \(\lambda \), let
with where the probabilities are taken over \({\mathcal {PG}\leftarrow _{\text {R}}\mathsf {GGen}(1^\lambda ,d)}\), \({\mathbf {A}\leftarrow _{\text {R}}\mathsf {DLIN}}\), \({\mathbf {r}\leftarrow _{\text {R}}\mathbb {Z}_p^2}\), \({\mathbf {u}\leftarrow _{\text {R}}\mathbb {Z}_p^3}\), and the random coins of \(\mathcal {A}\). We say bilateral DLIN holds relative to \(\mathcal {PG}\) if for all PPT adversaries \(\mathcal {A}\), \({\mathrm {Adv}^{\mathsf {DLIN}}_{\mathcal {A}}(\lambda )}\) is a negligible function of \(\lambda \).
2.3 Functional Encryption
A functional encryption scheme for a functionality \({\mathcal {F}: \mathcal {X}\rightarrow \mathcal {Z}}\) is a tuple of PPT algorithms:
-
\({\mathsf {Setup}(1^\lambda ,\mathcal {F})}\): on input the security paramter \(\lambda \), the functionality \(\mathcal {F}\), returns a public key \(\mathsf {pk}\) (which is implicitly an input of all other algorithms), and a master secret key \(\mathsf {msk}\).
-
\({\mathsf {Enc}(x \in \mathcal {X})}\): returns \(\mathsf {ct}_x\), an encryption of x.
-
\({\mathsf {KeyGen}(\mathsf {msk},f \in \mathcal {F})}\): returns \(\mathsf {sk}_f\), a decryption key for f.
-
\({\mathsf {Dec}(\mathsf {ct}_x,\mathsf {sk}_f)}\): deterministic algorithm that returns a value in \(\mathcal {Z}\), or \(\bot \) if it fails.
An FE scheme is said to be private-key if \(\mathsf {Enc}\) requires \(\mathsf {msk}\) as additional input, otherwise, it is public-key.
Correctness. For any security paramter \(\lambda \), any functionality \({\mathcal {F}: \mathcal {X}\rightarrow \mathcal {Z}}\), any \({x\in \mathcal {X}}\), and \({f \in \mathcal {F}}\), \({\Pr [\mathsf {Dec}(\mathsf {ct}_x,\mathsf {sk}_f)=f(x)]=1}\), where the probability is taken over \({(\mathsf {pk},\mathsf {msk}) \leftarrow \mathsf {Setup}(1^\lambda ,\mathcal {F})}\), \({\mathsf {ct}_x \leftarrow \mathsf {Enc}(x)}\), \({\mathsf {sk}_f \leftarrow \mathsf {KeyGen}(\mathsf {msk},f)}\).
Security. We recall the notion of simulation security, which implies its indistinguishability counterpart. Both notions were originally introduced in [BSW11, O’N10]. We work in the semi-adaptive setting, where the adversary sends its challenge x before querying any secret keys, but after receiving the public key. Semi-adaptive security has been introduced in [CW14] in the context of Attribute-Based Encryption, and subsequently studied in [GKW16]. It implies traditional selective security (where the adversary sends x before seeing the public key and querying secret keys), and is implied by the full-fledged adaptive security (where the adversary can query secret keys before sending its challenge x). We give both Chosen-Plaintext Attack (CPA) and Chosen-Ciphertext Attack variants of simulation security.
Definition 4 (Simulation CPA security)
For any FE scheme \(\mathsf {FE}\) for functionality \(\mathcal {F}\), any security parameter \(\lambda \), any PPT simulator \({\mathcal {S}:=(\widetilde{\mathsf {Setup}},\widetilde{\mathsf {Enc}},}\) \({\widetilde{\mathsf {KeyGen}})}\), and any PPT stateful adversary \(\mathcal {A}\), we define the following two experiments.
In the real experiment, the key generation oracle \({\mathcal {O}_{\mathsf {KeyGen}}}\), when given as input \({f \in \mathcal {F}}\), returns \({\mathsf {KeyGen}(\mathsf {msk},f)}\). In the ideal experiment, the key generation oracle \({\mathcal {O}_{\mathsf {KeyGen}}}\), when given as input \({f \in \mathcal {F}}\), computes \({f(x^\star )}\), and returns \({\widetilde{\mathsf {KeyGen}}(\widetilde{\mathsf {msk}},f,f(x^\star ))}\).
We say an FE scheme is CPA-SIM secure if there exists a PPT simulator \({\mathcal {S}:=(\widetilde{\mathsf {Setup}},\widetilde{\mathsf {Enc}},\widetilde{\mathsf {KeyGen}})}\) such that for all PPT adversaries \(\mathcal {A}\), we have:
Definition 5 (Simulation CCA security)
For any FE scheme \(\mathsf {FE}\) for functionality \(\mathcal {F}\), any security parameter \(\lambda \), any PPT simulator \(\mathcal {S}:=(\widetilde{\mathsf {Setup}},\widetilde{\mathsf {Enc}},\widetilde{\mathsf {KeyGen}},\widetilde{\mathsf {Dec}})\), and any PPT stateful adversary \(\mathcal {A}\), we define the following two experiments.
In the real experiment, the oracle \({\mathcal {O}_{\mathsf {KeyGen}}}\), when given as input \({f \in \mathcal {F}}\), returns \({\mathsf {KeyGen}(\mathsf {msk},f)}\); the oracle \({\mathcal {O}_{\mathsf {Dec}}}\), given as input a ciphertext \(\mathsf {ct}\) different from the challenge ciphertext \({\mathsf {ct}^\star }\) and a function \({f \in \mathcal {F}}\), computes \({\mathsf {sk}_f \leftarrow \mathsf {KeyGen}(\mathsf {msk},f)}\), and returns \({\mathsf {Dec}(\mathsf {ct},\mathsf {sk}_f)}\). If \({\mathcal {O}_{\mathsf {Dec}}}\) is queried on an input that contains the challenge ciphertext \({\mathsf {ct}^\star }\), it returns \(\bot \).
In the ideal experiment, the oracle \({\mathcal {O}_{\mathsf {KeyGen}}}\), when given as input \({f \in \mathcal {F}}\), computes \({f(x^\star )}\), and returns \({\widetilde{\mathsf {KeyGen}}(\widetilde{\mathsf {msk}},f,f(x^\star ))}\). The oracle \({\mathcal {O}_{\mathsf {Dec}}}\), when given as input a ciphertext \(\mathsf {ct}\) different from the challenge ciphertext \({\mathsf {ct}^\star }\) and a function \({f \in \mathcal {F}}\), returns \({\widetilde{\mathsf {Dec}}(\widetilde{\mathsf {msk}},f,\mathsf {ct})}\). If \({\mathcal {O}_{\mathsf {Dec}}}\) is queried on an input that contains the challenge ciphertext \({\mathsf {ct}^\star }\), it returns \(\bot \).
We say an FE scheme is CCA-SIM secure if there exists a PPT simulator \({\mathcal {S}:=(\widetilde{\mathsf {Setup}},\widetilde{\mathsf {Enc}},\widetilde{\mathsf {KeyGen}},\widetilde{\mathsf {Dec}})}\) such that for all PPT adversaries \(\mathcal {A}\), we have:
2.4 Quasi-Adaptive Non-Interactive Zero-Knowledge
This part is taken almost verbatim from [KW15]. Quasi-Adaptive NIZK (QA-NIZK) proofs are NIZK proofs where the common reference string (CRS) is allowed to depend on the specific language for which proofs have to be generated [JR13]. The CRS is generated in a specific way and contains a fixed part \(\mathsf {par}\), produced by an algorithm \(\mathsf {Gen}_\mathsf {par}\), and a language-dependent part \(\mathsf {crs}\). However, for the zero-knowledge property there should exist a single simulator for the entire class of languages.
For public parameters \(\mathsf {par}\) produced by \(\mathsf {Gen}_\mathsf {par}\), let \({\mathcal {D}_\mathsf {par}}\) be a probability distribution over a collection of relations \({R = \{R_\rho \}}\) parametrized by a string \(\rho \) with an associated language \({\mathcal {L}_\rho = \{y : \exists x \;\text {s.t.}\; R_\rho (y,x)=1 \}}\). We now recall the tag definition of QANIZK for \({\mathcal {D}_\mathsf {par}}\), in its tag-based variant.
Definition 6 (QANIZK Argument)
A Quasi-adaptive Non-Interactive Zero Knowledge Argument (QANIZK) \(\varPi \) for a language distribution \({\mathcal {D}_\mathsf {par}}\) consists of five PPT algorithms \({\varPi =(\mathsf {Gen}_\mathsf {par},\mathsf {Gen}_\mathsf {crs},\mathsf {Prove},\mathsf {Sim},\mathsf {Ver})}\):
-
\({\mathsf {Gen}_\mathsf {par}(1^\lambda )}\): returns the public parameters \(\mathsf {par}\).
-
\({\mathsf {Gen}_\mathsf {crs}(\mathsf {par},\rho )}\): returns a common reference string \(\mathsf {crs}\), and a trapdoor \(\mathsf {trap}\). We assume that \(\mathsf {crs}\) implicitly contains \(\mathsf {par}\) and \(\rho \), and that it defines a tag space \(\mathcal {T}\).
-
\({\mathsf {Prove}(\mathsf {crs},\tau ,x,y)}\): on input the \(\mathsf {crs}\), a tag \({\tau \in \mathcal {T}}\), a witness x and a statement y, it returns a proof \(\pi \).
-
\({\mathsf {Ver}(\mathsf {crs},\tau ,y,\pi )}\): on input \(\mathsf {crs}\), a tag \(\tau \in \mathcal {T}\), a statement y, and a proof \(\pi \), it returns 1 or 0, where 1 means that \(\pi \) is a valid proof of \({y \in \mathcal {L}_\rho }\), with respect to tag \(\tau \).
-
\({\mathsf {Sim}(\mathsf {crs},\mathsf {trap},\tau ,y)}\): returns a proof \(\pi \) for some \({y \in \mathcal {Y}}\) (not necessarily in \({\mathcal {L}_\rho }\)).
We require that the algorithms satisfy the following properties:
-
Perfect completeness. For all \(\lambda \), all \(\mathsf {par}\) output by \({\mathsf {Gen}_\mathsf {par}(\lambda )}\), all \(\rho \) output by \(\mathcal {D}_\mathsf {par}\), all (x, y) with \({R_\rho (y,x)=1}\), all \({\tau \in \mathcal {T}}\), we have:
$$\begin{aligned} \Pr [ \mathsf {Ver}(\mathsf {crs},\tau ,y,\pi )=1 | (\mathsf {crs},\mathsf {trap}) \leftarrow _{\text {R}}\mathsf {Gen}_\mathsf {crs}(\mathsf {par},\rho ); \pi \leftarrow _{\text {R}}\mathsf {Prove}(\mathsf {crs},\tau ,x,y) ] =1. \end{aligned}$$$$\Pr \left[ \mathsf {Ver}(\mathsf {crs},\tau ,y,\pi )=1 \left| \begin{array}{l} (\mathsf {crs},\mathsf {trap}) \leftarrow _{\text {R}}\mathsf {Gen}_\mathsf {crs}(\mathsf {par},\rho ) \\ \pi \leftarrow _{\text {R}}\mathsf {Prove}(\mathsf {crs},\tau ,x,y) \end{array} \right. \right] =1.$$ -
Perfect zero-knowledge. For all \(\lambda \), all \(\mathsf {par}\) output by \(\mathsf {Gen}_\mathsf {par}(\lambda )\), all \(\rho \) output by \(\mathcal {D}_\mathsf {par}\), all \((\mathsf {crs},\mathsf {trap})\) output by \({\mathsf {Gen}_\mathsf {crs}(\mathsf {par},\rho )}\), all (x, y) with \({R_\rho (y,x)=1}\), all tags \({\tau \in \mathcal {T}}\), the distributions
$$\begin{aligned} \mathsf {Prove}(\mathsf {crs},\tau ,x,y) \text { and } \mathsf {Sim}(\mathsf {crs},\mathsf {trap},\tau ,y) \end{aligned}$$are the same (where the coin tosses are taken over \({\mathsf {Prove}, \mathsf {Sim}}\)).
-
Simulation Soundness. For all PPT adversaries \(\mathcal {A}\) and any QANIZK argument \(\varPi \) the following advantage
is negligible, where \({\mathsf {SimO}(\tau ,y)}\) returns \({\pi := \mathsf {Sim}(\mathsf {crs},\mathsf {trap},\tau ,y)}\) and sets \({\mathcal {T}_\mathsf {sim}:=\mathcal {T}_\mathsf {sim}\cup \{\tau \}}\), where \({\mathcal {T}_\mathsf {sim}}\) is initially empty.
One-time Simulation Soundness. For any PPT adversary \(\mathcal {A}\) and QANIZK argument \(\varPi \), we define \({\mathrm {Adv}^{\mathsf {OT}\text {-}\varPi }_{\mathcal {A}}(\lambda )}\) as \({\mathrm {Adv}^{\varPi }_{\mathcal {A}}(\lambda )}\), except the adversary can only make one query to the oracle \(\mathsf {SimO}\).
3 Quadratic FE from Inner-Product FE
In this section we build a functional encryption scheme for bounded-norm quadratic functions, namely, for the functionality \({\mathcal {F}_{\mathsf {quad},B}: [0,B]^n \times [0,B]^m \rightarrow }\) \({[0,n\cdot m\cdot B^3]}\), \({\mathcal {X}:= [0,B]^n \times [0,B]^m}\), \({\mathcal {Z}:= [0,n\cdot m\cdot B^3]}\), such that each \({\mathbf {F}\in \mathcal {F}_{\mathsf {quad},B}}\) is represented by a matrix in \({[0,B]^{n \times m}}\), and for all \({(\mathbf {x},\mathbf {y}) \in }\) \({[0,B]^n \times [0,B]^m}\), the output of the function is \({\mathbf {x}^\top \mathbf {F}\mathbf {y}\in [0,n\cdot m\cdot B^3]}\). We consider B, n, m all polynomials in the security parameter.
Our quadratic FE is built from a so-called partially function-hiding inner product FE. After giving an overview of the quadratic FE, we define partially function-hiding inner-product FE in Sect. 3.1, and we use it build a simulation-secure quadratic FE in Sect. 3.2, based on the DLIN assumption in a type-3 pairing group \({e: \mathbb {G}_1 \times \mathbb {G}_2 \rightarrow \mathbb {G}_T}\).
Overview of the Quadratic FE. To encrypt the pair of vectors \(\mathbf {x}\) and \(\mathbf {y}\), we provide an encryption of \(\mathbf {x}\) which contains group elements from \(\mathbb {G}_1\), and an encryption of \(\mathbf {y}\), which contains group elements from \(\mathbb {G}_2\). Equipped with a pairing \({e: \mathbb {G}_1 \times \mathbb {G}_2 \rightarrow \mathbb {G}_T}\), we multiply these encryptions to obtain the desired value in \(\mathbb {G}_T\). A natural starting point is to use the ElGamal encryption [ElG84]. That is, the ciphertext \({\mathsf {ct}_{\mathbf {x},\mathbf {y}}}\) includes the encryption of \({\mathbf {x}\in \mathbb {Z}^n}\) in \(\mathbb {G}_1\): \({\mathsf {ct}_{\mathbf {x}} = (c_1:= [r]_1, c_2 := [\mathbf {x}+ \mathbf {a}r]_1)}\) with randomness \(r \leftarrow _{\text {R}}\mathbb {Z}_p\), public key \({[\mathbf {a}]_1 \in \mathbb {G}_1^n}\) and secret key \({\mathbf {a}\in \mathbb {Z}_p^n}\); and an ElGamal encryption of \({\mathbf {y}\in \mathbb {Z}^m}\) in \(\mathbb {G}_2\): \({\mathsf {ct}_{\mathbf {y}} = (c_3:= [s]_2, c_4 := [\mathbf {y}+ \mathbf {b}s]_2)}\), with randomness \({s \leftarrow _{\text {R}}\mathbb {Z}_p}\), public key \({[\mathbf {b}]_2 \in \mathbb {G}^m_2}\), and secret key \({\mathbf {b}\in \mathbb {Z}_p^m}\). Decryption computes the product \({c_2^\top \mathbf {F}c_4}\), using the pairing, to recover:
where the output \({[\mathbf {x}^\top \mathbf {F}\mathbf {y}]_T}\) is masked by extra terms, which can be expressed as the inner product between \(\begin{pmatrix} r \cdot \mathbf {y}\\ s \cdot \mathbf {x}\\ r \cdot s \end{pmatrix}\) and \(\begin{pmatrix} \mathbf {F}^\top \mathbf {a}\\ \mathbf {F}\mathbf {b}\\ \mathbf {a}^\top \mathbf {F}\mathbf {b}\end{pmatrix}\).
Note that the first vector only contains elements known to the encryptor (the randomness used by the encryption and the input vectors \(\mathbf {x}\) and \(\mathbf {y}\)), while the second vector only contains elements known to the decryption key generator (the master secret key \({\mathsf {msk}= (\mathbf {a}, \mathbf {b})}\), and the input \(\mathbf {F}\) to the key generation algorithm). Besides, the dimension of both vectors are linear in \(n+m\). Thus, to compute these extra terms (without compromising succinctness), we use an FE for inner products \({\mathsf {IPFE}.\mathsf {Enc}, \mathsf {IPFE}.\mathsf {KeyGen}}\), and we add \(\mathsf {IPFE}.\mathsf {Enc}\begin{pmatrix} r \cdot \mathbf {y}\\ s \cdot \mathbf {x}\\ r \cdot s \end{pmatrix}\) to the ciphertext \({\mathsf {ct}_{\mathbf {x},\mathbf {y}}}\), and we define \(\mathsf {sk}_{\mathbf {F}} = \mathsf {IPFE}.\mathsf {KeyGen}\begin{pmatrix} \mathbf {F}^\top \mathbf {a}\\ \mathbf {F}\mathbf {b}\\ \mathbf {a}^\top \mathbf {F}\mathbf {b}\end{pmatrix}\). This underlying inner-product FE needs to be function-hiding, since revealing the vector input to \({\mathsf {IPFE}.\mathsf {KeyGen}}\), which contains the master secret key \({\mathsf {msk}=(\mathbf {a}, \mathbf {b})}\), would be fatal for the security of the ElGamal encryptions. However, function-hiding FE is an inherently private-key primitive, since a public encryption would allow to recover \(\mathbf {y}\) from the decryption key \(\mathsf {sk}_{\mathbf {y}}\), simply by encrypting sufficiently many well-chosen vectors \(\mathbf {x}\) and decrypting them using \(\mathsf {sk}_{\mathbf {y}}\).
To obtain a public-key quadratic FE, we use an encryption scheme that has more structure than ElGamal, namely, Damgård ElGamal [Dam92]. This gives the possibility to relax the function-hiding property required from the inner-product FE, and bypass the impossibility result for public-key function-hiding FE.
Namely, the ciphertext \({\mathsf {ct}_{\mathbf {x},\mathbf {y}}}\) contains a Damgård ElGamal encryption in \(\mathbb {G}_1\): \({\mathsf {ct}_{\mathbf {x}} = (c_1:= [\mathbf {a}r]_1, c_2 := [\mathbf {x}+ \mathbf {U}\mathbf {a}r]_1)}\) with randomness \({r \leftarrow _{\text {R}}\mathbb {Z}_p}\), public key \({([\mathbf {a}]_1 \in \mathbb {G}_1^2, [\mathbf {U}\mathbf {a}]_1 \in \mathbb {G}_1^{n})}\), and secret key \({\mathbf {U}\in \mathbb {Z}_p^{n \times 2}}\); and a Damgård ElGamal encryption of \({\mathbf {y}\in \mathbb {Z}^m}\) in \(\mathbb {G}_2\): \({\mathsf {ct}_{\mathbf {y}} = (c_3:= [\mathbf {b}s]_2, c_4 := [\mathbf {y}+ \mathbf {V}\mathbf {b}s]_2)}\), with randomness \(s \leftarrow _{\text {R}}\mathbb {Z}_p\), public key \({([\mathbf {b}]_2 \in \mathbb {G}_2, [\mathbf {V}\mathbf {b}]_2 \in \mathbb {G}_2^m)}\), and secret key \({\mathbf {V}\in \mathbb {Z}_p^{m \times 2}}\). Decryption computes the product \({c_2^\top \mathbf {F}c_4}\), using the pairing, to recover:
where the output \({[\mathbf {x}^\top \mathbf {F}\mathbf {y}]_T}\) is masked by extra terms, which can be expressed as the inner product between \(\begin{pmatrix} \mathbf {a}r \otimes (\mathbf {y}+\mathbf {V}\mathbf {b}s) \\ \mathbf {x}\otimes \mathbf {b}s \end{pmatrix}\) and \(\begin{pmatrix} \mathsf {vect}(\mathbf {U}^\top \mathbf {F}) \\ \mathsf {vect}(\mathbf {F}\mathbf {V})\end{pmatrix}\), where for any vector \({\mathbf {x}\in \mathbb {Z}_p^n}\), \({\mathbf {y}\in \mathbb {Z}_p^m}\), and matrix \({\mathbf {M}\in \mathbb {Z}_p^{n \times m}}\), we denote by \({\mathsf {vect}(\mathbf {M}) \in \mathbb {Z}_p^{nm}}\) the vector such that the inner product of \({\mathbf {x}\otimes \mathbf {y}}\) with \({\mathsf {vect}(\mathbf {M})}\) is \({\mathbf {x}^\top \mathbf {M}\mathbf {y}}\).
As before, the first vector only contains elements known to the encryptor (the randomness used by the encryption, the input vectors \(\mathbf {x}\) and \(\mathbf {y}\), and the public keys), while the second vector only contains elements known to the decryption key generator (the master secret key \({\mathsf {msk}= (\mathbf {U}, \mathbf {V})}\), and the input \(\mathbf {F}\) to the key generation algorithm). Besides, the dimension of both vectors are linear in \(n+m\).
As before, to compute these extra terms, we use an FE for inner products \(\mathsf {IPFE}.\mathsf {Enc}\), \(\mathsf {IPFE}.\mathsf {KeyGen}\), and we add \(\mathsf {IPFE}.\mathsf {Enc}\begin{pmatrix} \mathbf {a}r \otimes (\mathbf {y}+\mathbf {V}\mathbf {b}s) \\ \mathbf {x}\otimes \mathbf {b}s\end{pmatrix}\) to the ciphertext \({\mathsf {ct}_{\mathbf {x},\mathbf {y}}}\), and we define \(\mathsf {sk}_{\mathbf {F}} = \mathsf {IPFE}.\mathsf {KeyGen}\begin{pmatrix} \mathsf {vect}(\mathbf {U}^\top \mathbf {F}) \\ \mathsf {vect}(\mathbf {F}\mathbf {V})\end{pmatrix}\).
Now, we make the crucial observation that the underlying function-hiding FE for inner products is only used for vectors that lie in some specific subspace, strictly included in the whole space, namely, vectors (column) spanned by the matrix: \(\mathbf {M}:= \left( \begin{array}{c|c} \mathbf {a}\otimes (\mathrm {Id}_m|\mathbf {V}\mathbf {b}) &{} \mathbf {0}\\ \hline \mathbf {0}&{} \mathrm {Id}_n \otimes \mathbf {b}\end{array}\right) \), where \(\mathrm {Id}_n\) (resp. \(\mathrm {Id}_m\)) denotes the identity matrix of dimension n (resp. m). Thus, we create, and make public, a restricted key that can only generate ciphertexts for these vectors, while still providing some meaningful function-hiding. Namely, we prove that only \({\mathbf {M}^\top \mathbf {y}}\) leaks from a decryption key \({\mathsf {sk}_{\mathbf {y}}}\) (in addition to what is supposed to leak by correctness of the scheme), which turns out to be sufficient for the security proof of the overall quadratic FE. [Lin17] also builds quadratic FE from function-hiding FE for inner products, but it uses [ABDP15] encryption of \(\mathbf {x}\) and \(\mathbf {y}\) in the ciphertext, and it requires a full-fledged function-hiding FE, which can only be private-key.
3.1 Partially Function-Hiding Inner-Product FE
A partially function-hiding functional encryption for inner products is defined with respect to a pairing group \({{\mathcal {PG}:=(\mathbb {G}_1,\mathbb {G}_2,P_1,P_2,e) \leftarrow \mathsf {PGGen}(1^\lambda )}}\), a full rank matrix \({\mathbf {M}\in \mathbb {Z}_p^{n \times m}}\), with \(n>m\), and such that \({\mathbf {M}^\top \mathbf {M}\in \mathbb {Z}_p^{m \times m}}\) is invertible; and a tag space \(\mathcal {T}\). It consists of the following PPT algorithms:
-
\({\mathsf {Setup}(1^\lambda ,\mathcal {PG},[\mathbf {M}]_1)}\): returns the public key \(\mathsf {pk}\) (implicitly input of all other algorithms), and the master secret key \(\mathsf {msk}\). We assume \(\mathsf {pk}\) contains a description of \({[\mathbf {M}]_1}\) and \(\mathcal {T}\).
-
\({\mathsf {Enc}(\mathbf {t}\in \mathbb {Z}_p^{m},\tau \in \mathcal {T})}\): returns a ciphertext \({\mathsf {ct}_{\mathbf {M}\mathbf {t}}}\), associated with vector \({\mathbf {M}\mathbf {t}\in \mathbb {Z}_p^n}\) and tag \(\tau \).
-
\({\mathsf {Enc}'(\mathsf {msk},[\mathbf {x}]_1 \in \mathbb {G}_1^n, \tau \in \mathcal {T})}\): returns a ciphertext \(\mathsf {ct}_{\mathbf {x}}\), associated with vector \({\mathbf {x}\in \mathbb {Z}_p^n}\) and tag \(\tau \).
-
\({\mathsf {KeyGen}(\mathsf {msk},\mathbf {y}\in \mathbb {Z}_p^n)}\): returns a decryption key \({\mathsf {sk}_{\mathbf {y}}}\).
-
\({\mathsf {Dec}(\tau ,\mathsf {ct}_{\mathbf {x}},\mathsf {sk}_{\mathbf {y}})}\): deterministic algorithm that returns a value in \(\mathbb {G}_T\), or \(\bot \) if it fails.
Note that \(\mathsf {Enc}\) is public key, and can only encrypt vectors in the span of \([\mathbf {M}]_1\), while \(\mathsf {Enc}'\) needs the \(\mathsf {msk}\), but can encrypt any vector \({[\mathbf {x}]_1 \in \mathbb {G}_1^n}\). Another crucial difference is that \(\mathsf {Enc}'\) works on vector of group elements, while \(\mathsf {Enc}\) needs to get the exponents as input. We require these two encryption algorithms agree on the their common input space, namely: for all \({\mathbf {t}\in \mathbb {Z}_p^m}\) and \({\tau \in \mathcal {T}}\), \({\mathsf {Enc}(\mathbf {t},\tau )}\) is identically distributed from \({\mathsf {Enc}'(\mathsf {msk},[\mathbf {M}\mathbf {t}]_1,\tau )}\), where \({(\mathsf {pk},\mathsf {msk}) \leftarrow \mathsf {Setup}(1^\lambda ,\mathcal {PG},[\mathbf {M}]_1)}\).
To build quadratic FE in Sect. 3, we require a tag-free partially function-hiding inner-product FE (which corresponds to the case \({\mathcal {T}:=\{\varepsilon \}}\)). The latter can be obtained generically from any tag-based partially function-hiding inner-product FE, using one-time signature.
Correctness. For all \({\mathbf {t}\in \mathbb {Z}_p^m}\), \({\mathbf {y}\in \mathbb {Z}_p^n}\), \({\tau \in \mathcal {T}}\), \(\Pr [\mathsf {Dec}(\tau ,\mathsf {ct}_{\mathbf {M}\mathbf {t}},\mathsf {sk}_{\mathbf {y}})=[(\mathbf {M}\mathbf {t})^\top \mathbf {y}]_T]=1\), where the probability is taken over \({(\mathsf {pk},\mathsf {msk}) \leftarrow \mathsf {Setup}(1^\lambda ,\mathcal {PG},[\mathbf {M}]_1)}\), \({\mathsf {ct}_{\mathbf {M}\mathbf {t}} \leftarrow \mathsf {Enc}(\mathbf {t},\tau )}\), \({\mathsf {sk}_{\mathbf {y}} \leftarrow \mathsf {KeyGen}(\mathsf {msk},\mathbf {y})}\).
Security. We define simulation security for partially function-hiding inner-product FE, which captures the fact that the only information that leaks from a ciphertext \(\mathsf {ct}_{\mathbf {x}}\) and keys \(\mathsf {sk}_{\mathbf {y}}\) is \({\mathbf {x}^\top \mathbf {y}}\), and some partial information on \(\mathbf {y}\), namely, \({\mathbf {M}(\mathbf {M}^\top \mathbf {M})^{-1}\mathbf {M}^\top \mathbf {y}}\). We give both CPA and CCA variant of security notions.
Definition 7 (partially function-hiding, CPA Simulation security)
For any inner-product FE scheme \(\mathsf {FE}\), any PPT simulator \({\mathcal {S}:=(\widetilde{\mathsf {Setup}},\widetilde{\mathsf {Enc}},\widetilde{\mathsf {KeyGen}})}\), and any PPT stateful adversary \(\mathcal {A}\), we define the following two experiments.
In the real experiment, the key generation oracle \({\mathcal {O}_{\mathsf {KeyGen}}}\), when given as input \({\mathbf {y}\in \mathbb {Z}_p^n}\), returns \({\mathsf {KeyGen}(\mathsf {msk},\mathbf {y})}\). In the ideal experiment, when \({\mathcal {O}_{\mathsf {KeyGen}}}\) is given as input \({\mathbf {y}\in \mathbb {Z}_p^n}\), it computes \({\mathbf {x}^\top \mathbf {y}}\), \({\widetilde{\mathbf {y}}:=\mathbf {M}(\mathbf {M}^\top \mathbf {M})^{-1}\mathbf {M}^\top \mathbf {y}}\), and returns \({\widetilde{\mathsf {KeyGen}}(\widetilde{\mathsf {msk}},\mathbf {x}^\top \mathbf {y},\widetilde{\mathbf {y}})}\).
We say an FE scheme is partially function-hiding simulation-secure if there exists a PPT simulator \({\mathcal {S}:=(\widetilde{\mathsf {Setup}},\widetilde{\mathsf {Enc}},\widetilde{\mathsf {KeyGen}})}\) such that for all PPT adversaries \(\mathcal {A}\), we have:
Definition 8 (partially function-hiding, CCA Simulation security)
For any inner-product FE scheme \(\mathsf {FE}\), any PPT simulator \({\mathcal {S}:=(\widetilde{\mathsf {Setup}},\widetilde{\mathsf {Enc}},}\) \({\widetilde{\mathsf {KeyGen}},\widetilde{\mathsf {Dec}})}\), and any PPT stateful adversary \(\mathcal {A}\), we define the following two experiments.
In the real experiment, \({\mathcal {O}_{\mathsf {KeyGen}}(\mathbf {y}\in \mathbb {Z}_p^n)}\) returns \({\mathsf {KeyGen}(\mathsf {msk},\mathbf {y})}\). The oracle \({\mathcal {O}_{\mathsf {Dec}}(\tau ,\mathsf {ct},\mathbf {y})}\) returns \(\bot \) if \({\tau =\tau ^\star }\); otherwise, it computes \({\mathsf {sk}_{\mathbf {y}} \leftarrow \mathsf {KeyGen}(\mathsf {msk},\mathbf {y})}\), and returns \({\mathsf {Dec}(\tau ,\mathsf {ct},\mathsf {sk}_{\mathbf {y}})}\).
In the ideal experiment, \({\mathcal {O}_{\mathsf {KeyGen}}(\mathbf {y}\in \mathbb {Z}_p^n)}\) computes \({\mathbf {x}^\top \mathbf {y}}\), \(\widetilde{\mathbf {y}}:=\mathbf {M}(\mathbf {M}^\top \mathbf {M})^{-1}\mathbf {M}^\top \mathbf {y}\), and returns \({\widetilde{\mathsf {KeyGen}}(\widetilde{\mathsf {msk}}, \mathbf {x}^\top \mathbf {y}, \widetilde{\mathbf {y}})}\). The oracle \({\mathcal {O}_{\mathsf {Dec}}(\tau ,\mathsf {ct},\mathbf {y})}\) returns \(\bot \) if \({\tau \ne \tau ^\star }\); otherwise, it computes \({\widetilde{\mathbf {y}}:=\mathbf {M}(\mathbf {M}^\top \mathbf {M})^{-1}\mathbf {M}^\top \mathbf {y}}\), and returns \({\widetilde{\mathsf {Dec}}(\tau ,\mathsf {ct},\widetilde{\mathbf {y}})}\).
We say an FE scheme is CCA partially function-hiding, simulation secure if there exists a PPT simulator \({\mathcal {S}:=(\widetilde{\mathsf {Setup}},\widetilde{\mathsf {Enc}},\widetilde{\mathsf {KeyGen}},\widetilde{\mathsf {Dec}})}\) such that for all PPT adversaries \(\mathcal {A}\), we have:
3.2 Quadratic FE from Partially Function-Hiding Inner-Product FE
We describe our quadratic FE in Fig. 4, for the functionality \({\mathcal {F}_{\mathsf {quad},B}}\). Its security relies on the security of the underlying partially function-hiding inner-product FE, the bilateral DLIN assumption, and the DDH assumption in \(\mathbb {G}_1\).
Correctness. By correctness of the underlying inner-product FE, we have:
which corresponds exactly to the extra terms obtained when computing \({\mathsf {ct}_{\mathbf {x}}^\top \mathbf {F}\mathsf {ct}_{\mathbf {y}}}\), that is, we have: \({\mathsf {ct}_{\mathbf {x}}^\top \mathbf {F}\mathsf {ct}_{\mathbf {y}} = \mathbf {x}^\top \mathbf {F}\mathbf {y}+ d}\). Finally, \(\mathsf {Dec}\) computes the discrete log of \({[\mathbf {x}^\top \mathbf {F}\mathbf {y}]_T}\), which is efficient since the output \({\mathbf {x}^\top \mathbf {F}\mathbf {y}}\) is bounded by \({n \cdot m \cdot B^3}\), which is a polynomial in the security parameter.
Theorem 1 (Simulation security of the quadratic FE)
The quadratic FE from Fig. 4 for the functionality is simulation CPA (resp. CCA) secure if the underlying inner-product FE is partially function-hiding CPA (resp. CCA) simulation secure, assuming the bilateral DLIN assumption and the DDH assumption in \(\mathbb {G}_1\).
Namely, for any PPT adversary \(\mathcal {A}\), there exist PPT adversaries \(\mathcal {B}_1\), \(\mathcal {B}_2\), and \(\mathcal {B}_3\) such that:
Besides, for any PPT adversary \(\mathcal {A}'\), there exist PPT adversaries \(\mathcal {B}'_1\), \(\mathcal {B}'_2\), and \(\mathcal {B}'_3\) such that:
Proof
We prove the second part of the theorem, that is, CCA security. The CPA security proof is a straightforward simplification, hence omitted. Let \(\mathcal {A}\) be a PPT adversary against the CCA security of \(\mathsf {Quad}\). We use a sequence of hybrid games \(\mathsf {Game}_i\) for \(i \in \{1,2,3,4\}\), defined in Fig. 5, and we denote the advantage \({\varepsilon _i := \Pr [1 \leftarrow \mathsf {Game}_i(\mathcal {A},1^\lambda )]}\). We show that these games are computationally indistinguishable: \(\mathsf {Real}^{\mathsf {CCA}\text {-}\mathsf {Quad}}_{\mathcal {A}}(1^\lambda ) \equiv \mathsf {Game}_1 \approx _c \mathsf {Game}_2 \approx _c \mathsf {Game}_3 \approx _c \mathsf {Game}_4 \approx _s \mathsf {Ideal}^{\mathsf {CCA}\text {-}\mathsf {Quad}}_{\mathcal {A},\mathcal {S}}(1^\lambda )\), for the PPT simulator \(\mathcal {S}:=(\widetilde{\mathsf {Setup}},\widetilde{\mathsf {Enc}},\widetilde{\mathsf {KeyGen}},\widetilde{\mathsf {Dec}})\) defined in Fig. 6.
\(\mathsf {Game}_1\): is as \({\mathsf {Real}^{\mathsf {CCA}\text {-}\mathsf {Quad}}_{\mathcal {A}}(1^\lambda )}\), except the encryption algorithm \(\mathsf {Enc}'\) is used instead of \(\mathsf {Enc}\). Since these algorithms are identically distributed on input vectors in the span on \([\mathbf {M}]_1\), this does not change the advantage of \(\mathcal {A}\):
\(\mathsf {Game}_2\): we use the DDH assumption in \(\mathbb {G}_1\) to switch the distribution of the vector \([\mathbf {a}r]_1\) in the challenge ciphertext to uniformly random over \(\mathbb {G}_1^2\). Namely, we build a PPT adversary \(\mathcal {B}_1\) against the DDH assumption such that
Upon receiving the DDH challenge \({(\mathcal {PG},[\mathbf {a}]_1,[\mathbf {c}]_1)}\), \(\mathcal {B}_1\) samples \({\mathbf {U}\leftarrow _{\text {R}}\mathbb {Z}_p^{n \times 2}}\), \({\mathbf {V}\leftarrow _{\text {R}}\mathbb {Z}_p^{m \times 3}}\), \({\mathbf {B}\leftarrow \mathsf {DLIN}}\), computes \({[\mathbf {M}]_1}\) as defined in Fig. 4, and runs \({(\mathsf {pk}_{\mathsf {IPFE}}, \mathsf {msk}_{\mathsf {IPFE}})\leftarrow \mathsf {Setup}_{\mathsf {IPFE}}(1^\lambda ,\mathcal {PG},[\mathbf {M}]_1)}\), tanks to which it can simulate the public key \(\mathsf {pk}\) for \(\mathcal {A}\), and answer its queries to \(\mathcal {O}_{\mathsf {KeyGen}}\) and \(\mathcal {O}_{\mathsf {Dec}}\). When \(\mathcal {A}\) submits its challenge \({(\mathbf {x},\mathbf {y})}\), \({\mathcal {B}_1}\) samples \({\mathbf {s}\leftarrow _{\text {R}}\mathbb {Z}_p^2}\), computes \({[\mathsf {ct}_{\mathbf {x}}]_1 := [\mathbf {x}+ \mathbf {U}\mathbf {c}]_1}\), \({[\mathsf {ct}_{\mathbf {y}}]_2 := [\mathbf {y}+ \mathbf {V}\mathbf {B}\mathbf {s}]_2}\), \([\mathbf {z}]_1 := \begin{bmatrix} \mathbf {c}\otimes \mathsf {ct}_{\mathbf {y}} \\ \mathbf {x}\otimes \mathbf {B}\mathbf {s}\end{bmatrix}_1\) and returns the challenge ciphertext \({([\mathsf {ct}_{\mathbf {x}}]_1, [\mathsf {ct}_{\mathbf {y}}]_2, \mathsf {Enc}'_{\mathsf {IPFE}}(\mathsf {msk}_{\mathsf {IPFE}},[\mathbf {z}]_1))}\) to \(\mathcal {A}\). When \([\mathbf {c}]_1\) is a real DDH challenge, that is, of the form \({[\mathbf {c}]_1 := [\mathbf {a}r]_1}\) for some \({r \leftarrow _{\text {R}}\mathbb {Z}_p}\), \(\mathcal {B}_1\) simulates \(\mathsf {Game}_1\), whereas it simulates \(\mathsf {Game}_2\) when \([\mathbf {c}]_1\) is uniformly random over \(\mathbb {G}_1^2\).
\(\mathsf {Game}_3\): we use the bilateral DLIN assumption to switch the distribution of the vector \({[\mathbf {B}\mathbf {s}]_2}\) to uniformly random over \(\mathbb {G}_2^3\). Namely, we build a PPT adversary \(\mathcal {B}_2\) such
Upon receiving the DLIN challenge \({(\mathcal {PG},\{[\mathbf {B}]_s,[\mathbf {t}]_s\}_{s \in \{1,2\}})}\), \(\mathcal {B}_2\) samples \({\mathbf {U}\leftarrow _{\text {R}}\mathbb {Z}_p^{n \times 2}}\), \({\mathbf {V}\leftarrow _{\text {R}}\mathbb {Z}_p^{m \times 3}}\), \({\mathbf {a}\leftarrow _{\text {R}}\mathsf {DDH}}\), computes \([\mathbf {M}]_1\) as defined in Fig. 4, and runs \({(\mathsf {pk}_{\mathsf {IPFE}},\mathsf {msk}_{\mathsf {IPFE}})\leftarrow \mathsf {Setup}_{\mathsf {IPFE}}(1^\lambda ,\mathcal {PG},[\mathbf {M}]_1)}\), tanks to which it can simulate the public key \(\mathsf {pk}\) for \(\mathcal {A}\), and answer its queries to \(\mathcal {O}_{\mathsf {KeyGen}}\) and \(\mathcal {O}_{\mathsf {Dec}}\). When \(\mathcal {A}\) submits its challenge \((\mathbf {x},\mathbf {y})\), \(\mathcal {B}\) samples \({\mathbf {c}\leftarrow _{\text {R}}\mathbb {Z}_p^2}\), computes \({[\mathsf {ct}_{\mathbf {x}}]_1 := [\mathbf {x}+ \mathbf {U}\mathbf {c}]_1}\), \({[\mathsf {ct}_{\mathbf {y}}]_2 := [\mathbf {y}+ \mathbf {V}\mathbf {t}]_2}\), \([\mathbf {z}]_1 := \begin{bmatrix} \mathbf {c}\otimes (\mathbf {y}+\mathbf {V}\mathbf {t}) \\ \mathbf {x}\otimes \mathbf {t}\end{bmatrix}_1\) and returns the challenge ciphertext \({([\mathsf {ct}_{\mathbf {x}}]_1, [\mathsf {ct}_{\mathbf {y}}]_2, \mathsf {Enc}'_{\mathsf {IPFE}}(\mathsf {msk}_{\mathsf {IPFE}},[\mathbf {z}]_1))}\) to \(\mathcal {A}\). When \(\{[\mathbf {t}]_s\}_{s \in \{1,2\}}\) is a real DLIN challenge, that is, of the form \({[\mathbf {t}]_s := [\mathbf {B}\mathbf {s}]_s}\) for some \({\mathbf {s}\leftarrow _{\text {R}}\mathbb {Z}_p^2}\), \(\mathcal {B}_2\) simulates \(\mathsf {Game}_2\), whereas it simulates \(\mathsf {Game}_3\) when \([\mathbf {t}]_s\) is uniformly random over \(\mathbb {G}_s^2\).
\(\mathsf {Game}_4\): we use the simulator \({(\widetilde{\mathsf {Setup}}_{\mathsf {IPFE}},\widetilde{\mathsf {Enc}}_{\mathsf {IPFE}}, \widetilde{\mathsf {KeyGen}}_{\mathsf {IPFE}},\widetilde{\mathsf {Dec}}_{\mathsf {IPFE}})}\) of \(\mathsf {IPFE}\), as described in Fig. 5. Namely, there exists a PPT adversary \(\mathcal {B}_3\) such that
Adversary \(\mathcal {B}_3\) samples \({\mathbf {a}\leftarrow _{\text {R}}\mathsf {DDH}}\), \({\mathbf {B}\leftarrow _{\text {R}}\mathsf {DLIN}}\), \({\mathbf {U}\leftarrow _{\text {R}}\mathbb {Z}_p^{n \times 2}}\), \({\mathbf {V}\leftarrow _{\text {R}}\mathbb {Z}_p^{m \times 3}}\), and simulates \(\mathcal {A}\)’s view straightforwardly, using the fact that for all \({\mathbf {x}\in \mathbb {Z}_p^n}\), \({\mathbf {y}\in \mathbb {Z}_p^m}\), \({\mathbf {F}\in \mathbb {Z}_p ^{n \times m}}\), \({\mathbf {c}\in \mathbb {Z}^2_p}\), \({\mathbf {t}\in \mathbb {Z}_p^3}\), we have:
where \({\mathsf {ct}_{\mathbf {x}} = \mathbf {x}+ \mathbf {U}\mathbf {c}}\), and \({\mathsf {ct}_{\mathbf {y}} = \mathbf {y}+ \mathbf {V}\mathbf {t}}\).
\({\mathsf {Ideal}^{\mathsf {CCA}\text {-}\mathsf {Quad}}_{\mathcal {A},\mathcal {S}}(1^\lambda )}\): is as \(\mathsf {Game}_4\), except that \(\mathsf {ct}_{\mathbf {x}}\) and \(\mathsf {ct}_{\mathbf {y}}\) in the challenge ciphertext are uniformly distributed. We show that these two games are statistically close. Namely, we show that the vectors \(\mathbf {U}\mathbf {c}\) and \(\mathbf {V}\mathbf {t}\) are statistically close to uniformly random over \(\mathbb {Z}_p^2\) and \(\mathbb {Z}_p^3\), respectively.
To prove so, we use the following basis of \(\mathbb {Z}_p^2\) and \(\mathbb {Z}_p^3\): \({(\mathbf {a}|\mathbf {a}^\bot )}\) and \({(\mathbf {B}|\mathbf {b}^\bot )}\) with \({\mathbf {a}\leftarrow _{\text {R}}\mathsf {DDH}}\), \({\mathbf {B}\leftarrow _{\text {R}}\mathsf {DLIN}}\), and \({\mathbf {a}^{\bot }\in \mathbb {Z}_p^2}\), \({\mathbf {b}^{\bot }\in \mathbb {Z}_p^3}\) are such that \({\mathbf {a}^\top \mathbf {a}^\bot = 0}\) and \({\mathbf {B}^\top \mathbf {b}^\bot = \mathbf {0}}\). Such basis exist assuming \(\mathbf {a}\) and \(\mathbf {B}\) are both full rank, which happens with probability at least \({1-\frac{2}{p}}\) over the choice of \({\mathbf {a}\leftarrow _{\text {R}}\mathsf {DDH}}\) and \({\mathbf {B}\leftarrow _{\text {R}}\mathsf {DLIN}}\). We have: \({\mathbf {U}^\top := \mathbf {a}\mathbf {u}^\top _0 + \mathbf {a}^\bot \mathbf {u}_1^\top }\), and \({\mathbf {V}^\top := \mathbf {B}\mathbf {V}_0 + \mathbf {b}^\bot \mathbf {v}_1^\top }\), with \({\mathbf {u}_0, \mathbf {u}_1 \leftarrow _{\text {R}}\mathbb {Z}_p^n}\), \({\mathbf {V}_0 \leftarrow _{\text {R}}\mathbb {Z}_p^{2 \times m}}\), and \({\mathbf {v}_1 \leftarrow _{\text {R}}\mathbb {Z}_p^m}\). We will show that \(\mathbf {u}_1\) and \(\mathbf {v}_1\) only appear in the adversary view as \({(\mathbf {c}^\top \mathbf {a}^\bot ) \mathbf {u}_1}\) in \(\mathsf {ct}_{\mathbf {x}}\), and as \({(\mathbf {t}^\top \mathbf {b}^\bot ) \mathbf {v}_1}\) in \(\mathsf {ct}_{\mathbf {y}}\). Since we have \({\mathsf {ct}_{\mathbf {x}} = \mathbf {x}+ \mathbf {u}_0 (\mathbf {c}^\top \mathbf {a}) + \mathbf {u}_1 (\mathbf {c}^\top \mathbf {a}^{\bot })}\) and \({\mathsf {ct}_{\mathbf {y}} = \mathbf {y}+ \mathbf {V}_0^\top (\mathbf {B}^\top \mathbf {t}) + \mathbf {v}_1 (\mathbf {t}^\top \mathbf {b}^{\bot })}\), when \({\mathbf {c}^\top \mathbf {a}^{\bot }\ne 0}\), and \({\mathbf {t}^\top \mathbf {b}^{\bot }\ne 0}\), the vectors \(\mathsf {ct}_{\mathbf {x}}\) and \(\mathsf {ct}_{\mathbf {y}}\) are uniformly random over \(\mathbb {Z}_p^2\) and \(\mathbb {Z}_p^3\), respectively. With probability \(1-\frac{2}{p}\) over the choice of \({\mathbf {c}\leftarrow _{\text {R}}\mathbb {Z}_p^2}\) and \({\mathbf {t}\leftarrow _{\text {R}}\mathbb {Z}_p^3}\), we have \({\mathbf {c}^\top \mathbf {a}^\bot \ne 0}\), and \({\mathbf {t}^\top \mathbf {b}^\bot \ne 0}\), which proves
We now show that \(\mathbf {u}_1\) and \(\mathbf {v}_1\) only appear in \(\mathsf {ct}_{\mathbf {x}}\) and \(\mathsf {ct}_{\mathbf {y}}\), as indicated above. In the public key, we have \({\mathbf {a}^\top \mathbf {U}^\top = \mathbf {a}^\top (\mathbf {a}\mathbf {u}^\top _0 + \mathbf {a}^\bot \mathbf {u}_1^\top ) = (\mathbf {a}^\top \mathbf {a}) \mathbf {u}_0^\top }\), and \({\mathbf {B}^\top \mathbf {V}^\top = \mathbf {B}^\top (\mathbf {B}\mathbf {V}_0 + \mathbf {b}^\bot \mathbf {v}_1^\top ) = (\mathbf {B}^\top \mathbf {B}) \mathbf {v}_0^\top }\). The information needed to simulate \({\mathcal {O}_{\mathsf {KeyGen}}}\) and \({\mathcal {O}_{\mathsf {Dec}}}\) is contained in \(\mathbf {F}\), \({\mathsf {ct}_{\mathbf {x}}}\), \(\mathsf {ct}_{\mathbf {y}}\), \({\mathbf {x}^\top \mathbf {F}\mathbf {y}}\), \(\mathbf {M}\), and
where the equality holds by definition of \(\mathbf {M}\). That is, the only information about \(\mathbf {u}_1\) and \(\mathbf {v}_1\) is contained in \(\mathsf {ct}_{\mathbf {x}}\), \(\mathsf {ct}_{\mathbf {y}}\), which concludes the proof. \(\square \)
4 Partially-Hiding Inner Product FE
In this section we build a partially-hiding, simulation-secure inner-product FE scheme, as defined in Sect. 3.1, based on the SXDH assumption. Together with the generic construction from Sect. 3, this gives the quadratic FE advertised in Sect. 1, Fig. 2.
Overview of the Partially-Hiding Inner-Product FE. We now highlight the construction of our new partially-hiding public-key FE for inner products. Our starting point is the FE for inner products from [ALS16], described in Fig. 7. It is not function-hiding since \(\mathbf {y}\) is part of the decryption keys generated by \(\mathsf {KeyGen}\). As in [Lin17, Section 6.3], we use the fact that the decryption computes the inner product of \(\mathsf {Enc}(\mathbf {x})\) and \({\mathsf {KeyGen}(\mathbf {y})}\) to obtain \({[\mathbf {x}^\top \mathbf {y}] \in \mathbb {G}}\). Namely, we replace the vector \(\mathbf {y}\) in each decryption key by an ALS encryption of \(\mathbf {y}\), and \(\mathbf {x}\) in each ciphertext is replaced by an ALS decryption key for \(\mathbf {x}\) (see Fig. 3). Function-Hiding (hiding \(\mathbf {y}\)) follows from the security of the inner ALS FE, whereas security (hiding \(\mathbf {x}\)) follows from the security of the outter ALS FE. Note that we use the fact that the \(\mathsf {KeyGen}\) algorithm from [ALS16] FE can act on vectors in \(\mathbb {G}_2\), and the multiplications can be computed using the pairing \(e: \mathbb {G}_1 \times \mathbb {G}_2 \rightarrow \mathbb {G}_T\) to recover the inner product of \(\mathbf {x}\) and \(\mathbf {y}\) in \(\mathbb {G}_T\).
To make our scheme public-key, we need to publish a restricted secret key for the inner layer FE that lets \({\mathsf {KeyGen}^{\mathsf {in}}(\mathbf {x})}\) run on vectors \(\mathbf {x}\) spanned by the matrix \(\mathbf {M}\) described in Sect. 3 (recall that \(\mathbf {M}\) is a full rank, n times m matrix, with \(n>m\)). If we denote the master secret key of the inner layer FE by \({\mathsf {msk}:=\mathbf {U}\in \mathbb {Z}_p^{d \times 2}}\), the restricted key would simply be \({\mathbf {U}^\top \mathbf {M}}\).
We prove simulation security, which is necessary to be of use in our quadratic FE scheme, and which is stronger than the classical indistinguishability based security for FE. To do so, we use the simulation security of [ALS16], which was proven in [AGRW17, Wee17]. We obtain simulation security in the semi-adaptive setting, where the adversary sends its challenge before querying any secret keys, but after receiving the public key. This is the best we can hope for, since a straightforward adaptation of the results from [BSW11, AGVW13] show that simulation security is impossible in the adaptive setting (where the adversary can query secret keys before sending its challenge ciphertext).
[Lin17] also builds function-hiding FE from a two layered FE encryption, but uses [ABDP15] instead of [ALS16], and only obtains indistinguishability security, in the private key setting (see Fig. 3).
Our partially-hiding, simulation-secure inner-product FE is described in Fig. 8.
Correctness. For all \({\mathbf {t}\in \mathbb {Z}_p^m}\) and \({\mathbf {y}\in \mathbb {Z}_p^n}\), we have:
The first equality uses the correctness of the outer ALS encryption, while the second equality uses the correctness of the inner ALS encryption. We conclude using the completeness of the QANIZK argument.
Remark 1 (Large inputs)
First, we observe that the encryption algorithm of our partially function-hiding inner product FE can take as input arbitrary vectors \({\mathbf {x}\in \mathbb {Z}_p^n}\), as opposed to \({\mathbf {x}\in [0,B]^n}\) for a polynomially bounded B. The decryption is in two step: first \({\mathsf {Dec}_{\mathsf {large}}(\mathsf {Enc}(\mathbf {x}),\mathsf {KeyGen}(\mathsf {msk},\mathbf {y}))}\) for arbitrary vectors \({\mathbf {x}\in \mathbb {Z}_p^n}\) and \({\mathbf {y}\in \mathbb {Z}_p^n}\), recovers \({[\mathbf {x}^\top \mathbf {y}]_T}\). The second step solves the discrete logarithm to recover \({\mathbf {x}^\top \mathbf {y}}\). The second step is only efficient for polynomially bounded output, whereas the first step handles arbitrary large inputs.
The second observation we make is that for all \({\mathbf {y}\in \mathbb {Z}_p^n}\), \({\mathsf {KeyGen}(\mathsf {msk},\mathbf {y})}\) outputs a vector or group elements \({[\mathbf {d}]_2\in \mathbb {G}_2^\ell }\), for some dimension \(\ell \). The algorithm \({\widetilde{\mathsf {KeyGen}}}\) from the simulator of our scheme described in Fig. 8, when given as input \({\widetilde{\mathsf {msk}}}\), \({\widetilde{\mathbf {y}}}\), and \({\mathbf {x}^\top \mathbf {y}}\), first computes \({\mathbf {d}\in \mathbb {Z}_p^\ell }\), and then returns \({[\mathbf {d}]_2}\) as the functional decryption key for \(\mathbf {y}\). Moreover, it is a linear function in its input \({\widetilde{\mathbf {y}}}\) and \({\mathbf {x}^\top \mathbf {y}}\). Thus, we can run \({\widetilde{\mathsf {KeyGen}}(\widetilde{\mathsf {msk}},[\widetilde{\mathbf {y}}]_2,[\mathbf {x}^\top \mathbf {y}]_2)}\) to get the functional decryption key \([\mathbf {d}]_2\). Otherwise stated, we achieved a slightly stronger simulation security than in Definition 7, since the simulator only requires to know the value \({[\widetilde{\mathbf {y}}]_2}\) and \({\mathbf {x}^\top \mathbf {y}]_2}\) in \(\mathbb {G}_2\), as opposed to the values \(\widetilde{\mathbf {y}}\) and \({\mathbf {x}^\top \mathbf {y}}\) over \(\mathbb {Z}_p\).
Consequently, the quadratic FE from Sect. 3 that builds upon our partially function-hiding inner product FE inherits the same properties. Therefore, it can be use to encrypt random vectors \({\mathbf {u}\in \mathbb {Z}_p^n}\), and \({\mathbf {v}\in \mathbb {Z}_p^m}\). Each functional decryption key corresponds to a pair of indices \({(i,j) \in [n] \times [m]}\), and the decryption outputs \([u_i v_j]_T\). Simulation security ensures that the adversary view can be simulated from \([u_i v_j]_2\) only, which are pseudorandom by the DDH assumption in \(\mathbb {G}_2\). This allows users to evaluate outputs of a PRG over \(\mathbb {G}_T\), which is unachievable with an indistinguishability-based quadratic FE.
Theorem 2 (Security)
The inner-product FE described in Fig. 8 is partially-hiding, CPA simulation-secure, assuming the SXDH assumption. Moreover, if the QANIZK argument \(\varPi \) is one-time simulation sound, then the FE is CCA simulation-secure. Namely, for any PPT adversary \(\mathcal {A}\), there exist PPT adversaries \(\mathcal {B}_1\) and \(\mathcal {B}_2\) such that:
where \(Q_\mathsf {sk}\) denotes the number of queries to \({\mathcal {O}_{\mathsf {KeyGen}}}\). Moreover, for any PPT adversary \(\mathcal {A}'\), there exist PPT adversaries \(\mathcal {B}'_1\), \(\mathcal {B}'_2\) and \(\mathcal {B}'_3\) such that:
where \(Q_\mathsf {sk}\) denotes the number of queries to \(\mathcal {O}_{\mathsf {KeyGen}}\), and \(Q_\mathsf {Dec}\) denotes the number of queries to \(\mathcal {O}_{\mathsf {Dec}}\).
The proof of Theorem 2 is given in the full version of this paper.
Notes
- 1.
Namely, the existence of pseudo-random generators of block-wise locality 3.
References
Abdalla, M., Bourse, F., De Caro, A., Pointcheval, D.: Simple functional encryption schemes for inner products. In: Katz, J. (ed.) PKC 2015. LNCS, vol. 9020, pp. 733–751. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46447-2_33
Abdalla, M., Gay, R., Raykova, M., Wee, H.: Multi-input inner-product functional encryption from pairings. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017, Part I. LNCS, vol. 10210, pp. 601–626. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56620-7_21
Agrawal, S., Gorbunov, S., Vaikuntanathan, V., Wee, H.: Functional encryption: new perspectives and lower bounds. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part II. LNCS, vol. 8043, pp. 500–518. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40084-1_28
Ananth, P., Jain, A.: Indistinguishability obfuscation from compact functional encryption. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015, Part I. LNCS, vol. 9215, pp. 308–326. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47989-6_15
Agrawal, S., Libert, B., Stehlé, D.: Fully secure functional encryption for inner products, from standard assumptions. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016, Part III. LNCS, vol. 9816, pp. 333–362. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53015-3_12
Ananth, P., Sahai, A.: Projective arithmetic functional encryption and indistinguishability obfuscation from degree-5 multilinear maps. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017, Part I. LNCS, vol. 10210, pp. 152–181. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56620-7_6
Benhamouda, F., Bourse, F., Lipmaa, H.: CCA-secure inner-product functional encryption from projective hash functions. In: Fehr, S. (ed.) PKC 2017, Part II. LNCS, vol. 10175, pp. 36–66. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-662-54388-7_2
Baltico, C.E.Z., Catalano, D., Fiore, D., Gay, R.: Practical functional encryption for quadratic functions with applications to predicate encryption. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017, Part I. LNCS, vol. 10401, pp. 67–98. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63688-7_3
Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S., Yang, K.: On the (Im)possibility of obfuscating programs. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 1–18. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44647-8_1
Boneh, D., Sahai, A., Waters, B.: Functional encryption: definitions and challenges. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 253–273. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19571-6_16
Bitansky, N., Vaikuntanathan, V.: Indistinguishability obfuscation from functional encryption. In: 56th FOCS, pp. 171–190. IEEE Computer Society Press, October 2015
Boneh, D., Waters, B.: Conjunctive, subset, and range queries on encrypted data. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 535–554. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-70936-7_29
Canetti, R., Halevi, S., Katz, J.: Chosen-ciphertext security from identity-based encryption. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 207–222. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24676-3_13
Chen, J., Wee, H.: Semi-adaptive attribute-based encryption and improved delegation for boolean formula. In: Abdalla, M., De Prisco, R. (eds.) SCN 2014. LNCS, vol. 8642, pp. 277–297. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-10879-7_16
Damgård, I.: Towards practical public key systems secure against chosen ciphertext attacks. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 445–456. Springer, Heidelberg (1992). https://doi.org/10.1007/3-540-46766-1_36
Dufour Sans, E., Gay, R., Pointcheval, D.: Reading in the dark: classifying encrypted digits with functional encryption. Cryptology ePrint Archive, Report 2018/206 (2018). https://eprint.iacr.org/2018/206
ElGamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. In: Blakley, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 10–18. Springer, Heidelberg (1985). https://doi.org/10.1007/3-540-39568-7_2
Fujisaki, E., Okamoto, T.: Secure integration of asymmetric and symmetric encryption schemes. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 537–554. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48405-1_34
Goldwasser, S., et al.: Multi-input functional encryption. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 578–602. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-55220-5_32
Goyal, R., Koppula, V., Waters, B.: Semi-adaptive security and bundling functionalities made generic and easy. In: Hirt, M., Smith, A. (eds.) TCC 2016, Part II. LNCS, vol. 9986, pp. 361–388. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53644-5_14
Goyal, V., Pandey, O., Sahai, A., Waters, B.: Attribute-based encryption for fine-grained access control of encrypted data. In: ACM CCS 2006, pp. 89–98. ACM Press, October/November 2006. Available as Cryptology ePrint Archive Report 2006/309
Gorbunov, S., Vaikuntanathan, V., Wee, H.: Predicate encryption for circuits from LWE. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015, Part II. LNCS, vol. 9216, pp. 503–523. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48000-7_25
Jutla, C.S., Roy, A.: Shorter quasi-adaptive NIZK proofs for linear subspaces. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013, Part I. LNCS, vol. 8269, pp. 1–20. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-42033-7_1
Kim, S., Lewi, K., Mandal, A., Montgomery, H., Roy, A., Wu, D.J.: Function-hiding inner product encryption is practical. In: Catalano, D., De Prisco, R. (eds.) SCN 2018. LNCS, vol. 11035, pp. 544–562. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-98113-0_29
Katz, J., Sahai, A., Waters, B.: Predicate encryption supporting disjunctions, polynomial equations, and inner products. In: Smart, N. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 146–162. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78967-3_9
Kiltz, E., Wee, H.: Quasi-adaptive NIZK for linear subspaces revisited. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015, Part II. LNCS, vol. 9057, pp. 101–128. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46803-6_4
Lin, H.: Indistinguishability obfuscation from SXDH on 5-linear maps and locality-5 PRGs. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017, Part I. LNCS, vol. 10401, pp. 599–629. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63688-7_20
Lin, H., Tessaro, S.: Indistinguishability obfuscation from trilinear maps and block-wise local PRGs. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017, Part I. LNCS, vol. 10401, pp. 630–660. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63688-7_21
Lin, H., Vaikuntanathan, V.: Indistinguishability obfuscation from DDH-like assumptions on constant-degree graded encodings. In: 57th FOCS, pp. 11–20. IEEE Computer Society Press, October 2016
Naor, M., Yung, M.: Public-key cryptosystems provably secure against chosen ciphertext attacks. In: 22nd ACM STOC, pp. 427–437. ACM Press, May 1990
O’Neill, A.: Definitional issues in functional encryption. Cryptology ePrint Archive, Report 2010/556 (2010). http://eprint.iacr.org/2010/556
Sahai, A., Waters, B.: How to use indistinguishability obfuscation: deniable encryption, and more. In: 46th ACM STOC, pp. 475–484. ACM Press, May/June 2014
Wee, H.: Attribute-hiding predicate encryption in bilinear groups, revisited. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017, Part I. LNCS, vol. 10677, pp. 206–233. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70500-2_8
Yamada, S., Attrapadung, N., Hanaoka, G., Kunihiro, N.: Generic constructions for chosen-ciphertext secure attribute based encryption. In: Catalano, D., Fazio, N., Gennaro, R., Nicolosi, A. (eds.) PKC 2011. LNCS, vol. 6571, pp. 71–89. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19379-8_5
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 International Association for Cryptologic Research
About this paper
Cite this paper
Gay, R. (2020). A New Paradigm for Public-Key Functional Encryption for Degree-2 Polynomials. In: Kiayias, A., Kohlweiss, M., Wallden, P., Zikas, V. (eds) Public-Key Cryptography – PKC 2020. PKC 2020. Lecture Notes in Computer Science(), vol 12110. Springer, Cham. https://doi.org/10.1007/978-3-030-45374-9_4
Download citation
DOI: https://doi.org/10.1007/978-3-030-45374-9_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-45373-2
Online ISBN: 978-3-030-45374-9
eBook Packages: Computer ScienceComputer Science (R0)