Privacy-Preserving Image Retrieval Based on Additive Secret Sharing

In the early stage of CBIR, the global features [10], such as color and texture, are firstly extracted by researchers. However, as the global feature is fragile to the influence like illumination or rotation. Benefiting from the scale-space theory, local features[11] (e.g., SIFT) are proposed and show a great advantage to global features. Some following local features like SURF [12] try to accelerate the extraction process. However, local features extracted from images are large and unstable, in this case, the actual retrieval time consumption will be unacceptable. Many feature aggregation methods, like Bag-Of-Words (BOW)[13], are proposed to cope with this problem. During the offline phase (i.e., before retrieval), a codebook is trained and the local features of each image will be finally encoded as the unified feature vector.

With the rapid development of CNN, the feature extracted by the pre-trained CNN shows a great advantage[14] to traditional hand-crafted features. Although the neural network is widely used in plenty of supervised learning tasks, as CBIR is typically an unsupervised task, pre-trained CNN is more reasonable for the image retrieval scene. Interestingly, Babenko et al. [15] found that the CNN trained in a quite different large image database (e.g., ImageNet dataset[16]) can still show excellent retrieval accuracy in a new dataset. In the later research, Uijlings et al. [14] noticed that the feature extracted from the convolutional layer is better than the final fully connected layer. However, similar to the local feature, the feature vectors extracted from the convolutional layer are in high dimension. For instance, the size of features, extracted from the last convolutional layer in VGG16, will be $512\times M/16\times N/16$, where $M$, $N$ is the length and width of the input color image. Babenko et al. [17] further noticed that the simpler aggregation method, like computing the mean value of each dimension as the feature, is more suitable for deep features. The above deep descriptor can be aggregated as a 512-dim (dimension) feature for each image. Although some later works[3] propose more optimization tricks, the improvement of accuracy is no longer outstanding for common images.

A problem closely related to CBIR is Nearest-Neighbor Search (NNS). After getting image features, it is still a difficult problem to search for some nearest images from a database that contains large-scale images efficiently. Accurate search is always time-consuming due to the ”curse of dimension”, and the mainstream schemes on NNS try to cope with the Approximate NNS (ANNS) problem. To our knowledge, the schemes in ANNS can be classified into the four categories: tree-based index[18], hash-based index[19], Product Quantization (PQ[20]), and graph-based index[2].

The kernel task in ANNS is reducing the computational complexity of retrieval by constructing an index in the offline phase. Tree-based schemes achieve the goal by splitting the original space into tree structure subspaces. During the retrieval, only points in partial subspaces will be involved in the actual distance computation. Therefore the most significant problem is how to divide the original space. One typical scheme called HKM (Hierarchical $k$-Means[21, 18]) tries to use typical $k$-means to construct the index. This scheme firstly uses $k$-means to divide all the data into $k$ different categories. Then, for each category, if the vectors in the current category are too many, the server will use $k$-means to split this category again. The index building process will be executed until the number of vectors in each category less than a fixed number.

Hash-based schemes follow the idea that the neighbor points in high dimension will still be neighbors when they are mapped into the low dimension. They build a reasonable mapping method called Locality Sensitive Hash (LSH) family[22] for common distance measurements (e.g., Euclidean distance). The original vector will be mapped to an integer number, and the similar images have a higher probability to collide (i.e., same hash value) with each other. One typical LSH method called C2LSH (Count Collusion LSH[19]) proposed the concept of dynamic collision and virtual rehash, which got significant storage and accuracy advantage. Briefly speaking, they construct a series of LSH mapping functions in the same LSH family, then use these functions to map all vectors in the database. The vectors which have higher collision frequency will have the chance to participate in actual distance computation. We will describe more calculation details of HKM and C2LSH in subsection 3.3.

In recent years, great progress has been made in the PQ-based and graph-based schemes, which make billion-scale vector retrieval practical. Although the motivation behind these methods is far different from the former two categories, however, the actual calculation is similar (e.g., multiplication, comparison, etc.). For simplicity and generality, in this paper, we choose two typical methods HKM and C2LSH as examples and apply them in encrypted image feature vectors index building. It will be easy to notice that other ANNS schemes are also able to incorporate into our work.

