# Secure and Efficient Image Retrieval over Encrypted Cloud Data

Authors: Haihua Liang; Xinpeng Zhang; Hang Cheng; Qiuhan Wei
Journal: Security and Communication Networks
 (2018)

---

## Abstract

This paper proposes a novel image retrieval scheme over encrypted cloud data, which achieves high efficiency and confidentiality. For the purpose of improving search efficiency, an index tree is often deployed in the image retrieval scheme. Meanwhile, the confidentiality of the sensitive cloud data, such as outsourced images, index tree, and query request, is also a key issue. Firstly, a balanced binary clustering algorithm is exploited over the integrated image features composed of basic features, such as HSV histogram and DCT histogram, yielding a balanced binary tree (BBT). In particular, due to the adoption of a balanced index tree, our scheme can achieve logarithmic search time. Secondly, the secure inner product is employed to encrypt the index vector and query feature. Finally, to resist the statistical attack of the frequency distribution of the retrieved results, we copy the database and merge the subtree of encrypted BBT to blind the search results. Security analysis and experimental results show that the proposed scheme is secure and efficient.


---

## Body

## 1. Introduction

With the arrival of the cloud computing, secure image retrieval on the cloud has attracted more and more attention in recent years [1]. Due to high convenience and economic savings, both enterprises and individuals tend to employ the cloud to store and manage their sensitive data, such as photo albums and personal health documents. To ensure the confidentiality of outsourced data, the common approach is to encrypt the data before it is outsourced to the cloud. However, the traditional encryption may make the basic data operations unfeasible, for example, the information retrieval of encrypted data. In the ciphertext scenario, how to achieve an efficient retrieval while protecting the privacy of customers becomes a challenging problem.At present, there are three main issues that restrict the development of information retrieval in the encrypted domain. The first issue is to realize searchable functionality on encrypted data and achieve the same precision as plaintext data. Certainly, a naive approach is to download all the ciphertext, decrypt them, and search locally in the plaintext. However, it will incur heavy cost of bandwidth and computation. To address this issue, cryptographic techniques, such as homomorphic encryption [2] and multiparty computation, can be employed to encrypt the plaintext data and support search operation in the ciphertext. However, the above methods are concerned more with data confidentiality than retrieval efficiency, and the cost is expensive in practical applications. In the contrary, some efficient techniques, such as order-preserving encryption (OPE) [3, 4], randomized hash functions [5–7], and asymmetric scalar-product-preserving encryption (ASPE) [8], are widely adopted. The reason is that they take both the data confidentiality and retrieval efficiency into account. The second issue is that although plaintext content of the encrypted data is not leaked in the above schemes, some statistical information, such as the request frequency of encrypted query (i.e., query pattern) or the access frequency of encrypted result (i.e., access pattern), may leak the privacy of query user. Oblivious RAMs [9] is a solution to protect the access pattern, but not practical enough. The third issue is that a retrieval scheme of linear efficiency is not desirable, because the search time will increase as the dataset becomes larger. In fact, secure information retrieval is commonly used for images or documents stored in a cloud server. We detail them as follows.On the one hand, abundant works have been put forward to achieve secure retrieval in the encrypted documents. For example, Boolean search based on the single keyword is separately proposed in symmetric key setting [11] and public key setting [12]. Since similarity search is more practical than Boolean search, multi-keyword ranked search [13] is studied to enrich search functionality and improve result accuracy, where each document is associated with an index vector. Each element of the vector indicates whether a keyword exists or represents its “term frequency (TF) × inverse document frequency (IDF).” Then, the k-nearest neighbor is found by comparing the cosine similarity between the query vector and all index vectors, which is linear efficiency. In order to improve retrieval efficiency, a few works based on index tree are proposed. For example, Sun et al. [14] present a tree-based search scheme that constructs index vectors of all documents as an MDB-tree. It achieves sublinear search efficiency via setting the prediction threshold for each level of the index tree. Although a tighter prediction value can obtain logarithmic search efficiency, the result accuracy is sacrificed at the same time. Moreover, Xia et al. [15] build a KBB-tree from a bottom-up approach. In KBB-tree, the element of internal node vector is the maximum value of the corresponding position of its child node vectors. A “Greedy-Depth-First Search” algorithm is executed to find k most relevant leaf nodes, which are stored in an RList. If the correlation score between the query vector and the internal node vector is smaller than the minimum score in the RList, the subtree of the internal node does not need to be searched. Thus, this scheme can also achieve sublinear efficiency.On the other hand, some works have been proposed for encrypted image retrieval. In [16], a privacy-enhanced face recognition is realized with a help of Paillier homomorphic encryption (HE). The drawback is that the adoption of HE incurs heavy cost of computation and communication. To be practical, Lu et al. propose a secure content-based image retrieval (CBIR) scheme based on feature/index randomization [17] or min-Hash [5]. Meanwhile, the performance comparison between homomorphic encryption and distance-preserving randomization is studied in [18]. Due to the one-way and binary property of hash code, secure CBIR that exploits the hash function to encrypt features is effective and efficient in the large-scale database [6]. However, the access pattern is leaked in the above schemes. To solve this issue, Weng et al. [7] omit certain bits of the hash code of query image. As a result, the cloud returns all possible candidates to the user. Therefore, the query pattern and access pattern are protected. But the user is involved to compare the features of candidates and obtain an accurate result. Also, it is difficult to generate hash codes that uniformly distributed in the feature space. In further, under the vector space model, there is only a handful of works that support efficient index structure. For example, Xia et al. [19] use local-sensitive hash (LSH) to construct a prefilter table, but a refinement of the candidate results is also a linear comparison. Thus, it just achieves sublinear search efficiency. Yuan et al. [20] employ k-means to build an index tree. Since k-means is not a balanced clustering algorithm, it is inevitable to generate an index tree of skewed hierarchies. Subsequently, due to uneven depth in different parts of index tree, the search efficiency tends to be sublinear. In short, under the vector space model, the requirement for secure and efficient image retrieval mechanisms remains open up to date.Besides the above schemes that based on the encrypted feature, the secure retrieval scheme directly based on encrypted images has been proposed. It is designed for the widely used JPEG image. For example, Zhang and Cheng first use DC histogram preserved in the encrypted image as a feature [21] and then exploit AC histogram [22] and a new block feature [23] for retrieval. However, the efficiency of linear comparison or block-wise comparison is unacceptable. Therefore, the construction of secure index tree is necessary.In this paper, we propose an efficient image retrieval scheme over encrypted cloud data, which based on a balanced index tree,i.e., balanced binary tree (BBT). We introduce a novel balanced binary clustering (BBC) algorithm and use integrated features to build the BBT. Owing to the fact that this paper realizes similarity search, we tend to utilize global feature (such as color, shape) instead of accurate local feature (such as SIFT, BRIEF). Hence, our integrated feature is composed of widely used HSV histogram and DCT histogram [5, 21, 22, 24]. We focus on the construction of index tree and protection of query pattern and access pattern. As for the image encryption, we adopt partial image encryption technique [23, 25, 26] for JPEG format image and mature cryptographic ciphers (such as AES) for the other format images. Note that the key distribution is an independent issue and out of the scope of this paper. Our main contributions lie in three aspects:(1) We combine HSV histogram in the color space and DCT histogram in the transform domain as an integrated feature. To improve the search efficiency, we construct a BBT for the image database. The BBT is built from a top-down approach. Since the hierarchical index tree is approximately balanced, the scheme can achieve logarithmic search time.(2) By incorporating secure inner product (i.e., ASPE), the BBT is encrypted as secure BBT (SBBT) by a secret key, and query feature is encrypted. The database image is encrypted by another secret key. After that, the sensitive data in the cloud is protected; meanwhile, the searchable functionality of the encrypted feature is still valid. Further, the random number extended in the query feature can blind the query pattern.(3) To blind the search result, we copy the database and merge the subtree to rebuild SBBT. The reduced SBBT and the weighted factor of the integrated feature make the search result of one query image not unique. Therefore, the query privacy about access pattern is protected.The rest of this paper is organized as follows. In Section2, we introduce system model, threat model, and design goals. Also, common notations are defined. In Section 3, we propose BBC algorithm, use BBC to build a BBT, and adopt ASPE to encrypted BBT. Section 4 presents and discusses experimental results. Finally, we conclude the paper in Section 5.


