Secret Sharing Scheme with variable share size?

Question

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.

Answer 1

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.)

Answer 2

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.