# Comparable Encryption Scheme over Encrypted Cloud Data in Internet of Everything

Authors: Qian Meng; Jianfeng Ma; Kefei Chen; Yinbin Miao; Tengfei Yang
Journal: Security and Communication Networks
 (2017)

---

## Abstract

User authentication has been widely deployed to prevent unauthorized access in the new era of Internet of Everything (IOE). When user passes the legal authentication, he/she can do series of operations in database. We mainly concern issues of data security and comparable queries over ciphertexts in IOE. In traditional database, a Short Comparable Encryption (SCE) scheme has been widely used by authorized users to conduct comparable queries over ciphertexts, but existing SCE schemes still incur high storage and computational overhead as well as economic burden. In this paper, we first propose a basic Short Comparable Encryption scheme based on sliding window method (SCESW), which can significantly reduce computational and storage burden as well as enhance work efficiency. Unfortunately, as the cloud service provider is a semitrusted third party, public auditing mechanism needs to be furnished to protect data integrity. To further protect data integrity and reduce management overhead, we present an enhanced SCESW scheme based on position-aware Merkle tree, namely, PT-SCESW. Security analysis proves that PT-SCESW and SCESW schemes can guarantee completeness and weak indistinguishability in standard model. Performance evaluation indicates that PT-SCESW scheme is efficient and feasible in practical applications, especially for smarter and smaller computing devices in IOE.


---

## Body

## 1. Introduction

With the new era of Internet of Everything (IOE) [1] and cloud computing [2, 3], smaller and smarter computing devices have begun to be integrated into our lives such as e-Health [4, 5], online shopping [6], and image retrieval [7]. Authentication is regarded as a first line of defense and has been widely used to prevent unauthorized access. Series of research efforts [8–17] have been made. User authentication can be password-based authentication [18, 19], biometric-based authentication [20, 21], and others [22–24]. However, security issues of user authentication, especially issues of data security and the availability of ciphertext data, are rather challenging tasks in IOE. When user passes the legal authentication, he/she can do comparable queries over ciphertexts. On the premise of ensuring safety, we concern how to make comparable queries over ciphertexts for authorized users.As the cloud service provider is not a completely trusted entity, data usually utilize encryption technique by authorized users to guarantee security before being outsourced to the cloud service provider. There exist some scenes such as e-Health and stock exchange, which need to compare numeric data [25] over encrypted data. Unfortunately, what is of prime importance is how to make comparable operations over ciphertexts as well as data integrity without leaking any information.To ensure comparable query operations over ciphertexts, series of research efforts [26–31] have been made. Among these efforts, one of popular works is a request-based comparable encryption scheme [31] which utilizes the idea of Prefix Preserving Encryption (PPE). Although this scheme can make comparable query operations over ciphertexts, it brings in high computational and storage burden. To this end, an efficient request-based comparable encryption scheme was discussed by Chen et al. [32] through utilizing sliding window method to reduce computational and storage burden. To further relief ciphertexts storage space, SCE scheme was presented by Furukawa through using PPE idea [33]. Compared with request-based comparable encryption scheme, SCE scheme encrypts each bit into 3-ary, thereby dramatically reducing ciphertexts space and improving work efficiency. As the semitrusted cloud service provider may maliciously conduct a fraction of operations and forge some ciphertexts, we should verify the correctness of outsourced data for the purpose of ensuring data integrity.To ensure data integrity without maliciously being forged, large amount of work [34–37] aimed to verify the integrity of static and dynamic outsourced data. For example, a remote integrity checking scheme which is based on modular-exponentiation cryptographic techniques was introduced by Deswarte et al. [38] Unfortunately, the new scheme has high computing complexity. To tackle this problem, Gazzoni Filho and Barreto [39] proposed a scheme by utilizing an RSA-based secure hash function in order to achieve safe data transfer transaction through a trusted third party. However, this protocol is still vulnerable to the collusion attack in a P2P environment [39] as most of existing schemes cannot prevent the user data from being leaked to external auditors. After that, Wang et al. [36] proposed a scheme known as privacy-preserving public auditing for data storage security in cloud computing, which was the first privacy-preserving auditing protocol to support scalable and public auditing in the cloud computing. In Wang et al. protocol, computational overhead came from several time-consuming operations. Aiming at reducing high computational and storage overhead, we use position-aware Merkle tree (PMT) [40] to ensure data integrity.Inspired by the aforementioned sliding window method and PMT, we first propose a basic scheme called SCESW scheme which is based on the sliding window method to reduce computational and storage overhead. Since the cloud service provider is a semitrusted entity which can obtain some sensitive information and then derive plaintexts, we further present an enhanced scheme named PT-SCESW scheme according to PMT to verify the stored data integrity. The main contributions of our work are listed as follows.(i)
SCESW scheme: inspired by sliding window method and SCE scheme, we first put forward the basic SCESW scheme to relief computational burden and storage overhead as well as enhance work efficiency.(ii)
PT-SCESW scheme: to further protect data integrity for authorized users, we then introduce the enhanced lightweight PT-SCESW scheme based on PMT, which allows the authorized verifier to check the correctness of stored cloud data. Table 1 shows comparisons among various schemes.(iii)
Security and efficiency: formal security analysis demonstrates that PT-SCESW and SCESW schemes can guarantee data security and integrity as well as weak indistinguishability in standard model and experimental results using real-world dataset show its efficiency in practice.Table 1
Comparisons among various schemes.
SCE
SCESW
PT-SCESW
S
1
Larger
Smaller
Smaller
S
2
Larger
Smaller
Smaller
S
3
Lower
Higher
Higher
S
4
✕
✓
✓
S
5
✕
✕
✓
Note.  S1: storage overhead; S2: computational overhead; S3: efficiency; S4: sliding window method; S5: public auditing; Yes: ✓; no: ✕.The reminder of this paper is organized as follows. Section2 depicts some preliminaries which will be used in our paper. Section 3 gives a detailed description of the proposed basic and enhanced schemes. Section 4 shows security analysis and Section 5 illustrates the performance of proposed schemes.


## 2. Preliminaries

In this section, we will give some descriptions of sliding window method and position-aware Merkle tree.


### 2.1. Sliding Window Method

Sliding window method proposed by Koç [41] is one of the widely used methods for exponentiation. For example, computing xe, we can write e using its binary code, such as e=bn-1,…,b1,b0,bi∈0,1,i=0,1,…,n-1. Based on the value of bi,(bn-1,…,b1,b0) is divided into a tuple of zero windows and nonzero windows. Sliding window technology can bring in the reduction in the amount of computation and management overhead. Algorithm 1 illustrates details of sliding window method [32].Algorithm 1:The sliding window method [32].
Input: two numbers x and e where x represents base and e represents exponent
Output:   y=xe
(
1
) for  all  w,w=3,5,7,…,2d-1  do
(
2
)
Compute and store xw;
(
3
)  e is divided into zero windows and non-zero windows Fi of length T(Fi)
where T(Fi) represents the length of windows;
(
4
) for  i=n-1,…,0  do
(
5
)
Compute the value of y≔xFn-1;
(
6
)  for  0≤i≤n-2  do
7
Compute and store y≔y2T(Fi);
(
8
)  if  fi≠0  then
(
9
)
Compute and store y≔y⋅xFi;
(
10
)
else
(
11
)
F
i is a zero window.
(
12
) Return y;In our schemes, numeric numbers are considered as a sequence of the binary codes. However, we suppose that all the windows have the same window size without distinguishing zero windows or nonzero windows. The fixed window size is chosen by the user’s security level requirements. Hence, security and efficiency can be trade-off in practice.


