# Verifiable Threshold Multi-Party Fully Homomorphic Encryption from Share Resharing
## 2 Preliminaries  
This section first defines the notation and preliminaries for the construction modules used in our scheme. Sections 3 and 4 then demonstrate how these components are integrated into the overall scheme. **Notation. ** In this work, we use bold lowercase letters to denote vectors (e.g., \(\mathbf{s}\)), and bold uppercase letters to denote matrices (e.g., \(\mathbf{A}\)). For two vectors \(\mathbf{a}\) and \(\mathbf{b}\) of the same dimension, we use \(\langle\mathbf{a},\mathbf{b}\rangle\) to denote their inner product. Let \(\lambda\) denote the security parameter, with other parameters depending on \(\lambda\), such as \(n=n(\lambda)\). If the parameter \(B(\lambda)\) is asymptotically bounded by the inverse of a polynomial in \(\lambda\), i.e., \(B(\lambda)=1/poly(\lambda)\), we say that the parameter \(B\) is negligible, denoted as \(negl(\lambda)\). For a prime power \(q\in\mathbb{N}\), we define integers in the range \((-q/2\), \(q/2)\) as elements in the finite field \(\mathbb{Z}_{q}\). For any set \(S\)we let \(|S|\) denote the cardinality of \(S\), and for any element \(a\in\mathbb{Z}_{q}\), \(|a|\) denotes the absolute value of \(a\). We use \(\left\|x\right\|_{\infty}\) to denote the infinity norm of a vector, which is the maximum absolute value of its elements, and a similar definition applies to the infinity norm of a matrix. For any \(k\in\mathbb{N}\), we use \([k]\) to denote the set \(\{1,2,\ldots,k\}\). We use \(x\stackrel{{ R}}{{\leftarrow}}\mathcal{D}\) to denote that \(x\) is randomly and uniformly sampled from the probability distribution \(\mathcal{D}\), and \(C\stackrel{{ R}}{{\leftarrow}}S\) to denote that \(C\) is randomly and uniformly sampled from the set \(S\). For two distributions \(\mathcal{D}_{0}\) and \(\mathcal{D}_{1}\), we denote that they are statistically indistinguishable and computationally indistinguishable by \(D_{0}\stackrel{{ S}}{{\approx}}D_{1}\) and \(D_{0}\stackrel{{ C}}{{\approx}}D_{1}\), respectively. Definition 1 (B-bounded Distribution): If an ensemble of distributions \(\left\{\chi_{n}\right\}_{n\in\mathbb{N}}\) on integers is called B-bounded distribution for an integer bound \(B=B(\lambda)\), it satisfies the following condition:  
\[Pr_{e^{\frac{R}{k}}\chi_{n}}[|e|>B(\lambda)]=negl(\lambda).\]  
The technique of \"smudging out\", proposed by [PERSON] et al. [8], seeks to render ciphertext noise unusable by overwhelming it with newly sampled noise from a distribution with larger variance. We depend on the following lemma, which describes introducing large noise to \"smudge out\" or conceal the small noise. Lemma 1 ([8]): _Let \(B_{1}=B_{1}(\lambda)\) and \(B_{2}=B_{2}(\lambda)\) be positive integers, with \(e_{1}\in[-B_{1},\ B_{1}]\) being a fixed integer. Let the integer \(e_{2}\stackrel{{ R}}{{\leftarrow}}[-B_{2},\ B_{2}]\) be uniformly randomly sampled. Then, provided that \(B_{1}/B_{2}=negl(\lambda)\), the distribution of \(e_{2}\) is statistically indistinguishable from the distribution of \(e_{2}+e_{1}\), i.e., \(e_{2}\stackrel{{ S}}{{\approx}}(e_{2}+e_{1})\)._  
For the short preimage matrix \(\mathbf{G}\), proposed by [PERSON] and [PERSON] [36], multiplying by \(\mathbf{G}\) can be viewed as executing the BitDecomp\({}^{-1}\) function in the GSW scheme, while the function \(\mathbf{G}^{-1}(\cdot)\) corresponds to the BitDecomp function. The low-level details of this implementation can be omitted (see [7; 9] for more details). Note that \(\mathbf{G}^{-1}(\cdot)\) is not a matrix, but an efficiently computable function.