# Verifiable Threshold Multi-Party Fully Homomorphic Encryption from Share Resharing
## 3 Module Construction
### Share Resharing  
In this scheme, we employ an \"ideal secret key\" generation process, where each party independently samples its own ideal secret key share \(\mathbf{s}_{i}\stackrel{{ R}}{{\leftarrow}}\mathbb{Z}_{q}^{n-1}\). The decryption key shares are generated in the subsequent distributed key generation protocol, which introduces the necessity of the secure channels between parties. We note that the ideal secret key satisfies the property \(\mathbf{s}=\sum_{i=1}^{N}\mathbf{s}_{i}\), meaning that complete knowledge of \(sk=\mathbf{s}\) is required for the final ciphertext decryption. This restricts the scheme to an N-out-of-N access structure, preventing support for arbitrary threshold settings. To address this limitation, we propose share resharing to support a t-out-of-N threshold access structure. We mitigate the rapid growth of smudging noise in partial decryption by applying share resharing techniques in the TMFHE scheme. This approach avoids the method used by [PERSON] et al. [19], which scales to eliminate denominators by considering Lagrange coefficients as rational numbers, thereby violating compactness requirements where the size of ciphertext is no longer a polynomial in the number of parties \(N\), but rather a polynomial of \(N^{2}\). In the share resharing process, each party interactively runs the protocol to achieve the ideal secret key additive sharing for the TMFHE scheme. This allows any subset of at least \(t\) parties to reconstruct the secret during decryption--even if they differ from those in the key generation phase--while requiring each party to maintain a constant-size state. Share resharing techniques leverage ideal secret keys and the linearity of resharing schemes to achieve more compact and communication-efficient schemes. Additionally, share resharing techniques allow for generating keys based on the set of parties currently online or flexibly updating keys for new computations. Specifically, let the set of parties be \(P=\{P_{1},\ldots,P_{N}\}\), and let \(\mathbb{A}_{t}\) be a threshold access structure on \(P\), with \(\mathcal{K}=\mathbb{Z}_{q}\) as the secret sharing space. As mentioned in Definition 6 of Section 2.2, each party \(P_{i}\) uniformly samples a Shamir public point \(x_{i}\) and distributes the secret shares of a polynomial of degree \((t-1)\), \(P(x_{i})\), to party \(P_{i}\) through the S.Share algorithm. The Lagrange coefficient for the secret reconstruction computation is \(\lambda_{i}=\prod_{j=1,j\
eq i}^{t}\frac{x_{j}}{x_{j}-x_{i}}\). **Definition 23** (Share Resharing). : _Share resharing is the process where each party redistributes their own secret key share \(sk_{i}\) through a t-out-of-N Shamir secret sharing scheme among themselves. This enables the secret key to be reconstructed in the threshold decryption phase through simple linear addition, thereby avoiding the rapid growth of smudging noise \(e_{i}^{sm}\) when multiplied by the Lagrange coefficient \(\lambda_{i}\). The process for each party to run the share resharing protocol is as follows:_  
* \(RS.Reshare\left(sk_{i},\mathbb{A}_{t},x_{1},\ldots,x_{N}\right)\rightarrow\left( sk_{i,1},\ldots,sk_{i,j}\right)\) _: Given the shared secret key share_ \(sk_{i}\)_, the threshold access structure_ \(\mathbb{A}_{t}\)_, and the public point sequence_ \((x_{1},\ldots,x_{N})\) _of all parties, each party_ \(P_{i}\) _uniformly samples_ \(t-1\) _elements_ \((c_{1},\ldots,c_{t-1})\stackrel{{ R}}{{\leftarrow}}\mathbb{Z}_{q}^{*}\)_.