For security considerations, the PPCBIR task has attracted more and more researchers in this decade. Different from CBIR, the schemes in PPCBIR need to protect the image and its feature for the owner of the image and provide the CBIR service to authorized users with the help of the cloud server.

Existing schemes on PPCBIR can be classified into two categories: feature-encryption based schemes and image-encryption based schemes. In the first category[4, 23, 24], the image owner needs to extract the features from plaintext images and builds an index for them. Then the owner uploads encrypted images and a corresponding index to the cloud server. Since the feature extraction and index building are always resource-consuming tasks, it is not appropriate for leaving them to the image owner.

In this case, schemes[5, 25] in the second category, which outsources these tasks, attract more researchers in recent years. In this category, the image owner only needs to encrypt his images and outsources them to CS. The key problem here is how to extract the valid feature from an encrypted image. In this case, schemes in the second category can be classified into two classes based on the type of encrypted features that CS extracts from the encrypted images. The detailed information is described as follows.

In this work, the feature is extracted from a typical CNN model called VGG16, and the parameters pre-trained by a large image dataset [16] are utilized. CNN is a sequence of layers that compute and transform the input into output. Each layer is made up of a set of neurons. Like most of the other CNN models, VGG16 is composed of Fully Connected layer (FC), Convolutional layer (Conv), Activation Layer (AL), and Pooling layer (Pool). In detail, each layer contains the following computation:

• •

  FC and Conv. FC and Conv layer only involve the linear computation. For example, the neurons in Conv layer share the same weights $W$ and biases $b$, which are often called filters. Consider a filter sizes $n\times n$, then each neuron in the current layer is transformed from an $n\times n$ region of neurons in previous layer. In detail, the $(j,k)^{th}$ neuron is obtained from $y_{j,k}$ $=$ $\sum_{l=0}^{n-1}\sum_{m=0}^{n-1}w_{l,m}x_{j+1,k+m}+b$. Here, $w_{l,m}$ means the corresponding value in weights matrix $W$ and $x$ represents the neuron in the previous layer. It should be noted that the $W$ is fixed when we use pre-trained CNN. As we disuse the FC layer in the VGG16, our scheme can deal with images in any size.

• •

  AL. Activation layer provides the non-linear computation in the neural networks, and Rectified Linear Unit (ReLU) is the unique AL in VGG16. For the input matrix $X$, the ReLU layer returns the result $ReLU(X)$ composed by $max(x,0)$, where $x$ is the member value in $X$. It is easy to notice that ReLU only involves comparison computations.

• •

  Pool. The pooling layer partitions the input layer into a set of non-overlapping rectangles, then a down-sampling operation is executed on each rectangle to get the value in the current layer. In VGG16, max-pooling sizes 2$\times$2 is utilized, which means the maximum number will be saved in each 2$\times$2 block and transmitted to the later layer. Max-pooling also only contains the comparison computations.

Secret sharing is one of the most important technologies in SMC. The secret information will be randomly split into multi-shares, and each participant only has one share. The secret can be reconstructed only when a sufficient number of shares are combined. Additive secret sharing can be seen as an $(n,n)$-threshold secret sharing technology. It means that the secret $x$ can be randomly split into $n$ shares, for example, $x$ $=$ $x_{1}+x_{2}+\cdots+x_{n}$, and recover the secret needs all $n$ share, here $n\geq 2$. In this paper, we only focus on the situation that $n=2$.

In recent years, more researchers try to use the additive secret sharing technologies to outsource computation tasks to CS. For example, the image owner can outsource his image by randomly splitting the image into two additive shares, and each cloud server $S_{i}$ $(i=1,2)$ owns one share. For simplicity, the following $S_{i}$ are all represents servers $S_{1}$ and $S_{2}$, similarly, the following values, with $i$ in subscript, represent the additive share of corresponding value if $i$ is undefined. It should be noted that the additive secret sharing has an important property: each server $S_{i}$ can execute linear computation without interaction. For example, each server owns $u_{i},v_{i}$, and they want to compute $u\pm v$. Due to $(u_{1}$ $\pm$ $v_{1})$ $+$ $(u_{2}$ $\pm$ $v_{2})$ $=$ $u$ $\pm$ $v$, $S_{i}$ only needs to compute $u_{i}$ $\pm$ $v_{i}$, and the result is still the share of $u$ $\pm$ $v$. Similarly, each server can execute the secure multiplication by a known number (e.g., pre-trained parameters).