## 2. Problem Formulation

### 2.1. System Model

The system contains three parties: the data owner, the cloud server, and authorized users, as illustrated in Figure1.Figure 1
A secure and efficient image retrieval scheme over encrypted data.The owner first extracts feature vectors, such as HSV histogram and DCT histogram, from each image in his database. They are concatenated into an integrated feature. After the feature extraction, the plaintext image is encrypted as the ciphertext by a secret key. For improving search efficiency, the owner builds an index tree based on the integrated features. Then, he utilizes another secret key to encrypt the index tree. The leaf node of the secure index tree is associated with the encrypted image. Afterward, the owner outsources the encrypted database images and the secure index tree to the cloud. In addition, the owner sends secret keys to each authorized user through a secure channel.The authorized user extracts feature vectors from the query image. To fetch encrypted images in the secure index tree, he encrypts the integrated feature of a query image and submits it to the cloud.The cloud stores the encrypted database images and secure index tree from the owner. After receiving an encrypted query feature, the cloud executes the search operation in the secure index tree. After that, he returns encrypted images that associated with retrieved leaf node to the user.


### 2.2. Thread Model

We assume that three parties follow a semihonest model, in which any two parties do not collude to share information. However, even if the cloud does not know the content of the encrypted query, it may count the query frequency of same encrypted request and the access frequency of the same returned result. Thus, depending on the available information to the cloud, we consider two threat models here.Known Ciphertext Model. The cloud only knows encrypted database, secure index tree, and the encrypted query.Known Background Model. In this stronger model, the cloud knows background knowledge about the frequency distribution of the query images. For example, Trump’s photos are very popular in the presidential campaign. The cloud can conduct a statistical attack to identify certain image via the access frequency of the returned images.


### 2.3. Design Goals

To enable secure image retrieval over encrypted cloud data under the above models, our scheme should achieve the following design goals.Effectiveness. The scheme is designed to support search over encrypted data. The result is as accurate as the search in the plaintext domain.Efficiency. Under vector space model, we structure the feature vectors of image database as an SBBT. Instead of linear or sublinear search efficiency, our scheme will achieve logarithmic search time.Privacy. The goal is to protect the privacy of owner and user, which is summarized as follows. (1) The database and its index tree confidentiality: namely, the image and its index tree exist in the ciphertext form in the cloud. (2) The query privacy: it is not possible to determine whether two requests are from the same query image. Note that to ease the overload of computation and communication, our goals are not to fully protect access pattern,i.e., the search path in the SBBT.


### 2.4. Notations

Assume that the total number of images in the database isN. We define common notations as follows:(i)
D: the database, namely, the set of images(ii)
C: the ciphertext form of D stored in the cloud(iii)
pi1: the normalized feature, such as HSV histogram from the ith image, 1≤i≤N, it is a d1-dimensional row vector(iv)
pi2: the normalized feature, such as DCT histogram from the ith image, 1≤i≤N, it is a d2-dimensional row vector(v)
p→i: the integrated feature, p→i=αpi1,1-αpi2, a weighted factor α∈0,1(vi)
v: the index vector in each node of BBT, it is generated from pi→(vii)
I: the H-height BBT for the whole image database D, H≈⌈log2N⌉(viii)
V: the ciphertext index which corresponds to plaintext v(ix)
T: the ciphertext form of I(x)
q1: the normalized feature of the query image, such as HSV histogram(xi)
q2: the normalized feature of the query image, such as DCT histogram(xii)
q→: the query vector, q→=βq1,1-βq2, a weighted factor β∈0,1(xiii)
M: the encryption key M∈Rd+1×d+1 is a random invertible matrix, d=d1+d2(xiv)
Q: the ciphertext query, corresponding to plaintext q→To find the k-nearest neighbor of the query image, we adopt “inner product similarity” to evaluate the distance among the features. Specifically,p→i is an integrated feature of the database image, including HSV histogram and DCT histogram. q→ is the integrated feature of the query image. The final similarity score is obtained by p→i∙q→. Based on the score, the most relevant images in the database are returned to the user.


## 2.1. System Model

The system contains three parties: the data owner, the cloud server, and authorized users, as illustrated in Figure1.Figure 1
A secure and efficient image retrieval scheme over encrypted data.The owner first extracts feature vectors, such as HSV histogram and DCT histogram, from each image in his database. They are concatenated into an integrated feature. After the feature extraction, the plaintext image is encrypted as the ciphertext by a secret key. For improving search efficiency, the owner builds an index tree based on the integrated features. Then, he utilizes another secret key to encrypt the index tree. The leaf node of the secure index tree is associated with the encrypted image. Afterward, the owner outsources the encrypted database images and the secure index tree to the cloud. In addition, the owner sends secret keys to each authorized user through a secure channel.The authorized user extracts feature vectors from the query image. To fetch encrypted images in the secure index tree, he encrypts the integrated feature of a query image and submits it to the cloud.The cloud stores the encrypted database images and secure index tree from the owner. After receiving an encrypted query feature, the cloud executes the search operation in the secure index tree. After that, he returns encrypted images that associated with retrieved leaf node to the user.


## 2.2. Thread Model

We assume that three parties follow a semihonest model, in which any two parties do not collude to share information. However, even if the cloud does not know the content of the encrypted query, it may count the query frequency of same encrypted request and the access frequency of the same returned result. Thus, depending on the available information to the cloud, we consider two threat models here.Known Ciphertext Model. The cloud only knows encrypted database, secure index tree, and the encrypted query.Known Background Model. In this stronger model, the cloud knows background knowledge about the frequency distribution of the query images. For example, Trump’s photos are very popular in the presidential campaign. The cloud can conduct a statistical attack to identify certain image via the access frequency of the returned images.


## 2.3. Design Goals

To enable secure image retrieval over encrypted cloud data under the above models, our scheme should achieve the following design goals.Effectiveness. The scheme is designed to support search over encrypted data. The result is as accurate as the search in the plaintext domain.Efficiency. Under vector space model, we structure the feature vectors of image database as an SBBT. Instead of linear or sublinear search efficiency, our scheme will achieve logarithmic search time.Privacy. The goal is to protect the privacy of owner and user, which is summarized as follows. (1) The database and its index tree confidentiality: namely, the image and its index tree exist in the ciphertext form in the cloud. (2) The query privacy: it is not possible to determine whether two requests are from the same query image. Note that to ease the overload of computation and communication, our goals are not to fully protect access pattern,i.e., the search path in the SBBT.


## 2.4. Notations

Assume that the total number of images in the database isN. We define common notations as follows:(i)
D: the database, namely, the set of images(ii)
C: the ciphertext form of D stored in the cloud(iii)
pi1: the normalized feature, such as HSV histogram from the ith image, 1≤i≤N, it is a d1-dimensional row vector(iv)
pi2: the normalized feature, such as DCT histogram from the ith image, 1≤i≤N, it is a d2-dimensional row vector(v)
p→i: the integrated feature, p→i=αpi1,1-αpi2, a weighted factor α∈0,1(vi)
v: the index vector in each node of BBT, it is generated from pi→(vii)
I: the H-height BBT for the whole image database D, H≈⌈log2N⌉(viii)
V: the ciphertext index which corresponds to plaintext v(ix)
T: the ciphertext form of I(x)
q1: the normalized feature of the query image, such as HSV histogram(xi)
q2: the normalized feature of the query image, such as DCT histogram(xii)
q→: the query vector, q→=βq1,1-βq2, a weighted factor β∈0,1(xiii)
M: the encryption key M∈Rd+1×d+1 is a random invertible matrix, d=d1+d2(xiv)
Q: the ciphertext query, corresponding to plaintext q→To find the k-nearest neighbor of the query image, we adopt “inner product similarity” to evaluate the distance among the features. Specifically,p→i is an integrated feature of the database image, including HSV histogram and DCT histogram. q→ is the integrated feature of the query image. The final similarity score is obtained by p→i∙q→. Based on the score, the most relevant images in the database are returned to the user.


