## 4 Security Definition and Problem Statement
### Problem Statement  
The common notations listed in Table 1 are used throughout this paper. Our proposed scheme includes two parties, namely, _[PERSON]_ and _[PERSON]_, each of whom has a collection of images. We assume that the images of both parties are private. Given an image \(I\) of _[PERSON]_, we are interested in determining whether _[PERSON]'s_ collection contains an image similar to \(I\) without disclosing _[PERSON]'s_ database to _[PERSON]_ and vice versa. We evaluate the similarity of two images under the SURF local feature vector model, in which each image is represented as a set of vectors. Let \(D=\{Img_{1},...,Img_{m}\}\) denote the set of \(m\) images in _[PERSON]'s_ collection. Without disclosing \(I\) to _[PERSON]_ and \(D\) to _[PERSON]_, our objective is to find a set  
Figure 1: Speeded up robust features (SURF) interest point of two images. of images in \(D\) similar to \(I\) without disclosing the matching results to \(Bob\). We term such protocol as SEPIM. Formally, SEPIM is defined as  
\[SEPIM(I,D)=\alpha_{1},\alpha_{2},...,\alpha_{M}. \tag{1}\]  
SEPIM returns the \(M\) similarity scores \(\alpha_{1},\alpha_{2},...,\alpha_{M}\) to _[PERSON]_ instead of returning the actual images. At another time, _[PERSON]_ can retrieve the similar image from \([PERSON]\). To evaluate the similarity between two images, each party initially extracts the feature vectors for each image in its own collection. Several metrics are used to evaluate the similarity between the sets of the two feature vectors such as Euclidean distance and cosine similarity [8]. The cosine similarity (CSIM) between vectors \(v_{1}\) and \(v_{2}\) of size \(n\) can be defined as follows:  
\[CSIM(v_{1},v_{2})=\frac{\sum_{i=1}^{n}\upsilon_{1}[i].v_{2}[i]}{\|v_{1}\|.\|v_{ 2}\|}, \tag{2}\]  
where \(\|v\|\) is the Euclidian length of vector \(v\), and is defined as the following:  
\[\|v\|=\sqrt{\sum_{i=1}^{n}\upsilon[i]^{2}}. \tag{3}\]  
Given normalized vectors \(\overrightarrow{V_{1}}\) and \(\overrightarrow{V_{2}}\), cosine similarity can be written as:  
\[CSIM(\overrightarrow{V}_{1},\overrightarrow{V}_{2})=\sum_{i=1}^{n} \overrightarrow{V}_{1}[i].\overrightarrow{V}_{2}[i]. \tag{4}\]  
Here,  
\[\overrightarrow{V}[i]=\frac{\upsilon[i]}{\left\|\upsilon\right\|}. \tag{5}\]  
Given two images, \(Img_{1}\) and \(Img_{2}\), of the two feature vector sets \(F_{1}=\{v_{1},v_{2},...,v_{k}\}\) and \(F_{2}=\{s_{1},s_{2},...,s_{p}\}\), respectively. Algorithm 1 illustrates how the distance between two feature vector sets can be measured through the cosine similarity without preserving privacy. \begin{table}
\begin{tabular}{c c} \hline \hline
**Symbol** & **Meaning** \\ \hline \(D\) & Large-scale image database \\ [PERSON]l\) & Query image \\ \(m\) & Number of images in \([PERSON]\)’s collection \\ \(k\) & Number of descriptors of _[PERSON]_[PERSON] image \\ \(p\) & Number of descriptors of each one of [PERSON]’s images \\ \(n\) & Size of descriptors \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Common symbols used. ```
Input: two feature vectors \(F_{1}=\{v_{1},v_{2},...,v_{k}\}\) and [PERSON]F_{2}=\{s_{1},s_{2},...,s_{p}\}\) of two images. All vectors \(v_{i}\) and \(s_{i}\) are of the same size \(n\). Output:Dist: distance between \(F_{1}\) and \(F_{2}\). \(Dist=0\); For\(i=1\) to \(k\)do  Compute \(\overrightarrow{v}_{i}\) as in Equation (5)  For\(j=1\) to \(p\)do  Compute \(\overrightarrow{s}_{i}\) as in Equation (5) \(D_{j}=1-CSIM(\overrightarrow{v}_{i},\overrightarrow{s}_{j})\) Endfor//j \(Dist=Dist+min(D_{j}),\forall j=1,...,p\) Endfor//k \(Dist=Dist/k\)
```  
**Algorithm 1** Insecure Image Distance Calculation  
Table 2 shows a trivial example for _[PERSON]_ image, which is represented by a set of three vectors of size 5. The first three columns are the feature vectors, while the last three columns are their corresponding normalized versions. Similarly, Table 3 illustrates the collection of _[PERSON]_, which consists of two images.