# Verifiable Threshold Multi-Party Fully Homomorphic Encryption from Share Resharing
## 5 Correctness, Security, and Performance Analysis
### Performance  
To simplify the performance analysis and maintain consistency with prior studies, we adopt a symbolic-level theoretical complexity model to evaluate the computational and communication overhead of our scheme. The analysis is based on symbolic expressionsinvolving key parameters such as the number of participants \(N\), the modulus \(q\), and the threshold \(t\), without assigning specific numerical values. The parameter settings and analytical methodology follow the typical models used in related works by [PERSON] and [PERSON] [9], [PERSON] et al. [19], [PERSON] et al. [21], and [PERSON] et al. [35], ensuring both comparability and theoretical representativeness. Our performance analysis begins with the study of the underlying FHE scheme. We adopt the GSW scheme [4] as the underlying encryption scheme. Unlike the BGV scheme [3], the GSW scheme evaluates on ciphertexts in matrix form with constant dimensions, thereby avoiding the need for key-switching and an evaluation key. This makes the scheme logically simple and clear. Secondly, to allow multiple parties to perform secure computations jointly, we use share resharing techniques to enable the parties to collaboratively generate a public key, with the secret key distributed and shared among them. This allows each party to encrypt using the same public key. Unlike the currently popular multi-key fully homomorphic encryption (MKFHE) schemes, ciphertexts under the same public key can directly execute homomorphic evaluation, avoiding the complex ciphertext extension steps in MKFHE schemes. This significantly reduces the size of ciphertexts involved in the evaluation. Thus, the VTMFHE scheme is compact, and the number of interactions between parties during the execution of our scheme is not affected by the function being executed or the number of parties \(N\). This reduces both the computational complexity and communication complexity of the scheme. It must be acknowledged that to make sure that the scheme is effective against malicious adversaries, we have included commitment and NIZK to construct a verification mechanism. This slightly increases the computational and communication overhead of our scheme. Specifically, according to the commitment scheme defined in Definition 11, each commitment corresponding to a submitted key share or intermediate value is a vector over \(\mathbb{Z}_{q}\) of dimension \(l_{1}+n\), where \(l_{1}\) is much less than \(n\). Thus, the communication cost of each commitment is \(O(n\text{log}\,q)\). For computation, both commitment generation and verification require a matrix-vector multiplication, resulting in a complexity of \(O\big{(}n^{2}\text{log}\,q\big{)}\). In the VDKeyGen protocol of our scheme, each party generates and sends \(N\) commitments and verifies the commitments received from others, yielding a total communication cost of \(O(Nn\text{log}\,q)\) and computation cost of \(O\Big{(}Nn^{2}\text{log}\,q\Big{)}\) per party. In the encryption and decryption algorithms, each party only needs to generate two commitments, each with a cost of \(O\big{(}n^{2}\text{log}\,q\big{)}\). For NIZK, according to the construction in Definition 15, each proof \(\pi\) consists of \(s\) commitments and responses. Its communication cost, based on [PERSON] et al. [30] (Appendix F.3), is given by the following:  
\[\|\pi\|=\Big{(}\text{log}\,\Big{(}\frac{q}{8}+1\Big{)}+n+(3l_{1}+2l_{2}+4n) \text{log}\,q\Big{)}\text{Nlog}q+sn\text{log}\,q.\]  
In our scheme, each proof contains a constant number of commitments. Therefore, the communication complexity per participant for each proof is \(O\big{(}nN\left[\text{log}\,q\right]^{2}+n\text{log}\,q\big{)}=O\big{(}nN \left[\text{log}\,q\right]^{2}\big{)}\). In terms of computation, generating the NIZK proof involves multiple commitments and multiplication relation checks, resulting in a complexity of \(O(N(nl_{1}+nl_{2}+n)\text{log}\,q)=O\big{(}Nn^{2}\text{log}\,q\big{)}\).