$Beaver^{\prime}s$ $triples$ is widely used in additive secret sharing to execute the secure multiplication called SecMul. During the offline phase (i.e., before computing secure multiplication), a pre-computed triple of the form $\{a_{i},b_{i},c_{i}|ab=c\}$ is generated and $(a_{i},b_{i},c_{i})$ is sent to server $S_{i}$, here $(a_{i},b_{i},c_{i})$ is the additive share of $(a,b,c)$. In online phase, each server computes $e_{i}=x_{i}-a_{i}$ and $f_{i}=y_{i}-b_{i}$. Then two server exchange the information of $e_{i}$ and $f_{i}$. Finally, $S_{i}$ can compute $z_{i}=fa_{i}+eb_{i}+c_{i}+(i-1)ef$. It is easy to notice that $z_{1}+z_{2}=xy$. The existing schemes [38] further expand the secure scalar multiplication to secure matrix dot product as shown in algorithm 1.

Although the fixed size vectors need to be computed during Offline phase in algorithm 1, we would show that it is feasible when facing a specific task in subsection 8.3.2. In recent work, Xiong et al. [9] further expands $Beaver^{\prime}s$ $triples$, and constructs protocols which can support almost all basic elementary function and four fundamental operations with only constant-rounds interaction rounds. In the rest of the paper, an additive share is called a share for simplicity.

Excessive comparison operations will lead to low retrieval efficiency, in this case, a reasonable index is indispensable. In PPCBIR schemes based on typical features, these methods can not only accelerate the retrieval, but also significantly reduce the communication consumption that will be shown in subsection 8.3.1. For simplicity, the HKM and C2LSH are chosen to represent tree-based and hash-based index building schemes. As we focus on the way which employs these technologies when feature vectors are stored as a share in two servers, only the numerical calculation process on feature vectors is given below. The readers can refer to [18] and [19] for more details (e.g., virtual rehash) about these schemes.

Similar to [31] and [33], the proposed scheme involves five entities, i.e., the image owner, the cloud server $S_{1}$, cloud server $S_{2}$, a trusty party $\mathcal{T}$ and authorized users. The system model is shown in Fig. 2.

Image owner owns a large-scale database $\mathcal{I}=\{I_{i}\}_{i=1}^{n}$ with the corresponding identity set $\mathcal{ID}=\{ID_{i}\}_{i=1}^{n}$ to be outsourced, here $n$ represents the number of images. To preserve privacy, the images are all randomly split into two parts $\mathcal{C}_{1}=\{C_{i}^{1}\}_{i=1}^{n}$ and $\mathcal{C}_{2}=\{C_{i}^{2}\}_{i=1}^{n}$ based on additive secret sharing. The encrypted image databases are separately sent to $\mathcal{S}_{1}$ and $\mathcal{S}_{2}$.

Cloud server $S_{1}$ and $S_{2}$ undertake the task of feature extraction, feature compression, index building, and secure retrieval. Two cloud servers need to interact with each other and collaboratively complete the above tasks.

Trusty third party called $\mathcal{T}$ takes the charge of generating random numbers or random vectors which will be used during the secure computation. It should be noted that the generation of numbers is offline and lightweight work. The $\mathcal{T}$ can be undertaken by the government or the owner of images, we will further discuss this problem in subsection 8.3.2.

Authorized user authorized by the image owner has the authorization to retrieve the corresponding images. During the retrieval, user sends the trapdoor to two servers and gets the encrypted images from the servers. The plaintext results can be obtained by simply adding the corresponding encrypted versions.

Similar to many previous works [31] in PPCBIR based on typical features, the semi-honest but non-collusion CS is considered in our scheme. It means each server will execute the protocol as asked but will try to analyze the information from data, however, due to their reputation and financial interests, they will not collude with each other. As described above, the third party $\mathcal{T}$ only needs to generate random numbers in the offline phase, which means it can be undertaken by a low-computation device. Therefore, it is reasonable to assume that $\mathcal{T}$ is honest and non-colluding.

