# Practical CCA-Secure Functional Encryptions for Deterministic Functions

Authors: Huige Wang; Kefei Chen; Tianyu Pan; Yunlei Zhao
Journal: Security and Communication Networks
 (2020)

---

## Abstract

Functional encryption (FE) can implement fine-grained control to encrypted plaintext via permitting users to compute only some specified functions on the encrypted plaintext using private keys with respect to those functions. Recently, many FEs were put forward; nonetheless, most of them cannot resist chosen-ciphertext attacks (CCAs), especially for those in the secret-key settings. This changed with the work, i.e., a generic transformation of public-key functional encryption (PK-FE) from chosen-plaintext (CPA) to chosen-ciphertext (CCA), where the underlying schemes are required to have some special properties such as restricted delegation or verifiability features. However, examples for such underlying schemes with these features have not been found so far. Later, a CCA-secure functional encryption from projective hash functions was proposed, but their scheme only applies to inner product functions. To construct such a scheme, some nontrivial techniques will be needed. Our key contribution in this work is to propose CCA-secure functional encryptions in the PKE and SK environment, respectively. In the existing generic transformation from (adaptively) simulation-based CPA- (SIM-CPA-) secure ones for deterministic functions to (adaptively) simulation-based CCA- (SIM-CCA-) secure ones for randomized functions, whether the schemes were directly applied to CCA settings for deterministic functions is not implied. We give an affirmative answer and derive a SIM-CCA-secure scheme for deterministic functions by making some modifications on it. Again, based on this derived scheme, we also propose an (adaptively) indistinguishable CCA- (IND-CCA-) secure SK-FE for deterministic functions. The final results show that our scheme can be instantiated under both nonstandard assumptions (e.g., hard problems on multilinear maps and indistinguishability obfuscation (IO)) and under standard assumptions (e.g., DDH, RSA, LWE, and LPN).


---

## Body

## 1. Introduction

PKE is the most useful asymmetric encryption, which encrypted the plaintext using a public encryption keypk and decrypted the ciphertext using a private key sk only owned by the receiver. In particular, in this cryptosystem, without sk, nobody can get any sensitive information about plaintext. This type of cryptosystem does not work well in some special case where fine-grained access control functionality [1, 2] is needed to act on the decrypted plaintext. FE with this functionality was introduced by Boneh et al. [3]. Informally speaking, FE scheme [4–6] can encrypt a message m into a ciphertext ct using a system public key. However, it can only recover a function value fm from the ciphertext ct with a private key associated with the function f.Security is a most important nature of functional encryption, among which indistinguishable chosen-plaintext attack (IND-CPA) security is the most common. IND-CPA security requires that an efficient adversary cannot distinguish the encryption of two different messages even if it allows the adversary to get some extra information such as allowing them access the private key oracle. Furthermore, according to the capability of the adversary, security can be classified into the selective mode and adaptive mode. In the former, the challenge message must be chosen before the public parameter and private key is generated, while in the latter, it may be chosen at any time.Constructing FE for general functionalities with adaptive IND-CCA [7] security has been an open problem. Now, expressive functional encryptions with adaptive security have got rapid development. In 2015, Ananth et al. proposed an adaptively secure FE from the selective one [8]. The same year, Waters also presented an adaptively secure FE, but it relies on the strong IO assumption [9–11].


### 1.1. CCA Security

Although a wealth of results have been obtained on IND-CPA security, those schemes can only resist passive attacks. In order to resist active attacks, an IND-CCA security notion is required which is the same as IND-CPA but with exception that it additionally allows the adversary to access a decryption oracle. IND-CCA security in PKE settings has got richly studied by many researchers. Also, in the IBE [12] and ABE [13] settings, it also got extensively studied. Although IBEs and ABEs are subordinate to functional encryption, none of them could apply to general functions. Thus, studying FE with CCA security for arbitrary functions is necessary. In particular, although we allow the adversary to decrypt any ciphertext with private keys, it obtains by making key queries, and the security equipped with decryption oracle is still stronger than that without decryption oracle. The reason is, for any decryption query g,ct, the challenger can use the private key skg to decrypt ct, even conditioned on gm0≠gm1, but if without decryption oracle, the private key skg conditioned on gm0≠gm1 is not allowed to obtain, and thus, ct cannot be decrypted with this key. Simulation-based CCA (SIM-CCA) is a stronger notion than IND-CCA, meaning that the reduction can be simulated via a probability polynomial time (PPT) simulator who only knows partial information and parameters that the system allows.The FEs with CCA security are presented in [14, 15]. In [14], Benhamouda et al. proposed a CCA-secure functional encryption (FE) that only solves the CCA security in FE based on the projective hash functions. In [15], Nandi and Pandit also solved this problem but with strong restrictions (e.g., needing restricted delegation or verifiability on the underlying IND-CPA FE). However, up to now, it is not known whether the underlying schemes with these special properties exist. Although the generic transformation of Naor and Yung’s [16] from IND-CPA to IND-CCA encryption scheme can be adapted to functional encryption, it is only applied to the nonadaptive case in the public-key setting. Of course, it may achieve unbounded collusions, but which is not the key point we focus on in this paper. In particular, in Naor and Yung’s generic transformation, the encryption needs to run the original PK-FE twice.


### 1.2. Our Contributions

To construct functional encryptions with CCA security, some nontrivial techniques will be needed. We propose two (adaptively) CCA-secure generic construction for FE with CCA security for deterministic generic functions where one is in PKE settings and the other is in private-key settings. These generic constructions first yield practical FE that can be instantiated in the standard assumptions.We first construct an (adaptively) SIM-CCA-secure PK-FE for deterministic functions by making a small modification on Agrawal and Wu’s SIM-CCA-secure PK-FE for randomized functions. Then, using the PK-FE scheme together with a NIZK equipped with the property of extractabilities, we construct an (adaptively) IND-CCA-secure SK-FE scheme. Particularly, in our construction, SIM-CPA-secure PK-FE can be used in a black-box way. Thus, the constructed SK-FE can also be based on the same assumption as the underlying PK-FE scheme.


### 1.3. An Informal Description of Our Schemes

Our constructions are inspired by Agrawal and Wu’s generic transformation of PK-FE from deterministic functions to randomized functions [17]. Our solutions can work on standard assumptions and are more efficient than that by Naor and Yung’s generic transformation (since we only use the original primitive once rather than twice which is the case in Naor and Yung’s generic transformation). They are essentially optimal in communication size: in the derived PK-FE with SIM-CCA security, the public parameter and private key are almost equal to that in the underlying PK-FE, while the ciphertext consists of a PK-FE ciphertext and a NIZK proof. In the SK-FE with IND-CCA security, in addition to a PK-FE ciphertext and a NIZK proof, the final ciphertext also adds an SE ciphertext. In Agrawal and Wu’s generic CPA-to-CCA transformation from deterministic functions to randomized functions, they use a simulation-sound extractable NIZK to implement CPA-to-CCA transformation and a Φ-RKA-secure PRF and a one-way permutation to implement deterministic-to-randomized function transformation. Concretely, in the decryption query, e.g., g,ct, where g is a function, the simulator deals with the decryption by first employing the NIZK to extract a message m from the ciphertext ct and then evaluating function g on m. Thus, the simulator can perfectly realize the decryption functionalities under the extractability of the NIZK. For the deterministic-to-randomized function transformation, the core idea is to use a PRF to remove randomization on the function. Specifically, the scheme transforms the encryption of m to that of the pair m,hk′ with randomness hck′ under the SIM-CPA FE scheme where h is a one-way permutation and hc is a hardcore function of h. In the construction of the private key for a randomized function f, the scheme first constructs a “derandomize” function gkfm,hk′=fm,PRFk⋄hk′,m and then computes a SIM-CPA FE private key sk for function gkf. The decryption algorithm uses sk to recover fm,PRFk⋄hk′,m from a ciphertext ct which encrypts the message m,hk′. For our goals of deterministic functions, we remove the PRF and one-way permutation h used for implementing the deterministic-to-randomization function transformation and directly define the final private key as that of the SIM-CPA PK-FE for deterministic functions. Luckily, the removal operation does not affect the CPA-to-CCA transformation since the PRF and h does not participate in the transformation. In this way, we get a SIM-CCA-secure PK-FE scheme for deterministic functions.In the construction of adaptive IND-CCA SK-FE, a similar methodology proposed by Elkind and Sahai in [18] is adopted. In their construction, the encryption scheme is designed by first constructing a “bare” oblivious-decryptor scheme (ODS) and then employing a designated-verifier NIZK to achieve adaptive CCA security. More specifically, their scheme first encrypted message m under the ODS encryption into a ciphertext c and then employed a designated-verifier NIZK to prove π of pk,c∈L.Compared with their scheme, our work on IND-CCA security for SK-FE uses some seemingly different techniques. In our scheme, beyond a standard simulation-sound NIZK and a PK-FE scheme secure against SIM-CCA, we also use a semantically secure symmetric encryption (SE). The symmetric encryption is used to mask the message directly. Particularly, in order to enable decrypting, the SE ciphertext together with the symmetric key are reencrypted in a PK-FE ciphertext. A simulation-sound NIZK proof functions as a “well-formedness” condition on the symmetric ciphertext and is contained in the overall ciphertext. The underlying PK-FE scheme corresponds to the oblivious-decryptor scheme by Elkind and Sahai [18], whose SIM-CCA security together with the standard NIZK proof is used for rejecting ill-formed ciphertexts.Note that simulation security is strong; in particular, it implies that we have to restrict ourselves to either secure against bounded collusion, which may hinder the practicability of the scheme, or to simple functionality (for example, IBE), for which the scheme cannot be simulation secure against bounded collusion. Although a weak notion, for example, an IND-CPA-secure SK-FE which may induce a more practical scheme or simple functionality, it is not applicable to our construction. This is because, when we directly use the weak scheme, during the decryption query phase, the master secret key encrypted in the underlying SK-FE ciphertext can be extracted out by the NIZK.


## 1.1. CCA Security

Although a wealth of results have been obtained on IND-CPA security, those schemes can only resist passive attacks. In order to resist active attacks, an IND-CCA security notion is required which is the same as IND-CPA but with exception that it additionally allows the adversary to access a decryption oracle. IND-CCA security in PKE settings has got richly studied by many researchers. Also, in the IBE [12] and ABE [13] settings, it also got extensively studied. Although IBEs and ABEs are subordinate to functional encryption, none of them could apply to general functions. Thus, studying FE with CCA security for arbitrary functions is necessary. In particular, although we allow the adversary to decrypt any ciphertext with private keys, it obtains by making key queries, and the security equipped with decryption oracle is still stronger than that without decryption oracle. The reason is, for any decryption query g,ct, the challenger can use the private key skg to decrypt ct, even conditioned on gm0≠gm1, but if without decryption oracle, the private key skg conditioned on gm0≠gm1 is not allowed to obtain, and thus, ct cannot be decrypted with this key. Simulation-based CCA (SIM-CCA) is a stronger notion than IND-CCA, meaning that the reduction can be simulated via a probability polynomial time (PPT) simulator who only knows partial information and parameters that the system allows.The FEs with CCA security are presented in [14, 15]. In [14], Benhamouda et al. proposed a CCA-secure functional encryption (FE) that only solves the CCA security in FE based on the projective hash functions. In [15], Nandi and Pandit also solved this problem but with strong restrictions (e.g., needing restricted delegation or verifiability on the underlying IND-CPA FE). However, up to now, it is not known whether the underlying schemes with these special properties exist. Although the generic transformation of Naor and Yung’s [16] from IND-CPA to IND-CCA encryption scheme can be adapted to functional encryption, it is only applied to the nonadaptive case in the public-key setting. Of course, it may achieve unbounded collusions, but which is not the key point we focus on in this paper. In particular, in Naor and Yung’s generic transformation, the encryption needs to run the original PK-FE twice.


## 1.2. Our Contributions

To construct functional encryptions with CCA security, some nontrivial techniques will be needed. We propose two (adaptively) CCA-secure generic construction for FE with CCA security for deterministic generic functions where one is in PKE settings and the other is in private-key settings. These generic constructions first yield practical FE that can be instantiated in the standard assumptions.We first construct an (adaptively) SIM-CCA-secure PK-FE for deterministic functions by making a small modification on Agrawal and Wu’s SIM-CCA-secure PK-FE for randomized functions. Then, using the PK-FE scheme together with a NIZK equipped with the property of extractabilities, we construct an (adaptively) IND-CCA-secure SK-FE scheme. Particularly, in our construction, SIM-CPA-secure PK-FE can be used in a black-box way. Thus, the constructed SK-FE can also be based on the same assumption as the underlying PK-FE scheme.


## 1.3. An Informal Description of Our Schemes

