# An Approach Enabling Various Queries on Encrypted Industrial Data Stream

Authors: Tao Wang; Bo Yang; Guoyong Qiu; Lina Zhang; Yong Yu; Yanwei Zhou; Juncai Guo
Journal: Security and Communication Networks
 (2019)

---

## Abstract

Massive data are generated and collected by devices in the industrial Internet of Things. Data sources would encrypt the data and send them to the data center through the gateway. For some supervision purpose, the gateway needs to observe the encrypted data stream and label the suspicious data. Instead of decrypting ciphertext at the gateway, which is not efficient, this paper presents aΦ-searchable functional encryption scheme that supports inner product evaluations on encrypted data. Based on this scheme, an approach enabling various queries on the encrypted industrial data stream is proposed. The adaptive security of our proposed underlying functional encryption scheme can be proven under general subgroup decision assumptions, and our scheme has the smaller public key, the smaller secret key, and the smaller ciphertext size compared to the related schemes. In addition, the experimental results show that our proposed scheme is efficient. Especially for the gateway, querying on the encrypted data only needs less than 20ms, which is practical for industrial data stream auditing scenario.


---

## Body

## 1. Introduction

### 1.1. Motivation

While manufacturers, mobile end systems, security cameras, wearable devices, and so forth have been generating highly distributed data from various systems, devices, and applications in industrial Internet of Things (iIoT), more and more data are gathered and intensively exploited by many organizations to extract valuable information either to make marketing decisions, track specific behaviours, or detect threat attacks. Big Data gives a huge opportunity to industries and decisions-makers, but it also represents a big risk for users. Due to data breaches, private information is leaked now and then [1, 2]. It is clear that safeguarding private data to protect manufacturers, sensitive customers, or patients is paramount [3, 4]. But, for massive manufacturers and health and financial organizations, actually implementing the best controls and security is challenging, especially when troves of data originate from multiple sources and are stored across singular or multiple databases and data warehouses.Using encryption for sensitive information can effectively protect privacy [5]. But, paradoxically, encryption will destroy the usability of data. Especially for real-time industrial application’s traffic, how to monitor or audit the encrypted data stream is a key problem. For example, as shown in Figure 1, a card payment gateway would observe the transaction stream, which often includes encrypted data between acquiring banks and issuing banks. The payment gateway needs to audit all encrypted data streams to label some suspicious transactions, say, whose value is over $10000. One solution is to encrypt all transactions under the card company’s public key and give the private key to the payment gateway, which can decrypt the transactions stream to do auditing. This solution has two obvious drawbacks. One is being not efficient, because decryption needs to be done for every transaction passing by. Another drawback is that it is bad for both security and privacy concerns, because when the gateway holds the card company’s private key, he can see everything he wants.Figure 1
Card payment gateway observes transactions.This work proposes aΦ-searchable functional encryption scheme that supports various types of queries on the encrypted data such as conjunctions, disjunctions, DNFs/CNFs, polynomial equations, and inner products. By utilizing this scheme, we show an approach that can enable the auditing gateways to query or to evaluate the encrypted data stream passing by.


### 1.2. Related Work

Querying on encrypted data is a long-term interesting open problem in applications with secure and privacy-preserved concerns. Encryption schemes supporting queries on ciphertext are called searchable encryption (SE) schemes, which have two different types of research roadmap. One is searchable symmetric encryption (SSE) [6–12]. The other is public key encryption with keyword search (PEKS) [13–16]. SSE is more efficient but less expressive, and it is hard to achieve privacy for search pattern and access pattern. PEKS is easy to support phrase search and even more complicated evaluations on encrypted data, such as conjunctive, subset, range [14–16], DNF/CNF, polynomial equation, inner product [15, 16], and negation [16]. However, PEKS often has much more computation overheads than SSE due to doing paring computations. There are more recent works for improving security [17, 18], improving functionality [19, 20], and improving performance [21] for the PEKS. Boneh et al. showed that PEKS implies IBE [13]. So, in some sense, an SE scheme is a special form of functional encryption. Brent Waters first publicly used the notion of functional encryption in his talkFunctional Encryption: Beyond Public Key Cryptography, and Boneh et al. formally defined functional encryption [22]. There was a long-standing open feasibility problem in cryptography:Does there exist a functional encryption scheme supporting all polynomial-size circuits? Until 2013, Garg et al. [23] had shown a method to construct functional encryption schemes for polynomial-size circuits based on the indistinguishability obfuscation [24]. Functional encryption has most powerful expressive ability, which can express identity-based encryption (IBE) [25, 26], ABE [27, 28], predicate encryption [14, 15], and inner product encryption [15, 29]. In functional encryption systems, a user who has a decryption key can learn a function of ciphertext. Roughly speaking, in a functional encryption system for functionality F
·
,
·, an authority holding a master secret key can generate a key s
k
K in which the key attribute  K   is encoded and that enables the computation of the function F
K
,
· on encrypted data which encoded the ciphertext attribute  A. More specifically, the user can compute F
K
,
M using s
k
K from encryption of plaintext M. We will show the formal definition and security notion of the functional encryption in Section 2.


### 1.3. Our Approaches and Results

Boneh, Sahai, and Waters have firstly presented formal syntax and put forth a general framework of functional encryption [22]. They also defined two subclasses of functional encryption which are predicate encryption and predicate encryption with public index. In predicate encryption subclass, a functional encryption scheme is defined in terms of a polynomial-time predicate P
:
Σ
K
×
Σ
A
→
{
0,1
}, where Σ
K is key attributes space and Σ
A is ciphertext attributes space. Formally, the functional encryption is defined as(1)
F
K
∈
Σ
K
,
A
,
M
≔
M
i
f
P
K
A
=
1
⊥
i
f
P
K
A
=
0Consequently, if P
K
(
A
)
=
1, decryption algorithm can recover plaintext and, otherwise, get nothing about the plaintext.Inspired by theΦ-searchable public key system proposed by Boneh and Waters [9], this paper describes a new functional encryption construction, that is, Φ-searchable functional encryption system providing security against adaptive adversaries and supporting conjunctive, subset, range, DNF/CNF, polynomial equation, and inner product on encrypted data. We use the predicate encryption subclass to express our functional encryption scheme. We will show the formal definition and security notion of the Φ-searchable functional encryption system in Section 3.For encoding the key attribute into the secret key and encoding the ciphertext attribute into ciphertext, we follow the inner product encryption (IPE) methodology [15, 29] to realize the predicate P
K
(
A
), which means P
K
(
A
)
=
1 if the inner product of key attribute vector K and ciphertext attribute vector A  is 0 and P
K
(
A
)
=
0 otherwise. Formally, for some K
∈
Σ
K and  A
∈
Σ
A, a predicateP over Σ
K
×
Σ
A is defined as(2)
P
K
A
≔
1
i
f
K
,
A
=
0
0
O
t
h
e
r
w
i
s
eThanks to “inner-product” style construction, our scheme supports any kind of inner product queries on encrypted data. Clearly, our scheme supports the equality test directly. To achieve this, for the attributeA
′ set  A
≔
(
-
A
′
,
1
) and encrypt a message M with  A
.In order to generate a secret key for the attribute  K
′, set K
≔
(
1
,
K
′
). Since K
,
A
=
0 if and only if K
′
=
A
′, correctness and security follow. Our scheme also supports the polynomial evaluation after we encode the coefficient of a univariate polynomial into secret keys and encode the univariate into ciphertexts. As a positive result, we can use the polynomial evaluation to achieve supporting conjunctions, disjunctions, CNF, and DNF formulas. We defer the details of applications of our scheme to Section 6.Our construction relies on general subgroup decision assumptions in composite-order groups which are described in Section2. We follow the standard Lewko-Waters [30] proof methodology to prove adaptive security of our construction. We propose a Φ-searchable functional encryption system which supports various evaluations on encrypted data including equality, comparison, subset tests, and polynomial evaluations as well as conjunctions, disjunctions, CNF, and DNF formulas. Moreover, compared to the prior constructions that are built for inner product evaluations on encrypted data in composite-order bilinear groups [15, 31], our scheme not only has the adaptive security but also has a smaller public key, smaller secret key, and smaller ciphertext size.From our proposed searchable encryption scheme, we present an approach enabling various queries on encrypted industrial data for general data flow structure, which includes data sources, gateway, and data center. Our proposed approach makes the gateway easily observe the encrypted data stream passing by sent by the data sources to the data center without decryption. Moreover, if the encrypted data passing by is not matching with some condition, the gateway will learn nothing about the data. From performance evaluation results, the gateway’s overhead is less than 20ms which is practical for application in the scenario of querying on the encrypted industrial data stream. We will show our proposed approach in Section6.1.


## 1.1. Motivation

While manufacturers, mobile end systems, security cameras, wearable devices, and so forth have been generating highly distributed data from various systems, devices, and applications in industrial Internet of Things (iIoT), more and more data are gathered and intensively exploited by many organizations to extract valuable information either to make marketing decisions, track specific behaviours, or detect threat attacks. Big Data gives a huge opportunity to industries and decisions-makers, but it also represents a big risk for users. Due to data breaches, private information is leaked now and then [1, 2]. It is clear that safeguarding private data to protect manufacturers, sensitive customers, or patients is paramount [3, 4]. But, for massive manufacturers and health and financial organizations, actually implementing the best controls and security is challenging, especially when troves of data originate from multiple sources and are stored across singular or multiple databases and data warehouses.Using encryption for sensitive information can effectively protect privacy [5]. But, paradoxically, encryption will destroy the usability of data. Especially for real-time industrial application’s traffic, how to monitor or audit the encrypted data stream is a key problem. For example, as shown in Figure 1, a card payment gateway would observe the transaction stream, which often includes encrypted data between acquiring banks and issuing banks. The payment gateway needs to audit all encrypted data streams to label some suspicious transactions, say, whose value is over $10000. One solution is to encrypt all transactions under the card company’s public key and give the private key to the payment gateway, which can decrypt the transactions stream to do auditing. This solution has two obvious drawbacks. One is being not efficient, because decryption needs to be done for every transaction passing by. Another drawback is that it is bad for both security and privacy concerns, because when the gateway holds the card company’s private key, he can see everything he wants.Figure 1
Card payment gateway observes transactions.This work proposes aΦ-searchable functional encryption scheme that supports various types of queries on the encrypted data such as conjunctions, disjunctions, DNFs/CNFs, polynomial equations, and inner products. By utilizing this scheme, we show an approach that can enable the auditing gateways to query or to evaluate the encrypted data stream passing by.


