# Verifiable Threshold Multi-Party Fully Homomorphic Encryption from Share Resharing
## 3 Module Construction
### Threshold Multi-Party Fully Homomorphic Encryption
For all security parameters \(\lambda\), circuit depth bound \(l\), threshold access structure \(\mathbb{A}_{t}\), and number of parties \(N\), the TMFHE scheme satisfies the following: for \(\left(pk,\,sk_{1},\ldots,sk_{N}\right)\gets T.KeyGen\left(params,\, \mathbb{A}_{t}\right)\) and \(\mu_{b}\in\{0,1\}\), the ciphertext \(\{ctx_{b}\leftarrow T.Enc(pk,\,\mu_{b})\}_{b\in\{0,1\}}\), and the ciphertexts \(ctx_{0}\) and \(ctx_{1}\) are computationally indistinguishable \(\left(ctx_{0}\stackrel{{ C}}{{\approx}}ctx_{1}\right)\). This implies that for any PPT adversary \(\mathcal{A}\), the probability of distinguishing between these two ciphertexts is negligible. Thus, the TMFHE scheme is considered IND-CPA-secure, i.e. :_  
\[Pr\left[ \begin{array}{cc}\mathcal{A}(pk,ctx_{b})\to b^{\prime}& \left(pk,\mu_{0}\right)\to ctx_{0}\\ b^{\prime}=b&\left(pk,\mu_{1}\right)\to ctx_{1}\\ b&\left(pk\in\{0,1\}\right)\end{array} \right]\leq\frac{1}{2}+negl(\lambda).\]  
Next, we extend the key generation method of this scheme to a distributed key generation protocol, which is an interactive process jointly run by all parties. In this protocol, all parties use the same matrix \(\mathbf{B}\) sampled from the common reference string (CRS) to generate the public key, with noise \(\mathbf{e}\leftarrow\chi^{m}\). In subsequent chapters, our construction follows a similar approach. We begin with a brief description of the modified TMFHE scheme:  
* T.SeeKeyGen\(\left(params\right)\to sk_{i}\): Each party \(P_{i}\) samples \(\mathbf{s}_{i}\leftarrow\mathbb{Z}_{q}^{n-1}\) and sets the secret key share \(sk_{i}= \begin{pmatrix}1\\ -\mathbf{s}_{i}\end{pmatrix} \). * T.PubKeyGen\(\left(sk_{1},\ldots,sk_{n}\right)\to pk\): Each party samples a matrix \(\mathbf{B}\leftarrow CRS\left(\mathbb{Z}_{q}^{m\times(n-1)}\right)\) and computes \(\mathbf{b}_{i}=\mathbf{B}\cdot\mathbf{s}_{i}+\mathbf{e}\). Then, \(\mathbf{b}=\sum\mathbf{b}_{i}\). The public key is set as \(pk=\left(\mathbf{b},\mathbf{B}\right)\). * T.PartDec\(\left(sk_{i},ctx\right)\to p_{i}\): Each party \(P_{i}\) inputs its own secret key share \(sk_{i}\) and the ciphertext \(ctx\), computes \(p_{i}=\left\langle\hat{ctx},sk_{i}\right\rangle+\mathbf{e}_{i}^{sm}\), and then outputs the partial decryption result \(p_{i}\), where \(\mathbf{e}_{i}^{sm}\stackrel{{ R}}{{\leftarrow}}\left[-B_{smdg},B_{ smdg}\right]^{m}\). * T.FinDec\(\left(D,\hat{ctx}\right)\to ptx\): Input all the partial decryption results \(D=\{p_{i}\}_{i\in N}\) and the ciphertext \(ctx\), and then combine them to compute the plaintext result \(ptx\). In the basic TMFHE scheme, when each party executes the T.PartDec algorithm, the smudging noise (Lemma 1) is added to the partial decryption result. This step prevents the leakage of information about the secret key share \(sk_{i}\) through the simple inner product of \(sk_{i}\) and the public value \(\hat{ctx}\). This converts the simple computation into a difficult problem, where \(\chi^{m}/B_{smdg}=negl(\lambda)\). However, ensuring that this added noise does not impact the correctness of the decryption is crucial. During the reconstruction of the secret from the partial decryption results, the noise is multiplied by the Lagrange coefficients, and thesmudging noise term becomes \(\sum_{i=1}^{t}\mathbf{e}_{i}^{sm}\lambda_{i}\). This can cause the noise to grow too quickly, affecting the scheme's correct decryption and reducing its practicality, i.e. :  
\[S.Combine(\{p_{i}\}_{i\in S^{\prime}}\{x_{i}\}_{i\in S})=\sum_{i=1}^{t}p_{i} \lambda_{i}=c\dot{x}x\sum_{i=1}^{t}sk_{i}\lambda_{i}+\sum_{i=1}^{t}\mathbf{e}_{i}^{ sm}\lambda_{i}=c\dot{x}x\cdot sk+\sum_{i=1}^{t}\mathbf{e}_{i}^{sm}\lambda_{i}\]