### 2.2. Position-Aware Merkle Tree

Merkle hash tree [42] is extensively utilized in data integrity [43]. The structure of Merkle tree [44] contains a root on the top of the tree, nonleaf nodes, and leaf nodes, which is shown in Figure 1. Every nonleaf node is labeled as the hash value of its children nodes and every leaf node is defined as the hash value of a file block. Λ=Ai∣Ai=h(xi),1≤i≤15, where h(·) represents a hash function. The root node of the Λ is regarded as Aroot. For a node Ai, Auxiliary Authentication Information (AAI) is used to depict the smallest order node set Υi=A1i≫A2i≫⋯. Given a node Ai, AAI contains all the brother nodes related to Ai through root path from Ai to root node Aroot. For example, the AAI of node A3 is Υi=A4≫A9≫A14, as shown in Figure 1.Figure 1
Position-aware Merkle tree.In the PMT structure, every node is noted asAi. Besides, Ai is presented by a 3-tuple Ai=(Ai·p;Ai·r;Ai·v), where Ai·p represents node Ai’s relative position to its parents node; Ai·r represents the number of node Ai’s leaf nodes; Ai·v represents the value of the node Ai. We label nodes from left to right in each layer with Ai·p, Ai·r, and Ai·v defined as follows, where set Ωl represents the set of left subtrees, set Ωr represents the set of right subtrees, set Ωroot represents the root of tree, and set Θ represents the set of leaf nodes.(1)Ai·p=0ifAi∈Ωl;1ifAi∈Ωr;nullifAi∈Ωroot,Ai·r=Ali·r+Ari·rifAi∉Θ;1ifAi∈Θ,Ai·v=hAi·p∥Ali·v∥Ari·v∥Ai·rifAi∉Θ;hAi·p∥xi∥1ifAi∈Θ.From Figure1, we know that node A3 is a leaf node that relates to the block x3 and A3 is located in the left of its parent node A10. According to the formula above, A3·p=0, A3·r=1, and A3·v=h(0∥x3∥1). Similarly, we can obtain A4=h(1∥x4∥1) and A10=h(1∥A3·v∥A4·v∥2). Table 2 illustrates the value of nodes in Figure 1.Table 2
Nodes of position-aware Merkle tree in Figure1.
Nodes
A
i
⋅
p
A
i
⋅
r
A
i
⋅
v
A
1
0
1
h
(
0
∥
x
1
∥
1
)
A
2
1
1
h
(
1
∥
x
2
∥
1
)
A
3
0
1
h
(
0
∥
x
3
∥
1
)
A
4
1
1
h
(
1
∥
x
4
∥
1
)
A
5
0
1
h
(
0
∥
x
5
∥
1
)
A
6
1
1
h
(
1
∥
x
6
∥
1
)
A
7
0
1
h
(
0
∥
x
7
∥
1
)
A
8
1
1
h
(
1
∥
x
8
∥
1
)
A
9
0
2
h
(
0
∥
A
1
⋅
v
∥
A
2
⋅
v
∥
2
)
A
10
1
2
h
(
1
∥
A
3
⋅
v
∥
A
4
⋅
v
∥
2
)
A
11
0
2
h
(
0
∥
A
5
⋅
v
∥
A
6
⋅
v
∥
2
)
A
12
1
2
h
(
1
∥
A
7
⋅
v
∥
A
8
⋅
v
∥
2
)
A
13
0
4
h
(
0
∥
A
9
⋅
v
∥
A
10
⋅
v
∥
4
)
A
14
1
4
h
(
1
∥
A
11
⋅
v
∥
A
12
⋅
v
∥
4
)
A
15
N
u
l
l
8
h
(
n
u
l
l
∥
A
13
⋅
v
∥
A
14
⋅
v
∥
8
)


## 2.1. Sliding Window Method

Sliding window method proposed by Koç [41] is one of the widely used methods for exponentiation. For example, computing xe, we can write e using its binary code, such as e=bn-1,…,b1,b0,bi∈0,1,i=0,1,…,n-1. Based on the value of bi,(bn-1,…,b1,b0) is divided into a tuple of zero windows and nonzero windows. Sliding window technology can bring in the reduction in the amount of computation and management overhead. Algorithm 1 illustrates details of sliding window method [32].Algorithm 1:The sliding window method [32].
Input: two numbers x and e where x represents base and e represents exponent
Output:   y=xe
(
1
) for  all  w,w=3,5,7,…,2d-1  do
(
2
)
Compute and store xw;
(
3
)  e is divided into zero windows and non-zero windows Fi of length T(Fi)
where T(Fi) represents the length of windows;
(
4
) for  i=n-1,…,0  do
(
5
)
Compute the value of y≔xFn-1;
(
6
)  for  0≤i≤n-2  do
7
Compute and store y≔y2T(Fi);
(
8
)  if  fi≠0  then
(
9
)
Compute and store y≔y⋅xFi;
(
10
)
else
(
11
)
F
i is a zero window.
(
12
) Return y;In our schemes, numeric numbers are considered as a sequence of the binary codes. However, we suppose that all the windows have the same window size without distinguishing zero windows or nonzero windows. The fixed window size is chosen by the user’s security level requirements. Hence, security and efficiency can be trade-off in practice.


## 2.2. Position-Aware Merkle Tree

