# An Indistinguishably Secure Function Encryption Scheme

Authors: Ping Zhang; Yamin Li; Muhua Liu
Journal: Security and Communication Networks
 (2019)

---

## Abstract

In this work, we first design a function encryption scheme by using key encapsulation. We combine public key encryption with symmetric encryption to implement the idea of key encapsulation. In the key encapsulation, we use a key to turn a message (plaintext) into a ciphertext by symmetric encryption, and then we use public key encryption to turn this key into another ciphertext. In the design of function encryption scheme, we use the public key encryption system, symmetric encryption system, noninteractive proof system, indistinguishable obfuscator, and commitment scheme. Finally, we prove the indistinguishable security of our function encryption scheme.


---

## Body

## 1. Introduction

Nowadays, network technology has been rapidly developed and widely used. Due to the emergence of hacking, virus, and electronic fraud and theft, various information leakage incidents occur frequently. Both personal information security and enterprise information security are getting more and more attention, which makes information security more important than ever.With the rise of cloud computing, in order to save local storage resources, more and more companies or individuals choose to store local data on third-party servers (such as cloud computing platforms). To prevent user data from leaking, the data can be encrypted before storing it on third-party servers. It is noteworthy that in this application, third-party servers need to operate something on the user’s ciphertext, such as data mining, query, and statistics of the ciphertext. However, the traditional encryption system does not support ciphertext computing.This problem can be solved by using fully homomorphic encryption [1]. It is possible to compute on the ciphertext using fully homomorphic encryption. In other words, a nontrusted information processing system can process information in ciphertext environment without disclosing any information of users. However, the main problem of fully homomorphic encryption is that the results are encrypted. That is to say, although the third-party servers can perform ciphertext calculation, it cannot obtain the calculation results. In many application scenarios, third-party servers need to make certain decisions based on the results of the calculations. Therefore, fully homomorphic encryption does not meet our requirements.Function encryption firstly appeared in the article [2]. It is an extension of the articles [2–7]. It enables the third party to operate and output a function of plaintext without decryption. Therefore, it is very suitable for the computing scenario of data outsourcing encryption. Specifically, in function encryption for a function family, the key generation algorithm can generate the corresponding decryption key for each function in this function family by using the master private key. Given the ciphertext of a plaintext, the owner of the decryption key of each function can calculate the corresponding function value for this plaintext. A secure function encryption system should satisfy that users with decryption key can only get a function value of the plaintext but not any information about the plaintext. The traditional public key encryption scheme is too extreme. It enables users with decrypted key to get all or no messages from the ciphertext. Therefore, it is of great significance to study function encryption.Function encryption is a perfect noninteractive solution to many problems that arise in delegating services to external servers. Consider the following scenario: Suppose a bank subscribes to an external cloud server for storing financial records of its customers. In order to ensure the security of these records and perform various computations on the outsourced data remotely from time to time, a cost-effective choice for the bank is to use a function encryption scheme to encrypt the records locally prior to uploading to the cloud server. Now, suppose the researchers wish to retrieve investment amount summary of all customers who have joined a certain wealth management product from the cloud server. For this, the bank needs to provide the researchers a decryption key for the corresponding functionality. However, if the encryption scheme used by the bank possesses no function privacy, then the researchers would get to know the specific customer’s information from the decryption key provided by the bank. Thus, after performing the assigned computation, for financial gain, the researchers may leak the information to someone. This is clearly undesirable from the privacy point of view. Our function encryption scheme can solve the aforementioned information leak problem, and it can be applied to the following application scenarios such as spam filtering in the mail service, patient record privacy protection in the hospital, and partial decryption of information in the encrypted information store.


### 1.1. Our Result

The design of our function encryption scheme depends on the idea of key encapsulation. Key encapsulation (also known as hybrid encryption) consists of two parts: an external scheme and an internal scheme. To encrypt messages in a hybrid encryption scheme, a new key is generated for the internal scheme and used to encrypt messages. The key itself is then encrypted using an external scheme. The final hybrid ciphertext consists of two parts: the external ciphertext and the internal ciphertext. If someone wants to decrypt, he should firstly decrypt the external ciphertext to get the key and use this key to decrypt the internal ciphertext. While the internal scheme is symmetric encryption and the external scheme is public key encryption, the hybrid scheme still belongs to public key encryption. Why use the idea of key encapsulation? The external scheme is inefficient, so it is only used to encrypt relatively short keys, while relatively long messages are encrypted by the internal scheme.We choose symmetric encryption and public key encryption as the internal and external schemes of key encapsulation, respectively. In the design of the function encryption scheme, our idea is as follows: at first, we choose a keyk of the internal scheme to encrypt the message x, and then use the external scheme to encrypt the key k to get the two parts of a complete ciphertext. This will allow for decryption during the two-step process described above. First, the key k of the internal scheme is obtained by decrypting the external ciphertext in the external scheme, and then fx is obtained by using this key in the internal scheme. Specifically, we describe how to use the public key encryption system, symmetric encryption system, noninteractive proof system, indistinguishable obfuscator, and commitment scheme to design our function encryption scheme. Our scheme achieves indistinguishable security [8].


### 1.2. Related Works