## 1.2. Related Work

Querying on encrypted data is a long-term interesting open problem in applications with secure and privacy-preserved concerns. Encryption schemes supporting queries on ciphertext are called searchable encryption (SE) schemes, which have two different types of research roadmap. One is searchable symmetric encryption (SSE) [6–12]. The other is public key encryption with keyword search (PEKS) [13–16]. SSE is more efficient but less expressive, and it is hard to achieve privacy for search pattern and access pattern. PEKS is easy to support phrase search and even more complicated evaluations on encrypted data, such as conjunctive, subset, range [14–16], DNF/CNF, polynomial equation, inner product [15, 16], and negation [16]. However, PEKS often has much more computation overheads than SSE due to doing paring computations. There are more recent works for improving security [17, 18], improving functionality [19, 20], and improving performance [21] for the PEKS. Boneh et al. showed that PEKS implies IBE [13]. So, in some sense, an SE scheme is a special form of functional encryption. Brent Waters first publicly used the notion of functional encryption in his talkFunctional Encryption: Beyond Public Key Cryptography, and Boneh et al. formally defined functional encryption [22]. There was a long-standing open feasibility problem in cryptography:Does there exist a functional encryption scheme supporting all polynomial-size circuits? Until 2013, Garg et al. [23] had shown a method to construct functional encryption schemes for polynomial-size circuits based on the indistinguishability obfuscation [24]. Functional encryption has most powerful expressive ability, which can express identity-based encryption (IBE) [25, 26], ABE [27, 28], predicate encryption [14, 15], and inner product encryption [15, 29]. In functional encryption systems, a user who has a decryption key can learn a function of ciphertext. Roughly speaking, in a functional encryption system for functionality F
·
,
·, an authority holding a master secret key can generate a key s
k
K in which the key attribute  K   is encoded and that enables the computation of the function F
K
,
· on encrypted data which encoded the ciphertext attribute  A. More specifically, the user can compute F
K
,
M using s
k
K from encryption of plaintext M. We will show the formal definition and security notion of the functional encryption in Section 2.


## 1.3. Our Approaches and Results

Boneh, Sahai, and Waters have firstly presented formal syntax and put forth a general framework of functional encryption [22]. They also defined two subclasses of functional encryption which are predicate encryption and predicate encryption with public index. In predicate encryption subclass, a functional encryption scheme is defined in terms of a polynomial-time predicate P
:
Σ
K
×
Σ
A
→
{
0,1
}, where Σ
K is key attributes space and Σ
A is ciphertext attributes space. Formally, the functional encryption is defined as(1)
F
K
∈
Σ
K
,
A
,
M
≔
M
i
f
P
K
A
=
1
⊥
i
f
P
K
A
=
0Consequently, if P
K
(
A
)
=
1, decryption algorithm can recover plaintext and, otherwise, get nothing about the plaintext.Inspired by theΦ-searchable public key system proposed by Boneh and Waters [9], this paper describes a new functional encryption construction, that is, Φ-searchable functional encryption system providing security against adaptive adversaries and supporting conjunctive, subset, range, DNF/CNF, polynomial equation, and inner product on encrypted data. We use the predicate encryption subclass to express our functional encryption scheme. We will show the formal definition and security notion of the Φ-searchable functional encryption system in Section 3.For encoding the key attribute into the secret key and encoding the ciphertext attribute into ciphertext, we follow the inner product encryption (IPE) methodology [15, 29] to realize the predicate P
K
(
A
), which means P
K
(
A
)
=
1 if the inner product of key attribute vector K and ciphertext attribute vector A  is 0 and P
K
(
A
)
=
0 otherwise. Formally, for some K
∈
Σ
K and  A
∈
Σ
A, a predicateP over Σ
K
×
Σ
A is defined as(2)
P
K
A
≔
1
i
f
K
,
A
=
0
0
O
t
h
e
r
w
i
s
eThanks to “inner-product” style construction, our scheme supports any kind of inner product queries on encrypted data. Clearly, our scheme supports the equality test directly. To achieve this, for the attributeA
′ set  A
≔
(
-
A
′
,
1
) and encrypt a message M with  A
.In order to generate a secret key for the attribute  K
′, set K
≔
(
1
,
K
′
). Since K
,
A
=
0 if and only if K
′
=
A
′, correctness and security follow. Our scheme also supports the polynomial evaluation after we encode the coefficient of a univariate polynomial into secret keys and encode the univariate into ciphertexts. As a positive result, we can use the polynomial evaluation to achieve supporting conjunctions, disjunctions, CNF, and DNF formulas. We defer the details of applications of our scheme to Section 6.Our construction relies on general subgroup decision assumptions in composite-order groups which are described in Section2. We follow the standard Lewko-Waters [30] proof methodology to prove adaptive security of our construction. We propose a Φ-searchable functional encryption system which supports various evaluations on encrypted data including equality, comparison, subset tests, and polynomial evaluations as well as conjunctions, disjunctions, CNF, and DNF formulas. Moreover, compared to the prior constructions that are built for inner product evaluations on encrypted data in composite-order bilinear groups [15, 31], our scheme not only has the adaptive security but also has a smaller public key, smaller secret key, and smaller ciphertext size.From our proposed searchable encryption scheme, we present an approach enabling various queries on encrypted industrial data for general data flow structure, which includes data sources, gateway, and data center. Our proposed approach makes the gateway easily observe the encrypted data stream passing by sent by the data sources to the data center without decryption. Moreover, if the encrypted data passing by is not matching with some condition, the gateway will learn nothing about the data. From performance evaluation results, the gateway’s overhead is less than 20ms which is practical for application in the scenario of querying on the encrypted industrial data stream. We will show our proposed approach in Section6.1.


## 2. Preliminaries

### 2.1. Notations

Given two vectorsU
=
(
u
1
,
u
2
,
.
.
.
,
u
d
)
∈
Z
N
d and V
=
(
v
1
,
v
2
,
.
.
.
,
v
d
)
∈
Z
N
d, we use the notation U
,
V to denote dot product U
T
V. For a group element g, we use g
U to denote a vector (
g
u
1
,
g
u
2
,
.
.
.
,
g
u
d
).


### 2.2. Syntax of Functional Encryption

We now describe the definition of functional encryption for a functionalityF
:
Σ
A
×
Σ
K
→
{
0,1
}, where Σ
A denotes the ciphertext attributes space and Σ
K denotes the key attributes space [22].Definition 1.
ForF, a functional encryption scheme consists of four PPT algorithms (Setup, Keygen, Enc, and Dec): for all A
∈
Σ
A and K
∈
Σ
K, the algorithm Setup(
1
λ
) generates public parameters p
p and master secret key m
k, the algorithm Keygen(
m
k
,
K
) outputs secret key for K, the algorithm Enc(
p
p
,
M
,
A
) generates ciphertext for a message M
∈
M, and Dec(
s
k
K
,
c
) uses s
k
K to compute y
=
F
(
K
,
M
) from c
.


### 2.3. Security Notion of Functional Encryption

Before defining the security of functional encryption, we need to describe a restriction for the adversary. Observe that, after the adversary gets the secret keys he wants, he will submit two distinct messagesM
0
,
M
1
∈
M. The challenger randomly chooses one to encrypt and sends the ciphertext c to the adversary. Therefore, we need to restrict M
0 and M
1 chosen by the adversary and for all K that the adversary has s
k
K, we require that(3)
F
K
,
M
0
=
F
K
,
M
1Clearly, if this restriction is not satisfied, that is, if the adversary hass
k
K for some K, he can trivially break the semantic security of the scheme by testing whether Dec(
s
k
K
,
c
) = F
(
K
,
M
0
) or not.For a functional encryption schemeE, b
∈
{
0,1
} and, for an adversary A, define an experiment as follows:(i)
Setup. Run S
e
t
u
p
(
1
λ
), get (
p
p
,
m
k
), and send p
p to A.
(ii)
Query phase1. A adaptively makes queries by submitting K
i
∈
Σ
K, where i
=
1,2
,
.
.
., and receives s
k
K
i
←
K
e
y
g
e
n
(
m
k
,
K
i
).
(iii)
Challenge. A outputs two messages M
0
,
M
1
∈
M satisfying the above restriction and receives E
n
c
(
p
p
,
M
b
).
(iv)
Query phase2. A continues to make queries for some K
i as query phase1 subject to the restriction and finally outputs a bit.Forb, define(4)
A
d
v
A
E
λ
≔
Pr
⁡
b
′
=
b
-
1
2Definition 2.
If, for allP
P
T
A, A
d
v
A
E
(
λ
) is negligible, we say a functional encryption scheme E is secure.


### 2.4. Assumptions over Composite-Order Bilinear Groups