## 3. Proposed Scheme

In order to achieve logarithmic search efficiency, we first build a balanced index tree for the plaintext image database, in which a novel balanced binary clustering algorithm is proposed. Then, to ensure the confidentiality of index vectorv and query vector q→, the secure inner product computation is employed to encrypt the vector v and q→. Also, we adopt a partial image encryption to encrypt database images. Finally, we improve the scheme to enhance privacy protection in the known background model.


### 3.1. BBC Algorithm: Balanced Binary Clustering

To build the balanced index tree, we need a balanced binary clustering (BBC) algorithm to find a separating vectorv which divides each dataset into two equal (or nearly equal) clusters. However, traditional k-means aims at finding cluster centers so that the sum of the distance between each point and its nearest center is maximized, rather than the equal size of clusters. Thus, frequency sensitive competitive learning (FSCL) [27] is introduced to improve k-means. FSCL is a conscience type algorithm that takes the size of clusters as a weight factor which makes the bigger cluster less likely to win more points in next iteration. It can converge to a local minimum [28]. Although the difference of cluster centers can be used as a separating vector v, FSCL does not ensure that the k clusters are equally sized. In fact, it is experienced as very unstable in high-dimensional vector spaces [29]. On the contrast, balanced k-means [30] can split a dataset into two equal-sized clusters by finding a perfect matching in a bipartite graph. But it does not generate the separating vector v. Thus, we propose a novel BBC to find a separating vector that makes the size of two clusters equal. To our best knowledge, this work is the first endeavor to combine FSCL and balanced k-means to achieve balanced clustering. The detail of BBC algorithm is elaborated in the following.Givenn points p→ii=1n∈Rd, at the tth iteration, the size of cluster is τkt≥0 and the cluster center is Ckt,k=1,2. The BBC algorithm works as follows.Initialization. We adopt k-means++ to choose two points from p→ii=1n as initial centers Ck1,k=1,2.First, uniformly choose an initial centerC11 from p→ii=1n.Second, choose the next initial centerC21 from p→i,p→i≠C11i=1n with probability Dp→i,C11/∑Dp→i,C11, Dp→i,C11=1-(p→i∙C11)/p→iC11.Finally, according to the distance to the initial centers, other points are divided into two categoriesCLk, the size of which is τk1,k=1,2.Cluster Assignment. Let new Ti,kt be the solution of optimization problem as follows.(1)minJTi,kt=∑k=12τkt·∑i=1nTi,ktDp→i,Ckt(2)s.t.Ti,kt∈0,1,i=1,…,n,k=1,2∑k=12Ti,kt=1,i=1,…,n∑i=1nTi,kt≥n2,k=1,2where Dpi→,Ckt=1-(p→i∙Ckt)/p→iCkt. A smaller value of Dp→i,Ckt indicates that the two vectors p→i,Ckt are more similar.Inspired by balanced k-means, we first turn (1) as a linear assignment problem (LAP) [31]. The cost matrix is defined as(3)CE=Dp→1,Ck1⋯Dp→n,Ck1Dp→1,Ck2⋯Dp→n,Ck2⋯Dp→1,Ck1⋯Dp→n,Ck1Dp→1,Ck2⋯Dp→n,Ck2,where CE∈R2⌈n/2⌉×n. If it is not a square matrix, a column of zeros is added to make it square. Then, we adopt Volgenant-Jonker (VJ) algorithm [32, 33] to find a perfect matching in a bipartite graph. Finally, if the vector p→i is assigned to center Ckt, Ti,kt=1 and 0 otherwise.Cluster Update. Update the cluster centers Ckt+1, the “selection” variables Ti,kt+1, and the size of clusters τkt+1 as follows:(4)Ckt+1=∑i=1nTi,ktp→i∑i=1nTi,kt,k=1,2Ti,1t+1=1,Ti,2t+1=0,ifDp→i,C1t+1-C2t+1≤0Ti,1t+1=0,Ti,2t+1=1,ifDp→i,C1t+1-C2t+1>0τkt+1=∑i=1nTi,kt+1,k=1,2.Cluster assignment and cluster update are repeated untilτkt+1≤2⌈log2n⌉-1 or Ckt+1=Ckt,k=1,2.Output. The above three steps run several times with different initial centers C11, C21.Owing to the fact that different initial centers may generate different results, the result that the sizes of two clusters are most similar is chosen as a final output. The size similarity of two clusters is defined as(5)sτkt+1=0,∏k=1,2τkt+1=0min⁡τkt+1,k=1,2max⁡τkt+1,k=1,2,∏k=1,2τkt+1≠0.Finally, the output is(6)p→i∈CLkifTi,kt+1=1,i=1,…,n,k=1,2v=C1tC1t-C2tC2t.The dataset of n points can be divided into two equal (nearly equal) clusters by the separating vector v.


### 3.2. UBBT: Unencrypted Balanced Binary Tree

In this subsection, we build the BBT for the whole database. Firstly, we generate an integrated featurep→i for each image in the database. Then, an index vector v of the root node or internal node of the BBT is generated by a top-down approach. BBC algorithm generates v to separate image features into two clusters of nearly equal size,i.e., CL1, CL2. Namely,(7)p→i∙v≥0ifp→i∈CL1p→i∙v<0ifp→i∈CL2.Algorithm 1 recursively divides feature vectors of the database images into two clusters until no cluster has more than two feature vectors. The hierarchical index tree is shown in Figure 2. The level of the root node is 0 and the level of the leaf node is H. Thus, the height of entire index tree is H. The subtree that the root node is at hth level of the index tree has the height of H-h. The root and internal node u in our BBT are defined as follows:(8)u=ID,v,uL,uRwhere ID is the identity of node, v is the index vector dividing images on the leaf nodes into two clusters CL1 and CL2, and uL and uR are the pointers to the left and right child node. If u is a leaf node, it is defined as(9)u=ID,iL,…,iL.where iL points to the images.Algorithm 1:Building balanced binary tree.
Input: p → i, 1≤i≤N; Balanced Binary Clustering, i.e., BBC. Output:Balanced Binary Tree I. (1) h=0 //the height of node (2) ChildrenGenp→i1≤i≤N→ root node (3) functionChildrenGenvectorsp→i (4)  BBCp→i→ two clusters CL1, CL2, separating vector as the indexv (5)  if the size of CL1≥ 2 then (6)   ChildrenGenp→ii∈CL1→ internal node (7)  else (8)   ithimagei∈CL1→ leaf node (9)  end if (10)  if the size of CL2≥ 2 then (11)   ChildrenGenp→ii∈CL2→ internal node (12)  else (13)   ithimagei∈CL2→ leaf node (14)  end if (15)  h=h+1 (16)  returnv, CL1, CL2 (17) end functionFigure 2
The hierarchical structure of unencrypted BBT.The search process starts from the root node of UBBT. Ifq→∙v≥0, we execute iterative retrieval upon the left subtree, otherwise upon the right subtree until obtaining the leaf node.


### 3.3. SBBT: Secure Balanced Binary Tree

