# Verifiable Threshold Multi-Party Fully Homomorphic Encryption from Share Resharing
## 4 Verifiable Threshold Multi-Party Fully Homomorphic Encryption
### NP Relations of NIZK  
To ensure security against active malicious adversaries, this scheme employs a verification mechanism based on commitments and NIZK, as formally defined in Section 2.4 and Section 2.5. In NIZK, proofs are generated based on the following NP relations over a language \(L\), covering distributed key generation, encryption, and threshold decryption. These proofs are used to demonstrate the correct execution of the corresponding algorithms. The NP relations are formally defined as follows:  
Definition 24 (\(\mathbf{\mathcal{R}}_{\text{DKG}}\)): During the distributed key generation protocol, the relation \(\mathcal{R}_{DKG}\) defines the correctness of the secret key share generation and proves this knowledge through the proof \(\pi_{b_{i}}\). The relation \(\mathcal{R}_{DKG}\) demonstrates that \(\mathbf{s}_{i}\) is correctly sampled from the specified distribution, \(\mathbf{s}_{i}^{\prime}\) is obtained through the share resharing process, and \(\mathbf{b}_{i}\) is correctly computed. The relation \(\mathcal{R}_{\text{DKG}}\) can be expressed as follows:_  
\[\mathcal{R}_{\text{DKG}}=\left\{\begin{array}{l}(x,w)\left|\begin{array}{c}x= \left(\mathbf{b}_{i},com_{\mathbf{s}_{i}},\left\{com_{\mathbf{s}_{i,j}}\right\}_{j\in[N],j \
eq i}\right)\wedge\\ w=\left(\mathbf{s}_{i},r_{\mathbf{s}_{i}},\left\{\mathbf{s}_{j,i}\right\}_{j\in[N],j\
eq i }\right.\left\{\mathbf{r}_{\mathbf{s}_{i,j}}\right\}_{j\in[N],j\
eq i}\right):\\ \forall i\,\mathbf{s}_{i}\in\mathbb{Z}_{q}^{n}\wedge\forall i\,C.Open\left(com_\mathbf{{s}_{i,j}},\mathbf{s}_{j,i},\mathbf{r}_{\mathbf{s}_{i,j}}\right)\\ \wedge\mathbf{s}_{i}^{\prime}=RS.Receive\left(\left\{\mathbf{s}_{j,i}\right\}_{j\in[N],j \
eq i}\right)\wedge\\ \mathbf{b}_{i}=\mathbf{B}\cdot\mathbf{s}_{i}^{\prime}+\mathbf{e}\end{array}\right\}.\]  
Definition 25 (\(\mathcal{R}_{\text{Enc}}\)): During the encryption phase of each party, the relation \(\mathcal{R}_{\text{Enc}}\) proves through the proof \(\pi_{ctx_{i}}\) that the ciphertext \(ctx_{i}\) is correctly computed by party \(P_{i}\) with the use of the given public key \(pk\) to encrypt the message \(\mu_{i}\), and that the sampled random matrix \(\mathbf{R}_{i}\) meets the encryption scheme requirements. The relation \(\mathcal{R}_{\text{Enc}}\) can be expressed as follows:_  
\[\mathcal{R}_{\text{Enc}}=\left\{\begin{array}{l}(x,w)\left|\begin{array}{c}x =\left(ctx_{i},com_{\mathbf{R}_{i}},com_{\mu_{i}}\right)\wedge\\ w=\left(\mathbf{R}_{i},r_{\mathbf{R}_{i}},\mu_{i},r_{\mu_{i}}\right):\\ \forall i\,\mu_{i}\in\left\{0,1\right\}\wedge\forall i\,\mathbf{R}_{i}\in\left\{0, 1\right\}^{m\times m}\\ \wedge ctx_{i}=\mathbf{R}(\mathbf{b},\mathbf{B})+\mu_{i}\mathbf{G}\end{array}\right\}.\]  
Definition 26 (\(\mathcal{R}_{\text{TDC}}\)): During the threshold decryption phase, the relation \(\mathcal{R}_{\text{TDC}}\) proves through the proof \(\pi_{p_{i}}\) that the partial decryption result \(p_{i}\) provided by party \(P_{i}\) is correctly computed with the use of the appropriate secret key share \(sk_{i}\) to decrypt the ciphertext \(\hat{ct}\) through the decryption algorithm, and that the smudging noise \(\mathbf{e}_{i}^{sm}\) within the specified range is added to the result. The relation \(\mathcal{R}_{\text{TDC}}\) can be expressed as follows:  
\[\mathcal{R}_{\text{TDC}}=\left\{\begin{array}{l}(x,w)\left|\begin{array}{c}x =\left(p_{i},\hat{ct},com_{sk_{i}},com_{\mathbf{e}_{i}^{sm}}\right)\wedge\\ w=\left(sk_{i},r_{sk_{i}},\mathbf{e}_{i}^{sm},r_{\mathbf{e}_{i}^{sm}}\right):\\ \forall i\,sk_{i}=RS.Combine\left(\mathbf{s}_{i}^{\prime},x_{1},\ldots,x_{t}\right) \\ \wedge\forall i\,\left\|\mathbf{e}_{i}^{sm}\right\|_{\infty}\leq B_{smdg}\wedge\\ \forall i\,p_{i}=T.PartDec\left(sk_{i},\hat{ct}\right)\end{array}\right\}.\]