Bilinear Groups of Composite Order. Composite-order bilinear groups were first introduced by Boneh et al. [32] and used by many researchers [15, 33, 34]. Let G be a group generator that takes a security parameter 1
n as input and outputs (
p
,
q
,
r
,
G
,
G
T
,
e
^
), where G and G
T are two cyclic groups of order N
=
p
×
q
×
r, where p
,
q
,
r are three distinct primes, and e
^
:
G
×
G
→
G
T is a function satisfying the following properties:(i)
Bilinear: ∀
g
1
,
g
2
∈
G, x
,
y
∈
Z
N, and e
^
(
g
1
x
,
g
2
y
)
=
e
^
(
g
1
,
g
2
)
x
y.
(ii)
Nondegenerate: ∃
g
∈
G such that e
^
(
g
,
g
) has order N in G
T.
(iii)
Cancellation: let G
p, G
q, and G
r be subgroups of G with order p
,
q, and r, respectively. For some elements h
1 and h
2 from distinct subgroups, we have(5)
e
^
h
1
,
h
2
=
1To see this, we note that G
=
G
p
×
G
q
×
G
r and also note that if g
∈
G is a generator of G, then g
p
q generates G
r; g
p
r generates G
q; g
q
r generates G
p. Hence, for some elements h
1 and h
2 from distinct subgroups (e.g., h
1
=
h
p
∈
G
p and h
2
=
h
q
∈
G
q), h
p
=
(
g
q
r
)
β (for some β) and h
q
=
(
g
p
r
)
γ (for some γ). So, we note that e
^
(
h
p
,
h
q
)
=
e
^
(
(
g
q
r
)
β
,
g
p
r
)
γ
=
e
^
(
g
β
,
g
r
γ
)
p
q
r
=
1.Cryptographic Assumptions. Our construction relies on the general subgroup decision assumptions in composite-order groups [33]. We now give the following three assumptions.Assumption 3.
LetG be a group generator as above, and define the following distribution:(6)
p
,
q
,
r
,
G
,
G
T
,
e
^
←
$
G
1
n
,
N
=
p
×
q
×
r
,
g
←
$
G
p
,
X
3
←
$
G
r
,
D
=
N
,
G
,
G
T
,
e
^
,
g
,
X
3
,
T
0
←
$
G
p
q
,
T
1
←
$
G
p
,where G
p
q is the subgroup of G with order p
q. Define A’s advantage in breaking Assumption 3 as(7)
A
d
v
G
,
A
S
D
1
λ
≔
Pr
⁡
A
D
,
T
0
=
1
-
Pr
⁡
A
D
,
T
1
=
1Definition 4.
For any ppt algorithmA, if A’s advantage in breaking Assumption 3 and A
d
v
G
,
A
S
D
1
(
λ
) is negligible, we say that G satisfies Assumption 3.Assumption 5.
LetG be a group generator as above, and define the following distribution:(8)
p
,
q
,
r
,
G
,
G
T
,
e
^
←
$
G
1
n
,
N
=
p
×
q
×
r
,
g
,
X
1
←
$
G
p
,
X
2
,
Y
2
←
$
G
q
,
X
3
Y
3
←
$
G
r
,
D
=
N
,
G
,
G
T
,
e
^
,
g
,
X
1
X
2
,
X
3
,
Y
2
Y
3
,
T
0
←
$
G
,
T
1
←
$
G
p
r
,where G
q
r is the subgroup of G with order q
r. Define A’s advantage in breaking Assumption 5 as(9)
A
d
v
G
,
A
S
D
2
λ
≔
Pr
⁡
A
D
,
T
0
=
1
-
Pr
⁡
A
D
,
T
1
=
1Definition 6.
For any ppt algorithmA, if A’s advantage in breaking Assumption 5 and A
d
v
G
,
A
S
D
2
(
λ
) is negligible, we say that G satisfies Assumption 5.Assumption 7.
LetG be a group generator as above, and define the following distribution:(10)
p
,
q
,
r
,
G
,
G
T
,
e
^
←
$
G
1
n
,
N
=
p
×
q
×
r
,
α
,
s
←
$
Z
N
g
←
$
G
p
,
X
2
,
Y
2
,
Z
2
←
$
G
q
,
X
3
←
$
G
r
,
D
=
N
,
G
,
G
T
,
e
^
,
g
,
g
α
X
2
,
X
3
,
g
s
Y
2
,
Z
2
,
T
0
=
e
^
g
,
g
α
s
,
T
1
←
$
G
T
.Define A’s advantage in breaking Assumption 7 as(11)
A
d
v
G
,
A
S
D
3
λ
≔
Pr
⁡
A
D
,
T
0
=
1
-
Pr
⁡
A
D
,
T
1
=
1Definition 8.
For any ppt algorithmA, if A’s advantage in breaking Assumption 7 and A
d
v
G
,
A
S
D
3
(
λ
) is negligible, we say that G satisfies Assumption 7.


### 2.5. Dual System Encryption

Brent Waters firstly introduced a methodology to build adaptively secure IBE and HIBE which is dual system encryption [35], and a lot of work relied on this powerful proof tool [33, 36–38]. In dual system encryption schemes, there are two forms of ciphertext and key: normal and semifunctional. The semifunctional ciphertext and key are only used in the hybrid security proof, while normal ciphertext and key are used in the real system. A normal ciphertext can be decrypted correctly by either normal key or semifunctional key. But semifunctional key cannot decrypt a semifunctional ciphertext, whereas only normal key can. The hybrid security games advance one by one, and the first one is real security game, while in the last one the ciphertext is replaced by encryption of a random message. The most important part of the proof is to show two consecutive games are indistinguishable.


## 2.1. Notations

Given two vectorsU
=
(
u
1
,
u
2
,
.
.
.
,
u
d
)
∈
Z
N
d and V
=
(
v
1
,
v
2
,
.
.
.
,
v
d
)
∈
Z
N
d, we use the notation U
,
V to denote dot product U
T
V. For a group element g, we use g
U to denote a vector (
g
u
1
,
g
u
2
,
.
.
.
,
g
u
d
).


## 2.2. Syntax of Functional Encryption

We now describe the definition of functional encryption for a functionalityF
:
Σ
A
×
Σ
K
→
{
0,1
}, where Σ
A denotes the ciphertext attributes space and Σ
K denotes the key attributes space [22].Definition 1.
ForF, a functional encryption scheme consists of four PPT algorithms (Setup, Keygen, Enc, and Dec): for all A
∈
Σ
A and K
∈
Σ
K, the algorithm Setup(
1
λ
) generates public parameters p
p and master secret key m
k, the algorithm Keygen(
m
k
,
K
) outputs secret key for K, the algorithm Enc(
p
p
,
M
,
A
) generates ciphertext for a message M
∈
M, and Dec(
s
k
K
,
c
) uses s
k
K to compute y
=
F
(
K
,
M
) from c
.


## 2.3. Security Notion of Functional Encryption

Before defining the security of functional encryption, we need to describe a restriction for the adversary. Observe that, after the adversary gets the secret keys he wants, he will submit two distinct messagesM
0
,
M
1
∈
M. The challenger randomly chooses one to encrypt and sends the ciphertext c to the adversary. Therefore, we need to restrict M
0 and M
1 chosen by the adversary and for all K that the adversary has s
k
K, we require that(3)
F
K
,
M
0
=
F
K
,
M
1Clearly, if this restriction is not satisfied, that is, if the adversary hass
k
K for some K, he can trivially break the semantic security of the scheme by testing whether Dec(
s
k
K
,
c
) = F
(
K
,
M
0
) or not.For a functional encryption schemeE, b
∈
{
0,1
} and, for an adversary A, define an experiment as follows:(i)
Setup. Run S
e
t
u
p
(
1
λ
), get (
p
p
,
m
k
), and send p
p to A.
(ii)
Query phase1. A adaptively makes queries by submitting K
i
∈
Σ
K, where i
=
1,2
,
.
.
., and receives s
k
K
i
←
K
e
y
g
e
n
(
m
k
,
K
i
).
(iii)
Challenge. A outputs two messages M
0
,
M
1
∈
M satisfying the above restriction and receives E
n
c
(
p
p
,
M
b
).
(iv)
Query phase2. A continues to make queries for some K
i as query phase1 subject to the restriction and finally outputs a bit.Forb, define(4)
A
d
v
A
E
λ
≔
Pr
⁡
b
′
=
b
-
1
2Definition 2.
If, for allP
P
T
A, A
d
v
A
E
(
λ
) is negligible, we say a functional encryption scheme E is secure.


## 2.4. Assumptions over Composite-Order Bilinear Groups

