# Efficient SMC Protocol Based on Multi-Bit Fully Homomorphic Encryption
## 2 Preliminaries
### Definitions and Theorems  
**Definition 1**.: ([19]) _(Learning With Errors, LWE) For the vector \(s\in\mathbb{Z}_{q}^{n}\), the LWE distribution \(A_{s,\chi}\) on \(\mathbb{Z}_{q}^{n}\times\mathbb{Z}_{q}\) refers to uniformly selecting \(a\in\mathbb{Z}_{q}^{n}\) at random, selecting the error \(e\leftarrow\chi\), and outputting \((\mathbf{a},\mathbf{b}=\mathbf{a}\cdot\mathbf{s}+e\bmod\!q)\)._  
**Definition 2**.: (_Search.LWE\({}_{m,n,q,\chi}\)) For vectors \(\in\mathbb{Z}_{q}^{n}\), \(s\) is recovered from the given \(m\) independent samples \((\mathbf{a}_{i},\mathbf{b}_{i})\in\mathbb{Z}_{q}^{n}\times\mathbb{Z}_{q}\) selected from the distribution of \(A_{s,\chi}\)._  
**Definition 3**.: (_Decision.LWE\({}_{m,n,q,\chi}\)) For vector \(s\in\mathbb{Z}_{q}^{n}\), the attacker is required to distinguish two sets of random variables containing \(m\) independent samples with non-negligible advantage. The two sets of variables are taken from the uniform distributions on distributions \(A_{s,\chi}\) and \(\mathbb{Z}_{q}^{n}\times\mathbb{Z}_{q}\), respectively._  
**Definition 4**.: (_Some-are-errorless LWE_) _for \(q\geq 1\), \(n>0\), the error distribution on \(R\) is \(\chi^{\prime}\), \(T_{q}=\left\{0,\frac{1}{q},\cdots,\frac{q-1}{q}\right\}\), where \(q\in Z\). The distribution \(A^{\prime}_{s,\chi}\) on \(T_{q}^{n}\times T_{q}\) refers to uniformly selecting \(\mathbf{a}\in T_{q}^{n}\), selecting the error \(e\leftarrow\chi^{\prime}\), and outputting \((\mathbf{a},\mathbf{b}=\mathbf{a}\cdot\mathbf{s}+e)\). Some-are-errorless LWE distinguishes the following two situations._  
1. _Select all samples uniformly from_ \(T_{q}^{n}\times T_{q}\)_._
2. _For the vector_ \(s\in T_{q}^{n}\)_, the previous sample is selected from_ \(A^{\prime}_{s,0}\)_. All the remaining samples are selected from_ \(A^{\prime}_{s,\chi}\)_. In other words, the previous sample is_ \((\mathbf{a}_{i},\mathbf{b}=\mathbf{a}_{i}\cdot\mathbf{s})\)_, and no error_ \(e\) _is introduced. The remaining samples are_ \((\mathbf{a}_{i},\mathbf{b}=\mathbf{a}_{i}\cdot\mathbf{s}+e_{i})\)_,_ \(i>l\)_, and each sample introduces a small error_ \(e_{i}\)_._  
**Definition 5**.: _Secure multi-party computation. The general formal definition of an SMC agreement [9] can be described as follows. It is assumed that there are \(N\) participants \(\{P_{1},P_{2},\cdots,P_{N}\}\), and \(\mathbf{x}_{i}(i\in[N])\) is the private data owned by each participant \(P\). In addition, all participants jointly calculate a certain effective function \(y=f(x_{1},x_{2},\cdots,x_{N})\). After the calculation, each \(P_{i}\) can obtain \(y\) but cannot obtain the private data of other participants._  
**Theorem 1**.: _If \(\alpha_{i}(i\in[N])\) is a series of independent random variables that obey a bounded distribution of \(B_{\chi}\), then the random variable \(\alpha=\frac{1}{N}\sum\limits_{i=1}^{N}\alpha_{i}\) also obeys the bounded distribution of \(B_{\chi}\)._  
Proof.: Suppose \(E(\alpha_{i})=\frac{B_{\chi}}{poly(\sigma)}\), according to Markov inequality,  
\[\Pr\{|\mathbf{a}|>B_{\chi}\}\leq\frac{E(|\mathbf{a}|)}{B_{\chi}}=\frac{1}{N\cdot B_{ \chi}}E\left(\sum\limits_{i=1}^{N}\alpha_{i}\right)\]  
\(=\frac{1}{\operatorname{poly}(\sigma)}\). So, the conclusion holds.  
End. \(\square\)