Merkle hash tree [42] is extensively utilized in data integrity [43]. The structure of Merkle tree [44] contains a root on the top of the tree, nonleaf nodes, and leaf nodes, which is shown in Figure 1. Every nonleaf node is labeled as the hash value of its children nodes and every leaf node is defined as the hash value of a file block. Λ=Ai∣Ai=h(xi),1≤i≤15, where h(·) represents a hash function. The root node of the Λ is regarded as Aroot. For a node Ai, Auxiliary Authentication Information (AAI) is used to depict the smallest order node set Υi=A1i≫A2i≫⋯. Given a node Ai, AAI contains all the brother nodes related to Ai through root path from Ai to root node Aroot. For example, the AAI of node A3 is Υi=A4≫A9≫A14, as shown in Figure 1.Figure 1
Position-aware Merkle tree.In the PMT structure, every node is noted asAi. Besides, Ai is presented by a 3-tuple Ai=(Ai·p;Ai·r;Ai·v), where Ai·p represents node Ai’s relative position to its parents node; Ai·r represents the number of node Ai’s leaf nodes; Ai·v represents the value of the node Ai. We label nodes from left to right in each layer with Ai·p, Ai·r, and Ai·v defined as follows, where set Ωl represents the set of left subtrees, set Ωr represents the set of right subtrees, set Ωroot represents the root of tree, and set Θ represents the set of leaf nodes.(1)Ai·p=0ifAi∈Ωl;1ifAi∈Ωr;nullifAi∈Ωroot,Ai·r=Ali·r+Ari·rifAi∉Θ;1ifAi∈Θ,Ai·v=hAi·p∥Ali·v∥Ari·v∥Ai·rifAi∉Θ;hAi·p∥xi∥1ifAi∈Θ.From Figure1, we know that node A3 is a leaf node that relates to the block x3 and A3 is located in the left of its parent node A10. According to the formula above, A3·p=0, A3·r=1, and A3·v=h(0∥x3∥1). Similarly, we can obtain A4=h(1∥x4∥1) and A10=h(1∥A3·v∥A4·v∥2). Table 2 illustrates the value of nodes in Figure 1.Table 2
Nodes of position-aware Merkle tree in Figure1.
Nodes
A
i
⋅
p
A
i
⋅
r
A
i
⋅
v
A
1
0
1
h
(
0
∥
x
1
∥
1
)
A
2
1
1
h
(
1
∥
x
2
∥
1
)
A
3
0
1
h
(
0
∥
x
3
∥
1
)
A
4
1
1
h
(
1
∥
x
4
∥
1
)
A
5
0
1
h
(
0
∥
x
5
∥
1
)
A
6
1
1
h
(
1
∥
x
6
∥
1
)
A
7
0
1
h
(
0
∥
x
7
∥
1
)
A
8
1
1
h
(
1
∥
x
8
∥
1
)
A
9
0
2
h
(
0
∥
A
1
⋅
v
∥
A
2
⋅
v
∥
2
)
A
10
1
2
h
(
1
∥
A
3
⋅
v
∥
A
4
⋅
v
∥
2
)
A
11
0
2
h
(
0
∥
A
5
⋅
v
∥
A
6
⋅
v
∥
2
)
A
12
1
2
h
(
1
∥
A
7
⋅
v
∥
A
8
⋅
v
∥
2
)
A
13
0
4
h
(
0
∥
A
9
⋅
v
∥
A
10
⋅
v
∥
4
)
A
14
1
4
h
(
1
∥
A
11
⋅
v
∥
A
12
⋅
v
∥
4
)
A
15
N
u
l
l
8
h
(
n
u
l
l
∥
A
13
⋅
v
∥
A
14
⋅
v
∥
8
)


## 3. Proposed Basic and Enhanced Schemes

Before presenting concrete constructions of SCESW and PT-SCESW schemes outlined above, we give some notations which will be utilized in the whole paper, as shown in Notations.


### 3.1. System Model

We first describe the system model of PT-SCESW scheme which mainly involves four entities, namely, Data Owner (DO), cloud service provider (CSP), user, and Third-Party Auditor (TPA), as shown in Figure2. When user passes the legal authentication, he/she can do comparable queries operations over encrypted data. First, the DO encrypts files by using SCESW scheme and finally sends the file CP and the corresponding φ to the CSP. When user wants to issue the search query over encrypted cloud data, he/she needs to submit a search query to CSP. The CSP returns the result of the query to the user. If the verifier wants to check the outsourced data integrity, she/he sends an auditing request to the TPA and the TPA submits the auditing challenge CL to the CSP. Upon receiving the auditing challenge CL, CSP computes P1, P2 and sends the auditing proof to the TPA. Then TPA conducts the integrity verification algorithm (Algorithm 2) to check the data integrity and returns the auditing report to the verifier. Figure 2 depicts the task of each entity, with an assumption that the DO is the verifier.(1)
DO: it has twofold responsibilities. Firstly, data files are encrypted through SCESW scheme and then outsourced to the CSP, as shown in step ①. Secondly, the DO sends auditing request to the TPA in order to check ciphertexts integrity, as illustrated in step ②.(2)
CSP: it can provide infinite storage and computation resources to the DO and the user. After executing auditing challenge, the CSP sends auditing proof to the TPA, as shown in step ④.(3)
User: it has the following responsibilities. Firstly, the user submits a query to compare a pair of ciphertextsCP and CP∗, as shown in step ⑥. Secondly, upon doing Cmp operation, the CSP returns the relationship of two numeric ciphertexts, as illustrated in step ⑦.(4)
TPA: it has twofold responsibilities. Firstly, the TPA submits auditing challenge to the CSP, as shown in step ③. Secondly, the TPA returns the auditing report to the verifier shown in step ⑤. If the result of auditing is correctness, system continues theCmp step; otherwise, the scheme demonstrates that ciphertexts are not with integrity and system stops working.Algorithm 2:Integrity verification algorithm.
Input: Root node Aroot, corresponding tag xi, integrity authentication path Υi, k′
represents numbers of corresponding nodes in Υi
Output: correct,  ⊥
(
1
) Let p0=¬A1i⋅p;r0=1;n0=1;v0=hp0∥xi∥r0;
(
2
) for  all  1≤j≤k′  do
(
3
) if  j=k′  then
(
4
)  pj=null;
(
5
) else
(
6
)  pj=¬Aj+1i⋅p.
(
7
)  rj=¬Aj+1i⋅r+rj-1;
(
8
) if  ¬Aji⋅p=1  then
(
9
)  nj=nj-1;vj=h(pj∥hj-1∥Aji⋅v∥rj);
(
10
)
else
(
11
)
if  ¬Aji⋅p=0  then
(
12
)  nj=nj-1+Aji⋅r;vj=h(pj∥Aji⋅v∥hj-1∥rj);
(
13
) if  rk′=Aroot⋅r;vk′=Aroot⋅v and nk′=i  then
(
14
) Output correct, nk′, A=null,rk′,vk′;
(
15
) else
(
16
) Output ⊥.Figure 2
The architecture of PT-SCESW scheme.


### 3.2. The SCESW Scheme

