## 3 Preliminaries
### Threshold Additive Secret Sharing
#### 4.2.1. \(n\)-Out-of-\(n\) Additive Secret Sharing  
We simply extend 2-out-of-2 additive secret sharing to \(n\)-out-of-\(n\) additive secret sharing: \(\mathbf{Share_{n-n}}:\) On input secret \(S\),  
* select \(s_{i}\in\mathbb{F}\) uniformly at random. * Set \(s_{n-1}=S-\sum_{i=0}^{n-2}s_{i}\). * Output \((s_{0},\ldots,s_{n-1})\). \(\mathbf{Reconstruct_{n-n}}:\) On input \((s_{0},\ldots,s_{n-1})\),
* Output \(S=\sum_{i=0}^{n-1}s_{i}\). **Theorem 1**. : _The scheme \((\mathbf{Share_{n-n}},\mathbf{Reconstruct_{n-n}})\) is a correct and secure additive secret sharing scheme._  
Proof. : Correctness follows immediately from \((\mathbf{Share_{n-n}},\mathbf{Reconstruct_{n-n}})\):  
\[\Pr_{\mathrm{Share(S)\to(s_{0},\ldots,s_{n-1})}}[\mathrm{Reconstruct(s_{0}, \ldots,s_{n-1})}=\mathrm{S}]=\Pr_{\mathrm{Share(S)\to(s_{0},\ldots,s_{n-1})}}[ s_{0}+\cdots+s_{n-1}=\mathrm{S}]=1\]  
Security follows immediately from \((\mathrm{Share_{n-n}},\mathrm{Reconstruct_{n-n}})\): let any \(S,S^{\prime}\in\mathbb{F}\), and consider one share. If it is the first share, and it is selected uniformly that \(\forall\alpha\in\mathbb{F}\),  
\[\Pr_{\mathrm{Share(S)\to(s_{0},\ldots,s_{n-1})}}[s_{0}=\alpha]=\frac{1}{| \mathbb{F}|}=\Pr_{\mathrm{Share(S^{\prime})\to(s^{\prime}_{0},\ldots,s^{ \prime}_{n-1})}}[s^{\prime}_{0}=\alpha].\]  
If it is the last share, and it is selected uniformly that \(\forall\alpha\in\mathbb{F}\),  
\[\Pr_{\mathrm{Share(S)\to(s_{0},\ldots,s_{n-1})}}[s_{n-1}=\alpha] =\Pr_{\mathrm{Share(S)\to(s_{0},\ldots,s_{n-1})}}[S-(s_{0}+s_{1}+ \cdots+s_{n-2})=\alpha]=\] \[\Pr_{\mathrm{Share(S)\to(s_{0},\ldots,s_{n-1})}}[(s_{0}+s_{1}+ \cdots+s_{n-2})=S-\alpha]=\frac{1}{|\mathbb{F}|}\]  
Similarly,  
\[\Pr_{\mathrm{Share(S^{\prime})\to(s^{\prime}_{0},\ldots,s^{\prime}_{n-1})}}[s ^{\prime}_{n-1}=\alpha]=\Pr_{\mathrm{Share(S^{\prime})\to(s^{\prime}_{0}, \ldots,s_{n-1})}}[(s^{\prime}_{0}+s^{\prime}_{1}+\cdots+s^{\prime}_{n-2})=S^{ \prime}-\alpha]=\frac{1}{|\mathbb{F}|}\]  
and both probabilities are equal, then \((\mathbf{Share_{n-n}},\mathbf{Reconstruct_{n-n}})\) is a secure scheme. 2.2. Build \(t\)-out-of-\(n\) Additive Secret Sharing from \(t\)-out-of-\(t\) Additive Secret Sharing  
\(t\)-out-of-\(n\) secret sharing was proposed by [PERSON] [26]. While it is a correct and secure scheme, it does not have additive characteristics. Therefore, we use the concept from [25]to extend the additive secret sharing scheme of 2-out-of-\(n\) from 2-out-of-2 to \(t\)-out-of-\(n\) via \(t\)-out-of-\(t\). Here, we use \(q\) to represent \(\log_{t}(n-1)\),  
\(\mathbf{Share_{t-n}:Oninput\) secret \(S\),  
* Execute \(\mathbf{Share_{t-t}(S)}\rightarrow(s_{i0,\ldots,s_{i,t-1}})\). * Set \(G_{j}=(s_{0,j_{0}},s_{1,j_{1}},\ldots,s_{q,j_{q}})\), where \(t\)-base representation of \(j\) is \(j_{0}\ldots j_{q}\). * Output \((G_{0},\ldots,G_{n-1})\). \(\mathbf{Reconstruct_{t-n}:Oninput\)\(t\)\(G\)s selected from \((G_{0},\ldots,G_{n-1})\),  
* Convert the index \(i\) of the selected \(t\)\(G\)s into \(t\)-base representation. For example, if \(G_{1}\) is selected, then \(i=1\) and \(i\to 1_{0}\ldots 1_{q}\). * Find a digit position \(k\) where the \(k\)-th digit of the \(t\)-base representation of the indices of the \(t\) selected \(G\)s is different for each index, and use \(k\) to find corresponding \(s_{k,i_{k}}\). For example, if \(G_{1}\) is selected, then \(i=1\), \(s_{k,1_{k}}\) is the share we need. Finally, we obtain \(t\) shares from \(t\) selected \(G\)s, and they can conveniently form \((s_{k,0},\ldots,s_{k,t-1})\). * Execute \(\mathbf{Reconstruct_{t-t}(s_{k,0},\ldots,s_{k,t-1})}\) and output \(S\), where \(S=s_{k,0}+\cdots+s_{k,t-1}\). If \((\mathbf{Share_{t-t},Reconstruct_{t-t}})\) is a correct and secure \(n\)-out-of-\(n\) additive secret sharing scheme, then the scheme \((\mathbf{Share_{t-n},Reconstruct_{t-n}})\) is a correct and secure \(t\)-out-of-\(n\) additive secret sharing scheme. Proof.