Bilinear Groups of Composite Order. Composite-order bilinear groups were first introduced by Boneh et al. [32] and used by many researchers [15, 33, 34]. Let G be a group generator that takes a security parameter 1
n as input and outputs (
p
,
q
,
r
,
G
,
G
T
,
e
^
), where G and G
T are two cyclic groups of order N
=
p
×
q
×
r, where p
,
q
,
r are three distinct primes, and e
^
:
G
×
G
→
G
T is a function satisfying the following properties:(i)
Bilinear: ∀
g
1
,
g
2
∈
G, x
,
y
∈
Z
N, and e
^
(
g
1
x
,
g
2
y
)
=
e
^
(
g
1
,
g
2
)
x
y.
(ii)
Nondegenerate: ∃
g
∈
G such that e
^
(
g
,
g
) has order N in G
T.
(iii)
Cancellation: let G
p, G
q, and G
r be subgroups of G with order p
,
q, and r, respectively. For some elements h
1 and h
2 from distinct subgroups, we have(5)
e
^
h
1
,
h
2
=
1To see this, we note that G
=
G
p
×
G
q
×
G
r and also note that if g
∈
G is a generator of G, then g
p
q generates G
r; g
p
r generates G
q; g
q
r generates G
p. Hence, for some elements h
1 and h
2 from distinct subgroups (e.g., h
1
=
h
p
∈
G
p and h
2
=
h
q
∈
G
q), h
p
=
(
g
q
r
)
β (for some β) and h
q
=
(
g
p
r
)
γ (for some γ). So, we note that e
^
(
h
p
,
h
q
)
=
e
^
(
(
g
q
r
)
β
,
g
p
r
)
γ
=
e
^
(
g
β
,
g
r
γ
)
p
q
r
=
1.Cryptographic Assumptions. Our construction relies on the general subgroup decision assumptions in composite-order groups [33]. We now give the following three assumptions.Assumption 3.
LetG be a group generator as above, and define the following distribution:(6)
p
,
q
,
r
,
G
,
G
T
,
e
^
←
$
G
1
n
,
N
=
p
×
q
×
r
,
g
←
$
G
p
,
X
3
←
$
G
r
,
D
=
N
,
G
,
G
T
,
e
^
,
g
,
X
3
,
T
0
←
$
G
p
q
,
T
1
←
$
G
p
,where G
p
q is the subgroup of G with order p
q. Define A’s advantage in breaking Assumption 3 as(7)
A
d
v
G
,
A
S
D
1
λ
≔
Pr
⁡
A
D
,
T
0
=
1
-
Pr
⁡
A
D
,
T
1
=
1Definition 4.
For any ppt algorithmA, if A’s advantage in breaking Assumption 3 and A
d
v
G
,
A
S
D
1
(
λ
) is negligible, we say that G satisfies Assumption 3.Assumption 5.
LetG be a group generator as above, and define the following distribution:(8)
p
,
q
,
r
,
G
,
G
T
,
e
^
←
$
G
1
n
,
N
=
p
×
q
×
r
,
g
,
X
1
←
$
G
p
,
X
2
,
Y
2
←
$
G
q
,
X
3
Y
3
←
$
G
r
,
D
=
N
,
G
,
G
T
,
e
^
,
g
,
X
1
X
2
,
X
3
,
Y
2
Y
3
,
T
0
←
$
G
,
T
1
←
$
G
p
r
,where G
q
r is the subgroup of G with order q
r. Define A’s advantage in breaking Assumption 5 as(9)
A
d
v
G
,
A
S
D
2
λ
≔
Pr
⁡
A
D
,
T
0
=
1
-
Pr
⁡
A
D
,
T
1
=
1Definition 6.
For any ppt algorithmA, if A’s advantage in breaking Assumption 5 and A
d
v
G
,
A
S
D
2
(
λ
) is negligible, we say that G satisfies Assumption 5.Assumption 7.
LetG be a group generator as above, and define the following distribution:(10)
p
,
q
,
r
,
G
,
G
T
,
e
^
←
$
G
1
n
,
N
=
p
×
q
×
r
,
α
,
s
←
$
Z
N
g
←
$
G
p
,
X
2
,
Y
2
,
Z
2
←
$
G
q
,
X
3
←
$
G
r
,
D
=
N
,
G
,
G
T
,
e
^
,
g
,
g
α
X
2
,
X
3
,
g
s
Y
2
,
Z
2
,
T
0
=
e
^
g
,
g
α
s
,
T
1
←
$
G
T
.Define A’s advantage in breaking Assumption 7 as(11)
A
d
v
G
,
A
S
D
3
λ
≔
Pr
⁡
A
D
,
T
0
=
1
-
Pr
⁡
A
D
,
T
1
=
1Definition 8.
For any ppt algorithmA, if A’s advantage in breaking Assumption 7 and A
d
v
G
,
A
S
D
3
(
λ
) is negligible, we say that G satisfies Assumption 7.


## 2.5. Dual System Encryption

Brent Waters firstly introduced a methodology to build adaptively secure IBE and HIBE which is dual system encryption [35], and a lot of work relied on this powerful proof tool [33, 36–38]. In dual system encryption schemes, there are two forms of ciphertext and key: normal and semifunctional. The semifunctional ciphertext and key are only used in the hybrid security proof, while normal ciphertext and key are used in the real system. A normal ciphertext can be decrypted correctly by either normal key or semifunctional key. But semifunctional key cannot decrypt a semifunctional ciphertext, whereas only normal key can. The hybrid security games advance one by one, and the first one is real security game, while in the last one the ciphertext is replaced by encryption of a random message. The most important part of the proof is to show two consecutive games are indistinguishable.


## 3. Definition

We first show a definition of aΦ-searchable functional encryption system inspired by the Φ-searchable public key system proposed by Boneh and Waters [14]. Then, we show the definition of the security notion.


### 3.1. Φ-Searchable Functional Encryption System

We useΣ to denote a finite set of binary strings and let Φ be a set of predicates over attributes space Σ. A predicate P
∈
Φ is a map: P
:
Σ
→
{
0,1
}. For two attribute vectors A
,
K
∈
Σ, we use the notion P
K
(
A
)
=
1 to denote that A satisfies P which is related to K. We also follow Boneh et al. [14] to use the termGenToken to denote the algorithm to generate a search or query token instead of the termGenKey, and we use the termQuery to denote the algorithm to query rather than the termDecrypt.Definition 9.
For a predicateP
∈
Φ, a Φ-searchable functional encryption system comprises four algorithms,Setup
(
1
λ
),Encrypt
(
P
K
,
(
A
,
M
)
),GenToken
(
S
K
,
P
K
), andQuery
(
T
K
K
,
C
) such that(i)
Setup
(
1
λ
): a probabilistic algorithm that takes as input a security parameter λ and outputs the public parameters P
P along with the public key P
K and the master secret key S
K.
(ii)
Encrypt
(
P
K
,
(
A
,
M
)
): a probabilistic algorithm that takes as input the public key P
K and a plaintext pair (
A
,
M
). We consider A as the searchable attribute vector of the data M. The algorithm outputs a searchable encryption of (
A
,
M
) under the public key P
K.
(iii)
GenToken
(
S
K
,
P
K
): a probabilistic algorithm that takes the secret key S
K and a description of a predicate P
K as input and outputs a search token T
K
K.
(iv)
Query
(
T
K
K
,
C
): a deterministic algorithm that takes a token T
K
K and a ciphertext C as input and outputs F
(
K
,
M
).
For correctness, we require that, for allλ and all (
P
P
,
P
K
,
S
K
)
←
S
e
t
u
p
(
1
λ
), all P
K
∈
Φ, any token T
K
K
←
GenToken
(
S
K
,
P
K
), and all A
∈
Σ:(i)
IfP
K
(
A
)
=
1, then F
(
K
,
M
)
=
M.
(ii)
IfP
K
(
A
)
=
0, then F
(
K
,
M
)
=
⊥ with all but negligible probability.


### 3.2. Security Notion

We now show a security notion definition of aΦ-searchable functional encryption system.Definition 10.
AΦ-searchable functional encryption system E defined as above is adaptive secure if, for all PPT adversaries A, the advantage of A in the following game is negligible in the security parameters λ:(i)
Setup. The challenger runsSetup
(
1
λ
) and gives the adversary A the P
P and P
K.
(ii)
Query phase 1. A outputs descriptions of predicates P
K
1
,
P
K
2
,
.
.
.
,
P
K
l
1
∈
Φ. The challenger responds with the corresponding tokens:(12)
T
K
K
j
←
G
e
n
T
o
k
e
n
S
K
,
P
K
j
.
(iii)
Challenge. A outputs two pairs of messages (
(
A
0
,
M
0
)
,
(
A
1
,
M
1
)
)
∈
Σ
×
M subject to the following restrictions:(13)
P
K
j
A
0
=
P
K
j
A
1for all P
K
j in predicates list queried at query phase 1 and if M
0
≠
M
1 then (14)
P
K
j
A
0
=
P
K
j
A
1
=
0These two restrictions ensure that the tokens given to the adversary do not trivially break the challenge. The first restriction ensures that tokens given to the adversary do not directly distinguish A
0 from A
1. The second restriction ensures that the tokens do not directly distinguish M
0 from M
1.
The challenger randomly choosesb
∈
{
0,1
} and gives C
←
Encrypt
(
P
K
,
(
A
b
,
M
b
)
) to A.(iv)
Query phase 2. A continues to output adaptively descriptions of predicates P
K
l
1
+
1
,
.
.
.
,
P
K
l
∈
Φ, subject to the two restrictions (13) and (14). The challenger responds with the corresponding tokens T
K
K
j
←
GenToken
(
S
K
,
P
K
j
).
(v)
Guess. A outputs a bit b
′ and wins if b
′
=
b.
The adversaryA’s advantage in breaking E is A
d
v
A
=
|
P
r
[
b
′
=
b
]
-
1
/
2
|.


## 3.1. Φ-Searchable Functional Encryption System

We useΣ to denote a finite set of binary strings and let Φ be a set of predicates over attributes space Σ. A predicate P
∈
Φ is a map: P
:
Σ
→
{
0,1
}. For two attribute vectors A
,
K
∈
Σ, we use the notion P
K
(
A
)
=
1 to denote that A satisfies P which is related to K. We also follow Boneh et al. [14] to use the termGenToken to denote the algorithm to generate a search or query token instead of the termGenKey, and we use the termQuery to denote the algorithm to query rather than the termDecrypt.Definition 9.
For a predicateP
∈
Φ, a Φ-searchable functional encryption system comprises four algorithms,Setup
(
1
λ
),Encrypt
(
P
K
,
(
A
,
M
)
),GenToken
(
S
K
,
P
K
), andQuery
(
T
K
K
,
C
) such that(i)
Setup
(
1
λ
): a probabilistic algorithm that takes as input a security parameter λ and outputs the public parameters P
P along with the public key P
K and the master secret key S
K.
(ii)
Encrypt
(
P
K
,
(
A
,
M
)
): a probabilistic algorithm that takes as input the public key P
K and a plaintext pair (
A
,
M
). We consider A as the searchable attribute vector of the data M. The algorithm outputs a searchable encryption of (
A
,
M
) under the public key P
K.
(iii)
GenToken
(
S
K
,
P
K
): a probabilistic algorithm that takes the secret key S
K and a description of a predicate P
K as input and outputs a search token T
K
K.
(iv)
Query
(
T
K
K
,
C
): a deterministic algorithm that takes a token T
K
K and a ciphertext C as input and outputs F
(
K
,
M
).
For correctness, we require that, for allλ and all (
P
P
,
P
K
,
S
K
)
←
S
e
t
u
p
(
1
λ
), all P
K
∈
Φ, any token T
K
K
←
GenToken
(
S
K
,
P
K
), and all A
∈
Σ:(i)
IfP
K
(
A
)
=
1, then F
(
K
,
M
)
=
M.
(ii)
IfP
K
(
A
)
=
0, then F
(
K
,
M
)
=
⊥ with all but negligible probability.