In UBBT scheme, the leaf node is retrieved by the sign of the inner productq→∙v. In order to protect the sensitive data q→ and v, we use the secure inner product (i.e., ASPE) [8] to encrypt the vectors and obtain the same result as the plaintext.First of all, the owner generates a random invertible matrixM∈Rd×d to encrypt v. The user also use it to encrypt q→,i.e.,(10)V=vM-1Q=Mq→T,where V is the ciphertext index and Q is the ciphertext query. In addition, the JPEG images are encrypted via a partial image encryption [22, 25]. Therefore, index tree I is encrypted as T. The leaf node of T is associated with the encrypted images. Then, they are outsourced to the cloud for secure image retrieval. When retrieving, the user submits Q of the query image to the cloud. Since VQ=q→∙v, the cloud can use Q to execute an effective search on secure index tree T. Therefore, the retrieved result and efficiency in the ciphertext would always be in line with that in the plaintext. Note that the more details of ASPE are described in [8].Unfortunately, the relationship betweenq→ and Q is deterministic. According to the same Q or VQ, the cloud can count the query frequency of q→. Further, according to the same result, the cloud can also count the access frequency of q→. Therefore, if the query image and q→ is a one-to-one relationship, the proposed scheme cannot resist the statistical attack in the known background model.To break the one-to-one relationship between the query image and ciphertext queryQ, we extend q→ and v as follows:(11)q→=θγ,q→v=0,v,where the random numbers θ>0, γ≫1. Thus, the same query image can generate different ciphertext query Q by setting θ and γ. Meanwhile, VQ=θq→∙v is blinded by positive θ. The cloud cannot get available statistical information from the ciphertext query Q and the result VQ. However, the sign of VQ remains the same even if γ and θ are different, so the retrieved result and search path remain the same. The request frequency of a query image can be inferred from the access frequency of the same return image.To overcome the issue, we first copy the image database. The owner uses partial image encryption [23] to protect plaintext image. According to different encryption keys, same plaintext image can be encrypted as different encrypted images, as shown in Figure 3. Meanwhile, the owner uses the embedding key to hide which encryption key was used [25]. Then, the owner shares encryption keys and the embedding key with authorized users through a secret channel. After obtaining an encrypted image, the user uses the embedding key to extract hidden data and select true encryption key to recover the plaintext image.Figure 3
(a) a query image, (b) one encrypted version, and (c) another encrypted version.
(a) (b) (c)Second, different encrypted images derived from the same plaintext image correspond to different integrated features. For the diversity of the integrated feature, we use HSV histogram and DCT histogram as basic features. The reason is that HSV histogram in color space and DCT histogram in transform domain are image features from different perspectives. As shown in Figure4, different features of the query image can still retrieve a similar image. For ease of description, we define the new ciphertext database as C′. Then, we set C corresponding to the feature p→i=α1pi1,1-α1pi2 and C′ corresponds to the feature p→i′=α2pi1,1-α2pi2. Finally, we use proposed BBC algorithm to build an index tree I from p→i,p→i′,C,C′ and employ ASPE to encrypt the plaintext tree as a ciphertext tree T.Figure 4
In Corel database [10], except for (a),(e) a query image, the most similar image by the retrieval based on (b),(f) HSV histogram, (c),(g) DCT histogram, or (d),(h) an integrated feature.
(a) (b) (c) (d) (e) (f) (g) (h)To further enhance query privacy, we reduce the height of the index treeT and return multiple encrypted images to the query user at the one time. Specifically, we set the internal node to be a new leaf node. Then, the new leaf node contains all the encrypted images in the subtree that the internal node of T is a root node. Due to the fact that the index tree is balanced, leaf nodes of reduced index tree can always point to multiple encrypted images. Please note that some images in a subtree are similar, which is a compromise with effective retrieval.


### 3.4. Security Analysis

We analyze SBBT concerning the privacy requirements in the design goals:(1) The database and its index are confidential. In SBBT, index vectorsv of BBT are encrypted as V by the high-dimensional random matrix which is kept confidential to the cloud. For images in the database, the partial encryption can protect their confidentiality [23, 25].(2) Since the feature vectorq→ of the query image is extended by random numbers γ and θ, it can generate different ciphertext queries Q. The cloud cannot identify the same query image from its different ciphertext queries. The query pattern is protected.(3) According to differentβ, different features of same query image can retrieve different images. When β is equal to α1 or α2, different results can be recovered to the same query image. Thus, the retrieved result and path of the same query image are not unique but the retrieval is still effective. The cloud cannot link the different returned image to the same query image. The access pattern is protected.(4) In addition, since the height of SBBT is reduced, one leaf node will point to multiple encrypted images. It further breaks the one-to-one relationship between the query image and the return images. The access pattern is further protected.In short, the SBBT is secure in the known ciphertext model and can resist the statistical attack in the known background model.


## 3.1. BBC Algorithm: Balanced Binary Clustering

To build the balanced index tree, we need a balanced binary clustering (BBC) algorithm to find a separating vectorv which divides each dataset into two equal (or nearly equal) clusters. However, traditional k-means aims at finding cluster centers so that the sum of the distance between each point and its nearest center is maximized, rather than the equal size of clusters. Thus, frequency sensitive competitive learning (FSCL) [27] is introduced to improve k-means. FSCL is a conscience type algorithm that takes the size of clusters as a weight factor which makes the bigger cluster less likely to win more points in next iteration. It can converge to a local minimum [28]. Although the difference of cluster centers can be used as a separating vector v, FSCL does not ensure that the k clusters are equally sized. In fact, it is experienced as very unstable in high-dimensional vector spaces [29]. On the contrast, balanced k-means [30] can split a dataset into two equal-sized clusters by finding a perfect matching in a bipartite graph. But it does not generate the separating vector v. Thus, we propose a novel BBC to find a separating vector that makes the size of two clusters equal. To our best knowledge, this work is the first endeavor to combine FSCL and balanced k-means to achieve balanced clustering. The detail of BBC algorithm is elaborated in the following.Givenn points p→ii=1n∈Rd, at the tth iteration, the size of cluster is τkt≥0 and the cluster center is Ckt,k=1,2. The BBC algorithm works as follows.Initialization. We adopt k-means++ to choose two points from p→ii=1n as initial centers Ck1,k=1,2.First, uniformly choose an initial centerC11 from p→ii=1n.Second, choose the next initial centerC21 from p→i,p→i≠C11i=1n with probability Dp→i,C11/∑Dp→i,C11, Dp→i,C11=1-(p→i∙C11)/p→iC11.Finally, according to the distance to the initial centers, other points are divided into two categoriesCLk, the size of which is τk1,k=1,2.Cluster Assignment. Let new Ti,kt be the solution of optimization problem as follows.(1)minJTi,kt=∑k=12τkt·∑i=1nTi,ktDp→i,Ckt(2)s.t.Ti,kt∈0,1,i=1,…,n,k=1,2∑k=12Ti,kt=1,i=1,…,n∑i=1nTi,kt≥n2,k=1,2where Dpi→,Ckt=1-(p→i∙Ckt)/p→iCkt. A smaller value of Dp→i,Ckt indicates that the two vectors p→i,Ckt are more similar.Inspired by balanced k-means, we first turn (1) as a linear assignment problem (LAP) [31]. The cost matrix is defined as(3)CE=Dp→1,Ck1⋯Dp→n,Ck1Dp→1,Ck2⋯Dp→n,Ck2⋯Dp→1,Ck1⋯Dp→n,Ck1Dp→1,Ck2⋯Dp→n,Ck2,where CE∈R2⌈n/2⌉×n. If it is not a square matrix, a column of zeros is added to make it square. Then, we adopt Volgenant-Jonker (VJ) algorithm [32, 33] to find a perfect matching in a bipartite graph. Finally, if the vector p→i is assigned to center Ckt, Ti,kt=1 and 0 otherwise.Cluster Update. Update the cluster centers Ckt+1, the “selection” variables Ti,kt+1, and the size of clusters τkt+1 as follows:(4)Ckt+1=∑i=1nTi,ktp→i∑i=1nTi,kt,k=1,2Ti,1t+1=1,Ti,2t+1=0,ifDp→i,C1t+1-C2t+1≤0Ti,1t+1=0,Ti,2t+1=1,ifDp→i,C1t+1-C2t+1>0τkt+1=∑i=1nTi,kt+1,k=1,2.Cluster assignment and cluster update are repeated untilτkt+1≤2⌈log2n⌉-1 or Ckt+1=Ckt,k=1,2.Output. The above three steps run several times with different initial centers C11, C21.Owing to the fact that different initial centers may generate different results, the result that the sizes of two clusters are most similar is chosen as a final output. The size similarity of two clusters is defined as(5)sτkt+1=0,∏k=1,2τkt+1=0min⁡τkt+1,k=1,2max⁡τkt+1,k=1,2,∏k=1,2τkt+1≠0.Finally, the output is(6)p→i∈CLkifTi,kt+1=1,i=1,…,n,k=1,2v=C1tC1t-C2tC2t.The dataset of n points can be divided into two equal (nearly equal) clusters by the separating vector v.