Our constructions are inspired by Agrawal and Wu’s generic transformation of PK-FE from deterministic functions to randomized functions [17]. Our solutions can work on standard assumptions and are more efficient than that by Naor and Yung’s generic transformation (since we only use the original primitive once rather than twice which is the case in Naor and Yung’s generic transformation). They are essentially optimal in communication size: in the derived PK-FE with SIM-CCA security, the public parameter and private key are almost equal to that in the underlying PK-FE, while the ciphertext consists of a PK-FE ciphertext and a NIZK proof. In the SK-FE with IND-CCA security, in addition to a PK-FE ciphertext and a NIZK proof, the final ciphertext also adds an SE ciphertext. In Agrawal and Wu’s generic CPA-to-CCA transformation from deterministic functions to randomized functions, they use a simulation-sound extractable NIZK to implement CPA-to-CCA transformation and a Φ-RKA-secure PRF and a one-way permutation to implement deterministic-to-randomized function transformation. Concretely, in the decryption query, e.g., g,ct, where g is a function, the simulator deals with the decryption by first employing the NIZK to extract a message m from the ciphertext ct and then evaluating function g on m. Thus, the simulator can perfectly realize the decryption functionalities under the extractability of the NIZK. For the deterministic-to-randomized function transformation, the core idea is to use a PRF to remove randomization on the function. Specifically, the scheme transforms the encryption of m to that of the pair m,hk′ with randomness hck′ under the SIM-CPA FE scheme where h is a one-way permutation and hc is a hardcore function of h. In the construction of the private key for a randomized function f, the scheme first constructs a “derandomize” function gkfm,hk′=fm,PRFk⋄hk′,m and then computes a SIM-CPA FE private key sk for function gkf. The decryption algorithm uses sk to recover fm,PRFk⋄hk′,m from a ciphertext ct which encrypts the message m,hk′. For our goals of deterministic functions, we remove the PRF and one-way permutation h used for implementing the deterministic-to-randomization function transformation and directly define the final private key as that of the SIM-CPA PK-FE for deterministic functions. Luckily, the removal operation does not affect the CPA-to-CCA transformation since the PRF and h does not participate in the transformation. In this way, we get a SIM-CCA-secure PK-FE scheme for deterministic functions.In the construction of adaptive IND-CCA SK-FE, a similar methodology proposed by Elkind and Sahai in [18] is adopted. In their construction, the encryption scheme is designed by first constructing a “bare” oblivious-decryptor scheme (ODS) and then employing a designated-verifier NIZK to achieve adaptive CCA security. More specifically, their scheme first encrypted message m under the ODS encryption into a ciphertext c and then employed a designated-verifier NIZK to prove π of pk,c∈L.Compared with their scheme, our work on IND-CCA security for SK-FE uses some seemingly different techniques. In our scheme, beyond a standard simulation-sound NIZK and a PK-FE scheme secure against SIM-CCA, we also use a semantically secure symmetric encryption (SE). The symmetric encryption is used to mask the message directly. Particularly, in order to enable decrypting, the SE ciphertext together with the symmetric key are reencrypted in a PK-FE ciphertext. A simulation-sound NIZK proof functions as a “well-formedness” condition on the symmetric ciphertext and is contained in the overall ciphertext. The underlying PK-FE scheme corresponds to the oblivious-decryptor scheme by Elkind and Sahai [18], whose SIM-CCA security together with the standard NIZK proof is used for rejecting ill-formed ciphertexts.Note that simulation security is strong; in particular, it implies that we have to restrict ourselves to either secure against bounded collusion, which may hinder the practicability of the scheme, or to simple functionality (for example, IBE), for which the scheme cannot be simulation secure against bounded collusion. Although a weak notion, for example, an IND-CPA-secure SK-FE which may induce a more practical scheme or simple functionality, it is not applicable to our construction. This is because, when we directly use the weak scheme, during the decryption query phase, the master secret key encrypted in the underlying SK-FE ciphertext can be extracted out by the NIZK.


## 2. Preliminaries

### 2.1. Noninteractive Zero Knowledge (NIZK)

Here, we first explain several notions.ℛ:ℒ×W⟶0,1 a PPT binary relation which takes as input a statement x∈ℒ and the corresponding witness w∈W and outputs a bit indicating whether x belongs to the language ℒ.Definition 1.
A NIZK system with respect to a relationℛ consists of three PPT algorithms ZK=ZK.Setup,ZK.Prov,ZK.Ver.Setup:crs⟵ZK.Setup1λ), where crs denotes the common random string, which is public and can be accessed by anyone.Prove:π⟵ZK.Provcrs,x,w, where π denotes the proof which proves that it owns the secret witness w of the statement x.Verification:b⟵ZK.Vercrs,x,π, where b=1 denotes the verifier “accept” and b=1 denotes “reject”.Perfect completeness: an argument systemZK is perfectly complete if for all PPT adversaries A, the following holds:(1)Prcrs⟵ZK.Setup1λ,x,w⟵Acrs,:ZK.Vercrs,x,π=1π⟵ZK.Provcrs,x,wx,w∈ℛ=1=1.Computational soundness: the computational soundness of the schemeZK is demonstrated as follows, where A is a PPT algorithm:(2)Prcrs⟵ZK.Setup1λ,x,π⟵Acrs:ZK.Vercrs,x,π=1,ifx∉ℒ=neglλ.Definition 2.
(zero knowledge). A systemZK=ZK.Setup,ZK.Prov,ZK.Ver is said to be computational zero-knowledge if ∃ is a PPT simulator S=S1,S2 s.t. for all PPT A, the following holds:(3)Prcrs⟵ZK.Setup1λ:AOcrs,⋅,⋅crs=1−Prcrs,τ⟵S11λ:AO′crs,τ,⋅,⋅crs=1=neglλ,where the oracles Ocrs,⋅,⋅ and O′crs,τ,⋅,⋅ are demonstrated as follows:(i)
The oracleOcrs,⋅,⋅ takes as input a pair x,w and outputs ZK.Provcrs,x,w if x,w∈ℛ; o.w. outputs ⊥.(ii)
The oracleO′crs,τ,⋅,⋅ is the simulator algorithm, which takes as input x,w and outputs S2crs,τ,x if x,w∈ℛ; o.w. outputs ⊥.Definition 3.
(simulation-sound extractability). LetZK=ZK.Setup,ZK.Prov,ZK.Ver be a NIZK with respect to a relation ℛ and S=S1,S2 be a PPT simulator. Then, ZK satisfies the notion of simulation-sound extractability if ∃ is an extraction algorithm ξ=ξ1,ξ2 s.t.(4)Prcrs,τ,ς⟵ξ11λ,x,π∉Qx,π⟵AS2crs,τ,⋅crs,:x,w∉ℛw⟵ξ2crs,ς,x,πZK.Vercrs,x,π=1=neglλ,where Q is the set that contains all queries A makes to S2 and the answers from S2.


### 2.2. Symmetric Encryption and Semantic Security

LetSE=SE.KG,SE.Enc,SE.Dec be a symmetric encryption (SE), KSE be the secret key space, and ℳSE be the message space. These PPT algorithms work as follows: (1) the key-generation algorithm works as sek⟵SE.KG1λ; (2) the encryption algorithm works as cSE⟵SE.Encsek,m; and (3) the decryption algorithm works as m∪⊥⟵SE.Decsek,cSE.Correctness of the scheme is obvious.Definition 4.
(semantic security). AnSE is called semantic security (SS), if for all PPT A in the game SSASE,bλ (see Figure 1) played by A, the function AdvSE,ASS is negligible in λ (security parameter), where AdvSE,ASSλ=PrSSASE,0λ=1−PrSSASE,1λ=1≤neglλ.Figure 1
Semantic security for symmetric encryption.


## 2.1. Noninteractive Zero Knowledge (NIZK)

Here, we first explain several notions.ℛ:ℒ×W⟶0,1 a PPT binary relation which takes as input a statement x∈ℒ and the corresponding witness w∈W and outputs a bit indicating whether x belongs to the language ℒ.Definition 1.
A NIZK system with respect to a relationℛ consists of three PPT algorithms ZK=ZK.Setup,ZK.Prov,ZK.Ver.Setup:crs⟵ZK.Setup1λ), where crs denotes the common random string, which is public and can be accessed by anyone.Prove:π⟵ZK.Provcrs,x,w, where π denotes the proof which proves that it owns the secret witness w of the statement x.Verification:b⟵ZK.Vercrs,x,π, where b=1 denotes the verifier “accept” and b=1 denotes “reject”.Perfect completeness: an argument systemZK is perfectly complete if for all PPT adversaries A, the following holds:(1)Prcrs⟵ZK.Setup1λ,x,w⟵Acrs,:ZK.Vercrs,x,π=1π⟵ZK.Provcrs,x,wx,w∈ℛ=1=1.Computational soundness: the computational soundness of the schemeZK is demonstrated as follows, where A is a PPT algorithm:(2)Prcrs⟵ZK.Setup1λ,x,π⟵Acrs:ZK.Vercrs,x,π=1,ifx∉ℒ=neglλ.Definition 2.
(zero knowledge). A systemZK=ZK.Setup,ZK.Prov,ZK.Ver is said to be computational zero-knowledge if ∃ is a PPT simulator S=S1,S2 s.t. for all PPT A, the following holds:(3)Prcrs⟵ZK.Setup1λ:AOcrs,⋅,⋅crs=1−Prcrs,τ⟵S11λ:AO′crs,τ,⋅,⋅crs=1=neglλ,where the oracles Ocrs,⋅,⋅ and O′crs,τ,⋅,⋅ are demonstrated as follows:(i)
The oracleOcrs,⋅,⋅ takes as input a pair x,w and outputs ZK.Provcrs,x,w if x,w∈ℛ; o.w. outputs ⊥.(ii)
The oracleO′crs,τ,⋅,⋅ is the simulator algorithm, which takes as input x,w and outputs S2crs,τ,x if x,w∈ℛ; o.w. outputs ⊥.Definition 3.
(simulation-sound extractability). LetZK=ZK.Setup,ZK.Prov,ZK.Ver be a NIZK with respect to a relation ℛ and S=S1,S2 be a PPT simulator. Then, ZK satisfies the notion of simulation-sound extractability if ∃ is an extraction algorithm ξ=ξ1,ξ2 s.t.(4)Prcrs,τ,ς⟵ξ11λ,x,π∉Qx,π⟵AS2crs,τ,⋅crs,:x,w∉ℛw⟵ξ2crs,ς,x,πZK.Vercrs,x,π=1=neglλ,where Q is the set that contains all queries A makes to S2 and the answers from S2.


## 2.2. Symmetric Encryption and Semantic Security

LetSE=SE.KG,SE.Enc,SE.Dec be a symmetric encryption (SE), KSE be the secret key space, and ℳSE be the message space. These PPT algorithms work as follows: (1) the key-generation algorithm works as sek⟵SE.KG1λ; (2) the encryption algorithm works as cSE⟵SE.Encsek,m; and (3) the decryption algorithm works as m∪⊥⟵SE.Decsek,cSE.Correctness of the scheme is obvious.Definition 4.
(semantic security). AnSE is called semantic security (SS), if for all PPT A in the game SSASE,bλ (see Figure 1) played by A, the function AdvSE,ASS is negligible in λ (security parameter), where AdvSE,ASSλ=PrSSASE,0λ=1−PrSSASE,1λ=1≤neglλ.Figure 1
Semantic security for symmetric encryption.


## 3. PK-FE [8]

Letℳ=ℳλλ∈ℕ, Y=Yλλ∈ℕ, and ℱ=ℱλλ∈ℕ, where each f∈ℱλ takes as input a string m∈ℳλ and outputs fm∈Yλ.


### 3.1. Definition of PK-FE

A PK-FE schemeFE=FE.Setup, FE.KG, FE.Enc, FE.Dec consists of the following four PPT algorithms:Setup: the setup algorithm works asmpk,msk⟵FE.Setup1λ, where mpk denotes the master public key and msk denotes the master secret key.Private key generation: this algorithm works asskf⟵FE.KGmsk,f, where f∈ℱλ denotes a deterministic function.Encryption: the encryption algorithm works asct⟵FE.Encmpk,m, where m∈ℳλ denotes a plaintext and ct denotes the generated ciphertext.Decryption: the decryption algorithm works asfm∪⊥⟵FE.Decskf,ct.Perfect correctness: for all sufficient largeλ∈ℕ, mpk,msk⟵FE.Setup1λ, f∈ℱλ, and m∈ℳλ, the correct implies that(5)PrFE.DecFE.KGmsk,f,FE.Encmpk,m=fm=1.


### 3.2. Simulation-Based Chosen-Ciphertext Security

For security, we give the definitions of simulation-based chosen-ciphertext (SIM-CCA) security and indistinguishability-based chosen-ciphertext (IND-CCA) security, respectively. We first give the definition of SIM-CCA security, whereSIM-CCAA,ℱFEλ (see Figure 2) denotes the SIM-CCA game played by a PPT adversary A=A1,A2.Figure 2
SIM−CCA securitygameforPK−FE.Then, we define the advantage of the adversaryA in game SIM-CCAA,ℱFEλ as AdvFE,ℱ,ASIM-CCAλ=PrREALA,ℱFEλ=1−PrIDEALA,ℱFEλ=1.


#### 3.2.1. Oracles

(i)
Real Game. In this game, both oracles O1msk,⋅ and O2msk,⋅ invoke the algorithm FE.KGmsk,⋅ when A makes key queries to O1msk,⋅ and copyright has been updated in VTW, please repush task to validation. Oracle O3msk,⋅,⋅ acts as the decryption oracle, i.e., when A makes a decryption query g,C, the oracle O3msk,⋅,⋅ first invokes FE.KGmsk,g to obtain skg and then computes yi=FE.Decskg,cti for all cti∈C, where C=ctiqd and outputs the ordered set yi. In this game, an ordered set g is used to denote the functions that the adversary A2 made queries to O3msk,⋅,⋅ and y used to denote the answers of the oracle O3.(ii)
Ideal Game. In the ideal game, oracles O1′st′,⋅ and O2′st′,⋅ denote the simulator algorithms S2st′,⋅ and S4st′,⋅. Simulator S2st′,⋅ takes a key query f′ as input and outputs a key skf′ for function f′. For simulator S4st′,⋅, besides given f′ as input, it is also allowed to access an oracle KIdealm,⋅, which inputs a function f′ and returns yi′=f′mi for all i∈qc. The (ordered) set f′ denotes the functions that the adversary had made key queries to oracles O1′st′,⋅ and O2′st′,⋅. Taking g′,C′ as input, oracle O3′msk,⋅,⋅ invokes the simulator S5st′,ctk′ to obtain mk′ or ⊥ for each ctk′∈C′. Next, for each k∈qd, if mk′=⊥, then set yk′=⊥; otherwise, compute yk′=g′mk′. Finally, it outputs the ordered set yk′. For convenience, we abbreviate yk′ as y′.Here, we give a further restriction on decryption queries. First, we give an equivalence relation notation∼ functioning on ciphertext space C. We say that any two ciphertexts satisfyct1∼ct2, if for all λ∈ℕ, mpk,msk⟵FE.Setup1λ and skf⟵FE.KGmsk,f so that one of the following conditions holds:(i)
FE.Decskf,ct1=⊥ or FE.Decskf,ct2=⊥.(ii)
FE.Decskf,ct1=FE.Decskf,ct2.Next, we give the restriction on decryption queries, namely, for each decryption queryg,C, whether in ideal game or real game, we require that, for all i,j∈qd and i≠j, then cti≁ctj, and for all i∈qd, j∈qc, and the challenge ciphertext ctj∗, it must hold cti≠ctj∗.Definition 5.
(SIM-CCA). We say that a PK-FE scheme for deterministic functions isq1,qc,q2-simulation-based chosen-ciphertext secure (q1,qc,q2-SIM-CCA secure) if for any efficient adversary A=A1,A2 where A1 and A2 make at most q1 and q2 key-generation queries, respectively, there exists an ∼over ciphertext space (∼) and a PPT simulator S=S1,S2,S3,S4,S5 s.t. the advantage AdvFE,ℱ,ASIM-CCAλ is negligible.
One thing in particular to note is that, in the SIM-CCA security game, if we disallow the adversaryA to query decryption oracles O3 and O3′, then the game becomes SIM-CPA game.