## 3.2. Security Notion

We now show a security notion definition of aΦ-searchable functional encryption system.Definition 10.
AΦ-searchable functional encryption system E defined as above is adaptive secure if, for all PPT adversaries A, the advantage of A in the following game is negligible in the security parameters λ:(i)
Setup. The challenger runsSetup
(
1
λ
) and gives the adversary A the P
P and P
K.
(ii)
Query phase 1. A outputs descriptions of predicates P
K
1
,
P
K
2
,
.
.
.
,
P
K
l
1
∈
Φ. The challenger responds with the corresponding tokens:(12)
T
K
K
j
←
G
e
n
T
o
k
e
n
S
K
,
P
K
j
.
(iii)
Challenge. A outputs two pairs of messages (
(
A
0
,
M
0
)
,
(
A
1
,
M
1
)
)
∈
Σ
×
M subject to the following restrictions:(13)
P
K
j
A
0
=
P
K
j
A
1for all P
K
j in predicates list queried at query phase 1 and if M
0
≠
M
1 then (14)
P
K
j
A
0
=
P
K
j
A
1
=
0These two restrictions ensure that the tokens given to the adversary do not trivially break the challenge. The first restriction ensures that tokens given to the adversary do not directly distinguish A
0 from A
1. The second restriction ensures that the tokens do not directly distinguish M
0 from M
1.
The challenger randomly choosesb
∈
{
0,1
} and gives C
←
Encrypt
(
P
K
,
(
A
b
,
M
b
)
) to A.(iv)
Query phase 2. A continues to output adaptively descriptions of predicates P
K
l
1
+
1
,
.
.
.
,
P
K
l
∈
Φ, subject to the two restrictions (13) and (14). The challenger responds with the corresponding tokens T
K
K
j
←
GenToken
(
S
K
,
P
K
j
).
(v)
Guess. A outputs a bit b
′ and wins if b
′
=
b.
The adversaryA’s advantage in breaking E is A
d
v
A
=
|
P
r
[
b
′
=
b
]
-
1
/
2
|.


## 4. Our Construction

Our construction is based on general subgroup decision assumptions in composite-order groups, that is, Assumptions3, 5, and 7. Let Φ be a set of predicates over Σ (in our construction, Σ
≔
Z
N
d); for a predicate P
∈
Φ, a Φ-searchable functional encryption scheme for P is defined as follows:(i)
Setup
(
1
λ
): this algorithm takes the security parameter λ as input. First, it runs G
(
1
n
) and gets (
p
,
q
,
r
,
G
,
G
T
,
e
^
), where G
=
G
p
×
G
q
×
G
r
(
N
=
p
×
q
×
r
). Then, it computes g
p
,
g
q
,
g
r as a generator of G
p
,
G
q
,
G
r, respectively. In addition, it chooses random α,  x
∈
R
Z
N
∗, and X
∈
R
Z
N
d. Finally, it outputs public parameters P
P
≔
(
G
,
g
p
,
g
r
) along with the public key:(15)
P
K
≔
g
p
x
,
g
p
X
,
e
^
g
p
,
g
p
αIt keepsS
K
≔
(
g
p
α
,
x
,
X
) private as the master secret key.(ii)
Encrypt
(
P
K
,
(
A
,
M
)
): let A
=
(
a
1
,
.
.
.
,
a
d
)
∈
Σ; this algorithm takes the public key P
K and a pair (
A
,
M
) as input and chooses random exponent s
∈
R
Z
N
∗; then it outputs C as the ciphertext, where(16)
C
≔
C
0
≔
e
^
g
p
,
g
p
α
s
∙
M
,
C
1
≔
g
p
s
x
A
+
X
,
1
(iii)
GenToken
(
S
K
,
P
K
): let K
=
(
k
1
,
.
.
.
,
k
d
)
∈
Σ; this algorithm takes as input master secret key S
K and a predicate P
K, in our case that is K itself, and chooses random y
∈
R
Z
N
∗ and W
∈
R
Z
N
d
+
1. Finally, it outputs a token:(17)
T
K
K
≔
g
p
y
K
,
α
-
y
X
,
K
g
r
W
(iv)
Query
(
T
K
K
,
C
): this algorithm takes a token T
K
K for a predicate P
K and a ciphertext C as input; it outputs (18)
F
K
,
M
≔
M
≔
C
0
e
^
C
1
,
T
K
K
P
K
A
=
1
⊥
P
K
A
=
0where(19)
P
K
A
≔
1
i
f
K
,
A
=
0
0
O
t
h
e
r
w
i
s
eCorrectness. Let C and T
K
K be as above. Then (20)
M
=
C
0
e
^
C
1
,
T
K
K
=
e
^
g
p
,
g
p
α
s
·
M
e
^
C
1
,
T
K
K
=
e
^
g
p
,
g
p
α
s
·
M
e
^
g
p
s
x
A
+
X
,
1
,
g
p
y
K
,
α
-
y
X
,
K
g
r
W
=
e
^
g
p
,
g
p
α
s
·
M
e
^
g
p
s
x
A
+
X
,
1
,
g
p
y
K
,
α
-
y
X
,
K
·
e
^
g
p
s
x
A
+
X
,
1
,
g
r
W
=
e
^
g
p
,
g
p
α
s
·
M
e
^
g
p
s
x
A
+
X
,
1
,
g
p
y
K
,
α
-
y
X
,
K
=
e
^
g
p
,
g
p
α
s
·
M
e
^
g
p
s
,
g
p
x
A
+
X
,
1
T
∙
y
K
,
α
-
y
X
,
Kwhere(21)
x
A
+
X
,
1
T
∙
y
K
,
α
-
y
X
,
K
=
x
A
+
X
,
1
T
∙
y
K
+
α
-
y
X
,
K
=
x
y
X
,
K
+
y
X
,
K
+
α
-
y
X
,
K
=
x
y
A
,
K
+
αFor all (
A
,
K
)
∈
A
×
K such that P
K
(
A
)
=
1, which means K
,
A
=
0
m
o
d
N, the data M will be recovered correctly.


## 5. Security Proof