Lett be the window size, which means each block file has t bits. We assume arbitrary number n is a multiple of t. If n is not a multiple of t, we make n a multiple of t by adding zero in the end of the n’s binary code. SCESW scheme consists of five algorithms, namely, KeyGen, Par, Der, Enc, and Cmp. When user passes the legal authentication, he/she can do comparable queries operations over encrypted data. Thus, we mainly consider data security and comparable queries operations over ciphertexts. A detailed construction of SCESW scheme is depicted as follows.(1) Definitions of SCESW Scheme.The SCESW scheme is composed of five algorithms involving KeyGen, Par, Der, Enc, and Cmp. SCESW system definition can be defined in Algorithm 3.Algorithm 3:Definition of SCESW scheme.
SCESW scheme is a tuple of algorithms includingKeyGen, Par, Der, Enc, Cmp,
which are shown as follows:
(i) KeyGen(1k): given the security parameter k∈N, range parameter n∈N and master
key MSK, the DO runs the algorithm to output the master key MSK and public
parameter PP.
(ii) ParN: given the number N, the DO runs the algorithm to output the number N′
rewritten through its binary code by utilizing sliding window method,
where t represents the window size, m=n/t is the number of blocks and N=N′
N
=
b
0
,
…
,
b
n
-
1
=
∑
0
≤
i
≤
n
-
1
b
i
2
i;
N
′
=
B
0
,
…
,
B
m
-
1
=
∑
0
≤
i
≤
m
-
1
B
i
2
t
i
.
(iii) Der(k,n,MSK,N): given the security parameter k∈N, range parameter n∈N,
master key MSK and num 0≤N≤2n, the DO runs the algorithm to output a token TK.
(iv) Enc(k,n,MSK,N): given the security parameter k∈N, range parameter n∈N,
master key MSK and num 0≤N≤2n, the DO runs the algorithm to generate
the ciphertext CP and submits it to the CSP.
(v) Cmp(PP,CP,CP∗,TK): given the public parameter PP, two ciphertexts CP
and CP∗, and token TK, the CSP outputs -1,0,1, then it returns the relevant
search results to the user.(2) Details of SCESW Scheme.Concrete construction of SCESW scheme can be defined as follows.(i)
KeyGen(k,n)→(PP,MSK): given a security parameter k∈N and range parameter n∈N, KeyGen first randomly chooses hash functions: H1(·),H2(·),H3(·):0,1k×0,1∗→0,1k and then returns PP=(n,H1,H2,H3).Finally,KeyGen algorithm outputs a public parameter PP and a master key MSK.(ii)
Par(N,t)→(N′): given an original number N, the DO rewrites it through its binary code by utilizing sliding window method with (2), where t represents the window size, m=n/t is the number of blocks, and N=N′:(2)N=b0,…,bn-1=∑0≤i≤n-1bi2i;N′=B0,…,Bm-1=∑0≤i≤m-1Bi2ti.(iii)
Der(PP,MSK,N)→(TK): given PP=(n,H1,H2,H3), master key MSK, and number N, Der algorithm outputs a token TK=(d1,d2,…,dm) with the following equations:(3)N=B0,…,Bm-1=∑0≤i≤m-1Bi2ti;B0=b0,b1,…,bt-1,…,Bm-1=bn-t,bn-t+1,…,bn-1,Bm=0;di=H1MSK,Bm,…,Bi,i=1,…,m.(iv)
Enc(PP,MSK,N)→(CP): given PP=(n,H1,H2,H3), master key MSK, and number N, Enc randomly picks TK=(d1,d2,…,dm) and a random number I∈0,1k, where(4)N=B0,…,Bm-1=∑0≤i≤m-1Bi2ti.Next,Enc generates fi, where(5)fi=H3di+1,I+H2MSK,di+1+Bimod2t+1-1i=m-1,…,0.Enc finally outputs ciphertexts CP=(I,F)=I,f0,f1,…,fm-1. The DO submits CP to the CSP.Here,(f0,f1,…,fm-1) can be encoded into Ft to reduce storage space, where(6)Ft=∑0≤i≤m-1fi·2t+1-1i.(v)
Cmp(CP,CP∗,TK)→(ϖ): given two ciphertexts CP=(I,(f0,f1,…,fm-1)), CP∗=(I′,F∗)=(I′,(f0′,f1′,…,fm-1′)), and a token TK=(d1,d2,…,dm), Cmp algorithm sets j=m-1 and keeps producing cj by decreasing j by 1 at each step, where(7)cj=fj-fj′-H3dj+1,I+H3dj+1,I′mod2t+1-1.This algorithm stops whenCmp produces cj such that cj≠0 or when cj=0 for all i=m-1,m-2,…,0. If N>N∗, then 1≤cj≤2t-1 holds. If N<N∗, then 2t≤cj≤2(t+1)-2 holds. If N=N∗, then cj≡0 holds. Then we have (8)ϖ=-1if1≤cj≤2t-10ifcj≡01if2t≤cj≤2t+1-2.


### 3.3. The PT-SCESW Scheme

