# Verifiable Threshold Multi-Party Fully Homomorphic Encryption from Share Resharing
## 5 Correctness, Security, and Performance Analysis
### Correctness  
We begin by analyzing the correctness of the VTMFHE scheme in homomorphic evaluation and decryption, focusing on homomorphic addition, homomorphic multiplication, and distributed decryption. Since all parties in our scheme use a shared public key for encryption, the correctness analysis of homomorphic evaluation is similar to that of single-key FHE schemes based on the LWE problem. As defined in Section 2.3, the VTMFHE scheme relies on the correctness of the underlying FHE scheme. We first prove the correctness of homomorphic addition and homomorphic multiplication:  
For the security parameter \(\lambda\) and the circuit depth bound \(l\), let the lattice dimension \(n=n(\lambda,l)\), modulus \(q=q(\lambda,l)\), and error distribution \(\chi_{B}=\chi_{B}(\lambda,l)\) be B-bounded distributions. In our scheme, \(pk=\mathbf{A}=(\mathbf{b},\mathbf{B})\) is the public key determined by the parties after executing the VDKeyGen protocol. The ciphertext \(ct_{i}\leftarrow\mathrm{V.Enc}(pk,\mu_{i})\) is obtained by party \(P_{i}\) encrypting the plaintext \(\mu_{i}\in\{0,1\}\) using the public key \(pk\), where \(ctx_{i}=\mathbf{R}_{i}\mathbf{A}+\mu_{i}\mathbf{G}\). The plaintext result obtained during decryption is computed as \(ptx\leftarrow\langle ctx,sk\rangle=\mathbf{R}\cdot\mathbf{e}+\mu^{\prime}\cdot\mathbf{v}\). We assume that \(ctx_{1}\) and \(ctx_{2}\) are encryptions of \(\mu_{1}\) and \(\mu_{2}\), respectively. The following properties hold in our scheme:  
* Homomorphic Addition: Let \(ctx^{\prime}=ctx_{1}+ctx_{2}\). Then, \(\langle ctx^{\prime},sk\rangle=(\mathbf{R}_{1}\mathbf{e}_{1}+\mathbf{R}_{2}\mathbf{e}_{2})+( \mu_{1}+\mu_{2})\mathbf{v}\), i.e., \(ctx_{1}+ctx_{2}=\mathrm{V.Enc}(pk,\mu_{1}+\mu_{2})\). * Homomorphic Multiplication Let \(ctx^{\prime}=ctx_{1}\timesctx_{2}\). Then, \(\langle ctx,sk\rangle=ctx_{1}(\mathbf{R}_{2}\mathbf{e}_{2}+\mu_{2}\mathbf{v})=ctx_{1} \mathbf{R}_{2}\mathbf{e}_{2}+\mu_{2}(\mathbf{R}_{1}\mathbf{e}_{1}+\mu_{1}\mathbf{v})=\mu_{1}\mu_{2} \mathbf{v}+\mathbf{e}^{\prime}\), i.e., \(ctx_{1}\timesctx_{2}=\mathrm{V.Enc}(pk,\mu_{1}\times\mu_{2})\), where \(\mathbf{e}^{\prime}=ctx_{1}\mathbf{R}_{2}\mathbf{e}_{2}+\mu_{2}\mathbf{R}_{1}\mathbf{e}_{1}\) is the resulting error vector. According to the definition of the GSW scheme [4], it size will not disrupt the essential form of the ciphertext. For the correctness of the distributed threshold decryption process, after completing the homomorphic evaluation \(\hat{ct}\leftarrow\mathrm{V.Eval}\left(F,\left\{ct_{i}\right\}_{i\in[k]}\right)\), the parties generate the secret key shares for decryption according to the share resharing algorithm \(sk_{i}\leftarrow\mathrm{RS.Combine}\left(s^{\prime}_{i},x_{1},\ldots,x_{t} \right)\). They then compute the partial decryption results \(\left\{p_{i}\leftarrow\mathrm{PartDec}\left(sk_{i},\hat{ct}\right)\right\}_{i \in\mathcal{P}_{min}}\). The decryption process of the VTMFHE scheme has the following correctness:  
\[\mathrm{FinDec}\left(\left\{p_{i}\right\}_{i\in\mathcal{P}_{min}},\hat{ct} \right)=F(\mu_{1},\ldots,\mu_{k})=ptx.\]  
Ultimately, we rely on the correctness of the underlying FHE scheme and the TMFHE scheme to prove the correctness of our scheme. Additionally, consistency checks through the commitment and the NIZK system further ensure that the actively secure scheme is correct. From a structural perspective, the proposed scheme offers good compactness and scalability. In terms of ciphertext and key sizes, the ciphertext size in our scheme is fixed, independent of the original plaintext length and the number of participants \(N\), and does not grow with the data volume or system scale. Additionally, since the proposed share resharing mechanism allows secret key shares to be randomly restructured into new sharing formats, the key size remains constant regardless of the number of parties or ciphertexts, providing better scalability than classical multi-party FHE schemes (e.g., [PERSON] and [PERSON] [9], [PERSON] et al. [35]), where ciphertext and key sizes depend on \(N\).