## 3.2. UBBT: Unencrypted Balanced Binary Tree

In this subsection, we build the BBT for the whole database. Firstly, we generate an integrated featurep→i for each image in the database. Then, an index vector v of the root node or internal node of the BBT is generated by a top-down approach. BBC algorithm generates v to separate image features into two clusters of nearly equal size,i.e., CL1, CL2. Namely,(7)p→i∙v≥0ifp→i∈CL1p→i∙v<0ifp→i∈CL2.Algorithm 1 recursively divides feature vectors of the database images into two clusters until no cluster has more than two feature vectors. The hierarchical index tree is shown in Figure 2. The level of the root node is 0 and the level of the leaf node is H. Thus, the height of entire index tree is H. The subtree that the root node is at hth level of the index tree has the height of H-h. The root and internal node u in our BBT are defined as follows:(8)u=ID,v,uL,uRwhere ID is the identity of node, v is the index vector dividing images on the leaf nodes into two clusters CL1 and CL2, and uL and uR are the pointers to the left and right child node. If u is a leaf node, it is defined as(9)u=ID,iL,…,iL.where iL points to the images.Algorithm 1:Building balanced binary tree.
Input: p → i, 1≤i≤N; Balanced Binary Clustering, i.e., BBC. Output:Balanced Binary Tree I. (1) h=0 //the height of node (2) ChildrenGenp→i1≤i≤N→ root node (3) functionChildrenGenvectorsp→i (4)  BBCp→i→ two clusters CL1, CL2, separating vector as the indexv (5)  if the size of CL1≥ 2 then (6)   ChildrenGenp→ii∈CL1→ internal node (7)  else (8)   ithimagei∈CL1→ leaf node (9)  end if (10)  if the size of CL2≥ 2 then (11)   ChildrenGenp→ii∈CL2→ internal node (12)  else (13)   ithimagei∈CL2→ leaf node (14)  end if (15)  h=h+1 (16)  returnv, CL1, CL2 (17) end functionFigure 2
The hierarchical structure of unencrypted BBT.The search process starts from the root node of UBBT. Ifq→∙v≥0, we execute iterative retrieval upon the left subtree, otherwise upon the right subtree until obtaining the leaf node.


## 3.3. SBBT: Secure Balanced Binary Tree

In UBBT scheme, the leaf node is retrieved by the sign of the inner productq→∙v. In order to protect the sensitive data q→ and v, we use the secure inner product (i.e., ASPE) [8] to encrypt the vectors and obtain the same result as the plaintext.First of all, the owner generates a random invertible matrixM∈Rd×d to encrypt v. The user also use it to encrypt q→,i.e.,(10)V=vM-1Q=Mq→T,where V is the ciphertext index and Q is the ciphertext query. In addition, the JPEG images are encrypted via a partial image encryption [22, 25]. Therefore, index tree I is encrypted as T. The leaf node of T is associated with the encrypted images. Then, they are outsourced to the cloud for secure image retrieval. When retrieving, the user submits Q of the query image to the cloud. Since VQ=q→∙v, the cloud can use Q to execute an effective search on secure index tree T. Therefore, the retrieved result and efficiency in the ciphertext would always be in line with that in the plaintext. Note that the more details of ASPE are described in [8].Unfortunately, the relationship betweenq→ and Q is deterministic. According to the same Q or VQ, the cloud can count the query frequency of q→. Further, according to the same result, the cloud can also count the access frequency of q→. Therefore, if the query image and q→ is a one-to-one relationship, the proposed scheme cannot resist the statistical attack in the known background model.To break the one-to-one relationship between the query image and ciphertext queryQ, we extend q→ and v as follows:(11)q→=θγ,q→v=0,v,where the random numbers θ>0, γ≫1. Thus, the same query image can generate different ciphertext query Q by setting θ and γ. Meanwhile, VQ=θq→∙v is blinded by positive θ. The cloud cannot get available statistical information from the ciphertext query Q and the result VQ. However, the sign of VQ remains the same even if γ and θ are different, so the retrieved result and search path remain the same. The request frequency of a query image can be inferred from the access frequency of the same return image.To overcome the issue, we first copy the image database. The owner uses partial image encryption [23] to protect plaintext image. According to different encryption keys, same plaintext image can be encrypted as different encrypted images, as shown in Figure 3. Meanwhile, the owner uses the embedding key to hide which encryption key was used [25]. Then, the owner shares encryption keys and the embedding key with authorized users through a secret channel. After obtaining an encrypted image, the user uses the embedding key to extract hidden data and select true encryption key to recover the plaintext image.Figure 3
(a) a query image, (b) one encrypted version, and (c) another encrypted version.
(a) (b) (c)Second, different encrypted images derived from the same plaintext image correspond to different integrated features. For the diversity of the integrated feature, we use HSV histogram and DCT histogram as basic features. The reason is that HSV histogram in color space and DCT histogram in transform domain are image features from different perspectives. As shown in Figure4, different features of the query image can still retrieve a similar image. For ease of description, we define the new ciphertext database as C′. Then, we set C corresponding to the feature p→i=α1pi1,1-α1pi2 and C′ corresponds to the feature p→i′=α2pi1,1-α2pi2. Finally, we use proposed BBC algorithm to build an index tree I from p→i,p→i′,C,C′ and employ ASPE to encrypt the plaintext tree as a ciphertext tree T.Figure 4
In Corel database [10], except for (a),(e) a query image, the most similar image by the retrieval based on (b),(f) HSV histogram, (c),(g) DCT histogram, or (d),(h) an integrated feature.
(a) (b) (c) (d) (e) (f) (g) (h)To further enhance query privacy, we reduce the height of the index treeT and return multiple encrypted images to the query user at the one time. Specifically, we set the internal node to be a new leaf node. Then, the new leaf node contains all the encrypted images in the subtree that the internal node of T is a root node. Due to the fact that the index tree is balanced, leaf nodes of reduced index tree can always point to multiple encrypted images. Please note that some images in a subtree are similar, which is a compromise with effective retrieval.


## 3.4. Security Analysis

We analyze SBBT concerning the privacy requirements in the design goals:(1) The database and its index are confidential. In SBBT, index vectorsv of BBT are encrypted as V by the high-dimensional random matrix which is kept confidential to the cloud. For images in the database, the partial encryption can protect their confidentiality [23, 25].(2) Since the feature vectorq→ of the query image is extended by random numbers γ and θ, it can generate different ciphertext queries Q. The cloud cannot identify the same query image from its different ciphertext queries. The query pattern is protected.(3) According to differentβ, different features of same query image can retrieve different images. When β is equal to α1 or α2, different results can be recovered to the same query image. Thus, the retrieved result and path of the same query image are not unique but the retrieval is still effective. The cloud cannot link the different returned image to the same query image. The access pattern is protected.(4) In addition, since the height of SBBT is reduced, one leaf node will point to multiple encrypted images. It further breaks the one-to-one relationship between the query image and the return images. The access pattern is further protected.In short, the SBBT is secure in the known ciphertext model and can resist the statistical attack in the known background model.


## 4. Performance Analysis

In this section, we show the experimental results and efficiency analysis of the proposed scheme. As we know that JPEG is the most commonly used image format and accounting for up to 95% of images on the web [34], so we adopt the Corel database [10] for the similarity search. The database contains 1000 JPEG images which belong to 10 categories: African, Beach, Architecture, Buses, Dinosaurs, Elephants, Flowers, Horses, Mountain, and Food. Each of them includes 100 images. As [5], we split an image into 256 blocks and extract hue, saturation, and value of brightness of each block. Then, we perform hierarchical clustering of block features to construct the “bag of word” model. The usage frequency of the visual word is the HSV histogram of the image. As [22], DC/AC coefficients of image blocks are quantized into different bins and the DCT histogram is the usage frequency of quantized DC/AC coefficients. Thus, the color feature pi1 and texture feature pi2 are set as the 991-dimensional HSV histogram and 780-dimensional DCT histogram, respectively.