(1) Definitions of PT-SCESW Scheme.To efficiently support public auditing, we propose an enhanced SCESW scheme called PT-SCESW scheme. PT-SCESW scheme consists of four phasesSetup, Encryption, Auditing and Comparison, defined in Algorithm 4. When user passes the legal authentication, he/she can do comparable queries operations over encrypted data. Thus, we mainly consider data security and comparable queries operations over ciphertexts.Algorithm 4:Definition of PT-SCESW scheme.
PT-SCESW scheme is a series of algorithms namelySetup, Encryption, Auditing, Comparison
phases, which are shown as follows:
Setup Phase.The DO chooses a security parameter k∈N, range parameter n∈N and master key
M
S
K to generate a public parameter PP. The DO runs KeyGen to produce the secret key SK
and public keyPK. Setup phase outputs the secret key SK, public key PK, public parameter
P
P and master key MSK. Setup phase contains KeyGen algorithm in SCESW scheme. The DO
sharesPK with others and preserves SK as a secret.
Encryption Phase
(i) Par(N), Der(PP,MSK,N): system definitions are similar to SCESW scheme, as shown
in Algorithm 3.
(ii) Enc(PP,MSK,N): given a security parameter k∈N, range parameter n∈N, master
key MSK, public key PK, private key SK and num 0≤N≤2n, the DO runs the
algorithm to output a ciphertext CP, set φ and the metadata. Then file CP and set φ will
be sent by the DO to the CSP. The metadata might be signed and kept by the DO.
Auditing Phase
(i) ChalGen(s)→(CL): given the secret parameter s, the verifier outputs auditing
challenge CL for the query.
(ii) ProofGen(gs,F,φ,CL)→(P): given the DO’s public parameter gs, file F, set φ and
auditing challenge CL, the TPA outputs the auditing proof P to verify that the CSP
owns the outsourced file correctly.
(iii) ProofCheck(PK,CL,metadata,P)→(correct,⊥): given the DO’s public key PK,
evidence P, metadata and auditing challenge CL, the TPA outputs corrector ⊥.
If the proof P passes the verification, the function outputs correct; otherwise, the
function outputs ⊥ and the system stops to work. At last, TPA sends the auditing
report to the verifier.
Comparison Phase
(i) Cmp(CP,CP∗,TK): system definition is similar to SCESW scheme, as illustrated
in Algorithm 3.(2) Details of PT-SCESW Scheme.Concrete construction of PT-SCESW scheme is defined as follows.Setup Phase.This phase contains the KeyGen algorithm, which is utilized by the DO to initialize system.The DO chooses a security parameterk∈N, range parameter n∈N, master key MSK∈0,1∗, and hash functions H1,H2,H3. Then he/she calculates the secret key SK=(p,q) and public key PK=(N=p·q,g), where p,q are two large primes and g is the generator of a high-order cyclic group. Besides, he/she defines PP=(n,H1,H2,H3). The DO runs KeyGen algorithm to generate the public parameter PP and secret key SK. Setup phase contains KeyGen algorithm in SCESW scheme.Setup phase outputs the secret key SK, public key PK, public parameter PP, and master key MSK.Encryption Phase.
Par algorithm is run by the DO to generate the num N which adopts the sliding window method. Der algorithm is used by the DO to produce the token of the num N. Enc algorithm is run by the DO to generate ciphertexts of the num N.(i)
Par(N)→(N′),Der(PP,MSK,N)→(TK): algorithms are similar to SCESW scheme.(ii)
Enc(PP,MSK,N)→(CP): suppose that a public parameter PP=(n,H1,H2,H3), master key MSK, and number N are given, where(9)N=B0,…,Bm-1=∑0≤i≤m-1Bi2ti,Enc algorithm randomly chooses a token TK=(d1,d2,…,dm) and a random number I∈0,1k. Next Enc generates(10)fi=H3di+1,I+H2MSK,di+1+Bimod2t+1-1i=m-1,…,0.Enc finally outputs ciphertexts CP=(I,(f0,f1,…,fm-1)). Here, (f0,f1,…,fm-1) can be encoded into an integer Ft to make ciphertexts shorter, where(11)Ft=∑0≤i≤m-1fi·2t+1-1i.The DO regardsF=(f0,f1,…,fm-1) as m parts. For each file block fi,(i=0,…,m-1), the DO computes tag xi=gmimodN. Then the user constructs the PMT according to the data block tags X=x1,…,xm and calculates root value Aroot as the metadata, where Aroot=(Aroot·p,Aroot·r,Aroot·v). A and SK can be kept by the DO, while file F and set φ=X,PMT can be sent to the CSP.Auditing Phase.
ChalGen algorithm is run by the verifier to produce the auditing challenge CL. ProofGen algorithm is used by the TPA to generate the auditing proof P. ChalGen algorithm is conducted by the TPA to produce auditing results.(i)
ChalGen(s)→(CL): the verifier randomly chooses the secret parameter s∈ZN∗ and calculates the public parameter gs=gsmodN. The verifier randomly chooses c weight coefficient pairs Q=ij,ajj=1,…,c, where ij∈[1,m] is different from each other, aj∈0,1l. Then the verifier sends the auditing request to the TPA, and TPA sends auditing challenge CL=gs,Q to the CSP.(ii)
ProofGen(gs,F,φ,CL)→(P): upon receiving the CL=gs,Q sent by the verifier, the CSP computes P1=gs∑ci=1aj·fijmodN, P2=xij,Υijj=1,…,c. Then the CSP returns auditing proof P=(P1,P2) to the TPA.(iii)
ProofCheck(PK,CL,metadata,P)→(correct,⊥): upon receiving the auditing proof P=(P1,P2), the TPA conducts Algorithm 2 to verify (A,xij,Υij)→correct,⊥, in which j=1,…,c. If Algorithm 2 outputs correct, it means tags corresponding to the auditing request are correct. Then, the TPA computes P3=∏j=1c(xij)ajmodN. If P3s=P1 holds, it outputs correct, which means the auditing challenge CL passes the verification and the system continues the Cmp algorithm; otherwise, it outputs ⊥, which means the outsourced file was forged at the CSP side and the system stops the Cmp algorithm.Comparison Phase.
Cmp algorithm is employed by the user to compare the relationship of the numbers N and N∗ from CP and CP∗.(i)
Cmp(CP,CP∗,TK)→(ϖ): Cmp algorithm is similar to SCESW scheme. Given two ciphertexts CP=(I,(f0,f1,…,fm-1)), CP∗=(I′,F∗)=(I′,(f0′,f1′,…,fm-1′)) and a token TK=(d1,d2,…,dm), Cmp algorithm outputs -1,0,1.


## 3.1. System Model

We first describe the system model of PT-SCESW scheme which mainly involves four entities, namely, Data Owner (DO), cloud service provider (CSP), user, and Third-Party Auditor (TPA), as shown in Figure2. When user passes the legal authentication, he/she can do comparable queries operations over encrypted data. First, the DO encrypts files by using SCESW scheme and finally sends the file CP and the corresponding φ to the CSP. When user wants to issue the search query over encrypted cloud data, he/she needs to submit a search query to CSP. The CSP returns the result of the query to the user. If the verifier wants to check the outsourced data integrity, she/he sends an auditing request to the TPA and the TPA submits the auditing challenge CL to the CSP. Upon receiving the auditing challenge CL, CSP computes P1, P2 and sends the auditing proof to the TPA. Then TPA conducts the integrity verification algorithm (Algorithm 2) to check the data integrity and returns the auditing report to the verifier. Figure 2 depicts the task of each entity, with an assumption that the DO is the verifier.(1)
DO: it has twofold responsibilities. Firstly, data files are encrypted through SCESW scheme and then outsourced to the CSP, as shown in step ①. Secondly, the DO sends auditing request to the TPA in order to check ciphertexts integrity, as illustrated in step ②.(2)
CSP: it can provide infinite storage and computation resources to the DO and the user. After executing auditing challenge, the CSP sends auditing proof to the TPA, as shown in step ④.(3)
User: it has the following responsibilities. Firstly, the user submits a query to compare a pair of ciphertextsCP and CP∗, as shown in step ⑥. Secondly, upon doing Cmp operation, the CSP returns the relationship of two numeric ciphertexts, as illustrated in step ⑦.(4)
TPA: it has twofold responsibilities. Firstly, the TPA submits auditing challenge to the CSP, as shown in step ③. Secondly, the TPA returns the auditing report to the verifier shown in step ⑤. If the result of auditing is correctness, system continues theCmp step; otherwise, the scheme demonstrates that ciphertexts are not with integrity and system stops working.Algorithm 2:Integrity verification algorithm.
Input: Root node Aroot, corresponding tag xi, integrity authentication path Υi, k′
represents numbers of corresponding nodes in Υi
Output: correct,  ⊥
(
1
) Let p0=¬A1i⋅p;r0=1;n0=1;v0=hp0∥xi∥r0;
(
2
) for  all  1≤j≤k′  do
(
3
) if  j=k′  then
(
4
)  pj=null;
(
5
) else
(
6
)  pj=¬Aj+1i⋅p.
(
7
)  rj=¬Aj+1i⋅r+rj-1;
(
8
) if  ¬Aji⋅p=1  then
(
9
)  nj=nj-1;vj=h(pj∥hj-1∥Aji⋅v∥rj);
(
10
)
else
(
11
)
if  ¬Aji⋅p=0  then
(
12
)  nj=nj-1+Aji⋅r;vj=h(pj∥Aji⋅v∥hj-1∥rj);
(
13
) if  rk′=Aroot⋅r;vk′=Aroot⋅v and nk′=i  then
(
14
) Output correct, nk′, A=null,rk′,vk′;
(
15
) else
(
16
) Output ⊥.Figure 2
The architecture of PT-SCESW scheme.


## 3.2. The SCESW Scheme

