## 2 Background and Related Work
### Secret Sharing  
Secret sharing is a technique that first splits one secret into multiple shares and distributes them. Typically, there is one dealer and \(n\) players from a collection \(\Delta\) in secret sharing, and the dealer distributes the secret to each player. The secret can be reconstructed only when \(k\) (for threshold) or more shares are provided by the players in the collection \(\Delta\). Such a cryptographic system is called a \((k,n)-\)threshold secret sharing system [11]. A secret sharing scheme is practical for storing and distributing confidential and sensitive information, such as the private key of a Certificate Authority. Secret sharing schemes are also effective in a distributed network system, but the split pieces make it harder for the eavesdropper to gain valuable information. The implementation of secret sharing was proposed by [PERSON] and [PERSON] independently in 1979.  
In the implementation made by [PERSON] [12], the scheme Shamir Secret Sharing (SSS) was described as follows: the secret is some data \(D\) that are divided into \(n\) pieces \(D_{1},...,D_{n}\) in such a way that:  
1. knowledge of any \(k\) or more \(D_{i}\) pieces makes \(D\) easily computable;
2. knowledge of any \(k-1\) or fewer \(D_{i}\) pieces leaves \(D\) completely undetermined.  
By using the \((k,n)-\) threshold secret sharing, the original secret can be reconstructed if no more than \(\lfloor n/2\rfloor=k-1\) of the \(n\) pieces are destroyed. The key idea of SSS is based on the Lagrange interpolation theorem that \(k\) points are enough to uniquely identify a polynomial of degree less than or equal to \(k-1\).  
**Theorem 1** (Lagrange interpolation).: _Let \(\mathcal{F}\) be a finite field. Then \(k\) pairs \((x_{i},y_{i})\) uniquely determine a polynomial \(f(x)\) of degree \(\leq k-1\), such that \(f(x_{i})=y_{i}\). We assume that \(k-1<|\mathcal{F}|\) so that all \(x_{i}\)'s can be distinct. \(f(x)\) is determined by:_  
\[f(x)=\sum_{i=1}^{k}y_{i}\prod_{\begin{subarray}{c}1\leq j<k\\ i\
eq j\end{subarray}}\frac{x-x_{j}}{x_{i}-x_{j}} \tag{1}\]  
To share the secret \(D\) as \(D\implies(D_{1},...,D_{n})\), the distribution of the secret is conducted by the following steps:  
1. Choose a large prime number \(p\) and let \(\mathcal{F}=\mathcal{Z}/p\mathcal{Z}\).
2. Choose coefficients \(f_{1},...,f_{k-1}\in\mathcal{F}\), which are to be the coefficients of degree \(k-1\) polynomial \(f\).
3. Let \(f(z)=f_{0}+f_{1}z+...+f_{k-1}z^{k-1}\), where \(f_{0}=D\).
4. Evaluate the value of each \(f(i)\) and distribute them to player \(i\), \(i=1...n\).  
The reconstruction of SSS is also based on the Lagrange interpolation theorem described in Theorem 1. If there are \(k\) players and each player has the corresponding \(f(i)\), then we have \(k\) points on the curve of a polynomial whose degree is less than \((\text{k}-1)\), and we can evaluate unique coefficients to a polynomial whose degree is \((\text{k}-1)\). The secret \(D\) is the coefficient \(f_{0}\) in the polynomial. With the following equation, given any \(k\) pieces of share, we can obtain \(f_{0}\) using interpolation:  
\[f(x)=\sum_{i=1}^{k}y_{i}\prod_{\begin{subarray}{c}1\leq j<k\\ i\
eq j\end{subarray}}\frac{x-x_{j}}{x_{i}-x_{j}}\qquad\Rightarrow\qquad f(0 )=\sum_{i=1}^{k}y_{i}\prod_{\begin{subarray}{c}1\leq j<k\\ i\
eq j\end{subarray}}\frac{x_{j}}{x_{j}-x_{i}} \tag{2}\]