### 3.3. Indistinguishable-Based Chosen-Ciphertext Security

For the IND-CCA security,IND-CCAA,ℱFE,bλ (see Figure 3) denotes the IND-CCA game played by a PPT adversary A=A1,A2. We define the advantage function IND-CCAA,ℱFE,bλ as AdvFE,ℱ,AIND-CCAλ=PrIND-CCAA,ℱFE,0λ=1−PrIND-CCAA,ℱFE,1λ=1.Figure 3
IND−CCA security for PK−FE.In the above game, we require that if the ordered setf denotes all key queries and m0,m1 denotes all challenge message pairs delivered by the adversary A, then the distributions mpk,st,fm0 and mpk,st,fm1 are identical. Now, we give the definitions of oracles below.


#### 3.3.1. Oracles

(i)
KeyGenmsk,⋅ denotes a key-generation oracle which, on inputting a function f, invokes the key-generation algorithm FE.KGmsk,f to obtain a key skf for function f.(ii)
Omsk,⋅,⋅ denotes a decryption oracle which, on taking as input a tuple g,ct such that ct≠ct∗, first invokes the key-generation algorithm FE.KGmsk,g to obtain a key skg and then computes y=FE.Decskg,ct and outputs y.Note that the above definition isadaptively secure, and it is easily modified to the nonadaptive security by requiring the adversary to specify two challenge messages before obtaining the master public key and function keys. In this paper, we only pay attention to the adaptive security.Definition 6.
(IND-CCA for PK-FE). We say that a PK-FE scheme for deterministic functions is adaptivelyq1,1,q2 indistinguishable chosen-ciphertext secure (q1,1,q2-IND-CCA secure) if for any PPT adversary A=A1,A2 where A1 and A2 make at most q1 and q2 key-generation queries, respectively, and we have that the function value AdvFE,ℱ,AIND-CCAλ is negligible.
In particular, as remarked in [19], the above definition can be trivially extended to multiple challenge message security, i.e., adaptive q1,qc,q2-IND-CCA security where q1, qc, and q2 are polynomials in λ. Particularly, we stress that the SIM-CCA security described in Section 3.2 implies IND-CCA security.Lemma 1.
Assume that a PK-FE schemeFE is adaptively SIM-CCA secure, then FE is also adaptively IND-CCA secure.The proof is described in AppendixA.


## 3.1. Definition of PK-FE

A PK-FE schemeFE=FE.Setup, FE.KG, FE.Enc, FE.Dec consists of the following four PPT algorithms:Setup: the setup algorithm works asmpk,msk⟵FE.Setup1λ, where mpk denotes the master public key and msk denotes the master secret key.Private key generation: this algorithm works asskf⟵FE.KGmsk,f, where f∈ℱλ denotes a deterministic function.Encryption: the encryption algorithm works asct⟵FE.Encmpk,m, where m∈ℳλ denotes a plaintext and ct denotes the generated ciphertext.Decryption: the decryption algorithm works asfm∪⊥⟵FE.Decskf,ct.Perfect correctness: for all sufficient largeλ∈ℕ, mpk,msk⟵FE.Setup1λ, f∈ℱλ, and m∈ℳλ, the correct implies that(5)PrFE.DecFE.KGmsk,f,FE.Encmpk,m=fm=1.


## 3.2. Simulation-Based Chosen-Ciphertext Security

For security, we give the definitions of simulation-based chosen-ciphertext (SIM-CCA) security and indistinguishability-based chosen-ciphertext (IND-CCA) security, respectively. We first give the definition of SIM-CCA security, whereSIM-CCAA,ℱFEλ (see Figure 2) denotes the SIM-CCA game played by a PPT adversary A=A1,A2.Figure 2
SIM−CCA securitygameforPK−FE.Then, we define the advantage of the adversaryA in game SIM-CCAA,ℱFEλ as AdvFE,ℱ,ASIM-CCAλ=PrREALA,ℱFEλ=1−PrIDEALA,ℱFEλ=1.


### 3.2.1. Oracles

(i)
Real Game. In this game, both oracles O1msk,⋅ and O2msk,⋅ invoke the algorithm FE.KGmsk,⋅ when A makes key queries to O1msk,⋅ and copyright has been updated in VTW, please repush task to validation. Oracle O3msk,⋅,⋅ acts as the decryption oracle, i.e., when A makes a decryption query g,C, the oracle O3msk,⋅,⋅ first invokes FE.KGmsk,g to obtain skg and then computes yi=FE.Decskg,cti for all cti∈C, where C=ctiqd and outputs the ordered set yi. In this game, an ordered set g is used to denote the functions that the adversary A2 made queries to O3msk,⋅,⋅ and y used to denote the answers of the oracle O3.(ii)
Ideal Game. In the ideal game, oracles O1′st′,⋅ and O2′st′,⋅ denote the simulator algorithms S2st′,⋅ and S4st′,⋅. Simulator S2st′,⋅ takes a key query f′ as input and outputs a key skf′ for function f′. For simulator S4st′,⋅, besides given f′ as input, it is also allowed to access an oracle KIdealm,⋅, which inputs a function f′ and returns yi′=f′mi for all i∈qc. The (ordered) set f′ denotes the functions that the adversary had made key queries to oracles O1′st′,⋅ and O2′st′,⋅. Taking g′,C′ as input, oracle O3′msk,⋅,⋅ invokes the simulator S5st′,ctk′ to obtain mk′ or ⊥ for each ctk′∈C′. Next, for each k∈qd, if mk′=⊥, then set yk′=⊥; otherwise, compute yk′=g′mk′. Finally, it outputs the ordered set yk′. For convenience, we abbreviate yk′ as y′.Here, we give a further restriction on decryption queries. First, we give an equivalence relation notation∼ functioning on ciphertext space C. We say that any two ciphertexts satisfyct1∼ct2, if for all λ∈ℕ, mpk,msk⟵FE.Setup1λ and skf⟵FE.KGmsk,f so that one of the following conditions holds:(i)
FE.Decskf,ct1=⊥ or FE.Decskf,ct2=⊥.(ii)
FE.Decskf,ct1=FE.Decskf,ct2.Next, we give the restriction on decryption queries, namely, for each decryption queryg,C, whether in ideal game or real game, we require that, for all i,j∈qd and i≠j, then cti≁ctj, and for all i∈qd, j∈qc, and the challenge ciphertext ctj∗, it must hold cti≠ctj∗.Definition 5.
(SIM-CCA). We say that a PK-FE scheme for deterministic functions isq1,qc,q2-simulation-based chosen-ciphertext secure (q1,qc,q2-SIM-CCA secure) if for any efficient adversary A=A1,A2 where A1 and A2 make at most q1 and q2 key-generation queries, respectively, there exists an ∼over ciphertext space (∼) and a PPT simulator S=S1,S2,S3,S4,S5 s.t. the advantage AdvFE,ℱ,ASIM-CCAλ is negligible.
One thing in particular to note is that, in the SIM-CCA security game, if we disallow the adversaryA to query decryption oracles O3 and O3′, then the game becomes SIM-CPA game.


## 3.2.1. Oracles

(i)
Real Game. In this game, both oracles O1msk,⋅ and O2msk,⋅ invoke the algorithm FE.KGmsk,⋅ when A makes key queries to O1msk,⋅ and copyright has been updated in VTW, please repush task to validation. Oracle O3msk,⋅,⋅ acts as the decryption oracle, i.e., when A makes a decryption query g,C, the oracle O3msk,⋅,⋅ first invokes FE.KGmsk,g to obtain skg and then computes yi=FE.Decskg,cti for all cti∈C, where C=ctiqd and outputs the ordered set yi. In this game, an ordered set g is used to denote the functions that the adversary A2 made queries to O3msk,⋅,⋅ and y used to denote the answers of the oracle O3.(ii)
Ideal Game. In the ideal game, oracles O1′st′,⋅ and O2′st′,⋅ denote the simulator algorithms S2st′,⋅ and S4st′,⋅. Simulator S2st′,⋅ takes a key query f′ as input and outputs a key skf′ for function f′. For simulator S4st′,⋅, besides given f′ as input, it is also allowed to access an oracle KIdealm,⋅, which inputs a function f′ and returns yi′=f′mi for all i∈qc. The (ordered) set f′ denotes the functions that the adversary had made key queries to oracles O1′st′,⋅ and O2′st′,⋅. Taking g′,C′ as input, oracle O3′msk,⋅,⋅ invokes the simulator S5st′,ctk′ to obtain mk′ or ⊥ for each ctk′∈C′. Next, for each k∈qd, if mk′=⊥, then set yk′=⊥; otherwise, compute yk′=g′mk′. Finally, it outputs the ordered set yk′. For convenience, we abbreviate yk′ as y′.Here, we give a further restriction on decryption queries. First, we give an equivalence relation notation∼ functioning on ciphertext space C. We say that any two ciphertexts satisfyct1∼ct2, if for all λ∈ℕ, mpk,msk⟵FE.Setup1λ and skf⟵FE.KGmsk,f so that one of the following conditions holds:(i)
FE.Decskf,ct1=⊥ or FE.Decskf,ct2=⊥.(ii)
FE.Decskf,ct1=FE.Decskf,ct2.Next, we give the restriction on decryption queries, namely, for each decryption queryg,C, whether in ideal game or real game, we require that, for all i,j∈qd and i≠j, then cti≁ctj, and for all i∈qd, j∈qc, and the challenge ciphertext ctj∗, it must hold cti≠ctj∗.Definition 5.
(SIM-CCA). We say that a PK-FE scheme for deterministic functions isq1,qc,q2-simulation-based chosen-ciphertext secure (q1,qc,q2-SIM-CCA secure) if for any efficient adversary A=A1,A2 where A1 and A2 make at most q1 and q2 key-generation queries, respectively, there exists an ∼over ciphertext space (∼) and a PPT simulator S=S1,S2,S3,S4,S5 s.t. the advantage AdvFE,ℱ,ASIM-CCAλ is negligible.
One thing in particular to note is that, in the SIM-CCA security game, if we disallow the adversaryA to query decryption oracles O3 and O3′, then the game becomes SIM-CPA game.


## 3.3. Indistinguishable-Based Chosen-Ciphertext Security

For the IND-CCA security,IND-CCAA,ℱFE,bλ (see Figure 3) denotes the IND-CCA game played by a PPT adversary A=A1,A2. We define the advantage function IND-CCAA,ℱFE,bλ as AdvFE,ℱ,AIND-CCAλ=PrIND-CCAA,ℱFE,0λ=1−PrIND-CCAA,ℱFE,1λ=1.Figure 3
IND−CCA security for PK−FE.In the above game, we require that if the ordered setf denotes all key queries and m0,m1 denotes all challenge message pairs delivered by the adversary A, then the distributions mpk,st,fm0 and mpk,st,fm1 are identical. Now, we give the definitions of oracles below.


### 3.3.1. Oracles

(i)
KeyGenmsk,⋅ denotes a key-generation oracle which, on inputting a function f, invokes the key-generation algorithm FE.KGmsk,f to obtain a key skf for function f.(ii)
Omsk,⋅,⋅ denotes a decryption oracle which, on taking as input a tuple g,ct such that ct≠ct∗, first invokes the key-generation algorithm FE.KGmsk,g to obtain a key skg and then computes y=FE.Decskg,ct and outputs y.Note that the above definition isadaptively secure, and it is easily modified to the nonadaptive security by requiring the adversary to specify two challenge messages before obtaining the master public key and function keys. In this paper, we only pay attention to the adaptive security.Definition 6.
(IND-CCA for PK-FE). We say that a PK-FE scheme for deterministic functions is adaptivelyq1,1,q2 indistinguishable chosen-ciphertext secure (q1,1,q2-IND-CCA secure) if for any PPT adversary A=A1,A2 where A1 and A2 make at most q1 and q2 key-generation queries, respectively, and we have that the function value AdvFE,ℱ,AIND-CCAλ is negligible.
In particular, as remarked in [19], the above definition can be trivially extended to multiple challenge message security, i.e., adaptive q1,qc,q2-IND-CCA security where q1, qc, and q2 are polynomials in λ. Particularly, we stress that the SIM-CCA security described in Section 3.2 implies IND-CCA security.Lemma 1.
Assume that a PK-FE schemeFE is adaptively SIM-CCA secure, then FE is also adaptively IND-CCA secure.The proof is described in AppendixA.


## 3.3.1. Oracles

