## 2 Problem Formulation and Related Work on Possible Solutions  
### The Strawman Protocol and Its Security Threat  
The strawman protocol for providing symptom retrieval is used and monitored by the administrator, A, of a hospital HA's EMRS. For convenience, hereafter, we will not indicate the name of the responsive hospital but directly refer the corresponding EMRS to the administrator's name, A. Therefore, the task of transmitting patients' ID numbers from hospital HA to other Hospitals, say Hospitals HB, HC, and HD, can be represented by the information flow diagram shown in Figure 1. If Hospitals HB and HC did have the relevant medical records of the searched patients, administrators B and C would send the related symptoms back to administrator A, respectively. The security threats of the Strawman protocol presented in Figure 1 can be understood as follows. Suppose a doctor or other interested person in the hospital pretends to be the administrator of the EMRS and initiates a request for symptom retrieval to other hospitals without authorization. In that case, it will infringe on the patient's privacy. This kind of threat is tough to deal with and is well-known as an insider attack. An essential idea to face insider attacks is that we can introduce a digital signature mechanism, allowing the administrator of the EMRS to sign the message, and other hospitals will verify the message's origin after receiving it. On the one hand, if Hospitals receive the querying messages in plaintext form, the hospitals can know which patient from which hospital is currently doing the search and whose patient's records are now being searched; both situations infringe on the patient's privacy. On the other hand, suppose Hospitals transmit medical records in ciphertext form but the patient's ID information in plaintext form through insecure channels \begin{table}
\begin{tabular}{c c} \hline \hline
**Abbreviation/Term** & **Definition** \\ \hline (R) LWE & Ring Learning With Errors \\ NTRU & Number Theory Research Unit \\ PSI & Private Set Intersection \\ PRF & Pseudo-Random Function \\ OT & Oblivious Transfer \\ SIMD & Single Instruction Multiple Data \\ \hline \hline \end{tabular}
\end{table} 
Table 1: _Cont._  
Figure 1: The Information Flow of the Considered Symptom Retrieving Protocol with the aid of a Cooperative Electronic Medical Recording System. (such as the Internet). Then, they will still be subjected to another severe security threat, the so-called man-in-the-middle attacks, leading to contaminated sensitive information. To conquer the threat caused by the middleman, encrypting all communication-related messages, i.e., converting both patient ID and treatment records into the ciphertext domain, is a feasible solution. However, using conventional encryption schemes such as DES and AES, other hospitals have to decrypt the encrypted searching-related message, say the patients' ID, before conducting the record-seeking task. Consequently, this intermediate decryption process will reveal the footprints of the search pattern. Moreover, after the Hospitals find the records, they must encrypt them again before sending the documents back to the Hospital that initiates the search. Searchable Encryption and Homomorphic Encryption are two well-known applicable cryptographic approaches to provide ways to relieve the burdens mentioned above. Many searchable encryption schemes and Algorithms [1; 2; 3; 4; 5; 6] have been proposed to provide various exciting features, such as fine-grained access control, dynamic updates, and attribute revocations. However, searching capabilities must be more potent in most schemes fulfilling actual needs. Usually, they can embed only a single or limited number of keywords into ciphertexts, which is inconvenient and makes searching time-consuming. Although some schemes allow combining multiple keywords and providing ranked search results, users can only fetch files containing all the keywords.