To prove the security of ourΦ-searchable functional encryption scheme, it depends on the above-mentioned assumptions. Before that, we need to define the semifunctional ciphertext and semifunctional token. These additional structures will only be used in our proof, not in the real system.(i)
Semifunctional ciphertext: first, we choose randomly Z
c
∈
R
Z
N
d
+
1; then we can use the algorithmEncrypt
(
P
K
,
(
A
,
M
)
) to construct the normal ciphertext as follows:(22)
C
′
≔
C
0
′
≔
e
^
g
p
,
g
p
α
s
·
M
,
C
1
′
≔
g
p
s
x
A
+
X
,
1
,
and we let the semifunctional ciphertext be(23)
C
^
≔
C
^
0
≔
C
0
′
,
C
^
1
≔
C
1
′
·
g
q
Z
c
(ii)
Semifunctional token: we also use the algorithmGenToken
(
S
K
,
P
K
) to generate the normal token T
K
K
′ and choose a random exponent Z
k
∈
R
Z
N
d
+
1. Then we can construct the semifunctional token as follows:(24)
T
K
K
^
=
T
K
K
′
·
g
q
Z
kRemark. About query (decryption) capabilities, we observe that a normal ciphertext can be decrypted correctly by either normal key or semifunctional key. But semifunctional key cannot decrypt a semifunctional ciphertext, whereas only normal key can because there is an additional blinding factor of e
^
(
g
q
,
g
q
)
Z
c
,
Z
k. But if Z
c and Z
k are orthotropic, the query will still work. We use the term nominally semifunctional token following the definition used by Katz et al. [10] which has components of the subgroup G
q.Now following the dual system encryption methodology presented by Lewko et al. [30], the proof proceeds with a game sequence starting from G
a
m
e
R
e
a
l, which is the real security game, followed by a restricted game G
a
m
e
R
e
s
t
r
i
c
t
e
d which is the same as G
a
m
e
R
e
a
l except that the adversary cannot query for the tokens for attributes that are equal to the challenge attributes A
0
,
A
1. Let l be the number of times of token generation queries that adversary makes. Then we define the following G
a
m
e
k
(
0
≤
k
≤
l
) as follows:(i)
G
a
m
e
0 is the real game except that the challenge ciphertext is semifunctional.
(ii)
G
a
m
e
k
(
0
≤
k
≤
l
) is the same as G
a
m
e
0 except that the first i token generation queries are answered by a semifunctional token, and the last l
-
i token generation queries are answered by a normal token.FollowingG
a
m
e
k, last game is G
a
m
e
F
i
n
a
l, which is identical to G
a
m
e
l, but the challenge ciphertext is not for one of the two messages submitted by the adversary but semifunctional encryption of a random message instead. In the following lemmas, we will prove the indistinguishability between two consecutive games and prove that the adversary A’s view in G
a
m
e
F
i
n
a
l is statistically independent of challenge bit b
′.Lemma 11.
If there is an algorithmA that can distinguish G
a
m
e
R
e
s
t
r
i
c
t
e
d from G
a
m
e
R
e
a
l with advantage of A
d
v
G
a
m
e
R
e
s
t
r
i
c
t
e
d
A
-
A
d
v
G
a
m
e
R
e
a
l
A
=
ϵ, then we can build an algorithm B to break Assumption 3 or Assumption 5 with advantage ϵ
/
2.Proof.
If there exists an adversaryA whose advantage is a nonnegligible ϵ, we can find a nontrivial factor of N with nonnegligible probability and break Assumption 5. The proof methodology is similar to the proof of Lemma 1 in [33].
B sets up the environment for A according to G
a
m
e
R
e
a
l. Suppose that A produces a ciphertext attribute A such that it is not equal to the challenge attributes A
0
∗ and A
1
∗. Since A
≠
A
0
∗, there exists at least one pair of components a
i and a
i
∗ such that a
i
≠
a
i
∗
m
o
d
N, and a
i
-
a
i
∗ can be divided by q, where a
i is a component of A and a
i
∗ is a component of A
0
∗. B can compute d
=
g
c
d
(
a
i
-
a
i
∗
,
N
); set d
′
=
N
/
d. Note that q divides d and N
=
d
d
′
=
p
·
q
·
r. With probability ϵ
/
2, one of these two cases must occur; that is, p divides d
′ or d
=
p
·
q and d
′
=
r. In the case of p dividing d
′, g
d
′ is the identity. Then, given g, B can test whether T
d
′ is the identity. If not, T
∈
G
p
q holds. Otherwise, T
∈
G
p. Then B breaks Assumption 3. In case of d
=
p
·
q and d
′
=
r, given g
,
X
1
X
2
,
X
3
,
Y
2
,
Y
3, B can verify that (
X
1
X
2
)
d is the identity and determine that d
=
p
·
q. Then B can test whether e
^
(
(
Y
2
Y
3
)
d
′
,
T
) is the identity. If not, then T
∈
G holds. Otherwise, T
∈
G
p
r. Then B breaks Assumption 5.Lemma 12.
If there is an algorithmA that can distinguish G
a
m
e
0  from G
a
m
e
R
e
s
t
r
i
c
t
e
d with advantage of A
d
v
G
a
m
e
0
A
-
A
d
v
G
a
m
e
R
e
s
t
r
i
c
t
e
d
A
=
ϵ, then we can build an algorithm B to break Assumption 3 with advantage ϵ
/
2.Proof.
On inputD
=
(
(
N
,
G
,
G
T
,
e
^
)
,
g
p
,
X
3
) and T
∈
{
T
0
,
T
1
}, where T
0
←
$
G
p and T
1
←
$
G
p
q, B simulates A as follows.
Setup. Choose random α, x
∈
R
Z
N, and X
∈
R
Z
N
d; set S
K
≔
(
g
α
,
x
,
X
) and output(25)
P
P
≔
G
,
g
p
,
g
r
,
P
K
≔
g
p
x
,
g
p
X
,
e
^
g
p
,
g
p
α
Token Queries. Each time B is asked to provide a token for a predicate P
K
j, it chooses random y
j
′
∈
R
Z
N
∗ and W
j
′
∈
R
Z
N
d
+
1 and outputs a token:(26)
T
K
K
j
≔
g
p
y
j
′
K
j
,
α
-
y
j
′
X
,
K
j
X
3
W
j
′
Challenge Ciphertext. After receiving two pair of messages (
A
0
,
M
0
)
,
(
A
1
,
M
1
), B chooses random β
∈
R
{
0,1
} and then forms the ciphertext:(27)
C
0
≔
e
^
g
p
,
T
α
·
M
β
,
C
1
≔
T
x
A
β
+
X
,
1It sets the G
p part of T equal g
p
s to implicitly. The correctness of decryption follows clearly. Observe that if T
=
T
0
←
$
G
p, this is a normal ciphertext and we are in G
a
m
e
R
e
s
t
r
i
c
t
e
d. If T
=
T
1
←
$
G
p
q, this is a semifunctional ciphertext; then we are in G
a
m
e
0.Lemma 13.
If there is an algorithmA that can distinguish G
a
m
e
k from G
a
m
e
k
-
1 with advantage of A
d
v
G
a
m
e
k
A
-
A
d
v
G
a
m
e
k
-
1
A
=
ϵ, then we can build an algorithm B to break Assumption 5 with advantage ϵ
/
2.Proof.
On inputD
=
(
(
N
,
G
,
G
T
,
e
^
)
,
g
p
,
X
1
X
2
,
X
3
,
Y
2
Y
3
) and T
∈
{
T
0
,
T
1
}, where T
0
←
$
G and T
1
←
$
G
p
r, B simulates A as follows.
Setup. Choose random α, x
∈
R
Z
N, and X
∈
R
Z
N
d; set S
K
≔
(
g
p
α
,
x
,
X
) and output(28)
P
P
≔
G
,
g
p
,
g
r
,
P
K
≔
g
p
x
,
g
p
X
,
e
^
g
p
,
g
p
α
Token Queries. When A requests the i
t
h token for the predicate P
K
i, B answers the tokens differently according to the following cases:(i)
Casei
<
k: B chooses y
i
′
∈
R
Z
N
∗ and W
i
′
∈
R
Z
N
d
+
1 randomly and creates the semifunctional tokens:(29)
T
K
K
i
≔
g
p
y
i
′
K
i
,
α
-
y
i
′
X
,
K
i
Y
2
Y
3
W
i
′
Observe that this is an identical distribution from semifunctional tokens.(ii)
Casei
>
k: B chooses y
i
′
∈
R
Z
N
∗ and W
i
′
∈
R
Z
N
d
+
1 randomly and creates the normal tokens:(30)
T
K
K
i
≔
g
p
y
i
′
K
i
,
α
-
y
i
′
X
,
K
i
X
3
W
i
′
(iii)
Casei
=
k: B chooses y
k
′
∈
R
Z
N
∗, Z
k
∈
R
Z
N
d
+
1, and W
k
′
∈
R
Z
N
d
+
1 randomly and creates the normal tokens:(31)
T
K
K
k
≔
g
p
y
k
′
K
k
,
α
-
y
k
′
X
,
K
k
T
Z
k
X
3
W
k
′
Challenge Ciphertext. After receiving two pair of messages (
A
0
,
M
0
)
,
(
A
1
,
M
1
), B chooses β
∈
R
{
0,1
} randomly and sets Z
c
∈
Z
N
d
+
1 such that Z
c
,
Z
k
=
0 and then forms the ciphertext:(32)
C
0
≔
e
^
g
p
,
X
1
X
2
α
·
M
β
,
C
1
≔
X
1
X
2
x
A
β
+
X
,
1Recall that X
1
X
2
∈
G
p
q and X
1 is the G
p part in it. This implicitly sets X
1
≔
g
p
s. Furthermore, X
2 is the G
q part in X
1
X
2, so there exits some δ such that X
2
≔
g
q
δ and δ
(
x
A
β
+
X
,
1
)
,
Z
k
=
0. Then this implicitly sets Z
c
≔
δ
(
x
A
β
+
X
,
1
). This relationship between Z
c and Z
k makes one thing happen; that is, if B wants to test whether the token T
K
K is semifunctional by creating a semifunctional ciphertext for predicate P
K and trying to decrypt and finish the query, the decryption will succeed no matter what T
K
K is due to Z
c
,
Z
k
=
0. So, if T
∈
G
p
r, then we are in G
a
m
e
k
-
1. If T
∈
G, then we are in G
a
m
e
k.Lemma 14.
If there is an algorithmA that can distinguish G
a
m
e
F
i
n
a
l from G
a
m
e
l with advantage of A
d
v
G
a
m
e
F
i
n
a
l
A
-
A
d
v
G
a
m
e
l
A
=
ϵ, then we can build an algorithm B to break Assumption 7 with advantage ϵ
/
2.Proof.
On inputα
,
s
←
$
Z
N, D
=
(
(
N
,
G
,
G
T
,
e
^
)
,
g
p
,
g
p
α
X
2
,
X
3
,
g
p
s
Y
2
,
Z
2
) and T
∈
{
T
0
,
T
1
}, where T
0
=
e
^
(
g
p
,
g
p
)
α
s and T
1
←
$
G
T; B simulates A as follows.
Setup. Choose randomα
,
x
∈
R
Z
N and X
∈
R
Z
N
d; set S
K
≔
(
g
p
α
,
x
,
X
) and output(33)
P
P
≔
G
,
g
p
,
g
r
,
P
K
≔
g
p
x
,
g
p
X
,
e
^
g
p
,
g
p
α
=
e
^
g
p
α
X
2
,
g
p
Token Queries. Each time B is asked to provide a token for a predicate P
K
j, it randomly chooses y
j
′
∈
R
Z
N, W
j
′
∈
R
Z
N
d
+
1, and Z
k
′
∈
R
Z
N
d
+
1 and outputs a semifunctional token:(34)
T
K
K
j
≔
g
p
y
j
′
K
j
,
α
-
y
j
′
X
,
K
j
Z
2
Z
k
′
X
3
W
j
′
Challenge Ciphertext. After receiving two pairs of messages (
A
0
,
M
0
)
,
(
A
1
,
M
1
), B randomly chooses β
∈
R
{
0,1
} and forms the ciphertext:(35)
C
0
≔
T
·
M
β
,
C
1
≔
g
p
s
Y
2
x
A
β
+
X
,
1This implicitly sets Z
c
≔
(
x
A
β
+
X
,
1
) and this has a proper distribution of semifunctional ciphertexts. So, if T
=
e
^
(
g
p
,
g
p
)
α
s, then we are in G
a
m
e
l. If T
=
T
1
←
$
G
T, then we are in G
a
m
e
F
i
n
a
l.Theorem 15.
Under Assumptions3, 5, and 7, our Φ-searchable functional encryption scheme described in Section 4 is adaptively secure.Proof.
When Assumptions3, 5, and 7 hold, we have shown the indistinguishability between two consecutive games by the previous lemmas, which means that the real security game is indistinguishable from the simulated game in G
a
m
e
F
i
n
a
l, in which β is theoretically hidden from the adversary. So, the adversary has no advantage in breaking our scheme.


## 6. Applications for Various Queries on Encrypted Data

In this section, we show a candidate system structure that enables the auditor to do various queries on the encrypted industrial data stream and discuss how to implement these query types.


