## 4 The Enhanced Labeled-PSI System and the Full Protocol  
This Section presents an improved version of the pre-described Labeled-PSI System in which the system's security level has been enhanced by combining Digital Signature and Homomorphic Encryption Schemes. Figure 2 illustrates the full protocol of Enhanced Labeled-PSI from a high-level perspective. A more in-depth sequence diagram is attached as supplementary material to ease the procedure-checking addressed later and for readers interested in an in-depth sequence diagram. The chart is big in size because it presents the global view and the detailed interactions among all modules of our system. The specific precautions and procedures can be understood as follows:  
* Step 1: The administrator of the EMRS randomly generates a pair of new public-key and private-key, respectively denoted as \(\text{pk}_{\text{auth}}\) and \(\text{sk}_{\text{auth}}\), every day to allow other hospitals to do authentication tasks. In addition, the administrator of the EMRS also needs to generate a pair of new public-key and private-key, respectively denoted as \(\text{pk}_{\text{homo}}\) and \(\text{sk}_{\text{homo}}\), for encrypting and decrypting the data into/from the homomorphic domain. * Step 2: The administrator of the EMRS broadcasts the randomly generated authentication public key, \(\text{pk}_{\text{auth}}\), to other hospitals through a secure channel so that other hospitals can record that key in their databases. \begin{table}
\begin{tabular}{c c c} \hline
**Number of Ciphertexts that the Client Needs to Send to the Server** & **Number of Ciphertexts that the Server Needs to Send Back to the Client** & **Multiplication Depth of Applying the HE Scheme** \\ \hline \(|Y|\) & \(\alpha\)\(|Y|\) & \(\log\left(|X|/\alpha\right)\) \\ \hline \end{tabular}
\end{table} 
Table 6: The Complexity of the Labeled PSI Protocol after Applying the Partitioning-based optimization Process. \begin{table}
\begin{tabular}{c c c} \hline
**Number of Ciphertexts that the Client Needs to Send to the Server** & **Number of Ciphertexts that the Server Needs to Send Back to the Client** & **Multiplication Depth of Applying the HE Scheme** \\ \hline \(|Y|\) & \(|Y|\)\  
* Step 3: The administrator of the EMRS needs to obtain the required parameters from other hospitals that need to participate in labeled PSI, such as the partitioning size of server data. * Step 4: When initiating a request for symptom retrieval from other hospitals, the administrator of the EMRS needs to encrypt the patient's ID number with a homomorphic public key (cf. \(\text{pk}_{\text{homo}}\)) into ciphertexts (denoted as \(\text{ID}_{\text{encrypted}}\)). In order to prevent insider attacks, the administrator uses \(\text{sk}_{\text{auth}}\) to sign \(\text{pk}_{\text{homo}}\), (denoted as \(\text{sk}_{\text{auth}}\) (\(\text{pk}_{\text{homo}}\))). The administrator of the EMRS can then initiate a labeled PSI request to other hospitals. The administrator needs to transmit \(\text{ID}_{\text{encrypted}}\) and \(\text{sk}_{\text{auth}}\) (\(\text{pk}_{\text{homo}}\)) to other hospitals. * Step 5: When other hospitals receive \(\text{sk}_{\text{auth}}\) (\(\text{pk}_{\text{homo}}\)), they can try to decrypt it with the stored authentication public key (i.e., \(\text{pk}_{\text{auth}}\)) in their databases. If the decryption is successful, that is \(\text{pk}_{\text{auth}}\) (\(\text{sk}_{\text{auth}}\) (\(\text{pk}_{\text{homo}}\))) = \(\text{pk}_{\text{homo}}\); it means the authentication is successful. Under this condition, other hospitals can accept the labeled PSI request initiated by the Hospital HA's EMRS administrator and safely use this authenticated \(\text{pk}_{\text{homo}}\) to retrieve symptoms from their EMRS in the HE domain. Otherwise, the authentication process will fail if an insider wants to use the \(\text{pk}^{\prime}_{\text{homo}}\) created by himself to initiate a request to retrieve symptoms from other hospitals.