The concept of function encryption originates from inner product encryption [6] and attribute-based encryption [5]. Early function encryption generally refers to attribute-based encryption, predicate encryption, or inner product encryption. These three kinds of encryption are the preliminary stages of function encryption. Sahai and Waters firstly created the concept of function encryption in 2008 [9]. Later, O’Neill proposed the security definition of the general function encryption [7], which laid the foundation for the research of function encryption.In 2011, Boneh et al. [3] not only gave the general form of function encryption, but also gave the formal definition and various security definitions of function encryption. In 2012, Gorbunov et al. [10] proposed a nonconcise general-purpose function encryption scheme based on multiparty security calculation. In 2013, Waters [11], Garg et al., [12] and Ananth et al. [13] further improved the efficiency of universal function encryption system. Subsequently, the function encryption scheme for regular language [14] and the function encryption scheme-based deterministic finite automata [15] were proposed. In the same year, Garg et al. [16] constructed a general function encryption scheme for the first time using indistinguishable obfuscation, which set up a new direction for the research of universal function encryption. Goldwasser et al. [17] proposed a simple universal function encryption scheme which uses fully homomorphic encryption, attribute-based encryption, and obfuscation circuit technology as the underlying modules. This scheme is a classical function encryption scheme. Later, Goldwasser et al. [18] firstly proposed multi-input function encryption. They not only proved the adaptive indistinguishable security of the scheme but also proved the simulation-based security of the scheme. It has to be noted that multi-input function encryption scheme is a refinement of function encryption, which can be applied in many occasions and can realize the security processing of multiuser information at different times.With the deepening of research on function encryption and fully homomorphic encryption, a new full key homomorphic encryption scheme (FKHE) [19] was proposed at the Eurocrypt 2014. It combines fully homomorphic encryption with function encryption. It overcomes the shortcomings of single key shortage of fully homomorphic encryption and provides possibilities for the use of function encryption in the outsourcing computing environment. In 2015, Goyal et al. [20] proposed for the first time the definition and construction of function encryption for random functions, which proved that the construction scheme was simulation-based security. Ananth et al. [13] proved that any selective secure function encryption can be transformed into adaptive secure function encryption and designed an adaptive function encryption scheme that combines public key function encryption with private key function encryption. Brakerski and Segev [21] studied the symmetric function encryption system with function hiding. Abdalla et al. [22] firstly proposed an internal product function encryption scheme based on public key, which set up a new direction of practical internal product function encryption scheme. Bishop et al. [23] firstly proposed the inner product function encryption scheme of the function hidden in symmetric case. Subsequently, Datta et al. [24] improved Bishop’s scheme. In 2018, Kim et al. [25] improved the inner product function encryption scheme of the function hidden to improve its efficiency. They also described three application scenarios of inner product function encryption of the function hidden. Kim et al. made it possible to use the inner product function encryption of the function hidden in practical applications.


### 1.3. Organization

This paper is organized as follows. The first section is the introduction of this paper. The second section is the existing definition of function encryption. In the third section, we recall some definitions of cryptographic primitives used in scheme construction. In the fourth section, we propose the design of our function encryption. In the fifth section, we prove the security of our constructed scheme. Finally, in the sixth section, we summarize the full text.


### 1.4. Basic Notation

In the following sections, the security parameter isλ∈ℕ. If neglλ<1/polyλ holds for all polynomials polyλ and all sufficiently large λ, we call neglλ as negligible function. In this paper, “PPT” represents probabilistic polynomial time and “xy” represents a concatenation of x and y. Let ℱ=ℱλ represent an ensemble, each of which is a finite function.


## 1.1. Our Result

The design of our function encryption scheme depends on the idea of key encapsulation. Key encapsulation (also known as hybrid encryption) consists of two parts: an external scheme and an internal scheme. To encrypt messages in a hybrid encryption scheme, a new key is generated for the internal scheme and used to encrypt messages. The key itself is then encrypted using an external scheme. The final hybrid ciphertext consists of two parts: the external ciphertext and the internal ciphertext. If someone wants to decrypt, he should firstly decrypt the external ciphertext to get the key and use this key to decrypt the internal ciphertext. While the internal scheme is symmetric encryption and the external scheme is public key encryption, the hybrid scheme still belongs to public key encryption. Why use the idea of key encapsulation? The external scheme is inefficient, so it is only used to encrypt relatively short keys, while relatively long messages are encrypted by the internal scheme.We choose symmetric encryption and public key encryption as the internal and external schemes of key encapsulation, respectively. In the design of the function encryption scheme, our idea is as follows: at first, we choose a keyk of the internal scheme to encrypt the message x, and then use the external scheme to encrypt the key k to get the two parts of a complete ciphertext. This will allow for decryption during the two-step process described above. First, the key k of the internal scheme is obtained by decrypting the external ciphertext in the external scheme, and then fx is obtained by using this key in the internal scheme. Specifically, we describe how to use the public key encryption system, symmetric encryption system, noninteractive proof system, indistinguishable obfuscator, and commitment scheme to design our function encryption scheme. Our scheme achieves indistinguishable security [8].


## 1.2. Related Works

The concept of function encryption originates from inner product encryption [6] and attribute-based encryption [5]. Early function encryption generally refers to attribute-based encryption, predicate encryption, or inner product encryption. These three kinds of encryption are the preliminary stages of function encryption. Sahai and Waters firstly created the concept of function encryption in 2008 [9]. Later, O’Neill proposed the security definition of the general function encryption [7], which laid the foundation for the research of function encryption.In 2011, Boneh et al. [3] not only gave the general form of function encryption, but also gave the formal definition and various security definitions of function encryption. In 2012, Gorbunov et al. [10] proposed a nonconcise general-purpose function encryption scheme based on multiparty security calculation. In 2013, Waters [11], Garg et al., [12] and Ananth et al. [13] further improved the efficiency of universal function encryption system. Subsequently, the function encryption scheme for regular language [14] and the function encryption scheme-based deterministic finite automata [15] were proposed. In the same year, Garg et al. [16] constructed a general function encryption scheme for the first time using indistinguishable obfuscation, which set up a new direction for the research of universal function encryption. Goldwasser et al. [17] proposed a simple universal function encryption scheme which uses fully homomorphic encryption, attribute-based encryption, and obfuscation circuit technology as the underlying modules. This scheme is a classical function encryption scheme. Later, Goldwasser et al. [18] firstly proposed multi-input function encryption. They not only proved the adaptive indistinguishable security of the scheme but also proved the simulation-based security of the scheme. It has to be noted that multi-input function encryption scheme is a refinement of function encryption, which can be applied in many occasions and can realize the security processing of multiuser information at different times.With the deepening of research on function encryption and fully homomorphic encryption, a new full key homomorphic encryption scheme (FKHE) [19] was proposed at the Eurocrypt 2014. It combines fully homomorphic encryption with function encryption. It overcomes the shortcomings of single key shortage of fully homomorphic encryption and provides possibilities for the use of function encryption in the outsourcing computing environment. In 2015, Goyal et al. [20] proposed for the first time the definition and construction of function encryption for random functions, which proved that the construction scheme was simulation-based security. Ananth et al. [13] proved that any selective secure function encryption can be transformed into adaptive secure function encryption and designed an adaptive function encryption scheme that combines public key function encryption with private key function encryption. Brakerski and Segev [21] studied the symmetric function encryption system with function hiding. Abdalla et al. [22] firstly proposed an internal product function encryption scheme based on public key, which set up a new direction of practical internal product function encryption scheme. Bishop et al. [23] firstly proposed the inner product function encryption scheme of the function hidden in symmetric case. Subsequently, Datta et al. [24] improved Bishop’s scheme. In 2018, Kim et al. [25] improved the inner product function encryption scheme of the function hidden to improve its efficiency. They also described three application scenarios of inner product function encryption of the function hidden. Kim et al. made it possible to use the inner product function encryption of the function hidden in practical applications.


