# Verifiable Threshold Multi-Party Fully Homomorphic Encryption from Share Resharing
## 5 Correctness, Security, and Performance Analysis
### Security
Input \(\left(1^{\lambda},1^{l}\right)\); the adversary \(\mathcal{A}\) sends a set of corrupted parties \(\mathcal{C}\), where \(|\mathcal{C}|\leq t-1\). The parties interact according to the VDKeyGen protocol in Section 4.1, generating the corresponding commitments and proofs \(\left\{\left.com_{s_{i}},\left\{com_{s_{i}}\right\}\right\}_{i\in[N],j\
eq i }\pi_{b_{i}}\right\}_{i\in P}\). After completing the verification, they generate the public key \(pk\) and \(\left\{s_{i}^{\prime}\right\}_{i\in P}\) through share resharing and oracle query. 2. \(\mathcal{A}\) issues encryption queries by choosing plaintexts \(\mu_{1},\ldots,\mu_{k}\in\{0,1\}\) and obtaining the ciphertexts \(\left\{ct_{i}\right\}_{i\in[k]}=\left\{\text{V.Enc}(pk,\mu_{i})\right\}_{i\in[k]}\) through the encryption algorithm. 3. \(\mathcal{A}\) issues polynomial adaptive queries in the form of \(\left(\mathcal{C}\subseteq P,F\right)\), where \(F:\{0,1\}^{k}\rightarrow\{0,1\}\) is a circuit with depth bound \(l\). For each query, the scheme executes \(\hat{\alpha}\leftarrow\text{V.Eval}\left(F,\left\{ct_{i}\right\}_{i\in P, \mathcal{C}}\right)\) and sends the partial decryption results \(\left\{\text{T.PartDec}(sk_{i},\hat{ct})\right\}_{i\in P\setminus\mathcal{C}}\) to the adversary \(\mathcal{A}\). These partial decryption results include the information used for verification: \(\left(com_{sk_{i}},com_{\epsilon_{i}^{sm}},\pi_{p_{i}}\right)\). 4. The corrupted parties controlled by the adversary \(\mathcal{A}\) compute the partial decryption results \(\left\{p_{j}\right\}_{j\in\mathcal{C}}\), according to the protocol, and send them. If any proof \(\pi_{p_{j}}\) in the partial decryption results \(\left\{p_{j}\right\}_{i\in\mathcal{C}}\) fails verification, \(\bot\) is output; otherwise, the plaintext result \(\mu\) is computed according to the threshold decryption protocol. 5. Finally, the adversary \(\mathcal{A}\) determines the value of the bit \(b\) through decryption queries and other information. Based to the previous IND-CPA security proof, the probability that \(\mathcal{A}\) can successfully distinguish \(b\) is no more than \(1/2\). \(\mathbf{Game_{1}}\): We introduce the first change, using the simulator \(Sim\) to generate proofs. In the third step of \(Game_{0}\), when honest users perform partial decryption, the proofs generated by the simulator are used to prove that these partial decryption results \(\left\{p_{i}\right\}_{i\in P\setminus\mathcal{C}}\) are correct, with the rest remaining unchanged. According to the honest verifier zero-knowledge property defined in Definition 18, the proofs generated by the simulator are computationally indistinguishable from those generated by an honest prover. Therefore, the experiments \(Game_{0}\) and \(Game_{1}\) are indistinguishable. \(\mathbf{Game_{2}}\): Furthermore, we replace the commitments that do not need to be opened during the threshold decryption process, such as \(com_{sk_{i}}\) and \(com_{\epsilon_{i}^{sm}}\). These commitments are only used for computing and verifying proofs, with the rest of the experiment remaining unchanged. According to the commitment hiding property defined in Definition 14, \(\mathcal{A}\) cannot obtain any information about the committed values from the commitments themselves. Therefore, the experiments \(Game_{1}\) and \(Game_{2}\) are indistinguishable. _Game\({}_{3}\)_: During the VDKeyGen protocol, we extract the secret key shares from the corrupted parties using a knowledge extractor, and then derive \(\left\{sk_{i}\right\}_{j\in\mathcal{C}}\) and simulate the behavior of these parts, with the rest of the experiment remaining unchanged. According to the knowledge soundness property defined in Definition 17, \(\mathcal{A}\) can accept the proofs generated using the witnesses provided by the knowledge extractor. Therefore, the experiments \(Game_{2}\) and \(Game_{3}\) are indistinguishable. _Game\({}_{4}\)_: Now, we replace the partial decryption results of each honest party during the threshold decryption process.