Additive vs Linear Secret Sharing

Question

I'm a beginner in the cryptography domain. Can anyone help me understand Additive Secret Sharing and Linear Secret Sharing? Are there any sources or references to understand their difference and how they work?

Answer 1

Based on your answer to my comment, additive secret sharing refers to the following scheme:

• $\mathsf{Share}(x):$ on input $x \in \mathcal{G}$, sample $x_1, \cdots, x_{n-1}$ uniformly at random from $\mathcal{G}$, and set $x_n \gets x -\sum_{i=1}^{n-1} x_i$.
• $\mathsf{Reconstruct}(x_1, \cdots, x_n):$ output $x \gets \sum_{i=1}^{n} x_i$.

Above, $\mathcal{G}$ is some group, and $n$ is the number of parties. This scheme is an $(n-1)$ out of $n$ secret sharing scheme (i.e. if $n-1$ parties reveal their shares, no information on $x$ is leaked, whereas $x$ can be reconstructed given all shares).

Linear secret sharing, on the other hand, refers to any secret sharing scheme which is linearly homomorphic. That is, fix any threshold secret sharing scheme $(\mathsf{Share}, \mathsf{Reconstruct})$, and let $k$ be its threshold (i.e the parameter such that, if $k$ or more parties combine their shares, they can reconstruct, but $k-1$ shares reveal no information). Then the scheme is said to be linear (over some group $\mathcal{G}$) if, given $(x_1, \cdots, x_n) \gets \mathsf{Share}(x)$ and $(y_1, \cdots, y_n) \gets \mathsf{Share}(y)$ (for any two inputs $x,y$), then $(x_1+y_1, \cdots, x_n+y_n)$ form valid shares of $x+y$, i.e. $\mathsf{Reconstruct}((x_i+y_i)_{i \in S}) = x+y$, where $S$ is any subset of $\{1, \cdots, n\}$ of size $|S| \geq t$.

From the above, it follows that the additive secret sharing scheme (over any group) is a special case of linear secret sharing with threshold $k=n$. Another common type of linear secret sharing (with an arbitrary threshold) is Shamir's construction using polynomial interpolation.