(i)
KeyGenmsk,⋅ denotes a key-generation oracle which, on inputting a function f, invokes the key-generation algorithm FE.KGmsk,f to obtain a key skf for function f.(ii)
Omsk,⋅,⋅ denotes a decryption oracle which, on taking as input a tuple g,ct such that ct≠ct∗, first invokes the key-generation algorithm FE.KGmsk,g to obtain a key skg and then computes y=FE.Decskg,ct and outputs y.Note that the above definition isadaptively secure, and it is easily modified to the nonadaptive security by requiring the adversary to specify two challenge messages before obtaining the master public key and function keys. In this paper, we only pay attention to the adaptive security.Definition 6.
(IND-CCA for PK-FE). We say that a PK-FE scheme for deterministic functions is adaptivelyq1,1,q2 indistinguishable chosen-ciphertext secure (q1,1,q2-IND-CCA secure) if for any PPT adversary A=A1,A2 where A1 and A2 make at most q1 and q2 key-generation queries, respectively, and we have that the function value AdvFE,ℱ,AIND-CCAλ is negligible.
In particular, as remarked in [19], the above definition can be trivially extended to multiple challenge message security, i.e., adaptive q1,qc,q2-IND-CCA security where q1, qc, and q2 are polynomials in λ. Particularly, we stress that the SIM-CCA security described in Section 3.2 implies IND-CCA security.Lemma 1.
Assume that a PK-FE schemeFE is adaptively SIM-CCA secure, then FE is also adaptively IND-CCA secure.The proof is described in AppendixA.


## 4. Private-Key Functional Encryption

Here, we give the definition of SK-FE for deterministic functions. LetSFE = SFE.Setup, SFE.KG, SFE.Enc, and SFE.Dec be an SK-FE scheme defined over function space ℱ=ℱλλ∈ℕ and message space ℳ=ℳλλ∈ℕ, respectively. The detailed definition is given as follows:Setup: the setup algorithm computesppr,msk⟵SFE.Setup1λ, where ppr denotes the system public parameter ppr, msk denotes the system master secret key, and the public parameter ppr is implied in the following algorithms:Key generation: the key-generation algorithm computesskf⟵SFE.KGmsk,f, where skf denotes the generated private key.Encryption: the encryption algorithm computesct⟵SFE.Encmsk,m, where m∈ℳλ denotes the being encrypted message and ct denotes the generated ciphertext.Decryption: the decryption algorithm computesfm∪⊥⟵SFE.Decskf,ct, where fm∪⊥ denotes the final decrypted result.Here, we give the perfect correctness of scheme SK-FE, which says that, for all sufficient largeλ∈ℕ, ppr,msk⟵SFE.Setup1λ, f∈ℱλ, and m∈ℳλ, it holds that PrSFE.DecSFE.KGmsk,f,SFE.Encmsk,m=fm=1.


### 4.1. Indistinguishable-Based Chosen-Ciphertext

Here, we review the IND-CCA of the SK-FE from [8]. In Figure 4, IND-CCAA,ℱSFE,bλ denotes the IND-CCA game played by a PPT adversary A. The advantage function is defined as AdvSFE,ℱ,AIND-CCAλ=PrIND-CCAA,ℱSFE,0λ=1−PrIND-CCAA,ℱSFE,1λ=1.Figure 4
IND−CCA of secret−key functional encryption.In the above game, we require that all challenge messages that the adversary delivers in the encryption queries to oracleENC satisfy fm0=fm1 for all the functions f∈ℱ that the adversary makes queries to the key-generation oracle KeyGen, where m0 and m1 denote the challenge message that the adversary delivers in the challenge phase. In the following, we define the functionalities of the oracles.


#### 4.1.1. Oracles

(i)
KeyGenmsk,⋅ denotes the key-generation oracle which means that when the adversary makes a function query f, the oracle invokes the algorithm SFE.KGmsk,f to get a private key skf.(ii)
ENCmsk,⋅,⋅ denotes an encryption oracle. On taking as input two messages m0,m1, it invokes SFE.Encmsk,mb to obtain ct∗ for a random bit b⟵$0,1. We denote all challenge ciphertexts as ct∗.(iii)
Omsk,⋅,⋅ denotes a decryption oracle which, on taking as input a tuple g,ct such that ct∉ct∗, invokes the algorithm SFE.KGmsk,g to obtain a private key skg and outputs y=SFE.Decskg,ct.Note that the above definition isadaptively secure and is easily modified to the nonadaptively security by requiring the adversary to make encryption queries before key queries.Definition 7.
(IND-CCA for SK-FE). We say that an SK-FE scheme for deterministic functions is adaptively indistinguishability-based chosen-ciphertext secure (adaptively IND-CCA secure) if for all PPTA, the advantage AdvSFE,ℱ,AIND-CCAλ is negligible in λ.


## 4.1. Indistinguishable-Based Chosen-Ciphertext

Here, we review the IND-CCA of the SK-FE from [8]. In Figure 4, IND-CCAA,ℱSFE,bλ denotes the IND-CCA game played by a PPT adversary A. The advantage function is defined as AdvSFE,ℱ,AIND-CCAλ=PrIND-CCAA,ℱSFE,0λ=1−PrIND-CCAA,ℱSFE,1λ=1.Figure 4
IND−CCA of secret−key functional encryption.In the above game, we require that all challenge messages that the adversary delivers in the encryption queries to oracleENC satisfy fm0=fm1 for all the functions f∈ℱ that the adversary makes queries to the key-generation oracle KeyGen, where m0 and m1 denote the challenge message that the adversary delivers in the challenge phase. In the following, we define the functionalities of the oracles.


### 4.1.1. Oracles

(i)
KeyGenmsk,⋅ denotes the key-generation oracle which means that when the adversary makes a function query f, the oracle invokes the algorithm SFE.KGmsk,f to get a private key skf.(ii)
ENCmsk,⋅,⋅ denotes an encryption oracle. On taking as input two messages m0,m1, it invokes SFE.Encmsk,mb to obtain ct∗ for a random bit b⟵$0,1. We denote all challenge ciphertexts as ct∗.(iii)
Omsk,⋅,⋅ denotes a decryption oracle which, on taking as input a tuple g,ct such that ct∉ct∗, invokes the algorithm SFE.KGmsk,g to obtain a private key skg and outputs y=SFE.Decskg,ct.Note that the above definition isadaptively secure and is easily modified to the nonadaptively security by requiring the adversary to make encryption queries before key queries.Definition 7.
(IND-CCA for SK-FE). We say that an SK-FE scheme for deterministic functions is adaptively indistinguishability-based chosen-ciphertext secure (adaptively IND-CCA secure) if for all PPTA, the advantage AdvSFE,ℱ,AIND-CCAλ is negligible in λ.


## 4.1.1. Oracles

(i)
KeyGenmsk,⋅ denotes the key-generation oracle which means that when the adversary makes a function query f, the oracle invokes the algorithm SFE.KGmsk,f to get a private key skf.(ii)
ENCmsk,⋅,⋅ denotes an encryption oracle. On taking as input two messages m0,m1, it invokes SFE.Encmsk,mb to obtain ct∗ for a random bit b⟵$0,1. We denote all challenge ciphertexts as ct∗.(iii)
Omsk,⋅,⋅ denotes a decryption oracle which, on taking as input a tuple g,ct such that ct∉ct∗, invokes the algorithm SFE.KGmsk,g to obtain a private key skg and outputs y=SFE.Decskg,ct.Note that the above definition isadaptively secure and is easily modified to the nonadaptively security by requiring the adversary to make encryption queries before key queries.Definition 7.
(IND-CCA for SK-FE). We say that an SK-FE scheme for deterministic functions is adaptively indistinguishability-based chosen-ciphertext secure (adaptively IND-CCA secure) if for all PPTA, the advantage AdvSFE,ℱ,AIND-CCAλ is negligible in λ.


## 5. Construction of SIM-CCA-Secure PK-FE

In this section, we modify Agrawal and Wu’s generic transformation [17] to the setting of deterministic functions.The modified scheme needs the following building blocks:(i)
A NIZK argumentZK = (ZK.Setup, ZK.Prov, ZK.Ver) with simulation-sound extractability.(ii)
An (adaptively) SIM-CPA-secure PK-FE schemeCPAFE = (CPAFE.Setup, CPAFE.KG, CPAFE.Enc, CPAFE.Dec).A SIM-CCA-secure PK-FE schemeCCAFE =  (CCAFE.Setup, CCAFE.Enc, CCAFE.KG, CCAFE.Dec) is constructed as follows:(i)
The setup algorithm:mpk,msk⟵CCAFE.Setup1λ. This algorithm first runs mpk′,msk′⟵CPAFE.Setup1λ and crs⟵ZK.Setup1λ and then sets mpk=mpk′,crs and msk=msk′ and releases mpk in public.(ii)
The key-generation algorithm:skf⟵CCAFE.KGmpk,f. This algorithm first parses mpk=mpk′,crs and then runs skf′⟵CPAFE.KGmpk′,f and sets skf=skf′.(iii)
The encryption algorithm: on taking as inputmpk=mpk′,crs and a message m, this algorithm CCAFE.Encmpk,m first samples a randomness r⟵$ℛ and runs CPAFE.Encmpk′,m;r to get ct′ and then computes π⟵ZK.Provcrs,x,w, where x=ct′∈ℒ, the witness w=m,r, and x,w∈ℛ. The relation ℛ and language ℒ satisfy the following equation:(6)∃m,rsuch thatct′=CPAFE.Encmpk′,m;r.The final ciphertext is set asct=ct′,π.(iv)
The decryption algorithm: on taking as input a private keyskf=skf′ and a ciphertext ct=ct′,π, the decryption algorithm first verifies whether ZK.Vercrs,x,π=1, where x=ct′; if so, it computes y=CPAFE.Decskf′,ct′ and outputs y; otherwise, it outputs ⊥.It is easy to see that the correctness of the schemeCCAFE follows from the completeness of ZK and the correctness of CPAFE.Theorem 1.
IfZK is a simulation-sound extractable noninteractive zero-knowledge argument, CPAFE is perfectly correct q1,qc,q2-SIM-CPA-secure PK-FE scheme for deterministic function class ℱ, then CCAFE is q1,qc,q2-SIM-CCA-secure functional encryption scheme for the same function class.Like [17], our definition also requires that the equivalence relation ∼ over the ciphertext space C is satisfied, i.e., given any two ciphertexts ct1=ct1′,π1, ct2=ct2′,π2∈C, the equivalence relation ct1∼ct2 holds, if ct1′=ct2′.To prove Theorem1, we will construct an ideal-world simulator S=S1,S2,S3,S4,S5 for the scheme CCAFE. Let SCPAFE=S1CPAFE,S2CPAFE,S3CPAFE,S4CPAFE be the simulator for the scheme CPAFE and SZK=S1ZK,S2ZK and ξZK=ξ1ZK,ξ2ZK be the simulator and extractor for the scheme ZK, respectively.


### 5.1. SimulatorS11λ

The setup simulatorS1 proceeds as follows. On taking as input 1λ, it first runs mpk′,st0CPAFE⟵S1CPAFE and then invokes crs,τ,ς⟵ξ1ZK, where crs denotes a common random string, τ denotes a simulation trapdoor, and ς denotes an extraction trapdoor. It finally sets mpk=mpk′,crs and st0=st0CPAFE,mpk,τ,ς and outputs mpk,st0.


### 5.2. SimulatorS2st0,f

The prechallenge key-generation query simulatorS2 proceeds as follows. On taking as input st0=st0CPAFE,mpk,τ,ς and f∈ℱ, it runs skf′,st1CPAFE⟵S2CPAFEst0CPAFE,f. Then, it outputs the key skf=skf′ and a fresh state st1=st1CPAFE,mpk,τ,ς.


### 5.3. SimulatorS3st0,yi,ji∈qc,j∈q1

S3 simulates the challenge ciphertext query procedure. On taking as input a statement st0=st0CPAFE,mpk,τ,ς and a function value set yi,ji∈qc,j∈q1, S3 proceeds as follows. It first computes cti∗i∈qc,st1CPAFE⟵S3CPAFEst0CPAFE,yi,ji∈qc,j∈q1; then for each i∈qc, it computes argument πi∗=S2ZKcrs,τ,xi∗ with the statement xi∗=cti′∗ described as follows:(7)∃mi,ri∗such thatcti′∗=CPAFE.Encmpk′,mi;ri∗,where m=m1,…,mqc are the challenge messages that the adversary delivers. At the end of the simulation, it outputs a challenge ciphertext set cti∗i∈qc and an updated state st1=st1CPAFE,mpk,τ,ς, where cti∗=cti′∗,πi∗.


### 5.4. SimulatorS4st0,f

S4 simulates the postchallenge key-generation queries with the help of the oracle CCAFE.KIdealm,⋅. Once getting input st0=st0CPAFE,mpk,τ,ς and f∈ℱ, it first computes skf′,st1CPAFE⟵S4CPAFEst0CPAFE,f with the help of oracle CPAFE.KIdealm,⋅ and then outputs skf=skf′ and st1=st1CPAFE,mpk,τ,ς, where the oracle CPAFE.KIdealm,⋅ is defined as follows: for any input function g′, it returns g′mi for all mi∈m.


### 5.5. SimulatorS5st0,ct

The decryption query simulatorS5 takes as input st0=st0CPAFE,mpk,τ,ς and ct, and it parses mpk=mpk′,crs and ct=ct′,π. Define the statement x=ct′ as(8)∃m,rsuch thatct′=CPAFE.Encmpk′,m;r.IfZK.Vercrs,x,π=0, it stops and outputs ⊥; otherwise, it computes m,r∈ℳ×ℛ⟵ξ2ZKcrs,ς,x,π. Finally, it outputs the massage m and state st.


### 5.6. Hybrid Games

