# Verifiable Threshold Multi-Party Fully Homomorphic Encryption from Share Resharing
## 3 Module Construction
### Threshold Multi-Party Fully Homomorphic Encryption
Note that this operation on_ \(sk_{i}\) _is linear._
* \(T.FinFec\left(D,\hat{ctx}\right)\to ptx\)_: Given a set of partial decryption results_ \(D=\left\{p_{i}\right\}_{i\in S}\)_and the corresponding ciphertext_ \(ctx\)_, select any_ \(t\) _partial decryption results from the parties and reconstruct the plaintext using the combination algorithm of the secret sharing scheme:_ \[\text{S.Combine}(p_{1},\ldots,p_{t},x_{1},\ldots,x_{t}) =\sum_{i=1}^{t}p_{i}\prod_{j=1,j\
eq i}^{t}\frac{x_{j}}{x_{j}-x_{ i}}\] \[=\left\langle c\hat{x},\sum_{i=1}^{t}sk_{i}\lambda_{i}\right\rangle +\sum_{i=1}^{t}\epsilon_{i}^{\text{sm}}\] \[=\left\langle c\hat{t}x,sk\right\rangle+\sum_{i=1}^{t}\epsilon_{i} ^{\text{sm}}\] \[=\mu^{\prime}.\boldsymbol{v}+\boldsymbol{R}.\boldsymbol{e}+\sum_{ i=1}^{t}\epsilon_{i}^{\text{sm}}.\]  
_where \(ptx=\mu^{\prime}=F(\mu_{1},\ldots,\mu_{k})\), and output the plaintext \(ptx\in\{0,\;1,\;\bot\}\)._  
Similarly to FHE schemes, the TMFHE scheme needs to satisfy the properties of compactness, correctness, and semantic security, as defined below. **Definition 20 (Compactness). **_If there exists a polynomial function \(p(\cdot)\) such that for all security parameters \(\lambda\), circuit depth bound \(l\), threshold access structure \(\mathbb{A}_{t}\), number of parties \(N\), and a circuit \(F:\{0,\;1\}^{k}\rightarrow\{0,\;1\}\) with depth at most \(l\), and \(\{\mu_{i}\}_{i\in[k]}\in\{0,\;1\}\), the TMFHE scheme satisfies the following: for \((pk,\;sk_{1},\ldots,sk_{N})\gets T.KeyGen\left(params,\;\mathbb{A}_{t} \right),\left\{ctx_{i}\gets T.Enc\left(pk,\;\mu_{i}\right)\right\}_{i\in[ k]}\), \(c\hat{t}x\gets T.Eval\left(\;F,\;ctx_{1},\ldots,ctx_{k}\right)\), \(p_{i}\gets T.PartDec\left(sk_{i},\;c\hat{t}x\right)\), the size of the ciphertext \(ctx\) is only polynomially related to \(\lambda\) and \(l\), and does not depend on the number of parties \(N\). The size of any partial decryption result \(\left\{p_{i}\right\}_{i\in[N]}\) is only polynomially related to \(\lambda\), \(l\), and \(N\), i.e., \(\left|ctx\right|\leq p(\lambda,l)\) and \(\left|p_{i}\right|\leq\text{poly}(\lambda,\;l,\;N)\); therefore, the TMFHE scheme satisfies compactness._  
**Definition 21** (Correctness). : _For all security parameters \(\lambda\), circuit depth bound \(l\), threshold access structure \(\mathbb{A}_{t}\), number of parties \(N\), a circuit \(F\): \(\{0,1\}^{t}\rightarrow\{0,1\}\) with depth at most \(l\), and \(\{\mu_{i}\}_{i\in\mathbb{R}}\in\{0,1\}\), the TMFHE scheme satisfies the following: for \(\left(pk,\,sk_{1},\ldots,sk_{N}\right)\gets T.KeyGen\left(params,\, \mathbb{A}_{t}\right),\)\(\left\{ctx_{i}\gets T.Enc(pk,\,\mu_{i})\right\}_{i\in[k]},\)\(\left.ctx\gets T.Eval\left(\,F,\,ctx_{1},\ldots,ctx_{k}\right)\right.\), and \(p_{i}\gets T.PartDec(sk_{i},\,ctx)\), the output of the combination algorithm executed in the final decryption algorithm TFinDec is given by \(S.Combine(p_{1},\ldots,p_{t},x_{1},\ldots,x_{t})=\mu^{\prime}\cdot\mathbf{v}+\mathbf{R }\cdot\mathbf{e}+\sum_{i=1}^{t}\mathbf{e}_{i}^{sm}\). If the infinity norm condition \(\left\|\mathbf{R}\cdot\mathbf{e}+\sum_{i=1}^{t}\mathbf{e}_{i}^{sm}\right\|_{\infty}=mB+tB _{smdg}\leq\frac{4}{4}\) holds, then the ciphertext \(ctx\) can be correctly decrypted in a threshold manner. Thus, the TMFHE scheme satisfies correctness, i.e. :  
\[Pr\big{[}T.FinDec\big{(}D,ctx\big{)}=F(\mu_{1},\ldots,\mu_{k})\big{]}=1-negl (\lambda),\]  
_where \(D=\{p_{i}\}_{i\in[k]}\) is a set of partial decryption results, and \(k\geq t\)._  
**Definition 22** (IND-CPA Security). : _The TMFHE scheme's semantic security is directly derived from the FHE scheme (Definition 10).