4
$\begingroup$

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?

$\endgroup$
2
  • 3
    $\begingroup$ Can you point to where you read about them? To me, they are two different names for the same thing. $\endgroup$ Oct 3, 2022 at 14:35
  • $\begingroup$ @GeoffroyCouteau it is mentioned that to reconstruct the secret in additive secret sharing we need all the shares of the n participants however in linear secret sharing we can reconstruct the secret by combining only k shares from n participants ( k < n) $\endgroup$ Oct 4, 2022 at 6:06

1 Answer 1

5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.