# Verifiable Threshold Multi-Party Fully Homomorphic Encryption from Share Resharing
## 4 Verifiable Threshold Multi-Party Fully Homomorphic Encryption
### Verifiable Distributed Key Generation Protocol  
We propose a new verifiable distributed key generation protocol (VDKeyGen) based on the LWE problem and Shamir secret sharing. The protocol employs commitments and NIZK proofs to secure against active attacks from malicious adversaries and to verify both the correctness of secret key shares and the validity of parameters used by the parties. Unlike traditional MFHE key generation methods, our protocol does not distribute a uniformly generated pair of public and secret keys. Instead, each party uniformly randomly samples from the secret key space and generates a locally stored secret key state through mutual share resharing. According to the results of the oracle query, the secret key share \(sk_{i}\) is determined through the secret reconstruction algorithm in secret sharing, and the public key \(pk\) for the current round of encryption is computed based on it. Building on the previous chapters, for the set of parties \(P=\{P_{1},\ldots,P_{N}\}\), the implicit parameters \(params\), the threshold access structure \(\mathbb{A}_{t}\), and \(\mathit{crs}\leftarrow\mathrm{N.Setup}(params)\), the detailed process of the VDKeyGen protocol is as follows:  
1. Each party \(P_{i}\) uniformly randomly samples \(\mathbf{s}_{i}\stackrel{{ R}}{{\leftarrow}}\mathbb{Z}_{q}^{n-1}\) from the ideal secret key space and commits to \(\mathbf{s}_{i}\) using a random value \(\mathbf{r}_{\mathbf{s}_{i}}\), resulting in \(\mathit{com}_{\mathbf{s}_{i}}\leftarrow\mathrm{C.Com}(\mathbf{s}_{i},\mathbf{r}_{\mathbf{s}_{ i}})\). Then, party \(P_{i}\) runs \(\big{(}\mathbf{s}_{i,1},\ldots,\mathbf{s}_{i,j}\big{)}\leftarrow\mathrm{RS.Share}(\mathbf{s }_{i},\mathbb{A}_{t},x_{1},\ldots,x_{N})\), where \(j\in[N]\) and \(j\
eq i\). Before sending the shares to other parties \(P_{j}\), \(P_{i}\) commits to each share \(\mathbf{s}_{i,j}\) using a random value \(\mathbf{r}_{\mathbf{s}_{i,j}}\stackrel{{ R}}{{\leftarrow}}\mathcal{D}_{r}\), resulting in \(\mathit{com}_{\mathbf{s}_{i,j}}\leftarrow\mathrm{C.Com}\big{(}\mathbf{s}_{i,j},\mathbf{r}_ {\mathbf{s}_{i,j}}\big{)}\). In this step, each commitment generated by the participating parties must be bound to the randomly sampled value used in the current round, ensuring that the committed value cannot be altered or forged afterward. Moreover, the structure of the commitment must satisfy the correctness requirement defined in Definition 12. 2. Each party \(P_{i}\) broadcasts the verification information \(\bigg{(}\mathit{com}_{\mathbf{s}_{i,j}}\Big{\{}\mathit{com}_{\mathbf{s}_{i,j}}\Big{\}} _{j\in[N],j\
eq i}\bigg{)}\) and securely sends \(\big{(}\mathbf{s}_{i,j},\mathbf{r}_{\mathbf{s}_{i,j}}\big{)}\) individually to the corresponding party \(P_{j}\) through a secure channel. Party \(P_{i}\) simultaneously receives shares \(\big{\{}\mathbf{s}_{j},\mathbf{r}_{j,i}\big{\}}_{j\in[N],j\
eq i}\) from all other parties \(P_{j}\). 3. After receiving the verification information from other parties, party \(P_{i}\) verifies the consistency of all commitments by running the \(\mathrm{C.Open}\big{(}\mathit{com}_{\mathbf{s}_{i,j}},\mathbf{s}_{j,i}\mathbf{r}_{\mathbf{s}_{ j}}\big{)}\) algorithm to check whether each share and its randomness satisfy the required constraints. If any commitment fails verification, the corresponding party is marked as invalid, and its share is excluded from key reconstruction and local state generation. Otherwise, \(P_{i}\) proceeds with secret resharing by computing \(\mathbf{s}^{\prime}_{i}\leftarrow\mathrm{RS.Receive}\Big{(}\big{\{}\mathbf{s}_{i,j} \big{\}}_{j\in[N],j\
eq i}\Big{)}\), and stores \(\mathbf{s}^{\prime}_{i}\) as the fixed local state for computing the secret key share \(sk_{i}\). 4. Before starting a round of computation, the public key for encryption in this round needs to be generated based on the set of parties that will remain online for this round of computation. First, the oracle is queried to obtain the set of online participants, \(P_{online}\gets Q(\mathit{Env})\).