Lett be the window size, which means each block file has t bits. We assume arbitrary number n is a multiple of t. If n is not a multiple of t, we make n a multiple of t by adding zero in the end of the n’s binary code. SCESW scheme consists of five algorithms, namely, KeyGen, Par, Der, Enc, and Cmp. When user passes the legal authentication, he/she can do comparable queries operations over encrypted data. Thus, we mainly consider data security and comparable queries operations over ciphertexts. A detailed construction of SCESW scheme is depicted as follows.(1) Definitions of SCESW Scheme.The SCESW scheme is composed of five algorithms involving KeyGen, Par, Der, Enc, and Cmp. SCESW system definition can be defined in Algorithm 3.Algorithm 3:Definition of SCESW scheme.
SCESW scheme is a tuple of algorithms includingKeyGen, Par, Der, Enc, Cmp,
which are shown as follows:
(i) KeyGen(1k): given the security parameter k∈N, range parameter n∈N and master
key MSK, the DO runs the algorithm to output the master key MSK and public
parameter PP.
(ii) ParN: given the number N, the DO runs the algorithm to output the number N′
rewritten through its binary code by utilizing sliding window method,
where t represents the window size, m=n/t is the number of blocks and N=N′
N
=
b
0
,
…
,
b
n
-
1
=
∑
0
≤
i
≤
n
-
1
b
i
2
i;
N
′
=
B
0
,
…
,
B
m
-
1
=
∑
0
≤
i
≤
m
-
1
B
i
2
t
i
.
(iii) Der(k,n,MSK,N): given the security parameter k∈N, range parameter n∈N,
master key MSK and num 0≤N≤2n, the DO runs the algorithm to output a token TK.
(iv) Enc(k,n,MSK,N): given the security parameter k∈N, range parameter n∈N,
master key MSK and num 0≤N≤2n, the DO runs the algorithm to generate
the ciphertext CP and submits it to the CSP.
(v) Cmp(PP,CP,CP∗,TK): given the public parameter PP, two ciphertexts CP
and CP∗, and token TK, the CSP outputs -1,0,1, then it returns the relevant
search results to the user.(2) Details of SCESW Scheme.Concrete construction of SCESW scheme can be defined as follows.(i)
KeyGen(k,n)→(PP,MSK): given a security parameter k∈N and range parameter n∈N, KeyGen first randomly chooses hash functions: H1(·),H2(·),H3(·):0,1k×0,1∗→0,1k and then returns PP=(n,H1,H2,H3).Finally,KeyGen algorithm outputs a public parameter PP and a master key MSK.(ii)
Par(N,t)→(N′): given an original number N, the DO rewrites it through its binary code by utilizing sliding window method with (2), where t represents the window size, m=n/t is the number of blocks, and N=N′:(2)N=b0,…,bn-1=∑0≤i≤n-1bi2i;N′=B0,…,Bm-1=∑0≤i≤m-1Bi2ti.(iii)
Der(PP,MSK,N)→(TK): given PP=(n,H1,H2,H3), master key MSK, and number N, Der algorithm outputs a token TK=(d1,d2,…,dm) with the following equations:(3)N=B0,…,Bm-1=∑0≤i≤m-1Bi2ti;B0=b0,b1,…,bt-1,…,Bm-1=bn-t,bn-t+1,…,bn-1,Bm=0;di=H1MSK,Bm,…,Bi,i=1,…,m.(iv)
Enc(PP,MSK,N)→(CP): given PP=(n,H1,H2,H3), master key MSK, and number N, Enc randomly picks TK=(d1,d2,…,dm) and a random number I∈0,1k, where(4)N=B0,…,Bm-1=∑0≤i≤m-1Bi2ti.Next,Enc generates fi, where(5)fi=H3di+1,I+H2MSK,di+1+Bimod2t+1-1i=m-1,…,0.Enc finally outputs ciphertexts CP=(I,F)=I,f0,f1,…,fm-1. The DO submits CP to the CSP.Here,(f0,f1,…,fm-1) can be encoded into Ft to reduce storage space, where(6)Ft=∑0≤i≤m-1fi·2t+1-1i.(v)
Cmp(CP,CP∗,TK)→(ϖ): given two ciphertexts CP=(I,(f0,f1,…,fm-1)), CP∗=(I′,F∗)=(I′,(f0′,f1′,…,fm-1′)), and a token TK=(d1,d2,…,dm), Cmp algorithm sets j=m-1 and keeps producing cj by decreasing j by 1 at each step, where(7)cj=fj-fj′-H3dj+1,I+H3dj+1,I′mod2t+1-1.This algorithm stops whenCmp produces cj such that cj≠0 or when cj=0 for all i=m-1,m-2,…,0. If N>N∗, then 1≤cj≤2t-1 holds. If N<N∗, then 2t≤cj≤2(t+1)-2 holds. If N=N∗, then cj≡0 holds. Then we have (8)ϖ=-1if1≤cj≤2t-10ifcj≡01if2t≤cj≤2t+1-2.


## 3.3. The PT-SCESW Scheme