### 6.1. General Structure for Querying on the Encrypted Industrial Data Stream

Based on our proposedΦ-searchable functional encryption scheme, one can easily enable the gateway to query encrypted industrial data stream. Specifically, as shown in Figure 2, data are collected from various sources such as manufactures, security cameras, and GPS chips. Data sources would send data to the data center through the gateway. The data center stores and analyzes these data, and the gateway observes and audits data stream for supervision purpose. For both security and privacy-preserving concerns, data sources encrypt the data stream under the data center’s public key P
K with the ciphertext attribute A by invoking theEncrypt algorithm. For a predicate P, the gateway sends the key attribute K to the data center, and the data center invokes theGenToken algorithm to delegate a query token T
K
K to the gateway instead of sending its secret key S
K to the gateway, which is a bad idea. The gateway who has the query token T
K
K can make tests on the encrypted data stream by invoking theQuery algorithm without decryption. If the output is 1, which means P
K
(
A
)
=
1, that is, the encrypted data passing by is matched with the conditions, then the gateway can decrypt that data correctly and take further actions, say, label it. If the output is 0, the gateway can learn nothing about that data; this is guaranteed by the security level of our proposed scheme.Figure 2
Logical structure for querying on the encrypted industrial data stream.


### 6.2. Equality, Comparison, and Subset Queries

LetΣ
A
≔
Z
N
d, A
′
≔
(
a
1
,
a
2
,
.
.
.
,
a
d
)
∈
Σ
A, and a data M
∈
M; we encrypt a pair (
A
′
,
M
) using theEncrypt algorithm of our scheme. For example, M is a personal bank transaction, a
1 is the transaction value, a
2 is the card expiration date, and so on. Also, let Σ
K
≔
Z
N
d and K
′
≔
(
k
1
,
k
2
,
.
.
.
,
k
d
)
∈
Σ
K. We interpret the predicate P
K
′
(
A
′
) (i.e., if k
i
=
a
i or not) for equality test. We interpret the predicate P
K
′
(
A
′
) as a comparison predicate (i.e., if k
i
≥
a
i or not) for a comparison test. We interpret A
′ as a set and interpret the predicate P
K
′
(
A
′
) as a subset predicate (i.e., if k
i
∈
A
′ or not) for subset test. Then, to achieve above-mentioned three kinds of tests, for the attribute A
′, set A
≔
(
-
A
′
,
1
) and encrypt a data M using A. To generate a token for the attribute K
′, set K
≔
(
1
,
K
′
). Since K
,
A
=
0, if and only if K
′
=
A
′, correctness and security follow.


### 6.3. Polynomial Evaluation

Similar to the predicate encryption scheme presented by Katz et al. [15], we can also support the polynomial evaluation by defining the classes of predicates accordingly. A Φ-searchable functional encryption for polynomials of degree ≤
d
(
p
(
x
)
=
k
0
+
k
1
x
1
+
⋯
+
k
d
x
d
) can be defined as follows. Let key attributes space Σ
K
P
o
l
y
≤
d
≔
Z
p
d
+
1; we map the polynomial p
(
x
)
=
k
0
+
k
1
x
1
+
⋯
+
k
d
x
d to K
≔
(
k
0
,
k
1
,
…
,
k
d
). For ciphertext attribute, each element w
∈
Z
p is mapped onto a ciphertext attribute vector A
≔
(
w
0
m
o
d
N
,
w
1
m
o
d
N
,
…
,
w
d
m
o
d
N
). We also need to define the predicate set Φ
≤
d
P
o
l
y
≔
{
P
K
P
o
l
y
(
A
)
|
p
∈
Z
N
[
x
]
,
d
e
g
(
p
)
≤
d
}, where(36)
P
K
P
o
l
y
A
≔
1
i
f
p
x
=
0
m
o
d
N
0
O
t
h
e
r
w
i
s
efor x
∈
Z
N.Then, for predicateP
K
P
l
o
y
(
A
)
∈
Φ
≤
d
P
l
o
y, correctness and security of our Φ-searchable functional encryption hold, since p
(
w
)
=
0 whenever K
,
A
=
0.


### 6.4. Conjunctions, Disjunctions, CNF, and DNF Formulas

Based on ourΦ-searchable functional encryption for P
K
P
l
o
y
(
A
)
∈
Φ
≤
d
P
l
o
y, we can easily support the conjunctions, disjunctions, and their extensions CNF/DNF. We show this ability using an example of conjunctions of equality tests. To do this, for some K
≔
(
k
0
,
k
1
,
.
.
.
,
k
d
) and A
≔
(
a
0
,
a
1
,
.
.
.
,
a
d
) we define the conjunction predicate as P
k
1
,
k
2
A
N
D
(
a
1
,
a
2
), where P
k
1
,
k
2
A
N
D
(
a
1
,
a
2
)
=
1 if both k
1
=
a
1 and k
2
=
a
2. This predicate can be a polynomial as(37)
p
x
1
,
x
2
=
r
·
x
1
-
k
1
+
x
2
-
k
2
,where r
←
$
Z
N. If P
k
1
,
k
2
A
N
D
(
a
1
,
a
2
)
=
1, then p
(
a
1
,
a
2
)
=
0. Otherwise, with all but negligible probability over the choice of r, it will hold that p
(
a
1
,
a
2
)
≠
0.In a similar fashion, we can define the predicate for disjunction of equality tests. For someK
≔
(
k
0
,
k
1
,
.
.
.
,
k
d
) and A
≔
(
a
0
,
a
1
,
.
.
.
,
a
d
), we define the disjunction predicate as P
k
1
,
k
2
O
R
(
a
1
,
a
2
), where P
k
1
,
k
2
O
R
(
a
1
,
a
2
)
=
1 if either k
1
=
a
1 or k
2
=
a
2. This predicate also can be a polynomial as(38)
p
x
1
,
x
2
=
x
1
-
k
1
·
x
2
-
k
2If P
k
1
,
k
2
O
R
(
a
1
,
a
2
)
=
1, then p
(
a
1
,
a
2
)
=
0; otherwise p
(
a
1
,
a
2
)
≠
0.We can combine disjunctions, conjunctions, and Boolean variables to handle arbitrary CNF or DNF formulas.


## 6.1. General Structure for Querying on the Encrypted Industrial Data Stream

Based on our proposedΦ-searchable functional encryption scheme, one can easily enable the gateway to query encrypted industrial data stream. Specifically, as shown in Figure 2, data are collected from various sources such as manufactures, security cameras, and GPS chips. Data sources would send data to the data center through the gateway. The data center stores and analyzes these data, and the gateway observes and audits data stream for supervision purpose. For both security and privacy-preserving concerns, data sources encrypt the data stream under the data center’s public key P
K with the ciphertext attribute A by invoking theEncrypt algorithm. For a predicate P, the gateway sends the key attribute K to the data center, and the data center invokes theGenToken algorithm to delegate a query token T
K
K to the gateway instead of sending its secret key S
K to the gateway, which is a bad idea. The gateway who has the query token T
K
K can make tests on the encrypted data stream by invoking theQuery algorithm without decryption. If the output is 1, which means P
K
(
A
)
=
1, that is, the encrypted data passing by is matched with the conditions, then the gateway can decrypt that data correctly and take further actions, say, label it. If the output is 0, the gateway can learn nothing about that data; this is guaranteed by the security level of our proposed scheme.Figure 2
Logical structure for querying on the encrypted industrial data stream.


## 6.2. Equality, Comparison, and Subset Queries

LetΣ
A
≔
Z
N
d, A
′
≔
(
a
1
,
a
2
,
.
.
.
,
a
d
)
∈
Σ
A, and a data M
∈
M; we encrypt a pair (
A
′
,
M
) using theEncrypt algorithm of our scheme. For example, M is a personal bank transaction, a
1 is the transaction value, a
2 is the card expiration date, and so on. Also, let Σ
K
≔
Z
N
d and K
′
≔
(
k
1
,
k
2
,
.
.
.
,
k
d
)
∈
Σ
K. We interpret the predicate P
K
′
(
A
′
) (i.e., if k
i
=
a
i or not) for equality test. We interpret the predicate P
K
′
(
A
′
) as a comparison predicate (i.e., if k
i
≥
a
i or not) for a comparison test. We interpret A
′ as a set and interpret the predicate P
K
′
(
A
′
) as a subset predicate (i.e., if k
i
∈
A
′ or not) for subset test. Then, to achieve above-mentioned three kinds of tests, for the attribute A
′, set A
≔
(
-
A
′
,
1
) and encrypt a data M using A. To generate a token for the attribute K
′, set K
≔
(
1
,
K
′
). Since K
,
A
=
0, if and only if K
′
=
A
′, correctness and security follow.


## 6.3. Polynomial Evaluation

Similar to the predicate encryption scheme presented by Katz et al. [15], we can also support the polynomial evaluation by defining the classes of predicates accordingly. A Φ-searchable functional encryption for polynomials of degree ≤
d
(
p
(
x
)
=
k
0
+
k
1
x
1
+
⋯
+
k
d
x
d
) can be defined as follows. Let key attributes space Σ
K
P
o
l
y
≤
d
≔
Z
p
d
+
1; we map the polynomial p
(
x
)
=
k
0
+
k
1
x
1
+
⋯
+
k
d
x
d to K
≔
(
k
0
,
k
1
,
…
,
k
d
). For ciphertext attribute, each element w
∈
Z
p is mapped onto a ciphertext attribute vector A
≔
(
w
0
m
o
d
N
,
w
1
m
o
d
N
,
…
,
w
d
m
o
d
N
). We also need to define the predicate set Φ
≤
d
P
o
l
y
≔
{
P
K
P
o
l
y
(
A
)
|
p
∈
Z
N
[
x
]
,
d
e
g
(
p
)
≤
d
}, where(36)
P
K
P
o
l
y
A
≔
1
i
f
p
x
=
0
m
o
d
N
0
O
t
h
e
r
w
i
s
efor x
∈
Z
N.Then, for predicateP
K
P
l
o
y
(
A
)
∈
Φ
≤
d
P
l
o
y, correctness and security of our Φ-searchable functional encryption hold, since p
(
w
)
=
0 whenever K
,
A
=
0.