### 4.1. Parameters Setting

First of all, we should set parametersα1 of p→i and α2 of p→i′ to construct an index tree. Because the integrated features compose of HSV histograms and DCT histogram, we first evaluate average histogram similarity of the images in the same category and different categories (denoted as corr-intra and corr-inter, respectively), as shown in Figure 5. We can see that the value of corr-intra is larger than corr-inter; thus, images of different categories can be distinguished by each histogram. According to the difference between corr-intra and corr-inter (i.e., corr-diff in Figure 5), we set α1=0.1 for the integrated feature p→i of the database C. The purpose is to make the HSV histogram and DCT histogram have the same contribution to the search results.Figure 5
The average correlation of HSV histogram (left) and DCT histogram (right) under same category and different categories.For the parameterα2 of p→i′, we hope that the index tree of database C,C′ can better protect the access pattern. We use two different metrics to measure the privacy protection achieved by different α2. The two metrics are the number of different image categories in each subtree and the category entropy of each subtree. Figure 6 shows the average number of image categories contained in the subtree of different levels. Because the index tree of the database based on different α2 has same height of 11 (i.e., ⌈log22000⌉), the proposed BBC algorithm performs well. However, we can see from Figure 6 that the subtree near the leaf node contains a similar number of image categories. We will use category entropy to measure the privacy. The category entropy, which is defined as -∑ici/∑icilog2ci/∑ici (ci is the number of existing i category), is used to measure the randomness of image categories in the subtree. From Table 1, we know that the index tree of α2=0.6 has the highest average entropy at the 3th-10th level, even its average category number at 3th-6th level is not the biggest in Figure 6. Thus, we set the weighted factor α2=0.6 for the integrated feature p→i′ of database C′.Table 1
Average category entropy of each level.
Parameter Level of the Index Tree α2 1 2 3 4 5 6 7 8 9 10 11 0.2 2.99 2.49 2.1 1.75 1.38 1.07 0.81 0.62 0.44 0.21 0 0.3 3.2 2.82 2.07 1.81 1.43 1.18 0.91 0.7 0.48 0.24 0 0.4 3.32 2.88 2.28 1.8 1.53 1.28 1.02 0.78 0.54 0.28 0 0.5 3.32 3.03 2.31 1.83 1.56 1.27 1.03 0.79 0.55 0.3 0 0.6 3.32 2.91 2.37 1.96 1.65 1.41 1.11 0.89 0.61 0.32 0 0.7 3.32 2.6 2.1 1.71 1.46 1.24 1.03 0.81 0.57 0.29 0 0.8 3.32 2.92 2.32 1.85 1.52 1.26 1.04 0.81 0.57 0.3 0 0.9 3.32 2.92 2.25 1.78 1.49 1.27 1.03 0.83 0.58 0.3 0Figure 6
The average number of image categories.


### 4.2. Index Tree Construction

In order to prove that our algorithm can classify feature vectors in a balanced manner, we use average similarity of the cluster size to compare the clustering performance of proposed BBC algorithm, balanced k-means (i.e., Bkmeans), k-means++, and FSCL. The average similarity based on (5) is defined as S=sτkt+1¯. From Figure 7, we can see that the index trees generated by the proposed BBC algorithm, Bkmeans, k-means++, and FSCL have the height of 11, 12, 13, and 16, respectively. The smaller the height of the index tree indicates that the proposed algorithm can classify feature vectors into two clusters more evenly at each level of the index tree. Figure 7 shows that the cluster size of FSCL is the most unbalanced at 1th-11th levels. There are two reasons: the first is that the change of the weight factor affects the stability of the clustering result, and the second is that the value of weight factor impacts the distance between the cluster center and other feature vectors. On contrast, due to the use of conscience weight factor, the proposed algorithm performs better than Bkmeans and k-means++, and the result is much better than FSCL. The reason is that the bipartite graph matching mechanism constrains a balance of the two clusters and restricts the influence of weight factor. In short, the weight factor is still effective in improve the balance of clustering. In fact, above result is also similar in the database of different α1,α2.Figure 7
The average size similarity of two clusters.In further, we employ Dunn index (DI) [35] to evaluate mentioned clustering algorithms. The Dunn index is defined as(12)DI=min∀x∈CL1,∀y∈CL2⁡Dx,ymaxk=1,2⁡max∀x,y∈CLk⁡Dx,y,where the numerator is the minimal distance of vectors in different clusters and the denominator is the largest within-cluster distance. Thus, we can know that when separating two points into two clusters, the denominator is zero and DI is infinite. A high value of DI means good compactness. Table 2 shows the minimal DI of clustering results in each level. In the same level of the index tree, the most of BBC’s DI is smaller than other algorithms (i.e., Bkmeans, K-means++, and FSCL). Meanwhile, BBC’s DI of the last level is much smaller than other algorithms. Obviously, for the proposed BBC algorithm, the cluster-size similarity is with higher priority than clustering compactness.Table 2
Minimal Dunn index of each level.
Algorithm Level of the Index Tree 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 BBC 0.47 0.01 0.01 0.02 0.01 0.01 0.01 0.01 0.01 0.02 ∞ - - - - - Bkmeans 0.47 0.01 0.02 0.01 0.02 0.02 0.02 0.03 0.04 0.24 0.73 ∞ - - - - Kmeans++ 0.21 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.02 0.03 0.22 1.05 ∞ - - - FSCL 0.47 0.04 0.05 0.06 0.07 0.1 0.15 0.19 0.23 0.38 0.28 0.58 0.62 0.66 0.95 ∞The above algorithms are implemented using MATLAB on a PC with an Intel Core i5 3.2 GHz CPU and 16 GB RAM. Time consumption for index tree construction is shown in Table3. In particular, we execute 30 times clustering with random initial centers and select the result of highest score of cluster-size similarity. Bkmeans is most time consuming because it is not designed to find a vector that splits a dataset evenly. In contrast, proposed BBC costs the least time.Table 3
Time cost of index tree construction.
Algorithm BBC Bkmeans Kmeans++[20] FSCL Time (s) 111 2316 1749 254


### 4.3. Retrieval Performance

To evaluate the retrieval performance, each image in the Corel database is selected as a query image. The retrieval performance is evaluated by average precision-recall (PR) curve,i.e.,(13)Precision=#ofreturnedpositiveimages#ofallreturnedimages,Recall=#ofreturnedpositiveimages#ofallpositiveimages.Figure 8(a) compares the PR curves of the query feature based on different β values. It can be seen that the performance of different β achieves high precision when recall belongs to (0, 0.05). Besides, when only one image is returned,i.e., recall=1%, the precision of β=0.1 or 0.6 is 100%. The reason is that we set β as α1 or α2. Although two integrated features of a query image are different, the retrieved results are different encrypted versions of the same plaintext image. Since the query features, the corresponding results, and search paths are different, the statistical information of query image is protected.Figure 8
(a) Precision-recall curves of original index tree. (b) Retrieval precision of reduced index trees.
(a) (b)Figure8(b) shows the retrieval performance of the reduced index trees with different heights. It can be seen that the precision increases with the height of index tree, even if β is set as 0 or 1. Further, Figure 9 shows the average maximum height of a reduced index tree, in which the returned leaf node contains the exact query image. It can be seen that the height of reduced index tree is 11 when β is set as 0.1 or 0.6. If β is set closer to 0.1 or 0.6, the height of reduced index tree is nearer to 11. When the height is 9, the most of exact query images are retrievable in the reduced index tree and one search returns four (22) images. Fortunately, as shown in Figure 8(b), the precision is about 70% at the 9th level of the index tree. Thus, the retrieval is still effective.Figure 9
Under differentβ, the average maximum height of a reduced index tree that the query image can retrieve itself.


### 4.4. Privacy Protection