(1) Definitions of PT-SCESW Scheme.To efficiently support public auditing, we propose an enhanced SCESW scheme called PT-SCESW scheme. PT-SCESW scheme consists of four phasesSetup, Encryption, Auditing and Comparison, defined in Algorithm 4. When user passes the legal authentication, he/she can do comparable queries operations over encrypted data. Thus, we mainly consider data security and comparable queries operations over ciphertexts.Algorithm 4:Definition of PT-SCESW scheme.
PT-SCESW scheme is a series of algorithms namelySetup, Encryption, Auditing, Comparison
phases, which are shown as follows:
Setup Phase.The DO chooses a security parameter k∈N, range parameter n∈N and master key
M
S
K to generate a public parameter PP. The DO runs KeyGen to produce the secret key SK
and public keyPK. Setup phase outputs the secret key SK, public key PK, public parameter
P
P and master key MSK. Setup phase contains KeyGen algorithm in SCESW scheme. The DO
sharesPK with others and preserves SK as a secret.
Encryption Phase
(i) Par(N), Der(PP,MSK,N): system definitions are similar to SCESW scheme, as shown
in Algorithm 3.
(ii) Enc(PP,MSK,N): given a security parameter k∈N, range parameter n∈N, master
key MSK, public key PK, private key SK and num 0≤N≤2n, the DO runs the
algorithm to output a ciphertext CP, set φ and the metadata. Then file CP and set φ will
be sent by the DO to the CSP. The metadata might be signed and kept by the DO.
Auditing Phase
(i) ChalGen(s)→(CL): given the secret parameter s, the verifier outputs auditing
challenge CL for the query.
(ii) ProofGen(gs,F,φ,CL)→(P): given the DO’s public parameter gs, file F, set φ and
auditing challenge CL, the TPA outputs the auditing proof P to verify that the CSP
owns the outsourced file correctly.
(iii) ProofCheck(PK,CL,metadata,P)→(correct,⊥): given the DO’s public key PK,
evidence P, metadata and auditing challenge CL, the TPA outputs corrector ⊥.
If the proof P passes the verification, the function outputs correct; otherwise, the
function outputs ⊥ and the system stops to work. At last, TPA sends the auditing
report to the verifier.
Comparison Phase
(i) Cmp(CP,CP∗,TK): system definition is similar to SCESW scheme, as illustrated
in Algorithm 3.(2) Details of PT-SCESW Scheme.Concrete construction of PT-SCESW scheme is defined as follows.Setup Phase.This phase contains the KeyGen algorithm, which is utilized by the DO to initialize system.The DO chooses a security parameterk∈N, range parameter n∈N, master key MSK∈0,1∗, and hash functions H1,H2,H3. Then he/she calculates the secret key SK=(p,q) and public key PK=(N=p·q,g), where p,q are two large primes and g is the generator of a high-order cyclic group. Besides, he/she defines PP=(n,H1,H2,H3). The DO runs KeyGen algorithm to generate the public parameter PP and secret key SK. Setup phase contains KeyGen algorithm in SCESW scheme.Setup phase outputs the secret key SK, public key PK, public parameter PP, and master key MSK.Encryption Phase.
Par algorithm is run by the DO to generate the num N which adopts the sliding window method. Der algorithm is used by the DO to produce the token of the num N. Enc algorithm is run by the DO to generate ciphertexts of the num N.(i)
Par(N)→(N′),Der(PP,MSK,N)→(TK): algorithms are similar to SCESW scheme.(ii)
Enc(PP,MSK,N)→(CP): suppose that a public parameter PP=(n,H1,H2,H3), master key MSK, and number N are given, where(9)N=B0,…,Bm-1=∑0≤i≤m-1Bi2ti,Enc algorithm randomly chooses a token TK=(d1,d2,…,dm) and a random number I∈0,1k. Next Enc generates(10)fi=H3di+1,I+H2MSK,di+1+Bimod2t+1-1i=m-1,…,0.Enc finally outputs ciphertexts CP=(I,(f0,f1,…,fm-1)). Here, (f0,f1,…,fm-1) can be encoded into an integer Ft to make ciphertexts shorter, where(11)Ft=∑0≤i≤m-1fi·2t+1-1i.The DO regardsF=(f0,f1,…,fm-1) as m parts. For each file block fi,(i=0,…,m-1), the DO computes tag xi=gmimodN. Then the user constructs the PMT according to the data block tags X=x1,…,xm and calculates root value Aroot as the metadata, where Aroot=(Aroot·p,Aroot·r,Aroot·v). A and SK can be kept by the DO, while file F and set φ=X,PMT can be sent to the CSP.Auditing Phase.
ChalGen algorithm is run by the verifier to produce the auditing challenge CL. ProofGen algorithm is used by the TPA to generate the auditing proof P. ChalGen algorithm is conducted by the TPA to produce auditing results.(i)
ChalGen(s)→(CL): the verifier randomly chooses the secret parameter s∈ZN∗ and calculates the public parameter gs=gsmodN. The verifier randomly chooses c weight coefficient pairs Q=ij,ajj=1,…,c, where ij∈[1,m] is different from each other, aj∈0,1l. Then the verifier sends the auditing request to the TPA, and TPA sends auditing challenge CL=gs,Q to the CSP.(ii)
ProofGen(gs,F,φ,CL)→(P): upon receiving the CL=gs,Q sent by the verifier, the CSP computes P1=gs∑ci=1aj·fijmodN, P2=xij,Υijj=1,…,c. Then the CSP returns auditing proof P=(P1,P2) to the TPA.(iii)
ProofCheck(PK,CL,metadata,P)→(correct,⊥): upon receiving the auditing proof P=(P1,P2), the TPA conducts Algorithm 2 to verify (A,xij,Υij)→correct,⊥, in which j=1,…,c. If Algorithm 2 outputs correct, it means tags corresponding to the auditing request are correct. Then, the TPA computes P3=∏j=1c(xij)ajmodN. If P3s=P1 holds, it outputs correct, which means the auditing challenge CL passes the verification and the system continues the Cmp algorithm; otherwise, it outputs ⊥, which means the outsourced file was forged at the CSP side and the system stops the Cmp algorithm.Comparison Phase.
Cmp algorithm is employed by the user to compare the relationship of the numbers N and N∗ from CP and CP∗.(i)
Cmp(CP,CP∗,TK)→(ϖ): Cmp algorithm is similar to SCESW scheme. Given two ciphertexts CP=(I,(f0,f1,…,fm-1)), CP∗=(I′,F∗)=(I′,(f0′,f1′,…,fm-1′)) and a token TK=(d1,d2,…,dm), Cmp algorithm outputs -1,0,1.


## 4. Security Analysis

In this section, we will give properties of completeness and weak indistinguishability in PT-SCESW scheme by theoretical analysis, which are similar to SCESW scheme.Theorem 1.
The PT-SCESW scheme is complete as long asH1, H2, and H3 are pseudorandom functions and the CSP honestly performs operations according to the auditing challenge.Proof.
We denote thatCP and CP∗ are generated from N and N∗, respectively.(12)N=∑0≤i≤n-1bi2i=∑0≤i≤m-1Bi2ti;N∗=∑0≤i≤n-1βi2i=∑0≤i≤m-1Bi′2ti,where t is the window size; m=n/t is the number of blocks via utilizing sliding window technology.(13)TK=d0,…,dm;TK∗=d0′,…,dm′;CP=I,f0,…,fm-1;CP∗=I′,f0′,…,fm-1′.
From (3) we know that di and di′ depend on Bi,Bi+1,Bi′,Bi+1′, and MSK. Suppose that l is the first different block of N and N∗, for i=l+1,…,m-1; if the equation Bi+1=Bi+1′ holds, then di+1=di+1′ holds. Hence, if N=N∗, cj=0 holds for i=0,…,m-1, and then ϖ outputs 0. If N≠N∗, for this arbitrary j,(14)cj=fj-fj′-H3dj+1,I+H3dj+1,I′mod2t+1-1=fj-H3dj+1,I-fj′-H3dj+1,I′mod2t+1-1=H3dj+1,I+H2MSK,dj+1+Bj-H3dj+1,I-H3dj′+1,I+H2MSK,dj′+1+Bj′-H3dj+1,I′mod2t+1-1=Bj-Bj′mod2t+1-1.
Forj=0,…,m-1, equation Bj-Bj′=0 means N=N∗; equation Bj-Bj′≠0 means j is the first different bit. Specifically, if 1≤cj≤(2t-1), then N>N∗; if 2t≤cj≤(2(t+1)-2), then N<N∗.
Upon receivingCL=gs,Q sent by the verifier, the CSP computes P1=gs∑ci=1aj·fijmodN,P2=xij,Aij,Υijj=1,…,c. According to the PMT formula, we can prove that xij is the corresponding tag to the leaf node Aij and the result outputs correctly.
The verifier computes(15)P3=∏j=1cxijajmodN=∏j=1cgfijajmodN=g∑ci=1aj·fijmodN,P3smodN=g∑ci=1aj·fijmodNsmodN=gs·∑ci=1aj·fijmodN=gs∑ci=1aj·fijmodN=P1modN.
Hence, the PA-SCESW scheme is complete.Theorem 2.
The PT-SCESW scheme is weakly indistinguishable ifH1, H2, and H3 are pseudorandom functions.Proof.
LetC,CA, and CB represent challengers. Suppose that there exists an adversary A such that AdvC,A≔PrExpC,Ak=0-PrExpC,Ak=1≥ϵ in the weak distinguishing game. Then, we know that hash function is distinguishable from the random function, which is against the assumption that they are pseudorandom functions. In particular, we consider a sequence of games by challengers C,CA, and CB and then prove the theorem by the hybrid argument. From literature [33], we know that AdvC,A-AdvCB,A<ϵ as long as hash is a pseudorandom function as well as AdvCB,A=0. Hence, AdvC,A<ϵ and Theorem 2 is proved.


