I'm having some hard time understanding why the size of the share must be at least as large as the secret itself, why is this restriction imposed? What would happen if the share is smaller?
4
-
7$\begingroup$ One wouldn't be able to achieve information-theoretic security because some secrets can be ruled out. Of course information-theoretic security is a bit of an old-fashioned notion but in the case of secret sharing where we usually share symmetric keys anyways the overhead doesn't matter. $\endgroup$– SEJPMMay 18, 2019 at 19:54
-
$\begingroup$ @SEJPM could you give a practical example? $\endgroup$– TreyMay 18, 2019 at 20:27
-
$\begingroup$ Note that secret-sharing schemes are essentially never what you want in practice, because whenever you reconstitute the secret, one party invariably has unilateral power to abuse it. Generally what you really want are multiparty computations like threshold signatures where there is never a single secret in a single place that grants that unilateral power. $\endgroup$– Squeamish OssifrageMay 22, 2019 at 14:06
-
$\begingroup$ @SqueamishOssifrage unless of course you have multiparty computation reconstitute that secret and use it in an operation without leaking it out (like signing a document and return just the signature) so no one can ever learn the reconstituted secret. $\endgroup$– mtraceurApr 20 at 18:36
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
As SEJPM notes in the comments above, an information-theoretically secure threshold secret sharing scheme (such as Shamir's secret sharing) has two properties that it needs to satisfy:
- any subset of at least $t$ shares must allow the secret to be unambiguously reconstructed, and
- no set of $t-1$ or fewer shares may reveal any information about the secret (beyond the fact that it's a member of the finite set of possible secrets that the scheme can share).
Furthermore, the second property must be satisfied even if the attacker has unlimited computing power available. In particular, even if the attacker knows $t-1$ shares and can guess and test every possible value of the $t$-th share, they must not be able to rule out any possible values of the secret based on this information.
Now, if there were $n$ possible secrets but only $m < n$ possible values of the $t$-th secret, then this property could not possibly be satisfied: there would be (at least) $n - m > 0$ secrets that the attacker would be able to rule out based on the fact that no additional share, when combined with the $t-1$ shares they already know, can reconstruct that secret.
Thus, each share must have at least as many possible values as there are possible secrets. In particular, if the secret can be any $b$-bit bitstring, then all the shares must also be at least $b$ bits long.
answered May 22, 2019 at 9:41
$\begingroup$
$\endgroup$
In Shamir's secret-sharing scheme, the secret and the shares of the secret all are elements of a finite field, and so necessarily have the same size. In the Reed-Solomon code based variant of Shamir's secret-sharing scheme proposed by the late Bob McEliece and myself (R.J. McEliece and D.V. Sarwate, "On sharing secrets and Reed-Solomon codes", Communications of the ACM, v. 24, Issue 9, Sep 1981), the $n$ shares are $\frac 1k$-th the size of the secret, but these schemes don't have the perfect information-theoretic security of Shamir's scheme. See this answer.