The typical comparison schemes [39, 6] based on additive secret sharing try to use the most significant bit; however, it will lead to $l$ rounds interaction, where $l$ is the bit-length of ciphertext. These schemes try to ensure the information-theoretic security of input; however, in the computation process of a practical task, plenty of intermediate values are meaningless. It means the leakage of some non-sensitive information (e.g., the range of numbers) will cause no actual damage to the specific task. In this paper, to avoid the difficulty of comparison, we try to get the sign of $secret$ by transforming the number into an irreversable number with the same sign.

Inspired by [7], the comparison protocol based on two servers can be constructed shown as algorithm 2. Each server firstly computes the share of $u-v$, then a random number $r$ generated by $\mathcal{T}$ is utilized to cover the $u-v$. In this paper, the $sgn(x)$ is defined as formula 3. If $r$ is positive, then the $share$ of $1$ will be sent to servers; otherwise, the $share$ of $0$ will be sent. Notably, since the multiplication on $0$ will result $0$ naturally, the shares of sign can help us execute ReLU or max-pooling functions secretly with the help of SecMul.

To enhance the randomness, a small random number $k$ is added. If the result $f=f_{1}+f_{2}$ is positive, it implies that $u-v$ is also positive, and vice versa. Please note that, although $k$ may cause the wrong judgment; however, on the one hand, it can hide the situation that $u$ equals to $v$. On the other hand, for an actual task, the result of the comparison is generally used for deciding a choice. The adjacent values always imply both the choices are feasible. For instance, if two images have similar distances to the query, it strongly implies that the two images are both the wanted or not wanted results.

We will analyze the security and potential information leakage of this protocol in section 7. With the help of $share$ of sign, it is easy to utilize SecCmp to compute the ReLU function as shown in algorithm 3. Compared to previous works [6], the sign of elements in ReLU layer is also under the protection in our work.

The motivation of SecCmp is transforming the number, which needs protection, to another random number in safety and then re-share the new number. At the same time, the complex computation we execute on the new number can be reflected in the original number after a reasonable transform. In this way, the complexity of operations like comparison can be avoided. This motivation can be further applied to the matrix computation. Inspired by [40], we propose the secure matrix inverse protocol as algorithm 4.

In SecMatInv, each server first generates a random square matrix, then servers compute its dot product with the input. As the property that $(Z\cdot X)^{-1}\cdot(Z_{1}+Z_{2})=X^{-1}$, each server can finally get the share of $X^{-1}$. As the sum of the random matrix generated by two servers is almost certainly (i.e., the probability is 1) reversible, for simplicity, we here ignore the potential risk brought by the random matrix. It should be noted that this situation can be detected by calculating the rank of $W$. Especially when the matrix is simplified as a number, the secure division computation SecDiv is shown as algorithm 5.

In this paper, following the suggestion in [14], the last activation layer before FC in pre-trained VGG16 is utilized as a feature extractor. As subsection 4.1 shows, the CNN model this paper involves mainly contains three different types of layers called Conv, AL, and Pool.

As the parameters or hyper-parameters are fixed and known by both two servers, which means all the weights are just constant in the CNN. For Conv, it is just the secure constant multiplication which means no interactions are necessary during the inference process.

ReLU is the unique AL in VGG16. As described in subsection 5.1, the number less than $0$ will be set as $0$ secretly with the help of the share of $0$. Benefiting from parallelism, only three rounds of interaction are needed between the servers.

The max-pooling layer in VGG16 needs to seek the position of the maximum value in each $2\times 2$ block. Similar to ReLU function, the protocol for max-pooling is shown in algorithm 6. The smaller value will be set as 0 secretly and only the greater one will be reshared. Benefiting from parallelism, only 6 rounds of interaction are needed in the max-pooling layer.

After the extraction, following the conclusion in [17], the average aggregation is used to aggregate all the numbers gotten by each filter. Obviously, no interaction is needed during the aggregation. Here, each server gets a 512-dim encrypted feature vector for each image.

PCA is the most commonly used feature compression method[3] for accelerating the retrieval. Here, we try to propose secure PCA computation on the encrypted features collaboratively stored in two servers. Note that the compression can significantly reduce communication consumption during secure retrieval.

To our knowledge, no existing schemes try to execute the secure PCA based on additive secret sharing, the essential problem here is the way in computing eigenvectors of the matrix in safety. The following Lemmas should be noticed in this case:

Lemma 1. If $A$ and $B$ are similar matrices (i.e., $A\sim B$), and $B=P^{-1}AP$, then $A$ and $B$ have the same eigenvalues; If there is an eigenvector $\vec{x}$ under eigenvalue $\lambda$ of matrix $A$, then $P^{-1}\vec{x}$ is an eigenvector of $B$ under eigenvalue $\lambda$.

Lemma 2. If $\lambda$ is an eigenvalue of matrix $A$, then $k\times\lambda$ is an eigenvalue of matrix $k\times A$; If there is an eigenvector $\vec{x}$ under eigenvalue $\lambda$ of matrix $A$, then the eigenvector $\vec{x}$ is also under eigenvalue $k\times\lambda$ of matrix $k\times A$.$(k\neq{}0)$

Based on Lemma 1 and 2, algorithm 7 shows the scheme of PCA on an encrypted matrix. Each server first executes zero-centering for each column of the matrix $X_{i}^{n\times d}$, the $\vec{m}_{i}$ composed by mean values will be stored in the server.

Then, each server will randomly generate a matrix $P_{i}$ and a random positive number $t_{i}$, and the matrix $(P^{-1})_{i}$ will be collaboratively computed based on SecMatInv. Here the $P$ and $P^{-1}$ are generated to transform the original matrix, and $t$ is used to protect the equivalent eigenvalues. The $Y$ can be computed with the above information as shown in line number $5$. To simplify the calculation, here we only let $S_{1}$ undertake the task of computing eigenvectors. Due to the high concurrency during the actual task, it is easy to balance the workload on two servers.

Since $Y$ shares the same eigenvalues with $t\times X$ and $t$ is a positive number, the eigenvectors $T$ under the $s$ maximal eigenvalues of $Y$ are related to those of $X$. In this case, based on Lemma 1, the $P\cdot T$ is the corresponding eigenvectors of $X$. In line number $8$ to $10$, to ensure the stability of the results, the vectors in all $s$-dim are standardized. To reduce the interaction, the $\vec{r}$ composed by the squared sum of each eigenvector which is insensitive will be directly re-shared by servers.

Due to $\texttt{SecMul}(t_{i},$ $\texttt{SecMatMul}($$\texttt{SecMatMul}($$X_{i}^{T},$ $X_{i}),$ $P_{i}))$ can be calculated in parallel with $\texttt{SecMatInv}(P_{i})$. The interaction rounds needed in secure PCA protocol is 8 if $S_{1}$ undertakes the task of computing eigenvectors. The complexity of communication sizes is $O(nd)$, where $n$ and $d$ are dimensions of the uncompressed matrix.

Finally, the server can get the share of compressed data based on the share of original data and compression matrix $V$. Each server will save the mean vector $\vec{m}_{i}$ and the compression matrix $V_{i}$ for the retrieval process.

To accelerate the retrieval process, the index building schemes are considered on encrypted feature vectors stored in two servers. The typical HKM and C2LSH are used as examples, and it will be easy to notice that the other schemes can be combined with our scheme too.

The comparison of distance is indispensable during the index building or query process. However, if we use the SecCmp to compare plenty of distances and try to find the minimum one, it will lead to too high interaction rounds or too much parallel calculation. For example, to seek the minimum value in $10$ numbers, it will lead to $55$ times of comparison in parallel. Note that the size relation of distances between features is insensitive, we propose the algorithm 8 to execute secure sorting effectively.

In algorithm 8, each server generates a random positive number and gets $\{f_{i}^{k}\}$ by executing SecMul on the number and share of true distances, then re-share them. In this case, the true distances will be protected by a random multiplication, but the size relation will be kept. The server can get the right size relationship of the share based on $\{f^{k}\}$. For efficiency, we also use the SecSort protocol in the pooling layer for each 2$\times$2 block. After constructing the secure sorting protocol, the secure index building schemes are shown as follows.

This section introduces the actual retrieval process and that is the only online phase from the respective of the secure retrieval task. The authorized user splits the query image into two shares and sends it as the trapdoor to $S_{i}$.

After verifying the authorization of the user, servers will extract the aggregation feature of the query as subsection 6.1. Then servers collaboratively compress the extracted feature $\vec{q}_{i}$, with the $\vec{m}_{i}$ and $V_{i}$ stored during compression, by computing $\vec{q}_{i}=\texttt{SecMatMul}(\vec{q}_{i}-\vec{m}_{i},V_{i})$. Finally, according to the method of index building, servers collaboratively search the $m$ nearest images of the query. The retrieval process of HKM and C2LSH is shown as follows.