For Theorem1, we prove it via 4 hybrid games where the first game G0 is the real-world game and the last game G3 is the simulator game. Each game contains the following phases:Setup: in this phase, the challenger generates the system public keympk′.Prechallenge queries: in this procedure,A is allowed to issue the key-generation queries f∈ℱ and decryption query f,ct∈ℱ×C such that for all decryption queries f,C and any cti, ctj∈C and i≠j, it holds that cti≁ctj.Challenge: when the adversaryA submits a vector of messages m∈ℳqc to the challenger, the challenger replies with cti∗i∈qc.Postchallenge queries: in this procedure, the adversaryA is again allowed to issue key-generation and decryption queries but with a further restriction that decryption query can be only allowed to contain queries f,C such that ctj≠cti∗, where ctj∈C for j∈qd and cti∗ is the challenge ciphertext for i∈qc.Output: finally, the adversaryA outputs a guess b′∈0,1 of the challenge bit b.Each of the hybrid games is described in detail as follows:HybridG0: this is the game in the real settings where the challenger interacts with the adversary.HybridG1: same as G0 except that the way that the common random string crs in the setup phase and the arguments in the challenge ciphertexts are generated. Specifically, in the setup phase, the challenger uses crs,τ⟵S1ZK1λ. In the challenge phase, the challenger uses the simulator S2ZK to generate the challenge argument in the challenge ciphertexts. Let m∗∈ℳqc be the challenge messages. It samples ri∗∈ℛ and computes cti′∗⟵CPAFE.Encmpk′,mi∗;ri∗ and πi∗⟵S2ZKcrs,τ,xi∗ for i∈qc, where the statement xi∗ is described as in equation (1). Finally, the challenger sets cti∗=cti′∗,πi∗ and mpk=mpk′,crs and sends mpk and cti∗ to the adversary A.HybridG2: same as G1 except that the challenger answers the decryption queries by extracting the message-randomness pair m,r from the noninteractive zero-knowledge argument ZK. Specifically, in the setup phase, the procedure is same as hybrid G1 except that the challenger computes crs,τ,ς⟵ξ1ZK1λ. In the prechallenge phase, the key-generation queries are dealt with as in G1, while the decryption queries are processed as follows: for query g,C, where C=ctii∈qd and cti=cti′,πi for i∈qd, and let xi be the statement as described in equation (2). If ZK.Vercrs,xi,πi=0, set yi=⊥; otherwise, it invokes the extractor ξ2ZKcrs,ς,xi,πi to obtain a witness mi,ri and sets yi=gmi. Finally, yii∈qd is sent to A.HybridG3: same as G2 but with the difference that the challenger uses the simulator SCPAFE=S1CPAFE,S2CPAFE,S3CPAFE,S4CPAFE to interact with the adversary. Specifically, in the setup phase, the challenger computes mpk′,stCPAFE⟵S1CPAFE1λ. In the prechallenge phase, the decryption queries are dealt with as in hybrid G2, while the key generation is handled as follows: for each query f∈ℱ, it runs S2CPAFEstCPAFE,f to obtain private key skf. In the challenge phase, let f1,…,fq1 be the function that the adversary A has made queries in the key-generation phase and m∈ℳqc be the challenge messages that the adversary queries. It computes yij=fjmi for all i∈qc and j∈q1 and invokes the simulator S3CPAFEstCPAFE,yi,ji∈qc,j∈q1 to obtain cti∗i∈qc. In the postchallenge queries, the decryption queries are processed as in hybrid G2, but the key-generation queries are processed differently as below: the challenger invokes S4CPAFEstCPAFE,f under the help of the oracle CPAFE.KIdealm,⋅ to obtain the private key skf.Claim 1.
IfZK is a computationally noninteractive zero-knowledge argument system, then hybrids G0 and G1 are computationally indistinguishable.Proof.
The hybrid gamesG0 and G1 are different in that, in G1, the challenger uses the NIZK simulator to compute the CRS and arguments. It is easy to see that the claim follows from the computational zero-knowledge of NIZK.
Concretely, letA=A1,A2 be an efficient adversary distinguishing hybrid games G0 and G1. A is used to construct an algorithm AZK that tries to distinguish the real and simulated distributions of the NIZK. AZK takes as input crs and is allowed to access to an argument oracle. In the setup, AZK computes mpk′,msk′⟵CPAFE.Setup1λ and sets mpk=mpk′,crs and msk=msk′. It then sends mpk to A. In the challenge phase, when A delivers challenge message m∈ℳλqc, the algorithm AZK samples ri∗⟵ℛ and computes cti′∗⟵CPAFE.Encmpk′,mi;ri∗ for each i∈qc. Let xi∗ be the statement in equation (2). AZK delivers xi∗,mi,ri∗ to its challenger and obtains an argument πi∗. Finally, A obtains cti∗=cti′∗,πi∗ and cti∗.
The rest steps are processed in the same way as inG0 and G1. Finally, AZK outputs whatever A outputs. Obviously, if the CRS and NIZK arguments are computed honestly, then AZK simulates the settings of G0; otherwise, it simulates the settings of G1. Thus, the lemma follows.Claim 2.
IfZK is simulation-sound extractable and CPAFE is perfectly correct, then hybrids G1 and G2 are computationally indistinguishable.Proof.
HybridsG1 and G2 are identical but only with the difference in the way the challenger responds to decryption queries. Conditioned on the simulation-sound extractability of ZK and perfect correctness of CPAFE, the two games are computationally indistinguishable. Let g,C be the decryption query pair that the adversary makes, where C=ctii∈qd and cti=cti′,πi.
The procedure can be classified into two cases. Ifπ can pass the verification, the challenger sets yi=⊥ in both G1 and G2. Otherwise, it is easy to see that the adversary cannot submit any challenge ciphertexts in the decryption queries. Thus, cti=cti′,πi was not generated by the challenger using SZK. Thus, by simulation-sound extractability, with probability at least 1−neglλ, the extraction algorithm ξ2ZK on xi and πi will produce a witness mi,ri to make cti′=CPAFE.Encmpk′,mi;ri hold. Furthermore, by perfect correctness of CPAFE, mi,ri is the only pair corresponding to cti′.
In addition, inG1, the challenger first computes skg⟵CPAFE.KGmsk′,g and then sets yi=CPAFE.Decskg,cti′. By the underlying PK-FE scheme CPAFE, yi=gmi, which is exactly the output in G2 after mi,ri is extracted. Therefore, with probability 1−neglλ, the distributions in both G1 and G2 are identical.Claim 3.
IfCPAFE is a q1,qc,q2-SIM-CPA-secure FE scheme for deterministic function family ℱ, then hybrids G2 and G3 are computationally indistinguishable.Proof.
SupposeA=A1,A2 is a distinguisher for hybrids G2 and G3. A is used to construct an algorithm ACPAFE=A1CPAFE,A2CPAFE that distinguishes REALA,ℱCPAFE and IDEALA,ℱCPAFE. Then, the detailed simulation procedure is processed as follows.


### 5.7. The Construction ofA1CPAFE

On taking as inputmpk′ which is generated by CPAFE.Setup1λ or S1CPAFE1λ, the setup and prechallenge queries are simulated as follows:Setup: in this phase, the adversary A1CPAFE first computes a simulated tuple crs,τ,ς⟵xi1ZK1λ. It then sets mpk=mpk′,crs and sends mpk to A.Prechallenge queries: in this phase, when A1 makes a function key query f, the adversary A1CPAFE queries its prechallenge key-generation oracle to obtain a key skf′ which is generated by skf′=CPAFE.KGmsk′,f or skf′=S2CPAFEst′,f, while the decryption queries are the same as in G2 and G3.


### 5.8. AdversaryA2CPAFE

On taking as inputmpk′ and a state st from A1CPAFE, the adversary A2CPAFE simulates the challenge phase and postchallenge queries as follows:Challenge: in this procedure, when the adversary A1 outputs a challenge message vector m, the adversary A2CPAFE queries its challenge oracle to obtain challenge ciphertext set cti′∗i∈qc for CPAFE. It then computes πi∗⟵S2ZKcrs,τ,xi∗ and sets cti∗=cti′∗,πi∗ for each i∈qc, where xi∗ is described as in equation (1). It finally sends cti∗i∈qc to A.Prechallenge queries: the simulation of this procedure is the same as prechallenge procedure, except that A2CPAFE queries his postchallenge key-generation oracle with the help of oracle CPAFE.KIdealm,⋅ to obtain a key skf′ which is generated by skf′=CPAFE.KGmsk′,f or skf′=S4CPAFEst′,f.At the end,ACPAFE outputs what A outputs. Obviously, if ACPAFE takes part in the game REALA,ℱCPAFE, then the view of A is computationally indistinguishable from G2; otherwise, if ACPAFE takes part in the ideal game IDEALA,ℱCPAFE, then the view of A is computationally indistinguishable from G3. Thus, the proof follows from the q1,qc,q2-SIM-CPA security of the scheme CPAFE.Remark 1.
Note that applying the above simulation-sound extractable NIZK to the secret-key settings for implementing the IND-CPA-to-IND-CCA security transformation is impossible. This is because beyond the encrypted message, the extractor of the NIZK also extracts out the master secret key used for a secret parameter in the encryption process. Once the extractor obtains the master secret key, it can use it to forge the private keys for any functions of its choice.
In the following, we will use the SIM-CCA-secure PK-FE proposed above and a NIZK scheme to put forward an IND-CCA-secure SK-FE.


## 5.1. SimulatorS11λ

The setup simulatorS1 proceeds as follows. On taking as input 1λ, it first runs mpk′,st0CPAFE⟵S1CPAFE and then invokes crs,τ,ς⟵ξ1ZK, where crs denotes a common random string, τ denotes a simulation trapdoor, and ς denotes an extraction trapdoor. It finally sets mpk=mpk′,crs and st0=st0CPAFE,mpk,τ,ς and outputs mpk,st0.


## 5.2. SimulatorS2st0,f

The prechallenge key-generation query simulatorS2 proceeds as follows. On taking as input st0=st0CPAFE,mpk,τ,ς and f∈ℱ, it runs skf′,st1CPAFE⟵S2CPAFEst0CPAFE,f. Then, it outputs the key skf=skf′ and a fresh state st1=st1CPAFE,mpk,τ,ς.


## 5.3. SimulatorS3st0,yi,ji∈qc,j∈q1

S3 simulates the challenge ciphertext query procedure. On taking as input a statement st0=st0CPAFE,mpk,τ,ς and a function value set yi,ji∈qc,j∈q1, S3 proceeds as follows. It first computes cti∗i∈qc,st1CPAFE⟵S3CPAFEst0CPAFE,yi,ji∈qc,j∈q1; then for each i∈qc, it computes argument πi∗=S2ZKcrs,τ,xi∗ with the statement xi∗=cti′∗ described as follows:(7)∃mi,ri∗such thatcti′∗=CPAFE.Encmpk′,mi;ri∗,where m=m1,…,mqc are the challenge messages that the adversary delivers. At the end of the simulation, it outputs a challenge ciphertext set cti∗i∈qc and an updated state st1=st1CPAFE,mpk,τ,ς, where cti∗=cti′∗,πi∗.


## 5.4. SimulatorS4st0,f

S4 simulates the postchallenge key-generation queries with the help of the oracle CCAFE.KIdealm,⋅. Once getting input st0=st0CPAFE,mpk,τ,ς and f∈ℱ, it first computes skf′,st1CPAFE⟵S4CPAFEst0CPAFE,f with the help of oracle CPAFE.KIdealm,⋅ and then outputs skf=skf′ and st1=st1CPAFE,mpk,τ,ς, where the oracle CPAFE.KIdealm,⋅ is defined as follows: for any input function g′, it returns g′mi for all mi∈m.


## 5.5. SimulatorS5st0,ct

The decryption query simulatorS5 takes as input st0=st0CPAFE,mpk,τ,ς and ct, and it parses mpk=mpk′,crs and ct=ct′,π. Define the statement x=ct′ as(8)∃m,rsuch thatct′=CPAFE.Encmpk′,m;r.IfZK.Vercrs,x,π=0, it stops and outputs ⊥; otherwise, it computes m,r∈ℳ×ℛ⟵ξ2ZKcrs,ς,x,π. Finally, it outputs the massage m and state st.


## 5.6. Hybrid Games