## 1.3. Organization

This paper is organized as follows. The first section is the introduction of this paper. The second section is the existing definition of function encryption. In the third section, we recall some definitions of cryptographic primitives used in scheme construction. In the fourth section, we propose the design of our function encryption. In the fifth section, we prove the security of our constructed scheme. Finally, in the sixth section, we summarize the full text.


## 1.4. Basic Notation

In the following sections, the security parameter isλ∈ℕ. If neglλ<1/polyλ holds for all polynomials polyλ and all sufficiently large λ, we call neglλ as negligible function. In this paper, “PPT” represents probabilistic polynomial time and “xy” represents a concatenation of x and y. Let ℱ=ℱλ represent an ensemble, each of which is a finite function.


## 2. Function Encryption

In the second section, the concept of function encryption [3] and its indistinguishable security are rementioned. Indistinguishable security is not only the first consideration of function encryption but also of predicate encryption [4, 6].


### 2.1. Syntax

For a class of functionsℱ=ℱλ over message space ℳ=ℳλ, a function encryption scheme is composed of the following four algorithms:(i)
Setup1λ⟶mpk,msk: This is a random algorithm. This algorithm requires a security parameter λ as the input of the algorithm, requires the master public key mpk, and the master secret key msk as the output of the algorithm.(ii)
Encmpk,m⟶CT: This algorithm requires the master public key mpk and the plaintext m∈ℳ as the input of the algorithm and requires a ciphertext CT as the output of the algorithm.(iii)
KeyGenmsk,f⟶skf: This algorithm requires the master secret key msk and the randomized function f∈ℱ as the input of the algorithm and requires a secret key skf as the output of the algorithm.(iv)
Decskf,CT⟶fm: This algorithm requires the ciphertext CT and the secret key skf as the input of the algorithm and requires a string fm as the output of the algorithm.Definition 1.
(correctness). If the following conclusion holds for every functionf∈ℱ and every message m∈ℳ, the function encryption scheme for ℱ is correct.(1)Prmpk,msk⟵Setup1λ;DecKeyGenmsk,f,Encmpk,m≠fm=neglλ.Definition 2.
(indistinguishable security of function encryption). The indistinguishable security can be seen as a game between the attackerA and challenger. This game is divided into five phases.(i)
Setup phase: the challenger generates master key by theSetup algorithm mpk,msk⟵Setup1λ and then makes the attacker A get the master public key mpk.(ii)
Query phase 1: the attackerA chooses fi in ℱ adaptively and makes the challenger get this fi. The challenger generates the key skfi of function fi by the KeyGen algorithm skfi⟵KeyGenmsk,fi and sends it to the attacker. The attacker can repeat this step in any polynomial number of times.(iii)
Challenge phase: the attackerA chooses two messages m0,m1∈ℳ such that fim0=fim1 and makes the challenger get it. The Challenger chooses mb (b⟵0,1) from m0 and m1, runs the Enc algorithm CT⟵Encmpk,mb (b⟵0,1), and makes the attacker get the ciphertext CT.(iv)
Query phase 2: key queries continue to be initiated by the attackerA as before, but it also needs to satisfy that for any query fi, there is fim0=fim1 holds.(v)
Guess phase: the attackerA guesses whether the ciphertext CT is encryption for message m0 or message m1. Finally, the attacker A give his guess b′ (b′⟵0,1).
In this game, the advantage of the attackerA is AdvA=Prb′=b−1/2.


## 2.1. Syntax

For a class of functionsℱ=ℱλ over message space ℳ=ℳλ, a function encryption scheme is composed of the following four algorithms:(i)
Setup1λ⟶mpk,msk: This is a random algorithm. This algorithm requires a security parameter λ as the input of the algorithm, requires the master public key mpk, and the master secret key msk as the output of the algorithm.(ii)
Encmpk,m⟶CT: This algorithm requires the master public key mpk and the plaintext m∈ℳ as the input of the algorithm and requires a ciphertext CT as the output of the algorithm.(iii)
KeyGenmsk,f⟶skf: This algorithm requires the master secret key msk and the randomized function f∈ℱ as the input of the algorithm and requires a secret key skf as the output of the algorithm.(iv)
Decskf,CT⟶fm: This algorithm requires the ciphertext CT and the secret key skf as the input of the algorithm and requires a string fm as the output of the algorithm.Definition 1.
(correctness). If the following conclusion holds for every functionf∈ℱ and every message m∈ℳ, the function encryption scheme for ℱ is correct.(1)Prmpk,msk⟵Setup1λ;DecKeyGenmsk,f,Encmpk,m≠fm=neglλ.Definition 2.
(indistinguishable security of function encryption). The indistinguishable security can be seen as a game between the attackerA and challenger. This game is divided into five phases.(i)
Setup phase: the challenger generates master key by theSetup algorithm mpk,msk⟵Setup1λ and then makes the attacker A get the master public key mpk.(ii)
Query phase 1: the attackerA chooses fi in ℱ adaptively and makes the challenger get this fi. The challenger generates the key skfi of function fi by the KeyGen algorithm skfi⟵KeyGenmsk,fi and sends it to the attacker. The attacker can repeat this step in any polynomial number of times.(iii)
Challenge phase: the attackerA chooses two messages m0,m1∈ℳ such that fim0=fim1 and makes the challenger get it. The Challenger chooses mb (b⟵0,1) from m0 and m1, runs the Enc algorithm CT⟵Encmpk,mb (b⟵0,1), and makes the attacker get the ciphertext CT.(iv)
Query phase 2: key queries continue to be initiated by the attackerA as before, but it also needs to satisfy that for any query fi, there is fim0=fim1 holds.(v)
Guess phase: the attackerA guesses whether the ciphertext CT is encryption for message m0 or message m1. Finally, the attacker A give his guess b′ (b′⟵0,1).
In this game, the advantage of the attackerA is AdvA=Prb′=b−1/2.