We consider the privacy protection from two aspects: query pattern and access pattern. Since the query feature is an integrated histogram,i.e., q→=βq1,1-βq2. Different β correspond to different query features. In addition, even if β is determined, the feature will be extended by random numbers θ,γ as q→=θγ,q→. Thus, the encrypted feature is Q=Mθγ,βq1,1-βq2T. Obviously, the encrypted feature of a query image is not unique. The query pattern of each query image is protected.To protect access pattern, the retrieved result of a query image should be not unique. We have built an index tree based on features of original database (α1=0.1) and features of the copied database (α2=0.6). Then, the integrated features of different β are used to retrieve in the index tree. We know the fact that the returned result is a leaf node of the index tree and different leaf nodes indicate different access paths. So, we define a path privacy to evaluate the protection level of access pattern(14)Privacy=#ofdifferentsearchpaths#ofallsearchpaths.Different search path can be obtained by using the query feature of differentβ. Figures 10(a) and 10(b) show the path privacy of different β, where β=0.1 and 0.6 are baselines, respectively. It can be seen that the path privacy is 100% when β is set as 0.6 in Figure 10(a) and 0.1 in Figure 10(b). The reason is that retrieval is separately carried out in the left or right subtree of the root node. Figure 10(a) also shows that search paths are in the same subtree of the root node when β is set to 0.6, 0.8, or 1. But the search path of β=0.8 or 1 is still different with β=0.6 as shown in Figure 10(b). Similarly, when β is set to 0, 0.0025, 0.05, 0.075, 0.1, 0.3, or 0.35, the search path is in the same subtree of the root node, but still different. Besides, when β is set to 0.4, the search traverses in both subtrees of the root node. In addition, the path privacy increases with the height of the tree. In short, the access pattern can be protected by setting different β. Please note that usage frequency of different β can be optimized based on the frequency distribution of the query images.Figure 10
Path privacy of differentβ: (a) β=0.1 is the baseline and (b) β=0.6 is the baseline.
(a) (b)In summary, Table4 compares the proposed scheme with other schemes in the terms of search efficiency, query pattern protection, and access pattern protection. We compare the search efficiency of different schemes by theoretical analysis instead of experiments. The reason is that encrypted image retrieval schemes are based on different image databases according to the application. Also, some schemes utilize encrypted image feature, but other schemes employ the hash code of the image feature.Table 4
Comparison of encrypted image retrieval schemes.
Goals Yuan [20] Xia [19] Weng [6] Weng [7] Cheng [22, 23] Proposed Efficiency O log ⁡ N ~ N O 1 ~ N ON Olog2N Query Pattern √ √ × √ × √ Access Pattern × × × √ × √In the schemes under vector space model, such as Yuan [20], a skew index tree leads to Olog⁡N~N search time. Xia [19] uses local-sensitive hash (LSH) to construct a prefilter table. Then, with corresponding image feature, the cloud carries out a refinement of candidate results. Thus, it is a sublinear scheme. Cheng [22, 23] does not build an index tree, so the retrieval efficiency is ON. Weng [6, 7] uses a hash table to improve the search efficiency (i.e., O1~N). In short, the index tree or hash table is a trade-off between space and efficiency. Although Weng's scheme [7] and proposed scheme both protect query pattern and access pattern, the hash code and feature vector are, respectively, used. Specifically, Weng [7] omits certain bits of the hash code of query image and returns multiple candidates to the user for refinement. The user is involved in completing retrieval and obtaining the accurate result. In our scheme, the user can set β as α1 or α2 to retrieve exact query image through different paths. Unlike [7], our scheme does not need the user to participate in the feature comparison. However, to protect access pattern and alleviate computation burden on the user, we copy the image database and cost more storage space in the cloud. Fortunately, the retrieval efficiency is Olog⁡2N.


## 4.1. Parameters Setting

First of all, we should set parametersα1 of p→i and α2 of p→i′ to construct an index tree. Because the integrated features compose of HSV histograms and DCT histogram, we first evaluate average histogram similarity of the images in the same category and different categories (denoted as corr-intra and corr-inter, respectively), as shown in Figure 5. We can see that the value of corr-intra is larger than corr-inter; thus, images of different categories can be distinguished by each histogram. According to the difference between corr-intra and corr-inter (i.e., corr-diff in Figure 5), we set α1=0.1 for the integrated feature p→i of the database C. The purpose is to make the HSV histogram and DCT histogram have the same contribution to the search results.Figure 5
The average correlation of HSV histogram (left) and DCT histogram (right) under same category and different categories.For the parameterα2 of p→i′, we hope that the index tree of database C,C′ can better protect the access pattern. We use two different metrics to measure the privacy protection achieved by different α2. The two metrics are the number of different image categories in each subtree and the category entropy of each subtree. Figure 6 shows the average number of image categories contained in the subtree of different levels. Because the index tree of the database based on different α2 has same height of 11 (i.e., ⌈log22000⌉), the proposed BBC algorithm performs well. However, we can see from Figure 6 that the subtree near the leaf node contains a similar number of image categories. We will use category entropy to measure the privacy. The category entropy, which is defined as -∑ici/∑icilog2ci/∑ici (ci is the number of existing i category), is used to measure the randomness of image categories in the subtree. From Table 1, we know that the index tree of α2=0.6 has the highest average entropy at the 3th-10th level, even its average category number at 3th-6th level is not the biggest in Figure 6. Thus, we set the weighted factor α2=0.6 for the integrated feature p→i′ of database C′.Table 1
Average category entropy of each level.
Parameter Level of the Index Tree α2 1 2 3 4 5 6 7 8 9 10 11 0.2 2.99 2.49 2.1 1.75 1.38 1.07 0.81 0.62 0.44 0.21 0 0.3 3.2 2.82 2.07 1.81 1.43 1.18 0.91 0.7 0.48 0.24 0 0.4 3.32 2.88 2.28 1.8 1.53 1.28 1.02 0.78 0.54 0.28 0 0.5 3.32 3.03 2.31 1.83 1.56 1.27 1.03 0.79 0.55 0.3 0 0.6 3.32 2.91 2.37 1.96 1.65 1.41 1.11 0.89 0.61 0.32 0 0.7 3.32 2.6 2.1 1.71 1.46 1.24 1.03 0.81 0.57 0.29 0 0.8 3.32 2.92 2.32 1.85 1.52 1.26 1.04 0.81 0.57 0.3 0 0.9 3.32 2.92 2.25 1.78 1.49 1.27 1.03 0.83 0.58 0.3 0Figure 6
The average number of image categories.


## 4.2. Index Tree Construction

In order to prove that our algorithm can classify feature vectors in a balanced manner, we use average similarity of the cluster size to compare the clustering performance of proposed BBC algorithm, balanced k-means (i.e., Bkmeans), k-means++, and FSCL. The average similarity based on (5) is defined as S=sτkt+1¯. From Figure 7, we can see that the index trees generated by the proposed BBC algorithm, Bkmeans, k-means++, and FSCL have the height of 11, 12, 13, and 16, respectively. The smaller the height of the index tree indicates that the proposed algorithm can classify feature vectors into two clusters more evenly at each level of the index tree. Figure 7 shows that the cluster size of FSCL is the most unbalanced at 1th-11th levels. There are two reasons: the first is that the change of the weight factor affects the stability of the clustering result, and the second is that the value of weight factor impacts the distance between the cluster center and other feature vectors. On contrast, due to the use of conscience weight factor, the proposed algorithm performs better than Bkmeans and k-means++, and the result is much better than FSCL. The reason is that the bipartite graph matching mechanism constrains a balance of the two clusters and restricts the influence of weight factor. In short, the weight factor is still effective in improve the balance of clustering. In fact, above result is also similar in the database of different α1,α2.Figure 7
The average size similarity of two clusters.In further, we employ Dunn index (DI) [35] to evaluate mentioned clustering algorithms. The Dunn index is defined as(12)DI=min∀x∈CL1,∀y∈CL2⁡Dx,ymaxk=1,2⁡max∀x,y∈CLk⁡Dx,y,where the numerator is the minimal distance of vectors in different clusters and the denominator is the largest within-cluster distance. Thus, we can know that when separating two points into two clusters, the denominator is zero and DI is infinite. A high value of DI means good compactness. Table 2 shows the minimal DI of clustering results in each level. In the same level of the index tree, the most of BBC’s DI is smaller than other algorithms (i.e., Bkmeans, K-means++, and FSCL). Meanwhile, BBC’s DI of the last level is much smaller than other algorithms. Obviously, for the proposed BBC algorithm, the cluster-size similarity is with higher priority than clustering compactness.Table 2
Minimal Dunn index of each level.
Algorithm Level of the Index Tree 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 BBC 0.47 0.01 0.01 0.02 0.01 0.01 0.01 0.01 0.01 0.02 ∞ - - - - - Bkmeans 0.47 0.01 0.02 0.01 0.02 0.02 0.02 0.03 0.04 0.24 0.73 ∞ - - - - Kmeans++ 0.21 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.02 0.03 0.22 1.05 ∞ - - - FSCL 0.47 0.04 0.05 0.06 0.07 0.1 0.15 0.19 0.23 0.38 0.28 0.58 0.62 0.66 0.95 ∞The above algorithms are implemented using MATLAB on a PC with an Intel Core i5 3.2 GHz CPU and 16 GB RAM. Time consumption for index tree construction is shown in Table3. In particular, we execute 30 times clustering with random initial centers and select the result of highest score of cluster-size similarity. Bkmeans is most time consuming because it is not designed to find a vector that splits a dataset evenly. In contrast, proposed BBC costs the least time.Table 3
Time cost of index tree construction.
Algorithm BBC Bkmeans Kmeans++[20] FSCL Time (s) 111 2316 1749 254