For Theorem1, we prove it via 4 hybrid games where the first game G0 is the real-world game and the last game G3 is the simulator game. Each game contains the following phases:Setup: in this phase, the challenger generates the system public keympk′.Prechallenge queries: in this procedure,A is allowed to issue the key-generation queries f∈ℱ and decryption query f,ct∈ℱ×C such that for all decryption queries f,C and any cti, ctj∈C and i≠j, it holds that cti≁ctj.Challenge: when the adversaryA submits a vector of messages m∈ℳqc to the challenger, the challenger replies with cti∗i∈qc.Postchallenge queries: in this procedure, the adversaryA is again allowed to issue key-generation and decryption queries but with a further restriction that decryption query can be only allowed to contain queries f,C such that ctj≠cti∗, where ctj∈C for j∈qd and cti∗ is the challenge ciphertext for i∈qc.Output: finally, the adversaryA outputs a guess b′∈0,1 of the challenge bit b.Each of the hybrid games is described in detail as follows:HybridG0: this is the game in the real settings where the challenger interacts with the adversary.HybridG1: same as G0 except that the way that the common random string crs in the setup phase and the arguments in the challenge ciphertexts are generated. Specifically, in the setup phase, the challenger uses crs,τ⟵S1ZK1λ. In the challenge phase, the challenger uses the simulator S2ZK to generate the challenge argument in the challenge ciphertexts. Let m∗∈ℳqc be the challenge messages. It samples ri∗∈ℛ and computes cti′∗⟵CPAFE.Encmpk′,mi∗;ri∗ and πi∗⟵S2ZKcrs,τ,xi∗ for i∈qc, where the statement xi∗ is described as in equation (1). Finally, the challenger sets cti∗=cti′∗,πi∗ and mpk=mpk′,crs and sends mpk and cti∗ to the adversary A.HybridG2: same as G1 except that the challenger answers the decryption queries by extracting the message-randomness pair m,r from the noninteractive zero-knowledge argument ZK. Specifically, in the setup phase, the procedure is same as hybrid G1 except that the challenger computes crs,τ,ς⟵ξ1ZK1λ. In the prechallenge phase, the key-generation queries are dealt with as in G1, while the decryption queries are processed as follows: for query g,C, where C=ctii∈qd and cti=cti′,πi for i∈qd, and let xi be the statement as described in equation (2). If ZK.Vercrs,xi,πi=0, set yi=⊥; otherwise, it invokes the extractor ξ2ZKcrs,ς,xi,πi to obtain a witness mi,ri and sets yi=gmi. Finally, yii∈qd is sent to A.HybridG3: same as G2 but with the difference that the challenger uses the simulator SCPAFE=S1CPAFE,S2CPAFE,S3CPAFE,S4CPAFE to interact with the adversary. Specifically, in the setup phase, the challenger computes mpk′,stCPAFE⟵S1CPAFE1λ. In the prechallenge phase, the decryption queries are dealt with as in hybrid G2, while the key generation is handled as follows: for each query f∈ℱ, it runs S2CPAFEstCPAFE,f to obtain private key skf. In the challenge phase, let f1,…,fq1 be the function that the adversary A has made queries in the key-generation phase and m∈ℳqc be the challenge messages that the adversary queries. It computes yij=fjmi for all i∈qc and j∈q1 and invokes the simulator S3CPAFEstCPAFE,yi,ji∈qc,j∈q1 to obtain cti∗i∈qc. In the postchallenge queries, the decryption queries are processed as in hybrid G2, but the key-generation queries are processed differently as below: the challenger invokes S4CPAFEstCPAFE,f under the help of the oracle CPAFE.KIdealm,⋅ to obtain the private key skf.Claim 1.
IfZK is a computationally noninteractive zero-knowledge argument system, then hybrids G0 and G1 are computationally indistinguishable.Proof.
The hybrid gamesG0 and G1 are different in that, in G1, the challenger uses the NIZK simulator to compute the CRS and arguments. It is easy to see that the claim follows from the computational zero-knowledge of NIZK.
Concretely, letA=A1,A2 be an efficient adversary distinguishing hybrid games G0 and G1. A is used to construct an algorithm AZK that tries to distinguish the real and simulated distributions of the NIZK. AZK takes as input crs and is allowed to access to an argument oracle. In the setup, AZK computes mpk′,msk′⟵CPAFE.Setup1λ and sets mpk=mpk′,crs and msk=msk′. It then sends mpk to A. In the challenge phase, when A delivers challenge message m∈ℳλqc, the algorithm AZK samples ri∗⟵ℛ and computes cti′∗⟵CPAFE.Encmpk′,mi;ri∗ for each i∈qc. Let xi∗ be the statement in equation (2). AZK delivers xi∗,mi,ri∗ to its challenger and obtains an argument πi∗. Finally, A obtains cti∗=cti′∗,πi∗ and cti∗.
The rest steps are processed in the same way as inG0 and G1. Finally, AZK outputs whatever A outputs. Obviously, if the CRS and NIZK arguments are computed honestly, then AZK simulates the settings of G0; otherwise, it simulates the settings of G1. Thus, the lemma follows.Claim 2.
IfZK is simulation-sound extractable and CPAFE is perfectly correct, then hybrids G1 and G2 are computationally indistinguishable.Proof.
HybridsG1 and G2 are identical but only with the difference in the way the challenger responds to decryption queries. Conditioned on the simulation-sound extractability of ZK and perfect correctness of CPAFE, the two games are computationally indistinguishable. Let g,C be the decryption query pair that the adversary makes, where C=ctii∈qd and cti=cti′,πi.
The procedure can be classified into two cases. Ifπ can pass the verification, the challenger sets yi=⊥ in both G1 and G2. Otherwise, it is easy to see that the adversary cannot submit any challenge ciphertexts in the decryption queries. Thus, cti=cti′,πi was not generated by the challenger using SZK. Thus, by simulation-sound extractability, with probability at least 1−neglλ, the extraction algorithm ξ2ZK on xi and πi will produce a witness mi,ri to make cti′=CPAFE.Encmpk′,mi;ri hold. Furthermore, by perfect correctness of CPAFE, mi,ri is the only pair corresponding to cti′.
In addition, inG1, the challenger first computes skg⟵CPAFE.KGmsk′,g and then sets yi=CPAFE.Decskg,cti′. By the underlying PK-FE scheme CPAFE, yi=gmi, which is exactly the output in G2 after mi,ri is extracted. Therefore, with probability 1−neglλ, the distributions in both G1 and G2 are identical.Claim 3.
IfCPAFE is a q1,qc,q2-SIM-CPA-secure FE scheme for deterministic function family ℱ, then hybrids G2 and G3 are computationally indistinguishable.Proof.
SupposeA=A1,A2 is a distinguisher for hybrids G2 and G3. A is used to construct an algorithm ACPAFE=A1CPAFE,A2CPAFE that distinguishes REALA,ℱCPAFE and IDEALA,ℱCPAFE. Then, the detailed simulation procedure is processed as follows.


## 5.7. The Construction ofA1CPAFE

On taking as inputmpk′ which is generated by CPAFE.Setup1λ or S1CPAFE1λ, the setup and prechallenge queries are simulated as follows:Setup: in this phase, the adversary A1CPAFE first computes a simulated tuple crs,τ,ς⟵xi1ZK1λ. It then sets mpk=mpk′,crs and sends mpk to A.Prechallenge queries: in this phase, when A1 makes a function key query f, the adversary A1CPAFE queries its prechallenge key-generation oracle to obtain a key skf′ which is generated by skf′=CPAFE.KGmsk′,f or skf′=S2CPAFEst′,f, while the decryption queries are the same as in G2 and G3.


## 5.8. AdversaryA2CPAFE

On taking as inputmpk′ and a state st from A1CPAFE, the adversary A2CPAFE simulates the challenge phase and postchallenge queries as follows:Challenge: in this procedure, when the adversary A1 outputs a challenge message vector m, the adversary A2CPAFE queries its challenge oracle to obtain challenge ciphertext set cti′∗i∈qc for CPAFE. It then computes πi∗⟵S2ZKcrs,τ,xi∗ and sets cti∗=cti′∗,πi∗ for each i∈qc, where xi∗ is described as in equation (1). It finally sends cti∗i∈qc to A.Prechallenge queries: the simulation of this procedure is the same as prechallenge procedure, except that A2CPAFE queries his postchallenge key-generation oracle with the help of oracle CPAFE.KIdealm,⋅ to obtain a key skf′ which is generated by skf′=CPAFE.KGmsk′,f or skf′=S4CPAFEst′,f.At the end,ACPAFE outputs what A outputs. Obviously, if ACPAFE takes part in the game REALA,ℱCPAFE, then the view of A is computationally indistinguishable from G2; otherwise, if ACPAFE takes part in the ideal game IDEALA,ℱCPAFE, then the view of A is computationally indistinguishable from G3. Thus, the proof follows from the q1,qc,q2-SIM-CPA security of the scheme CPAFE.Remark 1.
Note that applying the above simulation-sound extractable NIZK to the secret-key settings for implementing the IND-CPA-to-IND-CCA security transformation is impossible. This is because beyond the encrypted message, the extractor of the NIZK also extracts out the master secret key used for a secret parameter in the encryption process. Once the extractor obtains the master secret key, it can use it to forge the private keys for any functions of its choice.
In the following, we will use the SIM-CCA-secure PK-FE proposed above and a NIZK scheme to put forward an IND-CCA-secure SK-FE.


## 6. Construction of SK-FE

Here, we give an IND-CCA-secure SK-FE from SIM-CCA-secure PK-FE. LetSFE = SFE.Setup, SFE.KG, SFE.Enc, SFE.Dec be the scheme and ℱ and ℳSFE the associated function space and message space, respectively. The building blocks used in the scheme are as follows:(i)
A noninteractive zero-knowledge argumentZK=ZK.Setup,ZK.Prov,ZK.Ver over the common random string space 0,1crs and proof space Π.(ii)
A semantically secure symmetric encryption schemeSE=SE.KG,SE.Enc,SE.Dec over the key space KSE, message space ℳSE, and ciphertext space CSE.(iii)
A SIM-CCA-secure PK-FE schemeFE = FE.Setup, FE.KG, FE.Enc, FE.Dec over the message space ℳFE=0,1crs×CSE×Π×KSE and function space Uℱ.In particular, note that in this construction, the message space of the schemeSFE is identical to that of the scheme SE, namely, ℳSFE=ℳSE.Setup: taking1λ as input, the algorithm SFE.Setup1λ first computes fpk,fsk⟵FE.Setup1λ, sek⟵SE.KG1λ, and crs⟵ZK.Setup1λ. Then, it outputs the public parameter ppr=crs,fpk and master secret key msk=fsk,sek. Note that the parameter ppr is implicitly contained in the following algorithms.Encryption: taking a master secret keymsk and a message m∈ℳSE as input, the algorithm SFE.Encmsk,m first parses msk into msk=fsk,sek. It then computes a symmetric encryption ciphertext ctSE⟵SE.Encsek,m, an argument π⟵ZK.Provcrs,ctSE,sek,m, and a PK-FE ciphertext ctFE⟵FE.Encfpk,ctSE,sek. It finally outputs the overall ciphertext CT=ctSE,π,ctFE.Key generation: taking a master secret keymsk and a function f∈ℱ as input, the algorithm SFE.KGmsk,f first parses msk into msk=fsk,sek and then constructs a universal circuit Uf (see Figure 5) and computes skf⟵FE.KGfsk,Uf. It finally outputs the private key skf.Decryption: taking a private keyskf=skUf and a ciphertext CT=ctSE,π,ctFE as input, the algorithm SFE.Decskf,CT first verifies whether ZK.Vercrs,ctSE,π=1; if so, it computes and outputs y=FE.DecskUf,ctFE; otherwise, it outputs ⊥.The correctness follows from Theorem2.Figure 5
CircuitUf.Theorem 2.
IfFE is perfectly correct, SE is a correct SE scheme, ZK is a perfectly complete NIZK, and the circuit Uf is correctly defined, then the scheme SFE is a correct SK-FE scheme.Proof.
It is easily observed the correctness ofSFE follows from the perfect-completeness of ZK, the perfect correctness of FE, the correctness of SE, and the correct definition of the circuit Uf.Proof.
Intuition. Our construction is inspired by Agrawal and Wu’s generic transformation for PK-FE from deterministic functions to randomized functions [17]. From their scheme, we first derive an SIM-CCA-secure PK-FE for deterministic functions by removing Φ-RKA-secure pseudorandom function PRF and one-way permutation used to implement the deterministic-to-randomized function transformation (note that the details of Agrawal and Wu’s scheme can be found in [17], we will not dwell on them here). Then using the derived PK-FE together with a semantically secure symmetric encryption (SE) and a standard NIZK, we obtain an SK-FE scheme with IND-CCA security. Roughly speaking, the plaintext is masked with the SE scheme (where the symmetric key of the SE is a part of the master secret key), then it computes a proof under the NIZK which is used for verifying whether the SE ciphertext encrypts correct plaintext. In order to ensure correct decryption, we reencrypt the SE ciphertext together with the proof and the symmetric key under the derived PK-FE scheme, in which the symmetric key and the SE ciphertext make sure that the scheme enables to decrypt and the proof makes sure that ill-formed SE ciphertext can be rejected in the final scheme.
The security follows Theorem3.Theorem 3.
If the NIZK argumentZK is computationally indistinguishable, the SE scheme SE is semantically secure, the PK-FE scheme FE is perfectly correct (adaptively) q1,qc,q2-SIM-CCA secure, then the SK-FE scheme SFE described above is (adaptively) IND-CCA secure, where the adversary makes at most q1+q2 key queries and qc challenge queries.Proof.
We adopt a similar proof method as that of Theorem1. Likewise, each game contains the following procedures:Setup: the challenger computes the parameterppr.Key generation query: in this procedure, the adversaryA may make prechallenge key queries and postchallenge key queries for functions f∈ℱ. Particularly, note that, for all key queries fjj∈q1+q2 and encryption queries m0i,m1ii∈qc as below, we require that fjm0i=fm1i.Encryption query: in this procedure,A commits a collection of message pairs m0i,m1ii∈qc, and the challenger responds with cti∗i∈qc.Decryption query: here,A may make decryption queries g,CT, with a further restriction that decryption queries are only allowed to contain queries g,CT such that CT∉Q, where Q is the set of all encryption queries that A has made in the encryption query procedure.
In particular, since in the underlying PK-FE schemeFE, for any function Uf and message pair m0′=ctSE0,sek0,m1′=ctSE1,sek1 (assume ctSE0 is an SE encryption of message m0 under key sek0 and ctSE1 is an SE encryption of message m1 under key sek1, where f and m0,m1 are the function and message pair that the IND-CCA adversary of the SK-FE scheme delivers in key query and encryption query phases) that the SIM-CCA adversary delivers in key query and encryption query phases, and it satisfies Ufm0′=Ufm1′, namely, fm0=fm1. Thus, the admissible condition still holds in our SK-FE scheme. Furthermore, like in the PK-FE, we also require that a similar equation relation ∼ over ciphertext space C is satisfied, i.e., given any two ciphertexts CT1=ctSE1,π1,ctFE1 and CT2=ctSE2,π2,ctFE2, we say CT1∼CT2, if ctSE1=ctSE2.


### 6.1. Hybrid Games