## 3. Preliminaries

In the third section, we recall some concepts of primitives in cryptography, which are used in the construction of function encryption. Here, we omit not only the formal definitions of standard semantically secure public key encryption schemePKE=PKE.KeyGen,PKE.Enc,PKE.Dec but also the formal definitions of standard semantically secure symmetric encryption scheme SE=SE.Enc,SE.Dec. Next, we describe the formal definitions of indistinguishable obfuscation, commitment scheme, and witness indistinguishable proof system in detail.


### 3.1. Indistinguishable Obfuscation

According to the syntax of [16], the concept of indistinguishable obfuscation was recalled.Definition 3.
(Indistinguishable Obfuscation(iO)). If the following conclusions hold, then the uniform PPT machine iO is known as an indistinguishable obfuscator of a circuit class Cλ.(i)
Correctness: for every security parameterλ∈ℕ, C∈Cλ, and every input x, the following formula holds:(2)PrC′x=Cx:C′⟵iOλ,C=1.(ii)
Indistinguishability: there is a negligible functionnegl that makes the following conclusion hold for every PPT distinguisher Samp,D (which is not necessarily uniform). For every security parameter λ∈ℕ and every pair of circuits C0,C1∈Cλ, if C0x=C1x for every input x, then(3)PrDiOλ,C0=1−PrDiOλ,C1=1≤neglλ.


### 3.2. Commitment Scheme

According to the syntax of [26], a commitment scheme Com takes a random number r and a string x as the input and takes c⟵Comx;r as the output. The following two properties are necessary for a perfectly binding commitment scheme:(i)
Perfectly binding property: this property means that the commitments for two different strings must also be different. More formally,∀ x1≠x2 and r1, r2, Comx1;r1≠Comx2;r2.(ii)
Computational hiding property: for every stringx0 and x1 (the length of x0 and x1 is the same) and for every PPT adversary A, the following formula holds:(4)PrAComx0=1−PrAComx1=1≤neglλ.


### 3.3. Noninteractive Witness Indistinguishable Proof

The syntax of the noninteractive proof system was firstly recalled, and then the formal concept of noninteractive witness indistinguishable (NIWI) proof [27] was also recalled.


#### 3.3.1. Syntax

An efficiently computable relationR is composed of pairs x,w, in which x and w are named as the statement and the witness, respectively. The language consisting of statements in R is denoted by L. The following three algorithms constitute a noninteractive proof system for a language L:(i)
NIWI.Setup1λ⟶crs: this algorithm requires a security parameter 1λ as the input of the algorithm and requires a common reference string crs as the output of the algorithm.(ii)
NIWI.Provecrs,x,w⟶π: this prove algorithm requires the common reference string crs and a statement x along with a witness w as the input of the algorithm. This prove algorithm outputs a proof string π when x,w∈R or outputs fail when x,w∉R.(iii)
NIWI.Verifycrs,x,π⟶0,1: this verify algorithm requires the common reference string crs and a statement x with a corresponding proof π as the input. If the proof is valid, this algorithm outputs 1 and otherwise 0.Definition 4 (NIWI).
A noninteractive witness indistinguishable proof system for a languageL with a PPT relation R needs to satisfy the following properties:(i)
Perfect completeness property: for allx,w∈R, the following formula holds:(5)PrNIWI.Verifycrs,x,NIWI.Provecrs,x,w=1=1.
Here, the reference stringcrs is generated by the algorithm crs⟵NIWI.Setup1λ, and the probability is taken over the coins of NIWI.(ii)
Statistical soundness property: for all adversaryA, the following formula holds:(6)PrNIWI.Verifycrs,x,π=1∧x∉Lcrs⟵NIWI.Setup1λ;x,π⟵Acrs=negl1λ.(iii)
Witness indistinguishability property: for any tripletx,w0,w1 (x,w0∈R and x,w1∈R), the distributions crs,NIWI.Provecrs,x,w0 and crs,NIWI.Provecrs,x,w1 are computationally indistinguishable (here the reference string crs is generated by the algorithm crs⟵NIWI.Setup1λ).


## 3.1. Indistinguishable Obfuscation

According to the syntax of [16], the concept of indistinguishable obfuscation was recalled.Definition 3.
(Indistinguishable Obfuscation(iO)). If the following conclusions hold, then the uniform PPT machine iO is known as an indistinguishable obfuscator of a circuit class Cλ.(i)
Correctness: for every security parameterλ∈ℕ, C∈Cλ, and every input x, the following formula holds:(2)PrC′x=Cx:C′⟵iOλ,C=1.(ii)
Indistinguishability: there is a negligible functionnegl that makes the following conclusion hold for every PPT distinguisher Samp,D (which is not necessarily uniform). For every security parameter λ∈ℕ and every pair of circuits C0,C1∈Cλ, if C0x=C1x for every input x, then(3)PrDiOλ,C0=1−PrDiOλ,C1=1≤neglλ.


## 3.2. Commitment Scheme

