1
$\begingroup$

Consider Shamir Secret Sharing Scheme (SSSS). This is completely unfounded, but my intuition tells me that the threshold k we set (AKA the number of shares required to construct the original secret) with regards to the total number of shares distributed (n) has a profound relation with the security of the whole system.

There are two scenarios I'm imagining where the threshold that would affect the security.

1) When k = n.

2) When k is dramatically lower than n.

Is any of this true?

$\endgroup$
  • 1
    $\begingroup$ What do you mean by "security"? $\endgroup$ – DrLecter Sep 5 '18 at 21:00
  • $\begingroup$ @DrLecter anything, integrity, confidentiality, ...etc $\endgroup$ – B.Li Sep 5 '18 at 21:06
4
$\begingroup$

Absolutely no information about the secret is gained by having fewer than $k$ shares. This is true regardless of what $k$ is, and for an adversary with unlimited computational power. The secret is information theoretically hidden.

In at nutshell the reason for this is that, for every possible value of the secret, there exists a polynomial that interpolates it and the all the shares obtained.

Each share is a point on a degree $k-1$ polynomial $f$. The secret is also a point on the polynomial, typically it is taken to be the point $(0,S)$ (i.e. $f(0)=S$, so the constant term of the polynomial is the secret $S$).

SSS uses the following fact: for every $k$ points, there exists exactly one polynomial of degree $k-1$ that goes through all these points. This can be shown using Legrange interpolation.

Let's say that you knew $k-1$ shares and were trying to figure out if $S'$ was the secret. You think to your self, well if $S'$ is the secret, then I must have that $f(0)=S'$. Then, I would have a total of $k$ points on $f$, namely $k-1$ from the shares I know of and I'm assuming you have the point $(0,S')$. Such an $f$ always exists and could very well have been the polynomial generated by SSS, and so I cannot rule out $S'$ as the secret.

This is true for every value of $S'$, and so I gain no information about $S$.

Edit: a tangent about the case of $k=n$. You can actually do something much simpler than SSS. Randomly sample $n-1$ bit strings $s_1,\cdots,s_{n-1}$. Then let $s_n=S\oplus s_1\oplus\cdots\oplus s_{n-1}$. Note that the $s_i$ satisfy $S=s_1\oplus\cdots\oplus s_n$. If any one share is unknown (WLOG, say $s_n$ is unknown), then $s_n$ is functionally a OTP that protects $S$.

$\endgroup$
2
$\begingroup$

There are 2 ways to think about the "security of the whole system" that I can see.

  1. If we think of the security as the absolute number of share holders that the adversary must compromise (or the number of share holders that must collude) in order to reconstruct the secret, then yes having $k=n$ is clearly more "secure" than $k<n$.
  2. If we think of security in terms of the advantage an adversary has in recovering the secret for an increasing number of compromised or colluding share holders (but strictly less than the threshold), then whether $k=n$ or $k<n$, the adversary has the same advantage. In both cases information theoretic security holds.

I'm not sure which security definition you mean, but these are the two ways I think about security in SSS.

$\endgroup$
  • $\begingroup$ I guess what I'm thinking of is that it seems "too good to be true" that we can choose any $n$ and any $k$ s.t. $k \le n$. For any $n$ participants, I don't see a reason why we should ever choose a $k$ s.t. $k < n$. $\endgroup$ – B.Li Sep 5 '18 at 21:25
  • $\begingroup$ Think about it this way. You give 5 of your friends shares of your secret. If $k=n$, then all an adversary has to do is knock off 1 of your friends and the secret is no longer available. So in addition to the confidentiality argument, there is also an availability argument. $\endgroup$ – mikeazo Sep 6 '18 at 0:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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