# Verifiable Threshold Multi-Party Fully Homomorphic Encryption from Share Resharing
## 4 Verifiable Threshold Multi-Party Fully Homomorphic Encryption
### Verifiable Distributed Key Generation Protocol
If \(|P_{online}|\leq t\), it indicates that the current set of online parties does not meet the threshold requirement and is considered an invalid set. In this case, Step 4 of the protocol should be re-executed to ensure the correctness of key generation. If \(|P_{online}|\geq t\), then \(t\) parties are selected from \(P_{online}\) to execute thealgorithm \(sk_{i}\leftarrow\text{RS.Combine}\left(\mathbf{s}_{i}^{\prime},x_{1},\ldots,x_{i}\right).\) Then, these parties sample the common matrix \(\mathbf{B}\leftarrow\text{CRS}\left(\mathbb{Z}_{q}^{m\times(n-1)}\right)\) and the noise \(\mathbf{e}\leftarrow\text{CRS}(\chi^{m}),\) computing \(\mathbf{b}_{i}=\mathbf{B}\cdot\mathbf{s}_{i}^{\prime}+\mathbf{e}.\) After computing the key share, each party must generate an NIZK proof to ensure that other parties can verify the structural correctness, sampling validity, and source consistency of the share. The proof must satisfy the public NP relation \(\mathcal{R}_{DKG}\), and is computed as \(\pi_{\mathbf{b}_{i}}\leftarrow\text{N.Prove}(x,w,\text{crs}),\) where \(x=\left(\mathbf{b}_{i},\text{com}_{\mathbf{s}_{i}},\left\{\text{com}_{\mathbf{s}_{i}}, \left\{\text{com}_{\mathbf{s}_{i}}\right\}_{j\in[N],j\
eq i}\right)\) and \(w=\left(\mathbf{s}_{i},\mathbf{r}_{\mathbf{s}_{i}},\left\{\mathbf{s}_{j,i},\mathbf{r}_{\mathbf{s}_{i} \right\}\right\}_{j\in[N],j\
eq i}\right)\). The construction details of this relation will be explained in Section 4.4. 5. Finally, party \(P_{i}\) broadcasts \(\left(\mathbf{b}_{i},\pi_{\mathbf{b}_{i}}\right)\). Upon receiving it, each party verifies the proof \(\left\{0,1\right\}\leftarrow\text{N.Verify}\left(x,\pi_{\mathbf{b}_{i}},\text{crs} \right).\) This ensures that each participant's share satisfies the structural constraints defined in Definition 16. If any verification fails, the corresponding user is regarded as an abnormal participant, and their share is excluded from the public key aggregation process. This guarantees that the public key is formed only from valid data. If the number of shares that pass verification still satisfies the threshold access structure (allowing some public key shares to be invalid), then compute \(\mathbf{b}=\sum_{t}\mathbf{b}_{i}\) and output \(pk=\left(\mathbf{b},\mathbf{B}\right)\) as the public key. Otherwise, re-execute Step 4 of the protocol. Note that the VDKeyGen protocol is an interactive process in which shares \(\mathbf{s}_{i,j}\) are exchanged pairwise between parties via secure channels during the resharing phase. This allows each party to store a state \(\mathbf{s}_{i}^{\prime}\) locally, which can be used by a set of parties (at least \(t\) parties) to compute the secret key share for generating the public key. Thus, any qualified subset of parties can generate new secret key shares \(sk_{i}\) for use in later decryption phases. During the execution of the scheme, if new participants dynamically join the computation, the VDKeyGen protocol must be rerun among all current parties to regenerate secret shares and a new public key, ensuring the correctness of homomorphic evaluation and decryption. If some participants go offline after key generation, the protocol proceeds as long as the remaining online parties meet the threshold requirement. Otherwise, execution is halted and resumed only when the number of active participants meets the minimum threshold \(t\), as specified in the timeout handling of Section 3.3. Moreover, to provide active security, we incorporate commitment schemes and NIZK proofs to prevent corrupted parties from submitting forged or incorrect key shares during key generation. These mechanisms verify that each party follows the protocol correctly and that submitted data are well formed. If any commitment or proof fails, the corresponding share is marked invalid, the sender is treated as an abnormal participant, and their data are excluded from key aggregation. If the threshold condition is still met, the protocol proceeds with the remaining valid parties; otherwise, it must be re-executed.