# Verifiable Threshold Multi-Party Fully Homomorphic Encryption from Share Resharing
## 2 Preliminaries
### Shamir Secret Sharing  
In this section, we will introduce the standard definitions of the threshold access structures and the Shamir secret sharing used in this work. **Definition 3** (Threshold Access Structure). : _Let the set of parties be \(P=\{P_{1},\ldots,P_{N}\}\). A threshold access structure (TAS), denoted as \(\mathbb{A}_{t}\), is defined such that for any subset of parties \(S\subseteq P\), \(S\in\mathbb{A}_{t}\) if and only if \(|S|\geq t\). Furthermore, let \(S\subseteq P\) be a subset of the party set \(P\). If \(S\
otin\mathbb{A}_{t}\), but for any party \(P_{i}\in P\setminus S\), it holds that \(S\cup\{P_{i}\}\in\mathbb{A}_{t}\), then \(S\) is called a maximal invalid set. We categorize the TAS as the collection of access structures \(\mathbb{A}_{t}\) for all \(t\in\mathbb{N}\)._  
Next, we review the [PERSON] secret sharing scheme [37], which uses polynomial interpolation over a finite field to implement a t-out-of-N threshold access structure. In [PERSON]'s scheme, a secret \(s\in\mathbb{Z}_{q}\) from the secret space \(\mathcal{K}\) is divided into \(n\) shares, ensuring that at least \(t\) shares are needed to reconstruct the secret \(s\). For simplicity, we consider reconstructing the secret using the first \(t\) shares. **Definition 4** (Shamir Secret Sharing Scheme). : _Let the set of parties be \(P=\{P_{1},\ldots,P_{N}\}\), and let \(\mathbb{A}_{t}\) represent a class of threshold access structures on \(P\). A secret space \(\mathcal{K}=\mathbb{Z}_{q}\) exists. Then, Shamir secret sharing is a PPT algorithm Shamir = (S.Setup, S.Share, S.Combine), defined as follows:_  
* _S.Setup: Determine the threshold access structure_ \(\mathbb{A}_{t}\) _for the set of parties_ \(P\)_, and ensure the parties concur on a field_ \(\mathbb{Z}_{q}^{*}\)_. Each party_ \(P_{i}\in P\) _is associated with an element_ \(x_{i}\in\mathbb{Z}_{q}^{*}\)_, which is a non-zero value, and if_ \(i\
eq j\)_, then_ \(x_{i}\
eq x_{j}\)_. This sequence of public points_ \((x_{1},\ldots,x_{N})\) _is referred to as the Shamir public points._
* _S.Share_ \((s,\mathbb{A}_{t},x_{1},\ldots,x_{N})\rightarrow(s_{1},\ldots,s_{N})\)_: To share a secret_ \(s\in\mathbb{Z}_{q}\) _among_ \(N\) _parties and ensure that at least_ \(t\) _shares are required to recover the secret, the algorithm uniformly samples_ \(t-1\) _elements_ \((c_{1},\ldots,c_{t-1})\xleftarrow{R}\mathbb{Z}_{q}^{*}\)_. It then defines a polynomial of degree_ \((t-1)\)_:_ \(P(X)=s+c_{1}X+c_{2}X^{2}+\ldots+c_{t-1}X^{t-1}=s+\sum_{k=1}^{t-1}c_{k}X^{k}\in \mathbb{Z}_{q}[X]\)_. Thus,_ \(P(0)=s\)_. The value_ \(P(x_{i})=s_{i}\) _is then sent to party_ \(P_{i}\)* _S.Combine_\((s_{1},\ldots,s_{t},x_{1},\ldots,x_{t})\to s\) _: Any subset of shares from at least_ \(t\) _parties can reconstruct the secret_ \(s\) _, while no subset of fewer than_ \(t\) _parties can learn any information about the secret_ \(s\) _. The secret_ \(s\) _can be computed as_ \(s=\sum_{i=1}^{t}s_{i}\prod_{j=1,j\
eq i}^{t}\frac{x_{j}}{x_{j}-x_{i}}=\sum_{i=1 }^{t}s_{i}\lambda_{i}\) _, where_ \(\lambda_{i}=\prod_{j=1,j\
eq i}^{t}\frac{x_{j}}{x_{j}-x_{i}}\)_are the Lagrange coefficients._  
For a prime q, the Shamir secret sharing scheme satisfies the following properties of correctness and privacy:  
**Definition 5** (Correctness). : _For any valid subset of parties \(S\in\mathbb{A}_{t}\), and any secret \(s\in\mathcal{K}\), the Shamir secret sharing scheme can correctly recover the secret \(s\):_  
\[\Pr_{S\in\mathbb{A}_{t}}\Bigg{\{} \begin{matrix}s\leftarrow\\ S.\text{Combine}\big{(}\left\{s_{i}\right\}_{i\in S},\left\{x_{i}\right\}_{i \in S}\big{)}\bigg{|}_{S.\text{Share}}(s_{1},\ldots,s_{N})\leftarrow\\ \end{matrix} \]  
**Definition 6** (Privacy). : _For any subset of parties \(S\
otin\mathbb{A}_{t}\) and secret \(s_{b}\in\mathcal{K}\), where \(b\in\{0,1\}\), if \((s_{b,1},\ldots,s_{b,N})\gets S.\text{Share}(s_{b},\mathbb{A}_{t},x_{1}, \ldots,x_{N})\), then the two distributions \(\left\{s_{0,i}\right\}_{i\in S}\) and \(\left\{s_{1,i}\right\}_{i\in S}\) are indistinguishable, i.e.