According to the syntax of [26], a commitment scheme Com takes a random number r and a string x as the input and takes c⟵Comx;r as the output. The following two properties are necessary for a perfectly binding commitment scheme:(i)
Perfectly binding property: this property means that the commitments for two different strings must also be different. More formally,∀ x1≠x2 and r1, r2, Comx1;r1≠Comx2;r2.(ii)
Computational hiding property: for every stringx0 and x1 (the length of x0 and x1 is the same) and for every PPT adversary A, the following formula holds:(4)PrAComx0=1−PrAComx1=1≤neglλ.


## 3.3. Noninteractive Witness Indistinguishable Proof

The syntax of the noninteractive proof system was firstly recalled, and then the formal concept of noninteractive witness indistinguishable (NIWI) proof [27] was also recalled.


### 3.3.1. Syntax

An efficiently computable relationR is composed of pairs x,w, in which x and w are named as the statement and the witness, respectively. The language consisting of statements in R is denoted by L. The following three algorithms constitute a noninteractive proof system for a language L:(i)
NIWI.Setup1λ⟶crs: this algorithm requires a security parameter 1λ as the input of the algorithm and requires a common reference string crs as the output of the algorithm.(ii)
NIWI.Provecrs,x,w⟶π: this prove algorithm requires the common reference string crs and a statement x along with a witness w as the input of the algorithm. This prove algorithm outputs a proof string π when x,w∈R or outputs fail when x,w∉R.(iii)
NIWI.Verifycrs,x,π⟶0,1: this verify algorithm requires the common reference string crs and a statement x with a corresponding proof π as the input. If the proof is valid, this algorithm outputs 1 and otherwise 0.Definition 4 (NIWI).
A noninteractive witness indistinguishable proof system for a languageL with a PPT relation R needs to satisfy the following properties:(i)
Perfect completeness property: for allx,w∈R, the following formula holds:(5)PrNIWI.Verifycrs,x,NIWI.Provecrs,x,w=1=1.
Here, the reference stringcrs is generated by the algorithm crs⟵NIWI.Setup1λ, and the probability is taken over the coins of NIWI.(ii)
Statistical soundness property: for all adversaryA, the following formula holds:(6)PrNIWI.Verifycrs,x,π=1∧x∉Lcrs⟵NIWI.Setup1λ;x,π⟵Acrs=negl1λ.(iii)
Witness indistinguishability property: for any tripletx,w0,w1 (x,w0∈R and x,w1∈R), the distributions crs,NIWI.Provecrs,x,w0 and crs,NIWI.Provecrs,x,w1 are computationally indistinguishable (here the reference string crs is generated by the algorithm crs⟵NIWI.Setup1λ).


## 3.3.1. Syntax

An efficiently computable relationR is composed of pairs x,w, in which x and w are named as the statement and the witness, respectively. The language consisting of statements in R is denoted by L. The following three algorithms constitute a noninteractive proof system for a language L:(i)
NIWI.Setup1λ⟶crs: this algorithm requires a security parameter 1λ as the input of the algorithm and requires a common reference string crs as the output of the algorithm.(ii)
NIWI.Provecrs,x,w⟶π: this prove algorithm requires the common reference string crs and a statement x along with a witness w as the input of the algorithm. This prove algorithm outputs a proof string π when x,w∈R or outputs fail when x,w∉R.(iii)
NIWI.Verifycrs,x,π⟶0,1: this verify algorithm requires the common reference string crs and a statement x with a corresponding proof π as the input. If the proof is valid, this algorithm outputs 1 and otherwise 0.Definition 4 (NIWI).
A noninteractive witness indistinguishable proof system for a languageL with a PPT relation R needs to satisfy the following properties:(i)
Perfect completeness property: for allx,w∈R, the following formula holds:(5)PrNIWI.Verifycrs,x,NIWI.Provecrs,x,w=1=1.
Here, the reference stringcrs is generated by the algorithm crs⟵NIWI.Setup1λ, and the probability is taken over the coins of NIWI.(ii)
Statistical soundness property: for all adversaryA, the following formula holds:(6)PrNIWI.Verifycrs,x,π=1∧x∉Lcrs⟵NIWI.Setup1λ;x,π⟵Acrs=negl1λ.(iii)
Witness indistinguishability property: for any tripletx,w0,w1 (x,w0∈R and x,w1∈R), the distributions crs,NIWI.Provecrs,x,w0 and crs,NIWI.Provecrs,x,w1 are computationally indistinguishable (here the reference string crs is generated by the algorithm crs⟵NIWI.Setup1λ).


## 4. Construction

In the fourth section, we propose the design of function encryption scheme. In our construction, we set the key space of the symmetric encryption schemeSE to 0,1ℓSE.In our scheme, we set the ciphertext length of the public key encryption schemePKE=PKE.KeyGen,PKE.Enc,PKE.Dec to lenc=lenc1λ. In the design of our scheme, the parameter len=2⋅lenc will be used, and the symmetric encryption scheme SE needs to satisfy this property:(7)PrSE.Deck1,C′≠⊥:k0,k1⟵0,1ℓSE,k0≠k1,C′⟵SE.Enck0,m≤neglλ,where symbol “⊥” denotes an error.In the design of our scheme, theNIWI proof system used is denoted by NIWI.Setup,NIWI.Prove,NIWI.Verify, the perfectly binding commitment scheme used is denoted by Com, and the indistinguishable obfuscator used is denoted by iO. Now, we begin to give our scheme FE=Setup,Enc,KeyGen,Dec.(i)
Setup1λ⟶mpk,msk(1)
At first, two pairs of key pairs are generated using the key generation algorithmpk1,sk1⟵PKE.KeyGen1λ and pk2,sk2⟵PKE.KeyGen1λ of the public key encryption scheme (note: pk,sk⟵PKE.KeyGen1λ is a random algorithm)(2)
Compute a common reference stringcrs⟵NIWI.Setup1λ using the NIWI proof system(3)
Choose a symmetric encryption schemeSE(4)
ComputeC⟵Com0len(5)
Let the master public key and the master secret key bempk=pk1,pk2,crs,C,SE and msk=sk1, respectively(ii)
Encmpk,m⟶CT:(1)
Choose a secret keyKSE of the symmetric encryption and compute the ciphertextsCT1⟵PKE.Encpk1,KSECT2⟵PKE.Encpk2,KSECT3⟵SE.EncKSE,m(2)
Computeπ⟵NIWI.Provecrs,y,w (y=CT1,CT2,C,pk1,pk2)(i)
EitherCT1 and CT2 are encryptions for the same plaintext, or(ii)
C is a commitment for CT1CT2The real witnesswreal=KSE,r1,r2 is used to prove the first part of the statement, where the random numbers r1 and r2 are used to compute the ciphertexts CT1 and CT2, respectively; the trapdoor witness wtrap=s is used to prove the second part of the statement, where the random number s is used to compute C(3)
The ciphertext isCT=CT1,CT2,CT3,π(iii)
KeyGenmsk,f⟶skf(1)
Compute the decryption keyskf⟵iOG for function f, where the circuit G is showed in Figure 1; it should be noted that the circuit G contains the random function f, the secret key sk1, and the master public key mpk(iv)
Decskf,CT⟶fm(1)
It inputsCT and decryption key skf and outputs fmFigure 1
FunctionalityG.The correctness of the scheme we design is easily derived from the correctness of its components. Next, we will demonstrate the security of this scheme.


