# Efficient SMC Protocol Based on Multi-Bit Fully Homomorphic Encryption
## 1 Introduction  
As cloud computing develops rapidly, the problem of user privacy data security has become increasingly prominent. Fully Homomorphic Encryption (FHE) has just solved the problem of data privacy computing. Fully homomorphic encryption was first proposed by [PERSON] et al. [1] in 1978, which could perform various meaningful calculations on ciphertext without knowing the key. In other words, for any plain-text \(m\) and function \(f\), there is \(f(Enc(m))=Enc(f(m))\). Since [PERSON] et al. [2] proposed the first fully homomorphic encryption scheme in 2009, many fully homomorphic encryption schemes such as BV11 [3], BGV12 [4], Bra12 [5], GSW13 [6], and CKKS17 [7] have appeared in recent years. Fully homomorphic encryption can be used as a building block of a secure multi-party computation (SMC) protocol and shows good potential in the design of a secure multi-party computation protocol. In addition, the concept of secure multi-party computation originated from the millionaire problem proposed by [PERSON] [8], which is characterized by allowing multiple parties to jointly calculate a certain function to obtain the result without private data being leaked out. Nowadays, domestic and international scholars have carried out much research on the secure multi-party computation protocol based on the fully homomorphic encryption scheme. In 2012, [PERSON] et al. [9] proposed the concept of Multi-Key Fully Homomorphic Encryption (MFHE). Based on the improved NTRU scheme [10], an MFHE scheme was constructed, which can operate the input encrypted under multiple unrelated keys, but the complexity is too high. In 2016, based on the Learning With Errors (LWE) assumption, [PERSON] et al. (MW16 scheme) [11] implemented a multi-key secure multi-party computation protocol with only two rounds of interaction under the CRS model, achieving the best interaction rounds, but the ciphertext matrix was too large. In 2017, [PERSON] et al. [12]constructed a simple three-round, leveled, multi-key, secure multi-party computation protocol under the CRS model based on the GSW13 scheme. Compared with the MW16 scheme, although an additional round of interaction was added, the complexity of encryption and decryption was low, and the ciphertext expansion rate was small, which did not require a running key. In 2018, due to the problem that the secure multi-party computation protocol under the CRS model weakened the user's ability to independently generate their own keys, [PERSON] et al. (KLP18 scheme) [13] constructed a three-round, secure, multi-party computation protocol without CRS. The protocol was safe against semi-malicious opponents, but it could not fight against completely malicious opponents. In 2020, [PERSON] et al. [14] improved the ciphertext extension method of the KLP18 scheme with the help of the coding operation in [PERSON]'s scheme [15] and designed a three-round, secure, multi-party computation protocol based on MFHE without the CRS model, improving the efficiency and reducing decryption noise, but it still could not prove that it was safe in a fully malicious environment. In 2021, [PERSON] et al. [16] proved the key homomorphism of the multi-bit fully homomorphic encryption scheme proposed by [PERSON] [17]. Moreover, based on this scheme, a three-round, secure, multi-party computation protocol that could support multi-bit encryption under the CRS model was designed, which further reduced the complexity of the NAND gate. It can be seen from the above related work that although the secure multi-party computation protocol under the CRS-free model allows MFHE users to independently generate their own keys, the secure multi-party computation protocol under this model is not secure enough to resist completely malicious adversaries. What is more, nowadays, the fully homomorphic encryption-based secure multi-party computation protocol under the CRS model has problems such as large ciphertext size and insufficient efficiency.