## 2 Problem Formulation and Related Work on Possible Solutions
### The Homomorphic Encryption Schemes  
Homomorphic encryption schemes provide efficient ways for computing and verifying all the processed sensitive data while keeping data confidentiality simultaneously because we can directly conduct all the computations in the encrypted domain. An encryption scheme is called homomorphic over an operation \"\(\times\)\" if it satisfies the following equality of equation:  
\[Enc\left(m_{1}\right)\times Enc\left(m_{2}\right)=Enc\left(m_{1}\otimes m_{2} \right),\ \forall\ m_{1},m_{2}\in M, \tag{1}\]  
where \(Enc\left(\bullet\right)\) denotes the encryption algorithm, \(\otimes\) is an encryption domain operation, and M is the set of all plaintext messages. [PERSON], [PERSON], and [PERSON], [7] first mentioned the concept of \"privacy homomorphism\" in 1978. RSA [8] is a well-known multiplicatively homomorphic encryption scheme; however, it is not semantically secure. [PERSON] and [PERSON] [9] proposed the first semantically secure homomorphic encryption scheme, which is additively homomorphic over \(\mathbb{Z}_{2}\). More precisely, homomorphic encryption schemes can be classified into the following three categories: Partially homomorphic encryption (PHE), Somewhat homomorphic encryption (HE), and Fully homomorphic encryption (FHE). The category of PHE includes additively homomorphic encryption (AHE) and multiplicatively homomorphic encryption (MHE) schemes. AHE and MHE schemes can only do add/sub and multiplication in the encrypted domain but not simultaneously. AHE schemes with proofs of semantic security include Benaloh, Naccache-Stern, Okamoto and Uchiyama, Paillier, Damgard, Jurik, Kawachi, Tanaka, and Xgawa. On the other hand, RSA and ElGamal are the most well-known MHE schemes. Interested readers can find the definitions and properties of all the PHE schemes mentioned above from the HE-related Wikipedia website [10]. By definition, SHE schemes support both additive and multiplicative operations. However, they can only do a limited number of operations because the accumulated \"rounding error\" will contaminate the original data or the computational results during the encryption process. When the SHE scheme has been applied several times, the rounding errors mentioned above will grow proportionally and finally cause a decryption failure. Some valuable SHEs have been proposed recently, such as Sander, Young, Boneh, Goh, Nissim, Ishai, and Paskin. Likewise, interested readers can find the definitions and properties of all the schemes mentioned above from the SHE-related survey work [11]. The theoretical proof of the existence of FHE schemes was first provided by [PERSON] [12] in 2009. With the help of bootstrapping mechanism proposed by [PERSON], an unlimited number of arithmetic operations over the encrypted data is doable. [PERSON]'s work inspired many researchers to pay attention to developing various FHE schemes. According to the FHE-related survey given by [PERSON], [PERSON], [PERSON], and [PERSON] [13], FHE schemes can be categorized into the following four types: Ideal Lattice-based, Integer-based, (R) LWE-based, and NTRU-like. The following two video records give thorough and comprehensible reviews of the historical development, recent progress, and the challenges that remained on FHE:  
1. \"A Decade (or so) of fully homomorphic encryption, by [PERSON]\" ([[https://www.youtube.com/watch?v=487](https://www.youtube.com/watch?v=487) AjvFW1 lk]([https://www.youtube.com/watch?v=487](https://www.youtube.com/watch?v=487) AjvFW1 lk) (accessed on 4 May 2023)), and
2. \"Fully Homomorphic Encryption: Definitional issues and open problems, by [PERSON]\" ([[https://youtu.be/b24](https://youtu.be/b24) WJyS0 dmg]([https://youtu.be/b24](https://youtu.be/b24) WJyS0 dmg) (accessed on 4 May 2023)). By its nature to represent and process messages in ciphertext form, by applying FHE, our system not only can prevent the misconduct caused by the mediator but also ensures that the fraud of leaking and infringing on patients' privacy can be avoided.