# Verifiable Threshold Multi-Party Fully Homomorphic Encryption from Share Resharing
## 2 Preliminaries
### Non-Interactive Zero-Knowledge Proof  
A zero-knowledge (ZK) proof system allows a prover to convince a verifier of the truth of a certain statement without disclosing any knowledge of privacy. In this work, we adopt the standard definition of non-interactive zero-knowledge (NIZK) proofs [39] to ensure the verifiability of key components. This ensures that, even in the presence of malicious adversaries, the involved parties follow the protocol correctly, the data satisfy structural and bounded constraints, and no secrets or randomness are leaked. An NIZK proof can be derived from an interactive ZK proof system using the Fiat-Shamir transform [18], which allows messages as inputs and enables non-interactive proof generation under a common reference string, thereby improving efficiency. We adopt a non-interactive variant of the zero-knowledge proof by [PERSON] et al. [30], which supports the verification of witnesses with complex constraints in the random oracle model (ROM). In this construction, the prover commits to the witness and auxiliary vectors, hashes an initial transcript to generate a challenge, and computes response values as linear combinations. The final proof consists of the responses along with the auxiliary commitments. The verifier checks the witness's validity with respect to the relation by verifying linear and multiplicative constraints, and ensuring commitment consistency and norm bounds. This construction supports vector arithmetic verification with polynomial complexity. We now provide the definition of the non-interactive zero-knowledge proof required in this work:  
**Definition 15** (Nizk): _Consider \(\mathcal{R}_{L}\) to be an NP relation on the language \(L\), with \(x\) being an element of \(L\). A witness \(w\) exists such that \(\mathcal{R}_{L}=\{(x,w)\}\) forms the statement-witness set for the NP relation. NIZK = (N.Setup, N.Prove, N.Verify) is a tuple of polynomial-time algorithms, defined as follows:_  
* \(N.Setup\left(params\right)\rightarrow\mathit{crs}\) _: Given the public parameters params, output the common reference string \(\mathit{crs}\), which includes the public matrices_ \(\textbf{B}_{1}\in\mathbb{Z}_{q}^{(l_{1}+n)\times(l_{1}+n+l_{2})},\textbf{B}_{ 2}\in\mathbb{Z}_{q}^{(l_{1}+\
)\times(l_{1}+\
+l_{2})}\) _, and_ \(\textbf{A}\in\mathbb{Z}_{q}^{m\times n}\)_, two auxiliary vectors_ \(\textbf{u}\in\mathbb{Z}_{q}^{n}\) _and_ \(\textbf{v}\in\mathbb{Z}_{q}^{m}\)_, and a set_ \(\mathcal{M}\) _consisting of_ \(\updownarrow\) _triplets of the form_ \((h,i,j)\)_. These elements satisfy the following conditions:_ \(\textbf{A}\cdot\textbf{u}=\textbf{v}\)_, and for all_ \((h,i,j)\in M\)_, it holds that_ \(\textbf{u}[h]=\textbf{u}[i]\cdot\textbf{u}[j]\)_._
* \(N.Prove\left(x,w,\mathit{crs}\right)\rightarrow\pi\) _: Given_ \((x,w)\in\mathcal{R}_{L}\) _and the_ \(\mathit{crs}\)_, the prover commits to the witness_ \(w\) _using the commitment scheme to obtain_ \(c_{1}=\textbf{B}_{1}\cdot\textbf{s}_{1}+\left(0^{T}\|w^{T}\right)^{T}\)_. The following steps are then repeated for_ \(N\) _rounds with fixed parameters:_ 1. _Generate a random vector_ \(\textbf{r}_{i}\) _and compute_ \(\textbf{t}_{i}=\textbf{A}\cdot\textbf{r}_{i}\)_; Construct the intermediate multiplication vectors_ \(\textbf{a}_{i}[k]=\textbf{r}_{i}[h]-\textbf{r}_{i}[i]\cdot\textbf{u}[j]- \textbf{r}_{i}[i]\cdot\textbf{u}[i]\) _and_ \(\textbf{b}_{i}[k]=\textbf{r}_{i}[i]\cdot\textbf{r}_{i}[j]\)_;_ 2. _Use the public matrix_ \(\textbf{B}_{2}\) _to generate commitments_ \(c_{2,j},c_{3,j}\)_, and_ \(\textbf{c}_{4,i}\) _for_ \(\textbf{r}_{i},\textbf{a}_{i}\)_, and_ \(\textbf{b}_{i}\)_, respectively;_ 3.