## 5 Construction of Secure and Efficient Private Image Matching (SEPIM)  
As shown in Figure 2, our SEPIM protocol distributes scores calculation between the two participant parties and is composed of two phases, initialization and matching. In the first phase, each party computes the feature vector set for each image in its own collection and then normalizes each vector to enable the assessment of the cosine similarity. We demonstrate the proposed scheme using SURF descriptors, although this scheme is applicable to other feature vectors. Then, through the use of Algorithm 2, the data owner (_[PERSON]_) builds an effective search index tree _TreIndex_ used in image search. ```
Input:\(\overrightarrow{\{V_{i}\}},1\leq i\leq m,R\): \(k\)-means cluster number Output:\(TreeIndex\). \(N_{r}=m\);//Number of vectors in cluster \(r\) : \(CL_{r}\)  Child_Gen(\(\overrightarrow{\{V_{i}\}}_{1\leq i\leq m},R\));  Function Child_Gen(\(vectors\{V_{i}\},R\)) begin \(k\)-means(\(\{V_{i}\},R\)) \(\to R\) cluster \(CL_{r}\); For\(r=1\) to \(R\)do  If \(N_{r}>R\) Then  Child_Gen(\(vectors\{V_{i}\}_{i\in CL_{r}},R\)); Endfor//
```  
**Algorithm 2** Index Tree Building  
In the second phase, _[PERSON]_ generates a secure image search request. Upon receiving of _[PERSON]_'s request, _[PERSON]_ executes the secure and efficient private image matching algorithm (Algorithm 3) to retrieve values indicating similarity scores to _[PERSON]_ instead of returning the actual images. At another time, _[PERSON]_ can retrieve the similar image from _[PERSON]_. We now introduce the detail of each algorithm in our SEPIM construction. Figure 2: Architecture of Secure and Efficient Private Image Matching (SEPIM) scheme. ```
0:\(I\): \([PERSON]\)'s image. \(D=\{Img_{1},...,Img_{m}\}:[PERSON]^{\prime}s\) collection. \(\alpha_{1},\alpha_{2},....,\alpha_{M}\): the similarity scores. Initialization: [PERSON]: -Generate the homomorphic encryption public key pair \((pr,pk)\). -Define the similarity threshold \(Sht\). -Send \(pk\) and \(Sht\) to [PERSON]. -Use SURF algorithm to extract the feature vector set \(F=\{v_{1},v_{2},...,v_{k}\}\) for the image \(I\), all vectors \(v_{i}\) are of the same size \(n\). -Compute \(\overrightarrow{v}_{i}\) as in Equation (5), for \(i=1,...,k\), and replace it with \(v_{i}\) in \(F\). [PERSON]: For each image \(Img_{j}\in D,\forall_{j}=1,...,m\) - Use SURF algorithm to extract the feature vector set \(F_{j}=\{s_{1},s_{2},...,s_{p}\}\). - Compute \(\overrightarrow{s}_{i}\) as in Equation (5), for \(i=1,...,p\), and replace it with \(s_{i}\) in \(F_{j}\). Endor //j -The owner randomly selects \(R\) centroids -Use index tree building algorithm (Algorithm 2) to cluster the feature vector set \(\overrightarrow{\{F_{j}\}},1\leq j\leq m\) into clusters \(CL_{r},1\leq r\leq R\) and builds index tree structure. Matching: (\(\underline{\textit{{first round}}}\)) For\(i=1\) to \(k\)do  Encrypt the elements of vector \(\overrightarrow{v}_{i}\) as: \(z_{ij}\gets HEnc_{pk}(\overrightarrow{v}_{ij})\) for all \(j=,1,...,n\) Endor //i - Send \(z\) to [PERSON]: (Step1) -Starting the search enquiry from the top level to leaf level of \(TreeIndex\), and at every level: \(\bullet\) Acquire the set of node vectors \(\{VF_{hi}\},1\leq i\leq R\); \(\bullet\) Calculate the cosine similarity based on secure dot product between the \(Alice\)'s search vectors set and the node vectors set \(\{VF_{hi}\},1\leq i\leq R\); \(\bullet\) Finds the entry points of the next level by finding the nodes with vectors that have the minimal distances to the received search image vector \(z\) according to the threshold \(Sht\);
```  
**Algorithm 3** Secure and Efficient Private Image Matching  
```
- Get the feature vector set \(F_{m}\) of image \(m\). - Compute the secure dot product set between the _[PERSON]_'s vector set and the vector set of image \(m\) as: \(\mathit{Dot}\{m\}=\mathit{Secure\_dot\_product}(Z,F_{m})\); **Endfor//\(m\)**
- Send \(\mathit{Dot}\{m\}\) to _[PERSON]_.