G0: this is the premier game where the message m0 is encrypted in the encryption query phase.G1: same as G0 except that the generation of the common random string crs and the argument π are replaced with the simulation mode of the scheme ZK.G2: same as G1 but with the difference that the simulator SFE = S1FE, S2FE, S3FE, S4FE, S5FE is used to respond to the queries.G3: same as G2 but with the difference that challenge message m1 instead of m0 is encrypted in the challenge ciphertext. In particular, the symmetric encryption computes the encryption ctSE⟵SE.Encsek,m1 of m1.G4: this is the same as G3 except that the challenger uses the real algorithms of the scheme FE to respond to the queries.G5: this is the same as G4 except that the generation of the common random string crs and argument π is replaced with the real algorithms of the scheme ZK.Claim 4.
If the NIZK argumentZK is computational zero knowledge, then hybrids G0 and G1 are computationally indistinguishable.(i)
At the setup phase, the adversaryAZK first samples fpk′,fsk′⟵FE.Setup1λ and sek⟵SE.KG1λ. Then, it sets ppr=crs,fpk′ and msk=fsk′,sek.(ii)
In the key-generation procedure, when a key queryf∈ℱλ is queried by A, the adversary AZK first constructs a universal circuit Uf and then responds with skf⟵FE.KGfsk′,Uf.(iii)
During the encryption query, whenA makes an encryption query m0,m1, the adversary AZK first computes a symmetric encryption ctSE∗⟵SE.Encsek,m0. It then uses ctSE∗,sek,m0 to query the oracle Ocrs,⋅,⋅ and obtains an argument π∗ (which is generated by the real algorithm ZK.Prov or the simulation algorithm S2ZK). It next computes a PK-FE ciphertext ctFE∗⟵FE.Encfmk′,ctSE∗,sek. Finally, it sends CT∗=ctSE∗,π∗,ctFE∗ to A. Let Q denote the set of all challenge ciphertexts that A obtains via encryption queries.(iv)
In the decryption query phase, whenA makes g,CT query s.t. CT∉Q, the adversary AZK first parses CT into CT=ctSE,π,ctFE and verifies whether ZK.Vercrs,ctSE,π=1. If so, it generates skg, computes, and outputs y=FE.Decskg,ctFE to A.
Proof. AssumeG0 and G1 are distinguishable, then we can use the adversary A that distinguishes G0 and G1 to construct an adversary AZK that attempts to break the computational zero-knowledge property of ZK. AZK is given a common random string crs (which comes from the real algorithm or simulation algorithm) and may access to the oracle Ocrs,⋅,⋅, which computes the argument for statements belonging to the language:
At the end,AZK outputs whatever A outputs.
From above, we can see that the adversaryAZK perfectly simulates the environment for A. Obviously, if crs and π are from the real algorithm, then AZK simulates the hybrid G0 for A; otherwise, it simulates G1 for A.Claim 5.
If the PK-FE schemeFE is (adaptively) q1,qc,q2-SIM-CCA secure, then hybrids G1 and G2 are computationally indistinguishable.Proof.
Assume thatG1 and G2 are distinguishable, then an adversary A that distinguishes G1 and G2 can be used to construct an adversary AFE=A1FE,A2FE which tries to break through the SIM-CCA security of the scheme FE; that is, the experiments REAL and IDEAL can be distinguished. In the security proof, AFE will play the role of the challenger for the adversary A. Let OKGpre be the prechallenge key-generation oracle corresponding to the oracle O1fsk′,⋅ in the real experiment and the oracle O1′st′,⋅ in the ideal experiment, OKGpost be the postchallenge oracle corresponding to the oracle O2fsk′,⋅ in the real experiment and the oracle O2′st′,⋅ in the ideal experiment, and Odec be the decryption oracle corresponding to the oracle O3fsk′,⋅ in the real experiment and the oracle O3′st′,⋅ in the ideal experiment. The reduction is described as follows:(i)
At the begin,A1FE first gets fpk′. It then samples sek⟵SE.KG1λ and crs,τ⟵S1ZK1λ and finally sets the public parameter ppr=crs,fpk′.(ii)
For the key-generation query, whenA makes a prechallenge key query f∈ℱλ, A1FE first constructs a universal circuit Uf and then makes a query Uf to the oracle OKGpre, from which it obtains a key skf′ (which is generated by skf′⟵FE.KGfsk′,Uf or skf′⟵S2FEst′,Uf). When A makes a postchallenge key query f∈ℱλ, the adversary A2FE queries Uf to the oracle OKGpost to obtain a key skf=skf′ and sends it to A (note that skf′ is generated by skf′⟵FE.KGfsk′,Uf or skf′⟵S2FEst′,Uf).(iii)
During the encryption query, whenA makes an encryption query m0,m1, the adversary A2FE first computes a symmetric encryption ctSE∗⟵SE.Encsek,m0 and an argument π∗⟵S2ZKcrs,τ,ctSE∗. It then makes a challenge query ctSE∗,sek to its challenger, from which it obtains a PK-FE ciphertext ctFE∗ (which is generated by ctFE∗⟵FE.Encfpk′,ctSE∗,sek or ctFE∗⟵S3FEst′,fjm0j∈q1, where fjm0j∈q1 are the outputs of all functions Ufj on ctSE∗,sek, and the set fjj∈q1 refers to all functions that the adversary A1FE makes queries to the oracle OKGpre). Finally, it sends the ciphertext CT∗=ctSE∗,π∗,ctFE∗ to the adversary A. Let Q be the set of all responses of this phase. Note that the adversary can make at most qc encryption queries in this phase.(iv)
In the decryption query phase, whenA makes a query g,CT s.t. CT∉Q (for both prechallenge decryption queries and postchallenge decryption queries), the adversary A2FE first parses CT into CT=ctSE,π,ctFE. It then verifies whether ZK.Vercrs,ctSE,π=1. If the verification passes, a query g,ctFE is made to the oracle Odec (for both prechallenge decryption queries and postchallenge decryption queries) to get the result y and sends it to A (note that y is generated by the real decryption algorithm or the simulation algorithm of the scheme FE).
At the end,AFE outputs whatever A outputs.
From above, we can observe that the environment forA is perfectly simulated by the adversary AFE. Obviously, if the master public key fpk′, the private keys skf′, the challenge ciphertexts ctFE∗, and the value y are generated as in real experiment, then AFE simulates hybrid G1 for A; otherwise, it simulates hybrid G2 for A. Thus, if the adversary A distinguishes hybrids G1 and G2, then the adversary AFE breaks the q1,qc,q2-SIM-CCA security of FE. The claims are as follows.Claim 6.
If the SE schemeSE is semantically secure, then games G2 and G3 are computationally indistinguishable.Proof.
Assume thatG2 and G3 are distinguishable, then an adversary A can be used to construct an algorithm ASE that attempts to break through the semantic security of the scheme SE. In particular, the adversary is allowed to access the oracle Osek,⋅ that can generate ciphertexts for messages that the adversary chooses. Let ℬ be the challenger of the adversary ASE.(i)
In the setup phase, the adversaryASE samples fpk′,st′⟵S1FE1λ and crs,τ⟵S1ZK1λ and sets ppr=crs,fpk′.(ii)
In the key-generation phase, the adversaryASE deals with the function key queries for A as in hybrid G3.(iii)
In the encryption phase, whenA queries the challenge plaintext pair m0,m1, the adversary ASE first delivers a pair m0,m1 to ℬ (its challenger) to get a symmetric ciphertext ctSE∗ (which encrypts the message mb for a challenge bit b⟵$0,1). It then computes an argument π∗⟵S2ZKcrs,τ,ctSE∗ and an FE ciphertext ctFE∗⟵S3FEst′,fjmbj∈q1 (note that fjm0=fjm1), where the set fjj∈q1 refers to the functions that the adversary A1FE makes queries to the oracle OKGpre. In the end, it sends the ciphertext CT∗=ctSE∗,π∗,ctFE∗ to A.
Finally,ASE outputs whatever A outputs.
From above, we can observe that the adversaryASE perfectly simulates the environment for A. Obviously, if the challenge ciphertext CT∗ encrypts the message m0, then ASE simulates hybrid G2 for A; if it encrypts the message m1, then ASE simulates hybrid G3 for A. Thus, if the adversary A distinguishes hybrids G2 and G3, then the adversary ASE breaks through the security of SE.Claim 7.
If the PK-FE schemeFE is SIM-CCA secure, then hybrids G3 and G4 are computationally indistinguishable.Proof.
The same as that of Claim5.Claim 8.
If the NIZK argumentZK is computationally zero-knowledge, then hybrids G4 and G5 are computationally indistinguishable.Proof.
The same as that of Claim4.Remark 2.
Note that, since the generic functionf in the SK-FE scheme is hardwired in the circuit Uf in the underlying PK-FE, the transformation in this paper is restricted to security against bounded collusion only. Removing this restriction by allowing only very specific functions seems violating our goals for genetic functions. Bounded collusion appears inherent in this type of FE schemes and solving it seems not easy. We left this work as an open problem and hope to solve it in the future.


## 6.1. Hybrid Games

G0: this is the premier game where the message m0 is encrypted in the encryption query phase.G1: same as G0 except that the generation of the common random string crs and the argument π are replaced with the simulation mode of the scheme ZK.G2: same as G1 but with the difference that the simulator SFE = S1FE, S2FE, S3FE, S4FE, S5FE is used to respond to the queries.G3: same as G2 but with the difference that challenge message m1 instead of m0 is encrypted in the challenge ciphertext. In particular, the symmetric encryption computes the encryption ctSE⟵SE.Encsek,m1 of m1.G4: this is the same as G3 except that the challenger uses the real algorithms of the scheme FE to respond to the queries.G5: this is the same as G4 except that the generation of the common random string crs and argument π is replaced with the real algorithms of the scheme ZK.Claim 4.
If the NIZK argumentZK is computational zero knowledge, then hybrids G0 and G1 are computationally indistinguishable.(i)
At the setup phase, the adversaryAZK first samples fpk′,fsk′⟵FE.Setup1λ and sek⟵SE.KG1λ. Then, it sets ppr=crs,fpk′ and msk=fsk′,sek.(ii)
In the key-generation procedure, when a key queryf∈ℱλ is queried by A, the adversary AZK first constructs a universal circuit Uf and then responds with skf⟵FE.KGfsk′,Uf.(iii)
During the encryption query, whenA makes an encryption query m0,m1, the adversary AZK first computes a symmetric encryption ctSE∗⟵SE.Encsek,m0. It then uses ctSE∗,sek,m0 to query the oracle Ocrs,⋅,⋅ and obtains an argument π∗ (which is generated by the real algorithm ZK.Prov or the simulation algorithm S2ZK). It next computes a PK-FE ciphertext ctFE∗⟵FE.Encfmk′,ctSE∗,sek. Finally, it sends CT∗=ctSE∗,π∗,ctFE∗ to A. Let Q denote the set of all challenge ciphertexts that A obtains via encryption queries.(iv)
In the decryption query phase, whenA makes g,CT query s.t. CT∉Q, the adversary AZK first parses CT into CT=ctSE,π,ctFE and verifies whether ZK.Vercrs,ctSE,π=1. If so, it generates skg, computes, and outputs y=FE.Decskg,ctFE to A.
Proof. AssumeG0 and G1 are distinguishable, then we can use the adversary A that distinguishes G0 and G1 to construct an adversary AZK that attempts to break the computational zero-knowledge property of ZK. AZK is given a common random string crs (which comes from the real algorithm or simulation algorithm) and may access to the oracle Ocrs,⋅,⋅, which computes the argument for statements belonging to the language:
At the end,AZK outputs whatever A outputs.
From above, we can see that the adversaryAZK perfectly simulates the environment for A. Obviously, if crs and π are from the real algorithm, then AZK simulates the hybrid G0 for A; otherwise, it simulates G1 for A.Claim 5.
If the PK-FE schemeFE is (adaptively) q1,qc,q2-SIM-CCA secure, then hybrids G1 and G2 are computationally indistinguishable.Proof.
Assume thatG1 and G2 are distinguishable, then an adversary A that distinguishes G1 and G2 can be used to construct an adversary AFE=A1FE,A2FE which tries to break through the SIM-CCA security of the scheme FE; that is, the experiments REAL and IDEAL can be distinguished. In the security proof, AFE will play the role of the challenger for the adversary A. Let OKGpre be the prechallenge key-generation oracle corresponding to the oracle O1fsk′,⋅ in the real experiment and the oracle O1′st′,⋅ in the ideal experiment, OKGpost be the postchallenge oracle corresponding to the oracle O2fsk′,⋅ in the real experiment and the oracle O2′st′,⋅ in the ideal experiment, and Odec be the decryption oracle corresponding to the oracle O3fsk′,⋅ in the real experiment and the oracle O3′st′,⋅ in the ideal experiment. The reduction is described as follows:(i)
At the begin,A1FE first gets fpk′. It then samples sek⟵SE.KG1λ and crs,τ⟵S1ZK1λ and finally sets the public parameter ppr=crs,fpk′.(ii)
For the key-generation query, whenA makes a prechallenge key query f∈ℱλ, A1FE first constructs a universal circuit Uf and then makes a query Uf to the oracle OKGpre, from which it obtains a key skf′ (which is generated by skf′⟵FE.KGfsk′,Uf or skf′⟵S2FEst′,Uf). When A makes a postchallenge key query f∈ℱλ, the adversary A2FE queries Uf to the oracle OKGpost to obtain a key skf=skf′ and sends it to A (note that skf′ is generated by skf′⟵FE.KGfsk′,Uf or skf′⟵S2FEst′,Uf).(iii)
During the encryption query, whenA makes an encryption query m0,m1, the adversary A2FE first computes a symmetric encryption ctSE∗⟵SE.Encsek,m0 and an argument π∗⟵S2ZKcrs,τ,ctSE∗. It then makes a challenge query ctSE∗,sek to its challenger, from which it obtains a PK-FE ciphertext ctFE∗ (which is generated by ctFE∗⟵FE.Encfpk′,ctSE∗,sek or ctFE∗⟵S3FEst′,fjm0j∈q1, where fjm0j∈q1 are the outputs of all functions Ufj on ctSE∗,sek, and the set fjj∈q1 refers to all functions that the adversary A1FE makes queries to the oracle OKGpre). Finally, it sends the ciphertext CT∗=ctSE∗,π∗,ctFE∗ to the adversary A. Let Q be the set of all responses of this phase. Note that the adversary can make at most qc encryption queries in this phase.(iv)
In the decryption query phase, whenA makes a query g,CT s.t. CT∉Q (for both prechallenge decryption queries and postchallenge decryption queries), the adversary A2FE first parses CT into CT=ctSE,π,ctFE. It then verifies whether ZK.Vercrs,ctSE,π=1. If the verification passes, a query g,ctFE is made to the oracle Odec (for both prechallenge decryption queries and postchallenge decryption queries) to get the result y and sends it to A (note that y is generated by the real decryption algorithm or the simulation algorithm of the scheme FE).
At the end,AFE outputs whatever A outputs.
From above, we can observe that the environment forA is perfectly simulated by the adversary AFE. Obviously, if the master public key fpk′, the private keys skf′, the challenge ciphertexts ctFE∗, and the value y are generated as in real experiment, then AFE simulates hybrid G1 for A; otherwise, it simulates hybrid G2 for A. Thus, if the adversary A distinguishes hybrids G1 and G2, then the adversary AFE breaks the q1,qc,q2-SIM-CCA security of FE. The claims are as follows.Claim 6.
If the SE schemeSE is semantically secure, then games G2 and G3 are computationally indistinguishable.Proof.
Assume thatG2 and G3 are distinguishable, then an adversary A can be used to construct an algorithm ASE that attempts to break through the semantic security of the scheme SE. In particular, the adversary is allowed to access the oracle Osek,⋅ that can generate ciphertexts for messages that the adversary chooses. Let ℬ be the challenger of the adversary ASE.(i)
In the setup phase, the adversaryASE samples fpk′,st′⟵S1FE1λ and crs,τ⟵S1ZK1λ and sets ppr=crs,fpk′.(ii)
In the key-generation phase, the adversaryASE deals with the function key queries for A as in hybrid G3.(iii)
In the encryption phase, whenA queries the challenge plaintext pair m0,m1, the adversary ASE first delivers a pair m0,m1 to ℬ (its challenger) to get a symmetric ciphertext ctSE∗ (which encrypts the message mb for a challenge bit b⟵$0,1). It then computes an argument π∗⟵S2ZKcrs,τ,ctSE∗ and an FE ciphertext ctFE∗⟵S3FEst′,fjmbj∈q1 (note that fjm0=fjm1), where the set fjj∈q1 refers to the functions that the adversary A1FE makes queries to the oracle OKGpre. In the end, it sends the ciphertext CT∗=ctSE∗,π∗,ctFE∗ to A.
Finally,ASE outputs whatever A outputs.
From above, we can observe that the adversaryASE perfectly simulates the environment for A. Obviously, if the challenge ciphertext CT∗ encrypts the message m0, then ASE simulates hybrid G2 for A; if it encrypts the message m1, then ASE simulates hybrid G3 for A. Thus, if the adversary A distinguishes hybrids G2 and G3, then the adversary ASE breaks through the security of SE.Claim 7.
If the PK-FE schemeFE is SIM-CCA secure, then hybrids G3 and G4 are computationally indistinguishable.Proof.
The same as that of Claim5.Claim 8.
If the NIZK argumentZK is computationally zero-knowledge, then hybrids G4 and G5 are computationally indistinguishable.Proof.
The same as that of Claim4.Remark 2.
Note that, since the generic functionf in the SK-FE scheme is hardwired in the circuit Uf in the underlying PK-FE, the transformation in this paper is restricted to security against bounded collusion only. Removing this restriction by allowing only very specific functions seems violating our goals for genetic functions. Bounded collusion appears inherent in this type of FE schemes and solving it seems not easy. We left this work as an open problem and hope to solve it in the future.