The security analysis of our scheme is under the typical secure multiparty computation framework[41]. The execution of our scheme mainly involves the interactions between two cloud servers, and the process of the interaction is defined as the real experiment. In the proposed scheme, two cloud servers are the potential adversaries. To prove the security of the protocol, it suffices to show that the view of the corrupted party (i.e., $S_{1}$ or $S_{2}$) is simulatable given its input and output.

In the ideal experiment, the simulator $\mathcal{S}$ is defined as the one that can simulate the view of the corrupted party by using functionality $\mathcal{F}$. In this paper, similar to previous works[42], we define the $\mathcal{F}$ as follows: $\mathcal{F}$ owns the input information gotten from $\mathcal{S}_{i}$ and generates the random numbers or matrices locally, then it completes the calculation as subprotocols, the corresponding view of $\mathcal{S}$ will be filled by the calculation results. In the following, we will prove that the $view$ is indistinguishable from that in the real world, and the $view$ will not expose the detailed input information. To simplify the proofs, the following Lemmas will be used.

Theorem 1. The protocol SecCmp is secure in the honest-but-curious model.

Proof. For $S_{1}$, the $view_{1}$ during executing protocol will be $(r_{1},$ $sgn(r)_{1},$ $a_{1},$ $b_{1},$ $c_{1},$ $k_{1},$ $\alpha_{2},$ $\beta_{2},$ $f_{1},$ $f)$. Here $(r_{1},sgn(r)_{1},a_{1},$ $b_{1},$ $c_{1},$ $\alpha_{2},$ $\beta_{2},$ $f_{1})$ is random and simulatable based on Lemma 5. For simplicity, supposing $f$ is positive. Since $f$ is the result of $(u-v)$ $\times{}t$ computed by $\mathcal{F}$, based on Lemma 6, $f$ is randomly chosen from the range $(0,$ $+\infty)$. In this case, $f$ is indistinguishable from the real world. The $view_{2}$ for $S_{2}$ is similar and simulatable. $\hfill\qed$

Even if $f$ is happened to be zero, the servers can infer that $u$ and $v$ are close; however, they can not infer the detailed size relationship in that the sign of $k$ is unknown. Based on Lemma 4, the proofs for algorithm 3 and 6 are similar and we omit them for simplicity.

Theorem 2. The protocol SecMatInv is secure in the honest-but-curious model.

Proof. For $S_{i}$, except those brought by SecMatMul, the $view_{i}$ $=$ $(Z_{i},W)$. Here $Z_{i}$ is composed of random numbers that are indistinguishable. $W$ is the result of $(Z_{1}+Z_{2})$ $\cdot$ $(X_{1}+X_{2})$ computed by $\mathcal{F}$. Due to the randomization of $Z$, any non-singular matrix in corresponding size is the potential result, which means $W$ is indistinguishable. $\hfill\qed$

When $W$ is not full-rank, similarly, any full-rank matrix in corresponding size is the potential input. Therefore, the rare situation will not bring extra risk, and the servers only need to generate $Z$ again to get the inversion.

Besides the above protocols, we also construct some secure computation protocols for the PPCBIR task. For simplicity, the functionality $\mathcal{F}$ and the corresponding information leakages of these protocols are summarized in Fig. 4.

It is easy to note that only some insensitive intermediate values and the similarity relationship between the images are exposed. The detailed information of image contents and their features are always in safety when two servers are not colluding. To avoid almost all the information leakage, it is feasible to use SecCmp only; however, it will significantly decrease the efficiency of retrieval.

In the above sections, for simplicity, the $secrets$ and $shares$ are assumed in $\mathbb{R}$; however, a real computer can only cope with the numbers in limited range and precision (i.e., a finite field $\mathbb{F}$). In detail, for the convenience of analysis on security and accuracy, the fixed-point numbers with $l_{I}$ bits on integer place and $l_{D}$ bits on the decimal place are considered in this subsection. Considering all the $shares$ and $secrets$ discussed above are represented in the $\mathbb{F}$, in this case, we analyze the influence brought by the real computer on accuracy and security in PPCBIR.