# Verifiable Threshold Multi-Party Fully Homomorphic Encryption from Share Resharing
## 4 Verifiable Threshold Multi-Party Fully Homomorphic Encryption
### Construction of the VTMFHE Scheme  
In this section, we define the construction of our VTMFHE scheme. The scheme is based on the LWE problem, and leverages Shamir secret sharing and share resharing to distribute secret key shares among the parties. It ensures that the computation process is honestly and correctly executed by all parties and against active malicious adversaries through commitment and NIZK proof. Briefly, after the Setup, the scheme executes a verifiable distributed key generation protocol. Then, the current parties encrypt their plaintext using a common public key, send the ciphertexts, and perform homomorphic evaluation. Finally, a distributed threshold decryption process is performed to obtain the final plaintext result. Let \(P=\{P_{1},\ldots,P_{N}\}\) be a set of parties, and let \(B_{smdg}\) be the bound for the smudging noise. We construct the scheme VTMFHE = (V.Setup, V.KeyGen, V.Enc, V.Eval, V.TDec) as follows:  
* V.Setup \(\left(1^{\lambda},1^{l},\mathbb{A}_{t}\right)\to params\) : Given the security parameter \(\lambda\), the circuit depth bound \(l\), and the threshold \(t\) access structure \(\mathbb{A}_{t}\), \(params\gets T.Setup\left(1^{\lambda},\,1^{l},\,\mathbb{A}_{t}\right)\) is output as the implicit input for other algorithms, and each party \(P_{i}\in P\) is associated with a non-zero element \(x_{i}\in\mathbb{Z}_{q}^{*}\). * V.KeyGen \(\left(params\right)\rightarrow\left(\left\{s_{i}^{\prime}\right\}_{i\in[N]^{ \prime}},pk\right)\) : The VDKeyGen protocol is executed, where each party stores the \(s_{i}^{\prime}\) used to compute the secret key share locally. Then, based on the results of the oracle query, the public key \(pk\) is computed for encryption. * V.Enc \(\left(pk,\mu_{i}\right)\to ct_{i}\) : The parties involved in this round of computation uniformly sample a random matrix \(\mathbf{R}_{i}\in\{0,1\}^{m\times m}\) and use the public key \(pk\) to encrypt their own message \(\mu_{i}\), outputting the ciphertext \(ctx_{i}=\mathbf{R}_{i}\mathbf{A}+\mu_{i}\mathbf{G}\), where \(ctx_{i}\in\mathbb{Z}_{q}^{m\times n}\) and \(\mathbf{G}\in\mathbb{Z}_{q}^{m\times n}\) is the short preimage matrix. To prevent malicious participants from forging ciphertexts or submitting malformed data, each party commits to the encryption-related variables (e.g., \(\mathbf{R}_{i}\) and \(\mu_{i}\)) and computes an NIZK proof \(\pi_{ctx_{i}}\) under the encryption NP relation \(\mathcal{R}_{Enc}\) to prove the ciphertext's correctness and structural validity. The ciphertext and associated verification data are sent together, and must be verified before any homomorphic evaluation. Specifically, each party samples \(\mathbf{r}_{\mathbf{R}_{i}}\overset{R}{\leftarrow}S_{\mathbf{r}}\) and \(\mathbf{r}_{\mu_{i}}\overset{R}{\leftarrow}S_{\mathbf{r}}\), then computes \(com_{\mathbf{R}_{i}}\leftarrow\mathrm{C.Com}\left(\mathbf{R}_{i},\mathbf{r}_{ \mathbf{R}_{i}}\right)\) and \(com_{\mu_{i}}\leftarrow\mathrm{C.Com}\left(\mu_{i},\mathbf{r}_{\mu_{i}}\right)\). The proof is computed as \(\pi_{ctx_{i}}\leftarrow\mathrm{N.Prove}\left(x,w,\mathit{crs}\right)\), where \(x=\left(ctx_{i},\,com_{\mathbf{R}_{i}},com_{\mu_{i}}\right)\) and \(w=\left(\mathbf{R}_{i},\mathbf{r}_{\mathbf{R}_{i}},\mathbf{\mu}_{i},\mathbf{r} _{\mu_{i}}\right)\). The final output is \(ct_{i}=\left(ctx_{i},\pi_{ctx_{i}},com_{\mathbf{R}_{i}},com_{\mu_{i}}\right)\). * V.Eval \(\left(F,\left\{ct_{i}\right\}_{i\in[k]}\right)\rightarrow\hat{ct}\) : Given a Boolean circuit \(F:\{0,1\}^{k}\rightarrow\{0,1\}\) with a computation depth bound \(l\) and a set of ciphertexts \(\left\{ct_{i}\right\}_{i\in[k]}\); before performing homomorphic evaluation, each ciphertext \(ct_{i}\) is parsed and verified using the proof \(\pi_{ctx_{i}}\) via the NIZK verification algorithm: \(\{0,1\}\leftarrow\mathrm{N.Verify}\left(x,\pi_{ctx_{i}},\mathit{crs}\right)\). If any ciphertext fails verification, it is discarded, and its sender is marked as an invalid participant, and thus excluded from this round of homomorphic evaluation.