## 7. Instantiation

### 7.1. Instantiations of the Primitives

Both primitives used by our generic construction can be designed under some standard assumptions. For example, the simulation-sound extractable NIZK arguments can be instantiated from RSA assumption, and the SE scheme can be instantiated from one-way functions.


#### 7.1.1. Simulation-Sound Extractable NIZK Arguments

Agrawal and Wu [17] showed that the simulation-sound extractable NIZK argument can be constructed from trapdoor one-way permutations and dense cryptosystems by De Santis et al. [20] and both of which can be instantiated from RSA assumption.


#### 7.1.2. Semantically Secure Symmetric Encryption

We note that the semantically secure symmetric encryptionSE can be instantiated from one-way functions [21]. For example, it can be constructed from weak pseudorandom functions (wPRF) PRF, namely, SE.Encsek,m;r=r,PRFsek,r⊕m, and this wPRF can be again designed from only one-way functions.


### 7.2. Instantiations of the Underlying PK-FE

Here, we show several examples of how to instantiate a perfectly correctq1,qc,q2-SIM-CPA-secure functional encryption scheme CPAFE to apply to our generic constructions with CCA security in both public key and private key settings. The results described below show that the SIM-CPA-secure PK-FE used to construct the SIM-CCA-secure PK-FE can be designed from both standard assumptions (such as DDH, RSA, LWE, and LPN) and nonstandard assumptions (such as IO and intractable problems on composite-order multilinear maps).


#### 7.2.1. SIM-CPA-Secure PK-FE from Standard Assumptions

As in [22], Gorbunov et al. give a generic construction of PK-FE for a restricted number of secret key queries. Specifically, they proposed two q1,1,poly and q1,poly,0-SIM-CPA-secure PK-FE schemes for any class of deterministic functions computable by polynomial-size circuits based on the CPA-secure PKE and PRG computable by low-degree circuit. Particularly, both the PKE and PRG can be instantiated from standard assumptions. Concretely, the former can be designed based on the standard assumptions such as RSA [23], DDH [24], LWE [25], and LPN [26] assumptions, while the latter can be instantiated from the RSA assumption. Given the instantiated SIM-CPA-secure PK-FE, we obtain a SIM-CCA-secure PK-FE. Then using the SIM-CCA-secure PK-FE, we obtain an IND-CCA-secure SK-FE instantiable from the same assumptions.


#### 7.2.2. SIM-CPA-Secure PK-FE from Nonstandard Assumptions

As in [17], an adaptively IND-CPA-secure PK-FE with overwhelming correctness from intractable assumptions on composite-order multilinear maps by Garg et al. [10] can be applied to construct a PK-FE with SIM-CPA security by employing the overwhelming-to-perfect correctness transformation proposed by Dwork et al. [27] and the IND-to-SIM security transformation proposed by Caro et al. [28], respectively. In addition, SIM-CPA-secure PK-FE can also be obtained by applying the selective-to-adaptive transformation by Ananth et al. [8] and the IND-to-SIM transformation by Caro et al. [28] to the IO-based selectively-IND-secure PK-FE by Garg et al. [29]. Thus, given the instantiated SIM-CPA-secure PK-FE from nonstandard assumptions, we can obtain SIM-CCA-secure PK-FE and IND-CCA-secure SK-FE and both of which can be based on the nonstandard assumptions.


## 7.1. Instantiations of the Primitives

Both primitives used by our generic construction can be designed under some standard assumptions. For example, the simulation-sound extractable NIZK arguments can be instantiated from RSA assumption, and the SE scheme can be instantiated from one-way functions.


### 7.1.1. Simulation-Sound Extractable NIZK Arguments

Agrawal and Wu [17] showed that the simulation-sound extractable NIZK argument can be constructed from trapdoor one-way permutations and dense cryptosystems by De Santis et al. [20] and both of which can be instantiated from RSA assumption.


### 7.1.2. Semantically Secure Symmetric Encryption

We note that the semantically secure symmetric encryptionSE can be instantiated from one-way functions [21]. For example, it can be constructed from weak pseudorandom functions (wPRF) PRF, namely, SE.Encsek,m;r=r,PRFsek,r⊕m, and this wPRF can be again designed from only one-way functions.


## 7.1.1. Simulation-Sound Extractable NIZK Arguments

Agrawal and Wu [17] showed that the simulation-sound extractable NIZK argument can be constructed from trapdoor one-way permutations and dense cryptosystems by De Santis et al. [20] and both of which can be instantiated from RSA assumption.


## 7.1.2. Semantically Secure Symmetric Encryption

We note that the semantically secure symmetric encryptionSE can be instantiated from one-way functions [21]. For example, it can be constructed from weak pseudorandom functions (wPRF) PRF, namely, SE.Encsek,m;r=r,PRFsek,r⊕m, and this wPRF can be again designed from only one-way functions.


## 7.2. Instantiations of the Underlying PK-FE

Here, we show several examples of how to instantiate a perfectly correctq1,qc,q2-SIM-CPA-secure functional encryption scheme CPAFE to apply to our generic constructions with CCA security in both public key and private key settings. The results described below show that the SIM-CPA-secure PK-FE used to construct the SIM-CCA-secure PK-FE can be designed from both standard assumptions (such as DDH, RSA, LWE, and LPN) and nonstandard assumptions (such as IO and intractable problems on composite-order multilinear maps).


### 7.2.1. SIM-CPA-Secure PK-FE from Standard Assumptions

As in [22], Gorbunov et al. give a generic construction of PK-FE for a restricted number of secret key queries. Specifically, they proposed two q1,1,poly and q1,poly,0-SIM-CPA-secure PK-FE schemes for any class of deterministic functions computable by polynomial-size circuits based on the CPA-secure PKE and PRG computable by low-degree circuit. Particularly, both the PKE and PRG can be instantiated from standard assumptions. Concretely, the former can be designed based on the standard assumptions such as RSA [23], DDH [24], LWE [25], and LPN [26] assumptions, while the latter can be instantiated from the RSA assumption. Given the instantiated SIM-CPA-secure PK-FE, we obtain a SIM-CCA-secure PK-FE. Then using the SIM-CCA-secure PK-FE, we obtain an IND-CCA-secure SK-FE instantiable from the same assumptions.


### 7.2.2. SIM-CPA-Secure PK-FE from Nonstandard Assumptions

As in [17], an adaptively IND-CPA-secure PK-FE with overwhelming correctness from intractable assumptions on composite-order multilinear maps by Garg et al. [10] can be applied to construct a PK-FE with SIM-CPA security by employing the overwhelming-to-perfect correctness transformation proposed by Dwork et al. [27] and the IND-to-SIM security transformation proposed by Caro et al. [28], respectively. In addition, SIM-CPA-secure PK-FE can also be obtained by applying the selective-to-adaptive transformation by Ananth et al. [8] and the IND-to-SIM transformation by Caro et al. [28] to the IO-based selectively-IND-secure PK-FE by Garg et al. [29]. Thus, given the instantiated SIM-CPA-secure PK-FE from nonstandard assumptions, we can obtain SIM-CCA-secure PK-FE and IND-CCA-secure SK-FE and both of which can be based on the nonstandard assumptions.


## 7.2.1. SIM-CPA-Secure PK-FE from Standard Assumptions

As in [22], Gorbunov et al. give a generic construction of PK-FE for a restricted number of secret key queries. Specifically, they proposed two q1,1,poly and q1,poly,0-SIM-CPA-secure PK-FE schemes for any class of deterministic functions computable by polynomial-size circuits based on the CPA-secure PKE and PRG computable by low-degree circuit. Particularly, both the PKE and PRG can be instantiated from standard assumptions. Concretely, the former can be designed based on the standard assumptions such as RSA [23], DDH [24], LWE [25], and LPN [26] assumptions, while the latter can be instantiated from the RSA assumption. Given the instantiated SIM-CPA-secure PK-FE, we obtain a SIM-CCA-secure PK-FE. Then using the SIM-CCA-secure PK-FE, we obtain an IND-CCA-secure SK-FE instantiable from the same assumptions.


## 7.2.2. SIM-CPA-Secure PK-FE from Nonstandard Assumptions

As in [17], an adaptively IND-CPA-secure PK-FE with overwhelming correctness from intractable assumptions on composite-order multilinear maps by Garg et al. [10] can be applied to construct a PK-FE with SIM-CPA security by employing the overwhelming-to-perfect correctness transformation proposed by Dwork et al. [27] and the IND-to-SIM security transformation proposed by Caro et al. [28], respectively. In addition, SIM-CPA-secure PK-FE can also be obtained by applying the selective-to-adaptive transformation by Ananth et al. [8] and the IND-to-SIM transformation by Caro et al. [28] to the IO-based selectively-IND-secure PK-FE by Garg et al. [29]. Thus, given the instantiated SIM-CPA-secure PK-FE from nonstandard assumptions, we can obtain SIM-CCA-secure PK-FE and IND-CCA-secure SK-FE and both of which can be based on the nonstandard assumptions.


## 8. Conclusions and Open Problems

Our works propose two adaptively CCA-secure FEs in the PKE and SKE settings, respectively. The concrete works are as follows. We first derive an/a (adaptively) SIM-CCA-secure FE for deterministic functionalities in the public-key settings by making modifications on ones for randomized functionalities proposed by Agraval and Wu [17]. Then, based on the modified scheme together with a symmetric encryption and a standard NIZK, we present a private-key FE scheme (SK-FE) with adaptive IND-CCA security for deterministic functionalities. The instantiabilities of the underlying base SIM-CPA-secure PK-FEs, symmetric encryption, and NIZK from standard assumptions show that our proposed SK-FE scheme is practical under the standard assumptions.


### 8.1. IND-CCA-Secure SK-FE for Randomized Functionalities

A precursor to the work on SK-FE scheme supporting randomized functionalities was the work by Komargodski et al. [30]. They achieve this by utilizing function-private FE scheme for deterministic functionalities in the private-key settings. Brakerski and Segev [31] proposed a function-private scheme based on any SK-FE scheme for a sufficiently rich function class. To construct SK-FE with IND-CCA security for randomized functionalities, a function−private FE in the public-key settings with SIM-CCA security for randomized functionalities may be necessary, but deriving such a scheme from existing works is nontrivial, and it may require some new techniques. Thus, we left them as an open problem.


## 8.1. IND-CCA-Secure SK-FE for Randomized Functionalities

A precursor to the work on SK-FE scheme supporting randomized functionalities was the work by Komargodski et al. [30]. They achieve this by utilizing function-private FE scheme for deterministic functionalities in the private-key settings. Brakerski and Segev [31] proposed a function-private scheme based on any SK-FE scheme for a sufficiently rich function class. To construct SK-FE with IND-CCA security for randomized functionalities, a function−private FE in the public-key settings with SIM-CCA security for randomized functionalities may be necessary, but deriving such a scheme from existing works is nontrivial, and it may require some new techniques. Thus, we left them as an open problem.



---

*Source: 8823788-2020-09-08.xml*