## 4.3. Retrieval Performance

To evaluate the retrieval performance, each image in the Corel database is selected as a query image. The retrieval performance is evaluated by average precision-recall (PR) curve,i.e.,(13)Precision=#ofreturnedpositiveimages#ofallreturnedimages,Recall=#ofreturnedpositiveimages#ofallpositiveimages.Figure 8(a) compares the PR curves of the query feature based on different β values. It can be seen that the performance of different β achieves high precision when recall belongs to (0, 0.05). Besides, when only one image is returned,i.e., recall=1%, the precision of β=0.1 or 0.6 is 100%. The reason is that we set β as α1 or α2. Although two integrated features of a query image are different, the retrieved results are different encrypted versions of the same plaintext image. Since the query features, the corresponding results, and search paths are different, the statistical information of query image is protected.Figure 8
(a) Precision-recall curves of original index tree. (b) Retrieval precision of reduced index trees.
(a) (b)Figure8(b) shows the retrieval performance of the reduced index trees with different heights. It can be seen that the precision increases with the height of index tree, even if β is set as 0 or 1. Further, Figure 9 shows the average maximum height of a reduced index tree, in which the returned leaf node contains the exact query image. It can be seen that the height of reduced index tree is 11 when β is set as 0.1 or 0.6. If β is set closer to 0.1 or 0.6, the height of reduced index tree is nearer to 11. When the height is 9, the most of exact query images are retrievable in the reduced index tree and one search returns four (22) images. Fortunately, as shown in Figure 8(b), the precision is about 70% at the 9th level of the index tree. Thus, the retrieval is still effective.Figure 9
Under differentβ, the average maximum height of a reduced index tree that the query image can retrieve itself.


## 4.4. Privacy Protection

We consider the privacy protection from two aspects: query pattern and access pattern. Since the query feature is an integrated histogram,i.e., q→=βq1,1-βq2. Different β correspond to different query features. In addition, even if β is determined, the feature will be extended by random numbers θ,γ as q→=θγ,q→. Thus, the encrypted feature is Q=Mθγ,βq1,1-βq2T. Obviously, the encrypted feature of a query image is not unique. The query pattern of each query image is protected.To protect access pattern, the retrieved result of a query image should be not unique. We have built an index tree based on features of original database (α1=0.1) and features of the copied database (α2=0.6). Then, the integrated features of different β are used to retrieve in the index tree. We know the fact that the returned result is a leaf node of the index tree and different leaf nodes indicate different access paths. So, we define a path privacy to evaluate the protection level of access pattern(14)Privacy=#ofdifferentsearchpaths#ofallsearchpaths.Different search path can be obtained by using the query feature of differentβ. Figures 10(a) and 10(b) show the path privacy of different β, where β=0.1 and 0.6 are baselines, respectively. It can be seen that the path privacy is 100% when β is set as 0.6 in Figure 10(a) and 0.1 in Figure 10(b). The reason is that retrieval is separately carried out in the left or right subtree of the root node. Figure 10(a) also shows that search paths are in the same subtree of the root node when β is set to 0.6, 0.8, or 1. But the search path of β=0.8 or 1 is still different with β=0.6 as shown in Figure 10(b). Similarly, when β is set to 0, 0.0025, 0.05, 0.075, 0.1, 0.3, or 0.35, the search path is in the same subtree of the root node, but still different. Besides, when β is set to 0.4, the search traverses in both subtrees of the root node. In addition, the path privacy increases with the height of the tree. In short, the access pattern can be protected by setting different β. Please note that usage frequency of different β can be optimized based on the frequency distribution of the query images.Figure 10
Path privacy of differentβ: (a) β=0.1 is the baseline and (b) β=0.6 is the baseline.
(a) (b)In summary, Table4 compares the proposed scheme with other schemes in the terms of search efficiency, query pattern protection, and access pattern protection. We compare the search efficiency of different schemes by theoretical analysis instead of experiments. The reason is that encrypted image retrieval schemes are based on different image databases according to the application. Also, some schemes utilize encrypted image feature, but other schemes employ the hash code of the image feature.Table 4
Comparison of encrypted image retrieval schemes.
Goals Yuan [20] Xia [19] Weng [6] Weng [7] Cheng [22, 23] Proposed Efficiency O log ⁡ N ~ N O 1 ~ N ON Olog2N Query Pattern √ √ × √ × √ Access Pattern × × × √ × √In the schemes under vector space model, such as Yuan [20], a skew index tree leads to Olog⁡N~N search time. Xia [19] uses local-sensitive hash (LSH) to construct a prefilter table. Then, with corresponding image feature, the cloud carries out a refinement of candidate results. Thus, it is a sublinear scheme. Cheng [22, 23] does not build an index tree, so the retrieval efficiency is ON. Weng [6, 7] uses a hash table to improve the search efficiency (i.e., O1~N). In short, the index tree or hash table is a trade-off between space and efficiency. Although Weng's scheme [7] and proposed scheme both protect query pattern and access pattern, the hash code and feature vector are, respectively, used. Specifically, Weng [7] omits certain bits of the hash code of query image and returns multiple candidates to the user for refinement. The user is involved in completing retrieval and obtaining the accurate result. In our scheme, the user can set β as α1 or α2 to retrieve exact query image through different paths. Unlike [7], our scheme does not need the user to participate in the feature comparison. However, to protect access pattern and alleviate computation burden on the user, we copy the image database and cost more storage space in the cloud. Fortunately, the retrieval efficiency is Olog⁡2N.


## 5. Conclusion

This paper introduces a secure and efficient image retrieval scheme over encrypted cloud data. In this scheme, we propose a novel clustering algorithm,i.e., BBC, to build a balanced index tree, namely, BBT. Thus, our scheme can achieve logarithmic search time. Firstly, to support effective image retrieval in the ciphertext, we employ ASPE to encrypt the index of the image database and feature of the query image. In this case, the proposed SBBT is secure in the known ciphertext model. Secondly, to resist the statistical attack on known background model, we copy the database and build a new SBBT of the original database and the copied database. After that, adjusting the weighted factor of integrated feature, the search results of a query image are different leaf nodes. Finally, through merging the subtree of SBBT, the leaf node of new SBBT contains multiple encrypted images. Therefore, the one-to-one relationship between the query image and the return image is broken. In short, the SBBT can protect query pattern and access pattern. Furthermore, proposed BBC and SBBT can be used as independent tools for encrypted document retrieval.In future, we will improve the ASPE to support multiuser scenario, where a dishonest user may try to reveal the encrypted query of other users. It is also a meaningful work to generate a generic, high-semantic feature.



---

*Source: 7915393-2018-07-08.xml*