## 3 Retrieving Private Data with Optimization Processes on Homomorphic Encryption Schemes
### Transform the PSI Problem into a HE-Operatable Form  
Reference [22] converts the PSI problem into the following polynomial form to meet the types of operable operations (addition and multiplication) supported by HE and asks the Server to calculate it on the encryption domain:  
\[F_{x}(y)=(y-x_{1})(y-x_{2})\ldots\left(y-x_{\left\lvert x\right\rvert}\right) = \begin{cases}0,&y\ \in\ \ X\\ else,&y\ \
otin\ \ X^{\prime}\end{cases}  \tag{3}\]  
where \(y\in Y\) is an element on the Client side, and \(x_{i}\in X\) is an element on the Server side. If the result of \(F_{x}(y)\) is 0, it indicates that \(y\) is also one of the elements on the server side (i.e., there is an intersection between X and Y). If the result is not 0, \(y\) does not belong to the Intersection Set. It is worth noting that for the Server when calculating \(F_{x}(y)\), \(x_{i}\) is the plaintext form, while \(y\) is in the ciphertext form transmitted by the Client after conducting the HE operations. However, when the result of \(F_{x}(y)\) is not 0, the Client could infer the elements on the Server by initiating multiple PSI requests to the Server, resulting in indirect leakage of the elements on the Server. To eliminate the concerns about leaking elements on the Server, multiplying the above polynomial by a random number \(r\) is an ingenious way, that is:  
\[F_{x}(y;r)=(y-x_{1})(y-x_{2})\ldots\left(y-x_{|x|}\right)r= \begin{cases}0,&y \ \in\ \mathrm{X}\\ random,&y\ \
otin\ \mathrm{X}^{\prime}\end{cases}  \tag{4}\]  
This simple operation can ensure that the Client cannot speculate the data on the Server. We can now learn whether the two sets have an intersection through the evaluation of \(F_{x}\left(y;r\right)\) on \(\mathrm{Y}\) by the similar expounds associated with \(F_{x}(y)\). That is, we regard the \(F_{x}(y;r)\) the Client requests the Server to evaluate the encryption domain as a PSI-checking request. Next, if there is an intersection between \(\mathrm{X}\) and \(\mathrm{Y}\), we hope to obtain the corresponding labels of the intersected elements. As suggested in [23], a new polynomial \(H_{x}(y)\) could be created based on \(F_{x}(y;r)\) to fulfill this requirement. That is  
\[H_{x}(y)=F_{x}(y;r)+G_{x}(y), \tag{5}\]  
In Equation (5), \(F_{x}(y;r)\) is used to determine whether there is an intersection, and \(G_{x}(y)\) is a curve-fitting polynomial passing through a sequence of given data points which is used to retrieve the corresponding labels of the intersected elements. Taking the two-dimensional space as an example, given the coordinates of k points, we can use the well-known Lagrange Interpolation Formula to find the polynomial that passes through all the given k points on the plane. Therefore, we can transform the server's database into the coordinate and retrieve the corresponding data label by polynomial interpolation. Suppose there are three data on the server, say 1, 2, and 3, and the corresponding labels are 6, 11, and 18. Then, we can regard the data and the corresponding labels as three points (1, 6), (2, 11), (3, 18) in the two-dimensional space. Then, through the polynomial-based curve-fitting, we can find the desired polynomial. Taking the Lagrange interpolation as an example, \(G_{x}(y)\) can be written as:  
\[ \begin{split}& G_{x}(y)=6\frac{(y-x_{2})(y-x_{3})}{(x_{1}-x_{2})(x_{ 1}-x_{3})}+11\frac{(y-x_{1})(y-x_{3})}{(x_{2}-x_{1})(x_{2}-x_{3})}+18\frac{(y-x _{1})(y-x_{2})}{(x_{3}-x_{1})(x_{3}-x_{2})}\\ &=6\frac{(y-2)(y-3)}{(1-2)(1-3)}+11\frac{(y-1)(y-3)}{(2-1)(2-3)}+18 \frac{(y-1)(y-2)}{(3-1)(3-2)}=y^{2}+2y+3\end{split}  \tag{6}\]  
It can be easily checked that \(G_{x}(y)\) generated above does satisfy \(G_{x}(1)=6\), \(G_{x}(2)=11\), \(G_{x}(3)=18\). So far, we can use \(H_{x}(y)\) to complete Task 1 (by \(F_{x}(y;r)\)) and Task 2 (by \(G_{x}(y)\)) mentioned at the end of Section 2.2.