2
$\begingroup$

Is there a secret sharing scheme construction that allows the shares to have different sizes/lengths?

For example a (3,3) scheme, where shares 1 and 2 have large sizes while share 3 has a very small size.

$\endgroup$
4
$\begingroup$

While it's possible to artificially increase the length of some shares, it's not generally possible to make any of the shares shorter than they would be in normal Shamir's secret sharing.

In fact, at least for information-theoretically secure $(n,n)$ secret sharing schemes (i.e. those that require all participants to reconstruct the secret), it's easy to show that each share must be a random element of some set that is at least as large as the set of all possible secrets — if this were not the case, a colluding group of shareholders with access to all but one of the shares would be able to narrow down the set of possible shares to only those secrets that some possible value of the missing share could yield, contradiction the assumption of information-theoretic security.

In particular this implies that, if the secret can be any $\ell$-bit bitstring, then each share must also require at least $\ell$ bits to store (assuming that the lengths of the shares are public).


Ps. I believe the same result also holds for more general $(k,n)$ threshold secret sharing schemes, but I'm too tired to prove it off the top of my head right now.

If you don't require information-theoretic security, then there obviously exist practical schemes that can meet your requirements. For example, you can generate a random 128-bit AES key, encrypt your secret data using it, and then share the AES key among the $n$ shareholders using e.g. Shamir's secret sharing. Finally, append the encrypted secret to the first $n-k+1$ shares, where $k$ is the number of shareholders needed to reconstruct the AES key. (This ensures that, in any group of $k$ shareholders, there will be at least one shareholder with a "long share" containing the encrypted secret.)

$\endgroup$
  • $\begingroup$ The same result does indeed hold "for more general $(k,m)$ threshold secret sharing schemes" $\hspace{.62 in}$ - ​ Just replace "all but one of the shares" with "one share less than the threshold". $\hspace{1.42 in}$ $\endgroup$ – user991 Apr 6 '17 at 23:57
4
$\begingroup$

Adapt Shamir's scheme using a high degree, say degree $d$ polynomial.

Thus $d+1$ shares result. Share them out to 3 users, say giving $d/2$ shares to User 1, $d/2$ shares to User 2, and 1 share to User 3.

Edit: As noted by @Ilmari Karonen this doesn't allow you to make shares shorter due to information theoretic reasons explained in his answer.

$\endgroup$
  • $\begingroup$ Note, though, that this scheme only allows you to artificially make some shares longer, but not to make them any shorter. $\endgroup$ – Ilmari Karonen Apr 6 '17 at 0:10
  • 1
    $\begingroup$ I am aware of the info theoretic lower bounds and the inefficiency of my suggestion is obvious. The OP might not care, but maybe I should have mentioned this in the answer. $\endgroup$ – kodlu Apr 6 '17 at 0:15
  • $\begingroup$ @kodlu You still can :) $\endgroup$ – Maarten Bodewes Apr 6 '17 at 12:35

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.