# Verifiable Threshold Multi-Party Fully Homomorphic Encryption from Share Resharing
## 2 Preliminaries
### Fully Homomorphic Encryption  
Our scheme is built upon FHE schemes based on the standard LWE problem, such as the GSW scheme [4]. FHE enables computation directly on encrypted data, without the need for decryption. **Definition 7** (FHE Scheme). : _FHE = (F.Setup, F.SecKeyGen, F.PubKeyGen, F.Enc, F.Eval, F.Dec) is a tuple of PPT algorithms, defined as follows:_  
* _F.Setup_ \(\left(1^{\lambda},1^{l}\right)\to\text{params}\)_: Given a security parameter_ \(\lambda\) _and a circuit depth bound_ \(l\)_, compute the lattice dimension_ \(n=n(\lambda,l)\)_, the modulus_ \(q=q(\lambda,l)\)_, and the error distribution_ \(\chi_{B}=\chi_{B}(\lambda,l)\) _as a B-bounded distribution, where the bound is_ \(B=B(\lambda,l)\)_. Let_ \(m=m(\lambda,l)=O(\text{nlogq})\)_, and_ \(\updownarrow=\left\lfloor\text{logq}\right\rfloor+1\)_. Output_ \(\text{params}=(n\)_,_ \(q\)_,_ \(\chi\)_,_ \(m,\updownarrow)\)_; use the params as implicit input for other algorithms._
* _F.SecKeyGen_ \((\text{params})\to sk\)_: Given the params, uniformly sample_ \(\mathbf{t}\stackrel{{ R}}{{\leftarrow}}\mathbb{Z}_{q}^{n-1}\)_, and output the secret key_ \(sk=\mathbf{v}=\left( \begin{matrix}1\\ -\mathbf{t}\end{matrix} \right)\)_, where_ \(\mathbf{v}\in\mathbb{Z}_{q}^{n}\)_._
* _F.PubKeyGen_ \((sk)\to pk\)_: Given the secret key_ \(sk\)_, uniformly sample the matrix_ \(\mathbf{B}\stackrel{{ R}}{{\leftarrow}}\mathbb{Z}_{q}^{m\times(n-1)}\) _and the error vector_ \(\mathbf{e}\stackrel{{ R}}{{\leftarrow}}\mathbb{Z}_{B}^{m}\)_. Let_ \(\mathbf{b}=\mathbf{B}\cdot\mathbf{t}+\mathbf{e}\)_. Output the public key_ \(pk=\mathbf{A}=(\mathbf{b}\)_,_ \(\mathbf{B}\)_), where_ \(\mathbf{A}\in\mathbb{Z}_{q}^{m\times n}\)_._* \(F.Enc\left(pk,\;\mu\right)\to ctx:\) _Given the public key pk and the message \(\mu\in\left\{0,\;1\right\},\) uniformly sample a random matrix \(\mathbf{R}\in\left\{0,\;1\right\}^{m\times m}.\) Output the ciphertext \(ctx=\mathbf{R}\mathbf{A}+\mu\mathbf{G}\) corresponding to the message \(\mu\), where \(ctx\in\mathbb{Z}_{q}^{m\times m}\) and \(\mathbf{G}\in\mathbb{Z}_{q}^{m\times m}\) is the short preimage matrix (Lemma 2)._
* \(F.Eval\left(\;F,\;ctx_{1},\ldots,ctx_{k}\right)\to c\bar{c}x:\) _Given a circuit_ \(F:\left\{0,\;1\right\}^{k}\to\left\{0,\;1\right\}\) _with a depth bound_ \(l\) _and a set of ciphertexts \(ctx_{  
intermediate states in multi-party encryption and zero-knowledge protocols. Moreover, this commitment scheme supports a \"relaxed opening\" strategy, which permits the use of a non-zero polynomial coefficient \(f\) to scale both the commitment and the message simultaneously during validity verification, thus enhancing compatibility with subsequent NIZK proofs. Definition 11 (Commitment Scheme): Let \(l_{1}\) and \(l_{2}\) be positive integers that are polynomial in the security parameter \(\lambda\). Let \(\sigma\) be a small positive integer, such that \(\sigma\geq\sqrt{2l_{2}/\pi}\). The public parameters of the commitment scheme include a matrix \(\textbf{B}\in\mathbb{Z}_{q}^{l_{1}+n\times(l_{1}+n+l_{2})}\), structured as \(\textbf{B}= \begin{pmatrix}\textbf{I}_{l_{1}}&\textbf{B}_{1}\\ 0^{n\times l_{1}}&\textbf{I}_{n}&\textbf{B}_{2}\end{pmatrix} \), where \(\textbf{I}_{l_{1}}\) and \(\textbf{I}_{n}\) are identity matrices, and \(\textbf{B}_{1}\) and \(\textbf{B}_{2}\) are random matrices sampled from \(\mathbb{Z}_{q}^{l_{1}\times(n+l_{2})}\) and \(\mathbb{Z}_{q}^{n\times l_{2}}\), respectively. Let the above public parameters (denoted as params) be provided as implicit input. The message space is defined over a set \(S_{\textbf{x}}\subseteq\mathbb{Z}_{q}^{n}\), and the randomness \(r\) is drawn from a set \(S_{\textbf{r}}\subseteq\mathbb{Z}_{q}^{l_{1}+n+l_{2}}\) according to the distribution \(\mathcal{D}_{\sigma}^{l_{1}+n+l_{2}}\).