5
$\begingroup$

This question already has an answer here:

Shamir's Secret Sharing works by sharing data points on a curve, whereby when you have the required number of data points, you can find the function of the curve and find out the secret, which is effectively f(0).

In the polynomial form of the function, the constant (the coefficient of $x^0$) is the secret information.

Could you treat the coefficients of the other powers of $x$ as secret values as well?

If so, are they just as secure / secret? Or is there some subtlety going on where you need fewer values to get the other coefficients?

It seems that if you had a cubic curve that you could have 4 secrets $S_i$, instead of 3 random numbers and one secret:

$$f(x) = S_1x^3 + S_2x^2+S_3x+S_4$$

$\endgroup$

marked as duplicate by yyyyyyy, e-sushi Apr 26 '16 at 18:31

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ So, you're looking for using not only $S_4$, but also one or more of the other coefficients as a secret. What would be the point of this? If you're trying to increase the size of the secret, you could just use a larger modulus or run multiple instances in parallel. $\endgroup$ – Artjom B. Apr 24 '16 at 23:45
  • $\begingroup$ Sure those could work too, but I'm curious if using the other co-efficients can be done, or if it's discouraged for any specific reasons. $\endgroup$ – Alan Wolfe Apr 25 '16 at 0:03
  • $\begingroup$ What you are looking for is multi-secret sharing. It has been a while since I've read up on it, but there are plenty of papers out there on the topic. $\endgroup$ – mikeazo Apr 25 '16 at 0:45
  • $\begingroup$ Thanks! I will read up on those. I'm actually just trying to understand why samshir's isn't a multi secret sharing algorithm - or if it is one, that'd be interesting to know too! $\endgroup$ – Alan Wolfe Apr 25 '16 at 1:00
  • $\begingroup$ @poncho, I'm not sure this is a duplicate. That other question seems to be asking about sharing a single secret but using other coefficients instead of the $x^0$ term of the polynomial. This one is asking about using sharing multiple secrets at once. $\endgroup$ – mikeazo Apr 25 '16 at 11:44
4
$\begingroup$

What you're looking for is called packed secret sharing. It was introduced by Franklin & Yung in:

If you have a polynomial of degree $< d$, with at most $t$ corrupt parties, then you can use a single polynomial to hide $d - t$ secrets. It's not hard to see that you can't hide more secrets than this. To share $k$ secrets, you need $k$ degrees of freedom. The $d$ coefficients induce $d$ degrees of freedom, but each of the $t$ corrupt parties learns one linear constraint.

Note: in what you described in your post you have a polynomial of degree $< 4$ so if you take the standard Shamir setting of $t=3$ corrupt parties you can only hide the one secret value. While it is true that 3 shares together don't reveal any individual secret coefficient, they reveal linear relationships that constrain the secret coefficients to a 1-dimensional subspace.

$\endgroup$
  • $\begingroup$ thanks! Do you know off hand if that is still true when using finite fields? It seems that they wouldn't get knowledge of linear constraints in that case. $\endgroup$ – Alan Wolfe Apr 25 '16 at 1:52
  • $\begingroup$ Finite fields as opposed to what? Shamir's scheme is defined over a finite field. $\endgroup$ – mikeazo Apr 25 '16 at 2:08
  • $\begingroup$ I wasn't sure if your answer applied to when not used over a finite field. Bad assumption, thanks for the info! $\endgroup$ – Alan Wolfe Apr 25 '16 at 2:20
  • 1
    $\begingroup$ Note that, depending on the $d-1$ shares being known, this 'linear relationship' can be "$S_2$ is this specific value". This sort of thing doesn't happen with Shamir's original method. $\endgroup$ – poncho Apr 25 '16 at 2:25

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