# Verifiable Threshold Multi-Party Fully Homomorphic Encryption from Share Resharing
## 3 Module Construction
### Threshold Multi-Party Fully Homomorphic Encryption  
We define a multi-party FHE scheme based on the LWE problem that incorporates the distributed threshold decryption protocol (TMFHE). The scheme is similar to the lattice-based threshold scheme by [PERSON] et al. [25] and the threshold PKE scheme proposed by [PERSON] et al. [35]. In our construction, the decryption secret key is distributed to all partiesvia secret sharing, and all parties use the same public key for encryption. This enables ciphertexts generated by each party to be directly evaluated homomorphically, without requiring complex and costly ciphertext extension steps (compared to MW16 [9]). The final distributed threshold decryption can be achieved through the threshold properties of secret reconstruction in secret sharing. **Definition 19 (TMFHE). **_Let \(P=\{P_{1},\ldots,P_{N}\}\) be a set of parties, and let \(B_{smdg}\) be the bound for the smudging noise (Lemma 1). TMFHE = (T.Setup, T.KeyGen, T.Enc, T.Eval, T.PartDec, T.FinDec) is a tuple of algorithms, defined as follows:_  
* \(T.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}\)_, run_ \(params\gets F.Setup\left(1^{\lambda},\;1^{l}\right).\) _Execute S.Setup to associate each party_ \(P_{i}\in P\) _with a non-zero element_ \(x_{i}\in\mathbb{Z}_{q}^{*}\)_, and incorporate the sequence of public points_ \((x_{1},\ldots,x_{N})\) _into params. Use params and_ \(\mathbb{A}_{t}\) _as public parameters, serving as implicit inputs for other algorithms._
* \(T.KeyGen\left(params,\;\mathbb{A}_{t}\right)\rightarrow(pk,\;sk_{1},\ldots,sk_{N})\)_: Given the public parameters, run the algorithms_ \(sk\gets F.SetKeyGen\left(params\right)\) _and_ \(pk\gets F.PubKeyGen\left(sk\right)\) _to output a key pair_ \((pk,\;sk)\)_. Then, run the algorithm_ \((sk_{1},\ldots,sk_{N})\gets S.Share\left(sk,\mathbb{A}_{t},x_{1},\ldots,x_{N}\right)\) _to distribute a secret key share_ \(sk_{i}\) _to each party_ \(P_{i}\in P\)_._
* \(T.Enc\left(pk,\mu_{i}\right)\to ctx_{i}\)_: Each party_ \(P_{i}\) _uses the public key_ \(pk\) _and its own message_ \(\mu_{i}\) _as input, executes the_ \(ctx_{i}\gets F.Enc\left(pk,\mu_{i}\right)\) _algorithm, and then outputs the ciphertext_ \(ctx_{i}\)_._
* \(T.Eval\left(\;F,\;ctx_{1},\ldots,ctx_{k}\right)\to ctx\)_: Given a circuit_ \(F:\{0,\;1\}^{k}\rightarrow\{0,\;1\}\) _with a depth bound_ \(l\) _and a set of ciphertexts_ \(\left\{ctx_{i}\right\}_{i\in[k]}\)_, execute the_ \(c\hat{x}\leftarrow F.Eval\left(\;F,\;ctx_{1},\ldots,ctx_{k}\right)\) _algorithm and output the evaluated ciphertext_ \(ctx\)_._
* \(T.PartDec\left(sk_{i},\;ctx\right)\to p_{i}\)_: Each party_ \(P_{i}\) _in the subset_ \(S\in\mathbb{A}_{t}\) _takes its own secret key share_ \(sk_{i}\) _and the ciphertext_ \(ctx\) _as input, computes_ \(p_{i}=\left\langle ctx,\;sk_{i}\right\rangle+\epsilon_{i}^{\text{sm}}\)_, and then outputs the partial decryption result_ \(p_{i}\)_, where_ \(\epsilon_{i}^{\text{sm}}\overset{R}{\leftarrow}\left[-B_{smdg},B_{smdg}\right]^{ \text{sm}}\) _is the added \"smudging\" noise vector.