## 3 Retrieving Private Data with Optimization Processes on Homomorphic Encryption Schemes
### Transform the PSI Problem into a HE-Operatable Form
Moreover, we can regard the Server's evaluation of \(H_{x}(y)\) based on the request sent from the Client in the homomorphic encryption domain as a labeled PSI, which retrieves the corresponding labels of the intersected data on both sides of the databases without leaking any sensitive information. Let us focus on the situation of the pre-described symptom retrieval system. Suppose that the administrator of the EMRS has a set of patient ID numbers \(\mathrm{Y}=\{\)A123456789, X298659978, Z297466383, and so on], and another hospital, say Hospital HA, has the patient ID numbers and the associated symptoms set \(\mathrm{X}=\{\)(A123456789, hypertension), (T203584780, heart disease, diabetes), (B119641539, asthma), and so on]. The administrator of the EMRS initiates a labeled PSI request to the hospital HA to retrieve the patient's symptoms, ensuring that the remaining patient information stored in the hospital HA's database will not be known to the requester. Moreover, the administrator of hospital HA's EMRS cannot know which patients' symptoms are being retrieved. Nonetheless, there are still some issues to be resolved. In HE schemes, there is noise associated with each ciphertext, and sequence operations on the ciphertext will increase the noise progressively. The nature of HE has the operation (whether it is addition or multiplication) on a ciphertext always be a ciphertext. Therefore, we can regard \(F_{x}(y;r)\) as multiplication operations among the server's ciphertexts. Further note, that when the noise is too loud, the ciphertext cannot be decrypted correctly. Adding ciphertext and ciphertext, multiplying ciphertext and plaintext, and adding ciphertext and plaintext will not enlarge the noise too much. However, if two ciphertexts are multiplied, the noise will be amplified quickly. Notice that the larger the noise is, the slower the calculation of the ciphertext will be. Therefore, we must resolve these issues; otherwise, when the number of \(F_{x}(y;r)\) reaches an application-dependent threshold, say more than 10 million items, it will be difficult for the Server to calculate the polynomial correctly within a short period. Therefore, we must optimize the server's polynomial calculation in the HE domain. The following Section briefly introduces the optimization methods proposed in [22]. Before applying any optimization process, we summarize the above-mentioned labeled PSI protocol between the Client and the Server as follows:  
* Step 1: The Client encrypts each element in Y with the homomorphic public key and transmits each encrypted element to the Server one by one. * Step 2: The server samples two random numbers, \(r\) and \(r^{\prime}\), for each received ciphertext \(y\) and calculates \(F_{x}\left(y;r\right)\) and \(H_{x}(y)=F_{x}(y;r^{\prime})+G_{x}(y)\) in the HE domain. * Step 3: The Server returns the calculated result of \(F_{x}(y;r)\) and \(H_{x}(y)\) corresponding to each received ciphertext \(y\) to the Client. * Step 4: The Client decrypts the received results of \(F_{x}(y;r)\) and \(H_{x}(y)\) with the HE decryption key. If the decrypted result of \(F_{x}(y;r)\) is 0, \(y\) is at the intersection of X and Y, and then refer to the decrypted result of \(H_{x}(y)\) as the label associated with \(y\). On the contrary, if the decrypted result of \(F_{x}(y;r)\) is not 0, it means that \(y\) is not at the intersection of X and Y, so the result of \(H_{x}(y)\) cannot be referred to as the corresponding label. The complexity of the above-mentioned labeled PSI protocol before applying any optimization process is shown in Table 2.  
For the convenience of explanation, the following complexity analysis of optimized Labeled PSI will take the complexity of its non-optimized version as a benchmark. Starting from Section 3.2, we will briefly explain each optimization method proposed in [22; 23].