# Verifiable Threshold Multi-Party Fully Homomorphic Encryption from Share Resharing
## 2 Preliminaries
### Non-Interactive Zero-Knowledge Proof
_Sample_ \(\textbf{\rho}_{i}\overset{R}{\leftarrow}\{0,1\}^{k}\) _uniformly at random and construct the auxiliary commitment_ \(C_{\text{max},i}=\textbf{a}\textbf{Commit}(\textbf{t}_{i}\|c_{1}\|c_{2,i}\|c_{3, j}\|c_{4,i}\textbf{\rho}_{i})\)_._  
_For each \(i\in[1,N]\), compute \(\textbf{a}_{i}=H\big{(}\textbf{A},\textbf{v},\mathcal{M},\{C_{\text{max},i} \}_{i\in[1,N]}\big{)}\), and then compute \(\textbf{z}_{0,i}=\textbf{a}_{i}\cdot\textbf{u}+\textbf{r}_{i}\), \(\textbf{z}_{1,i}=\textbf{a}_{i}\cdot\textbf{s}_{1}+\textbf{s}_{2,i}\), and \(\textbf{z}_{2,i}=\textbf{a}_{i}\cdot\textbf{s}_{3,i}-\textbf{s}_{4,i}\), where \(\textbf{s}_{1},\textbf{s}_{2,i},\textbf{s}_{3,i}\), and \(\textbf{s}_{4,i}\) are the randomness used during the commitment procedures. Finally, output the proof \(\pi=\Big{(}c_{1},\{\textbf{a}_{i},\textbf{\rho}_{i},c_{3,i},\textbf{z}_{0,i}, \textbf{z}_{1,i},\textbf{z}_{2,i}\}_{i\in[1,N]}\Big{)}\)._  
* \(N.Verify\left(x,\pi,\mathit{crs}\right)\rightarrow\{0,1\}\) _: Given the element_ \(x\) _to be proven, the proof_ \(\pi\)_, and the_ \(\mathit{crs}\)_, for each_ \(i\in[1,N]\)_, perform the following checks:_ 1. \(A\) \(\cdot\textbf{z}_{0,i}=\textbf{a}_{i}\cdot\textbf{v}+\textbf{t}_{i}\)_;_ 2. \(d\) \(i[k]=\textbf{a}_{i}\cdot\textbf{z}_{0,i}[h]-\textbf{z}_{0,i}[i]\cdot\textbf{z}_{ 0,i}[j]\)_;_ 3. _c_\({}_{2,i}=\textbf{B}_{1}\cdot\textbf{z}_{1,i}+\left(0^{T}\|\textbf{z}_{0,i} \right)^{T}-\textbf{a}_{i}\cdot c_{1}\)_;_\(c_{4,i}=\alpha_{i}\cdot c_{3,i}-B_{2}\cdot z_{2,i}-\left(0^{T}\|{\mathbf{d}_{i}}^{T} \right)^{T}\);
5. \(C_{aux,j}=\mathsf{aCommit}({\mathbf{t}_{i}}\|c_{1}\|c_{2,j}\|c_{3,i}\|c_{4,i};{\mathbf{ \rho}_{i}})\). _If all the above checks pass and the norms of all vectors are within the prescribed bounds, then the proof \(\pi\) is valid and the verifier outputs 1; otherwise, it outputs 0._  
An NIZK system should satisfy the following properties, as defined:  
Definition 16 (Completeness): An NIZK protocol satisfies completeness if, for arbitrary \((x,w)\in R_{L}\), the verifier will accept the proof \(\pi\) generated by the prover using the N.Prove algorithm, where this probability exceeds the randomness in the NIZK algorithm, i.e. :  
\[Pr\left[N.Verify(x,\pi,crs)=1: \begin{array}{c}\text{crs}\gets N.Setup (params)\\ (x,w)\in\mathcal{R}_{L}\\ \pi\leftarrow N.Prove(x,w,crs)\end{array} \right]=1.\]  
Definition 17 (Knowledge Soundness): An NIZK protocol satisfies knowledge soundness if for any malicious prover \(P^{*}\) running N.Prove without knowing a witness \(w^{*}\), there is a sufficiently high probability that the honest verifier will accept the statement \(x\). In this case, an extractor exists that, through black-box access to \(P^{*}\), can extract a valid witness \(w^{*}\) such that \(\big{(}x,w^{*}\big{)}\in\mathcal{R}_{L}\), i.e. :  
\[Pr\left[\begin{array}{c}N.Verify(x,\pi^{*},crs)=1: \begin{array}{c}\text{ crs}\gets N.Setup(params)\\ \pi^{*}\gets N.Prove(x,w,crs)\\ w^{*}\leftarrow Extractor(x,\pi^{*},crs)\end{array} \right]\geq 1-negl(\lambda).\]  
Definition 18 (Honest Verifier Zero-Knowledge): An NIZK protocol satisfies the honest verifier zero-knowledge property if, for any PPT adversary \(\mathcal{A}\), a simulator algorithm Sim exists that can simulate and output a proof such that the transcript produced by the Sim given \(x\) is computationally indistinguishable from the transcript produced by the honest prover, i.e. :  
\[\left\{\begin{array}{c}\text{crs}\gets N.Setup(params)\\ (x,\pi,crs): \begin{array}{c}\text{crs}\leftarrow N.Setup(params)\\ (x,w)\leftarrow\mathcal{A}(crs)\\ \pi\leftarrow N.Prove(x,w,crs)\end{array} \right\}\overset{\subset}{\approx} \left\{ \begin{array}{c}\text{crs}\leftarrow N.Setup(params)\\ (x,w)\leftarrow\mathcal{A}(crs)\\ \pi^{*}\leftarrow Sim(x,crs)\end{array} \right\}.\]  
Our scheme relies on three main NP relations: \(\mathcal{R}_{DKG}\) for proving the correctness of the distributed key generation protocol, \(\mathcal{R}_{ENC}\) for the encryption algorithm, and \(\mathcal{R}_{TD}\) for the threshold decryption process.