## 6.4. Conjunctions, Disjunctions, CNF, and DNF Formulas

Based on ourΦ-searchable functional encryption for P
K
P
l
o
y
(
A
)
∈
Φ
≤
d
P
l
o
y, we can easily support the conjunctions, disjunctions, and their extensions CNF/DNF. We show this ability using an example of conjunctions of equality tests. To do this, for some K
≔
(
k
0
,
k
1
,
.
.
.
,
k
d
) and A
≔
(
a
0
,
a
1
,
.
.
.
,
a
d
) we define the conjunction predicate as P
k
1
,
k
2
A
N
D
(
a
1
,
a
2
), where P
k
1
,
k
2
A
N
D
(
a
1
,
a
2
)
=
1 if both k
1
=
a
1 and k
2
=
a
2. This predicate can be a polynomial as(37)
p
x
1
,
x
2
=
r
·
x
1
-
k
1
+
x
2
-
k
2
,where r
←
$
Z
N. If P
k
1
,
k
2
A
N
D
(
a
1
,
a
2
)
=
1, then p
(
a
1
,
a
2
)
=
0. Otherwise, with all but negligible probability over the choice of r, it will hold that p
(
a
1
,
a
2
)
≠
0.In a similar fashion, we can define the predicate for disjunction of equality tests. For someK
≔
(
k
0
,
k
1
,
.
.
.
,
k
d
) and A
≔
(
a
0
,
a
1
,
.
.
.
,
a
d
), we define the disjunction predicate as P
k
1
,
k
2
O
R
(
a
1
,
a
2
), where P
k
1
,
k
2
O
R
(
a
1
,
a
2
)
=
1 if either k
1
=
a
1 or k
2
=
a
2. This predicate also can be a polynomial as(38)
p
x
1
,
x
2
=
x
1
-
k
1
·
x
2
-
k
2If P
k
1
,
k
2
O
R
(
a
1
,
a
2
)
=
1, then p
(
a
1
,
a
2
)
=
0; otherwise p
(
a
1
,
a
2
)
≠
0.We can combine disjunctions, conjunctions, and Boolean variables to handle arbitrary CNF or DNF formulas.


## 7. Comparison and Evaluation

### 7.1. Comparison

We compare our construction to prior constructions which are built for inner product evaluations on encrypted data in composite-order bilinear groups [15, 31]. We show the comparison of the basic parameters’ performance between these schemes in Table 1.Table 1
Comparison of basic parameters∗.
Scheme
L
e
n
P
K
L
e
n
T
K
L
e
n
C
SecLev
KSW12 ‎[15]
(
3
+
2
d
)
|
G
|
(
1
+
2
d
)
|
G
|
(
1
+
2
d
)
|
G
|
selectively
LL18 ‎[31]
(
3
+
2
d
)
|
G
|
2
d
|
N
|
(
1
+
d
)
|
G
|
selectively
Our proposal
(
2
+
d
)
|
G
|
+
|
G
T
|
(
1
+
d
)
|
G
|
(
1
+
d
)
|
G
|
+
|
G
T
|
adaptively
∗ Let L
e
n
P
K denote the length of the public key including public parameters, let L
e
n
T
K denote the length of the search token (in some schemes, i.e., the private key), let L
e
n
C denote the length of the ciphertext, and let SecLev denote the security level. Let |
G
| and |
G
T
| denote the length of the element in groups G and G
T, respectively, let |
N
| denote the length of the element in the field Z
N
∗, and let d denote the dimension of the ciphertext attribute and the key attribute.We use KSW12 to denote the scheme proposed by Katz, Sahai, and Waters [15] and LL18 to denote the scheme proposed by Lee and Lee [31]. As shown in Table 1, our scheme has been proven to be secure against adaptive adversaries, whereas the other two schemes just have selective security. The lengths of the public key are (
3
+
2
d
)
|
G
| for KSW12 and LL18, whereas (
2
+
d
)
|
G
|
+
|
G
T
| for our proposal. Obviously, our construction has a smaller public key than others. For the length of the search token (i.e., the private key), our construction has nearly half elements of others. Our construction also gets smaller ciphertext size, (
1
+
d
)
|
G
|
+
|
G
T
|, which has just one more group element than LL18 but nearly half elements of KSW12.


### 7.2. Performance Evaluation

We implement the algorithms of proposed functional encryption scheme using pairing-based cryptography library pbc-0.5.14 with pbc wrapper-0.8.0 [39] on a PC with 3.3GHz Intel, i5-6600 CPU, and 8GB memory. In our implementation, we made use of parametera.param, one of the standard parameter settings of pbc library. The implementation time overheads are demonstrated as shown in Figure 3. We would like to observe the impact of the dimension of ciphertext (key) attribute vector in terms of the time cost of the algorithms. Obviously, the bigger dimension of ciphertext (key) attribute will make the attributes more expressive, which means the scheme will support more complex predicates. We can see that the time consumptions of theSetup algorithm,Encrypt algorithm, andGenToken algorithm are linearly increasing with the increase from 1 to 50 of the dimension of ciphertext (key) attribute d. TheSetup algorithm is run by the trusted authority which usually can be executed once and offline. TheEncrypt algorithm is run by the data source which also can be executed offline. TheGenToken algorithm is run by the data center that has powerful computing ability. So, the time cost of these three algorithms is considerably acceptable. Fortunately, theQuery algorithm’s time cost is nearly constant (less than 20ms) with the increase of the dimension of ciphertext (key) attribute d. This merit makes the gateway able to effectively test the encrypted data passing by without a significant reduction in processing speed.Figure 3
Time cost of the algorithms.


## 7.1. Comparison

We compare our construction to prior constructions which are built for inner product evaluations on encrypted data in composite-order bilinear groups [15, 31]. We show the comparison of the basic parameters’ performance between these schemes in Table 1.Table 1
Comparison of basic parameters∗.
Scheme
L
e
n
P
K
L
e
n
T
K
L
e
n
C
SecLev
KSW12 ‎[15]
(
3
+
2
d
)
|
G
|
(
1
+
2
d
)
|
G
|
(
1
+
2
d
)
|
G
|
selectively
LL18 ‎[31]
(
3
+
2
d
)
|
G
|
2
d
|
N
|
(
1
+
d
)
|
G
|
selectively
Our proposal
(
2
+
d
)
|
G
|
+
|
G
T
|
(
1
+
d
)
|
G
|
(
1
+
d
)
|
G
|
+
|
G
T
|
adaptively
∗ Let L
e
n
P
K denote the length of the public key including public parameters, let L
e
n
T
K denote the length of the search token (in some schemes, i.e., the private key), let L
e
n
C denote the length of the ciphertext, and let SecLev denote the security level. Let |
G
| and |
G
T
| denote the length of the element in groups G and G
T, respectively, let |
N
| denote the length of the element in the field Z
N
∗, and let d denote the dimension of the ciphertext attribute and the key attribute.We use KSW12 to denote the scheme proposed by Katz, Sahai, and Waters [15] and LL18 to denote the scheme proposed by Lee and Lee [31]. As shown in Table 1, our scheme has been proven to be secure against adaptive adversaries, whereas the other two schemes just have selective security. The lengths of the public key are (
3
+
2
d
)
|
G
| for KSW12 and LL18, whereas (
2
+
d
)
|
G
|
+
|
G
T
| for our proposal. Obviously, our construction has a smaller public key than others. For the length of the search token (i.e., the private key), our construction has nearly half elements of others. Our construction also gets smaller ciphertext size, (
1
+
d
)
|
G
|
+
|
G
T
|, which has just one more group element than LL18 but nearly half elements of KSW12.


## 7.2. Performance Evaluation

We implement the algorithms of proposed functional encryption scheme using pairing-based cryptography library pbc-0.5.14 with pbc wrapper-0.8.0 [39] on a PC with 3.3GHz Intel, i5-6600 CPU, and 8GB memory. In our implementation, we made use of parametera.param, one of the standard parameter settings of pbc library. The implementation time overheads are demonstrated as shown in Figure 3. We would like to observe the impact of the dimension of ciphertext (key) attribute vector in terms of the time cost of the algorithms. Obviously, the bigger dimension of ciphertext (key) attribute will make the attributes more expressive, which means the scheme will support more complex predicates. We can see that the time consumptions of theSetup algorithm,Encrypt algorithm, andGenToken algorithm are linearly increasing with the increase from 1 to 50 of the dimension of ciphertext (key) attribute d. TheSetup algorithm is run by the trusted authority which usually can be executed once and offline. TheEncrypt algorithm is run by the data source which also can be executed offline. TheGenToken algorithm is run by the data center that has powerful computing ability. So, the time cost of these three algorithms is considerably acceptable. Fortunately, theQuery algorithm’s time cost is nearly constant (less than 20ms) with the increase of the dimension of ciphertext (key) attribute d. This merit makes the gateway able to effectively test the encrypted data passing by without a significant reduction in processing speed.Figure 3
Time cost of the algorithms.


## 8. Conclusions

In this paper, we have put forth anΦ-searchable functional encryption scheme. We have built our scheme on the composite-order bilinear groups and have proven the adaptive security by utilizing dual system encryption proof technology. By using our proposed scheme as the underlying encryption scheme, we present an approach that supports the fact that the gateway effectively audits the encrypted data stream. According to the comparison and performance evaluation results, our proposed encryption scheme has the smaller public key, the smaller query token, and the smaller ciphertext. Moreover, our proposed approach can enable the gateway to effectively test the encrypted data stream, which is practical for industrial data stream auditing scenario.



---

*Source: 6293970-2019-07-03.xml*