## 5. Proof of Security

Theorem 1.
Assume that the aforementioned function encryption instantiated with a standard semantically secure public key encryption, a standard semantically secure symmetric encryption, a computational hiding commitment, a noninteractive witness indistinguishable proof, and indistinguishably secure obfuscator, it is indistinguishably secure.Now, we prove that if the aforementioned assumption is true, no polytime attacker can break our scheme. We will prove indistinguishable security of the function encryption using indistinguishable game. We assume that a polytime attackerA makes q private key queries. Let fi (i∈q) denote the ith function query. There is a constraint fim0=fim1 for each function query.We need to define a sequence of games to prove theorem 1. The first game is the experiment with the challenge messagem0. Next, we prove that any PPT adversary has almost the same advantage in each game as that of the previous game.Game 1. The challenger encrypts message m0 in the challenge ciphertext.(i)
Setup Phase. The challenger firstly computes the key pair mpk,msk⟵Setup1λ and gives master public mpk to A. Choose a symmetric encryption scheme SE and three secret keys k1⟵0,1ℓSE, k0⟵0,1ℓSE, and k2⟵0,1ℓSE for the symmetric encryption scheme. Compute the ciphertexts:CT1,1∗⟵PKE.Encpk1,k1, CT2,1∗⟵PKE.Encpk2,k1.CT1,0∗⟵PKE.Encpk1,k0, CT2,0∗⟵PKE.Encpk2,k0.CT1,2∗⟵PKE.Encpk1,k2, CT2,2∗⟵PKE.Encpk2,k2.Setc1=CT1,1∗CT2,1∗, c2=CT1,0∗CT2,0∗, c3=CT1,2∗CT2,2∗, c4=CT1,1∗CT2,0∗, c5=CT1,2∗CT2,0∗.(ii)
Query Phase. The adversary A submits query of f adaptively. The challenger sends skf⟵KeyGenmsk,f to A.(iii)
Challenge Phase. The challenger chooses a challenge plaintext m0 from two plaintexts and a secret key k1 of the symmetric encryption, computes the ciphertexts CT1∗⟵PKE.Encpk1,k1, CT2∗⟵PKE.Encpk2,k1, and CT3∗⟵SE.Enck1,m0. Compute a NIWI proof π∗⟵NIWI.Provecrs,y∗,w (y∗=CT1∗,CT2∗,C,pk1,pk2). Set st=CT1∗,CT2∗,k1,π∗. At last, it returns CT∗=CT1∗,CT2∗,CT3∗,π∗.Game 2. This game is exactly the same as the previous game (Game 1) except for a little difference. The difference is that for all key queries of f, the corresponding secret key skf is computed by skf⟵iOGf, where the circuit Gf is described in Figure 2.Game 3. This game is exactly the same as the previous game (Game 2) except for a little difference. The difference is that the commitment C is computed as follows: the challenge ciphertext is denoted by CT∗=CT1∗,CT2∗,CT3∗,π∗ and C⟵ComCT1∗CT2∗.Game 4. This game is exactly the same as the previous game (Game 3) except for a little difference. The difference is that in every challenge ciphertext CT∗=CT1∗,CT2∗,CT3∗,π∗ π∗ is computed using the trapdoor witness.Game 5. This game is exactly the same as the previous game (Game 4) except for a little difference. The difference is that we modify the challenge ciphertext CT∗=CT1∗,CT2∗,CT3∗,π∗: the second ciphertext CT2∗ is an encryption of k0, that is, CT2∗⟵PKE.Encpk2,k0.Game 6. This game is exactly the same as the previous game (Game 5) except for a little difference. The difference is that for all key queries of f, the corresponding secret key skf is computed by skf⟵iOGf∗, where the circuit Gf∗ is described in Figure 3.Game 7. This game is exactly the same as the previous game (Game 6) except for a little difference. The difference is that we modify the challenge ciphertext CT∗=CT1∗,CT2∗,CT3∗,π∗: the first ciphertext CT1∗ is an encryption of k0, that is, CT1∗⟵PKE.Encpk1,k0.Game 8. This game is exactly the same as the previous game (Game 7) except for a little difference. The difference is that the symmetric encryption key k1 is replaced by another key k2.Game 9. This game is exactly the same as the previous game (Game 8) except for a little difference. The difference is that we modify the challenge ciphertext CT∗=CT1∗,CT2∗,CT3∗,π∗: the third ciphertext CT3∗ is an encryption of m1, that is, CT3∗⟵SE.Enck2,m1.Game 10. This game is exactly the same as the previous game (Game 9) except for a little difference. The difference is that we modify the challenge ciphertext CT∗=CT1∗,CT2∗,CT3∗,π∗: the first ciphertext CT1∗ is an encryption of k2, that is CT1∗⟵PKE.Encpk1,k2.Game 11. This game is exactly the same as the previous game (Game 10) except for a little difference. The difference is that for all key queries f, the corresponding secret key skf is computed by skf⟵iOGf.Game 12. This game is exactly the same as the previous game (Game 11) except for a little difference. The difference is that we modify the challenge ciphertext CT∗=CT1∗,CT2∗,CT3∗,π∗: the second ciphertext CT2∗ is an encryption of k2, that is, CT2∗⟵PKE.Encpk2,k2.Game 13. This game is exactly the same as the previous game (Game 12) except for a little difference. The difference is that in every challenge ciphertext CT∗=CT1∗,CT2∗,CT3∗,π∗, the proof π∗ is computed using the real witness.Game 14. This game is exactly the same as the previous game (Game 13) except for a little difference. The difference is that the commitment C is computed as follows: C⟵Com0len. Note that this game corresponds to the selective indistinguishable game that has been honestly executed, where the challenger encrypts the message m1 in the challenge ciphertext.The description for the sequence of games is completed. Next, we prove that the neighbouring games are indistinguishable.Figure 2
FunctionalityGf.Figure 3
FunctionalityGf∗.Lemma 1.
Game 1 and Game 2 are computationally indistinguishable wheniO is an indistinguishable obfuscator.Proof.
We can see that the difference between Game 1 and Game 2 lies only in the calculation method of the secret keyskf. In the former experiment, Game 1, for any key query f, the secret key skf is outputted by iOG; however, in the latter experiment, Game 2, the secret key skf is outputted by iOGf. If we want to prove that Game 1 and Game 2 are computationally indistinguishable, we need to prove that for any input CT, G and Gf have identical output for identical input. Then, according to the security of indistinguishable obfuscator, we can get that iOG and iOGf are computationally indistinguishable, which means that Game 1 and Game 2 are computationally indistinguishable.
First, we will prove that for any inputCT=CT1,CT2,CT3,π, G outputs ⊥ if and only if Gf outputs ⊥.
We can find that bothG and Gf output ⊥ if and only if the proof π is invalid, that is, NIWI.Verifycrs,y,π=0. Here, y=CT1,CT2,C,pk1,pk2. If the proof π is valid, we define that an input CT=CT1,CT2,CT3,π is valid.
Next, we prove that for any valid inputCT=CT1,CT2,CT3,π, GCT=GfCT.
Here we have to consider two cases:(i)
Case 1. There does not exist a ci, such that ci=CT1∗CT2∗.(ii)
Case 2. There exists a ci, such that ci=CT1∗CT2∗.
For the case 1, bothG and Gf compute k1 with sk1 by decrypting CT1, compute m with k1 by decrypting CT3, and outputs fm. In the case 2, G computes k1 with sk1 by decrypting CT1, computes m with k1 by decrypting CT3, and also outputs fm. What’s more, because ci=CT1∗CT2∗, Gf also outputs fm. So we can get that GCT=GfCT.
The experimentG2,i (0≤i≤q) is defined as follows: in G2,i, the first ith queries are answered by G and the remaining i+1th to qth queries are answered by Gf. We can see that G2,0 happens to be Game 1 and G2,q happens to be Game 2.
Here, we prove that if there is a PPT adversaryA which can distinguish the experiments G2,i and G2,i+1 with nonnegligible advantage, there is another PPT adversary ℬ which can break the security of indistinguishable obfuscator with nonnegligible advantage.
We constructℬ by A as follows:(1)
First of all, the adversaryℬ honestly runs the Game 1.(2)
For the firstith key queries f, the adversary ℬ computes the key skf by Gf. For the remaining i+2th to qth key queries f, the adversary ℬ computes the key skf by G.(3)
For thei+1th key queries f, the adversary ℬ respectively constructs the circuit G and Gf and sends them to the challenger of the iO and receives an obfuscation skf. Then, the adversary ℬ gives skf to A.(4)
The adversaryℬ runs the rest of the experiment according to the Game 1.(5)
At last, the adversaryℬ gives the output of the game to the adversary A and the obfuscation challenger.
We happen to be in experimentG2,i when the challenger of iO chose the circuit G; We happen to be in experiment G2,i+1 when the challenger of iO chose the circuit Gf. Therefore, if the adversary A can distinguish between the two experiments with nonnegligible advantage, then the adversary ℬ can break the security of indistinguishable obfuscator with the same advantage.
In summary, Game 1 is computationally indistinguishable from Game 2.Lemma 2.
IfCom is a computationally hiding commitment scheme, Game 2 is computationally indistinguishable from Game 3.Proof.
We can see that the difference between Game 2 and Game 3 lies only in the calculation method of the commitmentC. In the former game, Game 2, C is a commitment for 0len; however, in the latter game, Game 3, C is a commitment for CT1∗CT2∗. It is important to note that the random number used to compute C is never used anywhere. Therefore, the property of computational hiding in the commitment guarantees that Game 2 is computationally indistinguishable from Game 3.Lemma 3.
Because of witness indistinguishability ofNIWI, Game 3 is computationally indistinguishable from Game 4.Proof.
We can see that the difference between Game 3 and Game 4 lies only in the witnessw used. In Game 3, for proving that CT1∗ and CT2∗ are encryptions of the same message, we use the real witness to compute π. However, in Game 4, for proving that C is a commitment for CT1∗CT2∗, we use the trapdoor witness to compute π. Since NIWI is witness indistinguishable, Game 3 is computationally indistinguishable from Game 4.Lemma 4.
IfPKE.KeyGen,PKE.Enc,PKE.Dec is a semantically secure public key encryption scheme, Game 4 is computationally indistinguishable from Game 5.Proof.
We can see that the difference between Game 4 and Game 5 lies only in the calculation method of the second ciphertextsCT2∗ in the challenge ciphertexts CT∗. In Game 4, CT2∗ is an encryption of the random message k1, while in Game 5, CT2∗ is an encryption of the random message k0. Next, we show that if there is an adversary A who can distinguish Game 4 from Game 5, there is an adversary ℬ who can break the semantic security of the public key encryption system. The adversary ℬ is designed as follows:(1)
At first, the adversaryℬ received a public key pk from the challenger.(2)
ℬ generates pk1,sk1⟵PKE.KeyGen1λ, crs⟵NIWI.Setup1λ, and chooses a symmetric encryption scheme SE. Next, the adversary ℬ encrypts the string k1 using pk1 to compute the ciphertext CT1∗.(3)
The adversaryℬ sends k1,k0 to the challenger and receives a ciphertext CT2∗. Then, ℬ computes the commitment C=ComCT1∗CT2∗.(4)
The adversaryℬ runs the rest of the experiment according to Game 4 and Game 5.(5)
At last, the adversaryA received the output of the experiment from the adversary ℬ.(6)
If adversaryA outputs Game 4, the adversary ℬ outputs that CT2∗ is an encryption of k1, otherwise outputs that CT2∗ is an encryption of k0.
We can see that the adversaryℬ just runs Game 4 when CT2∗ is an encryption of k1, and ℬ just runs Game 5 when CT2∗ is an encryption of k0. Therefore, if there exists an adversary who can distinguish the outputs of the two games with nonnegligible advantage, we can construct another adversary who can break the semantic security of public key encryption with nonnegligible advantage.Lemma 5.
IfCom is perfectly binding, and NIWI is statistically sound, iO is an indistinguishable obfuscator and Game 5 and Game 6 are computationally indistinguishable.Proof.
Similar to the proof of Lemma 1, we firstly prove that for any inputCT=CT1,CT2,CT3,π, Gf outputs ⊥ if and only if Gf∗ outputs ⊥.
We can see that bothGf and Gf∗ output ⊥ if and only if the proof π is invalid, that is, NIWI.Verifycrs,y,π=0 (y=CT1,CT2,C,pk1,pk2).
So we need to consider valid inputs only. Then, we will prove that all valid inputsCT=CT1,CT2,CT3,π meet one of the following properties:(i)
CT1 and CT2 are encryptions for the same message(ii)
There exists ani such that CT1CT2=ci
We are going to use a proof by contradiction here. We assume that there is a valid input that satisfies neither of the above properties. BecauseNIWI is statistically sound, the statement y=CT1,CT2,C,pk1,pk2 must have either a real witness or a trapdoor witness when the input is valid. However, because CT1 and CT2 are encryptions of different messages, the real witness does not exist. Therefore, there must be a trapdoor witness to make the input valid. That means there is s such that C=ComCT1CT2;s. On the other hand, since C=ComCT1∗CT2∗;s and Com is perfectly binding, CT1CT2=CT1∗CT2∗=c5. Thus, we get a contradiction, and the assumption is not true.
Next, we will prove that for any inputCT=CT1,CT2,CT3,π, GfCT=Gf∗CT.
If bothCT1 and CT2 are encryptions for the same message, then PKE.Decsk1,CT1=PKE.Decsk2,CT2=k1, and SE.Deck1,CT3=m. Therefore, both Gf and Gf∗ output fm. On the other hand, if there is an i satisfying CT1CT2=ci, then both Gf and Gf∗ output fm. Therefore, for all valid inputs, Gf and Gf∗ have same output for the same input, that is, GfCT=Gf∗CT.
In summary, if there exists an adversary which can distinguish the outputs of these games with nonnegligible advantage, we can construct another adversary which can break the security of indistinguishable obfuscation with the same advantage.Lemma 6.
Game 6 is computationally indistinguishable from Game 7, whenPKE is a semantically secure public key encryption scheme.Proof.
The proof method of this lemma is the same as the proof method of lemma 4, so it is omitted here.Lemma 7.
Game 7 is computationally indistinguishable from Game 8.Proof.
We can see that Game 7 and Game 8 differ in the secret key used in the symmetric encryption scheme. In Game 7,k1 is used to encrypt m0, while in Game 8, k2 is used to encrypt m0. We can find that both k1 and k2 are chosen randomly from the key space of symmetric encryption scheme. So Game 7 is computationally indistinguishable from Game 8.Lemma 8.
The outputs of Game 8 and Game 9 are computationally indistinguishable whenSE.KeyGen,SE.Enc,SE.Dec is a semantically secure symmetric encryption scheme.Proof.
Since the proof method of this lemma is the same as that of lemma 4, the proof process is omitted here.Lemma 9.
The outputs of Game 9 and Game 10 are computationally indistinguishable whenPKE.KeyGen,PKE.Enc,PKE.Dec is a semantically secure public key encryption scheme.Proof.
Since the proof method of this lemma is the same as that of lemma 4, the proof process is omitted here.Lemma 10.
Game 10 and Game 11 are computationally indistinguishable whenNIWI is statistically sound, Com is perfectly binding, and iO is an indistinguishable obfuscator.Proof.
Since the proof method of this lemma is the same as that of lemma 5, the proof process is omitted here.Lemma 11.
The outputs of Game 11 and Game 12 are computationally indistinguishable whenPKE.KeyGen,PKE.Enc,PKE.Dec is a semantically secure public key encryption scheme.Proof.
Since the proof method of this lemma is the same as that of lemma 4, the proof process is omitted here.Lemma 12.
Because of witness indistinguishability ofNIWI, Game 12 and Game 13 are computationally indistinguishable.Proof.
Since the proof method of this lemma is the same as that of lemma 3, the proof process is omitted here.Lemma 13.
Game 13 is computationally indistinguishable from Game 14 whenCom is a computationally hiding commitment scheme.Proof.
Since the proof method of this lemma is the same as that of lemma 2, the proof process is omitted here.


## 6. Conclusion

We firstly design a function encryption scheme using the key encapsulation mechanism in this paper. This mechanism combines public key encryption with symmetric encryption. We encrypt the message using symmetric encryption, and then we encrypt the key of symmetric encryption using public key encryption. In the construction of function encryption scheme, we use noninteractive witness indistinguishable proof, commitment scheme, and indistinguishable obfuscator. Finally, the indistinguishable security of the designed function encryption is proven.



---

*Source: 8567534-2019-11-05.xml*