## 5. Performance

In this section, we first compare our schemes with SCE scheme inEncryption Phase, Comparison Phase, andAuditing Phase in experiments, as shown in Tables 3 and 4, respectively. InAuditing Phase, auditing costs of [40] are almost of PT-SCESW scheme, so we just evaluate the actual performance of PT-SCESW scheme in experiments. These experiments are conducted using C on a Ubuntu Server 15.04 with Intel Core i5 Processor 2.3 GHz and Paring Based Cryptography (PBC). In Table 3, L is the L bit of numbers N1=(β0,…,βm-1),N2=(γ0,…,γm-1) such that (βL,…,βm-1)=(γL,…,γm-1),βL-1<γL-1 for two numbers. We randomly choose k and n, where k=160 bits, n=1024 bits in experimental simulations. Experimental tests are conducted for 100 times.Table 3
Comparison of computational cost in various schemes.
PT-SCESW scheme
SCESW scheme
SCE scheme [33]
Encryption phase
3
m
⋅
a
+
m
⋅
E
3
m
⋅
a
4
n
⋅
a
Comparison phase
2
(
m
-
L
+
1
)
⋅
a
2
(
m
-
L
+
1
)
⋅
a
2
(
n
-
L
+
2
)
⋅
a
Auditing phase
(
2
+
c
)
E
+
(
k
′
+
1
)
a
0
0
Note. m,n,L,a,c,k′,E represent sliding window numbers of N, original window numbers of N, hash operations, number of windows for verification, numbers of corresponding nodes in Υi, and exponentiation operation, respectively.Table 4
Comparison of storage overhead in various schemes.
Ciphertext generation phase
Token generation phase
SCE scheme [33]
(
n
+
1
)
⋅
k
k
+
(
ln
⁡
3
/
ln
⁡
2
)
⋅
n
SCESW scheme
m
⋅
k
k
+
(
ln
⁡
2
t
+
1
-
1
/
ln
⁡
(
t
+
1
)
)
⋅
m
PA-SCESW scheme
m
⋅
k
k
+
(
ln
⁡
2
t
+
1
-
1
/
ln
⁡
(
t
+
1
)
)
⋅
m
Note. m,n,k represent sliding window numbers of N, original window numbers of N, and output bits of hash operations, respectively.We will mainly focus on the computational and storage overhead. Due to the fact that SCESW scheme utilizes sliding window method, a comparison in computational and storage overhead between SCESW scheme and SCE scheme is made, which shows that SCESW scheme is cost-effective. Analysis can demonstrate that PT-SCESW scheme by using sliding window technology can relief the high computational and storage overhead. To largely reduce storage overhead,(f0,f1,…,fm-1) can be encoded into an integer Ft to make ciphertexts shorter in SCESW scheme and PT-SCESW scheme, shown in Table 4, where(16)Ft=∑0≤i≤m-1fi·2t+1-1i.Considering computational costs, we just only consider several time-consuming operations, such as exponentiation operation “E” and Hashi(i=1,2,3,4,5) operations. Table 3 shows the theoretical analysis of these schemes. Now we give detailed theoretical analysis of PT-SCESW scheme as an example.(1)
InEncryption Phase, computing CP and tags xi for each block fi can bring the exponentiation operation “E” and Hashi(i=1,2,3) operation “h.” Overall, this phase costs 3m·a+m·E operations.(2)
InComparison Phase, costs mainly depends on computing cj, with computing cj only bringing Hashi(i=1,2,3) operation “h.” Overall, this phase costs 2(m-L+1)·a operations.(3)
InAuditing Phase, costs mainly depend on computing gs=gsmodN, P1=gs∑ci=1aj·fijmodN,P3=∏j=1c(xij)ajmodN, and hash operations in Algorithm 2. Overall, this phase costs (2+c)E+(k′+1)a operations.In Figure3, we set n=1024 bits and vary numbers of sliding windows m from 4 to 512, and then we notice that the encryption time in PT-SCESW scheme approximately increases with m. For example, when we set m=32, encryption costs of SCESW scheme and PT-SCESW scheme are 1.214 ms and 2.034 ms, respectively, which is much more smaller than SCE scheme. Due to using sliding window method, PT-SCESW scheme and SCESW scheme can significantly reduce encryption costs.Figure 3
Encryption costs in PT-SCESW scheme.In Figure4, we set n=1024 bits and m=256, and then we notice that the comparable time in PT-SCESW scheme approximately decreases with L. For example, when setting L=63, our scheme needs 4.674 ms to compare ciphertexts. InComparison Phase, the PT-SCESW scheme and SCESW scheme have similar computational burden. Based on sliding window method, our PT-SCESW scheme and SCESW scheme can significantly reduce the computational overhead when these schemes are compared with SCE scheme.Figure 4
Comparison costs in PT-SCESW scheme.In Figure5, we set n=1024 bits and vary number of windows for verification presented by c from 2 to 256, and then we notice that the auditing time in PT-SCESW scheme approximately increases with c. For example, when setting c=16, our scheme needs 2.472 ms to make auditing. Therefore, our PT-SCESW scheme is still acceptable in practice, especially for users with constrained computing resources and capacities.Figure 5
Auditing costs in PT-SCESW scheme.In summary, actual performance results are completely in accord with the theoretical analysis shown in Tables3 and 4. Exploring PT-SCESW scheme mainly focuses on achieving one property that is auditing. PT-SCESW scheme is feasible and efficient in practice applications, especially for users with constrained computing resources and capacities.


## 6. Conclusion

In this paper, a basic scheme named SCESW scheme is proposed for relief of the computational and storage overhead by using sliding window method. Furthermore, PT-SCESW scheme is presented for authorized users to support public auditing and reduce computational and storage overhead. Formal security analysis proves that PT-SCESW and SCESW schemes can guarantee data security and integrity as well as weak indistinguishability in standard model. Actual performance evaluation shows that, compared with SCE scheme, SCESW scheme and PT-SCESW scheme can relieve the computational and storage burden to some extent. In our future work, we will enhance PT-SCESW scheme by deducing its computational and storage overhead. Nevertheless, there exists another important problem to be solved. How to apply the PT-SCESW scheme to image retrieval field is rather a challenging task to be solved in cloud computing and artificial intelligence fields.



---

*Source: 6430850-2017-12-27.xml*