# Secret sharing thresold scheme with small shares

Shamir secret sharing1 is a common method to split an arbitrary secret (login credentials, symmetric or private key) between $$n$$ persons, so that a threshold of $$k$$ persons is required to rebuild the secret. The share given to each person is about the size of the original secret2.

The question asks how to make the shares as small as possible, if necessary at the expense of information-theoretic security.

More precisely: given parameters $$k,n,d$$ with $$1\le k\le n$$, we want a $$(k,n)$$ Thresold Scheme to share any given $$d$$-bit bitstring $$D$$, by efficiently producing $$n$$ shares $$D_i$$ each $$e$$-bit with $$e$$ a function of parameters, such that

1. Any set of $$k$$ shares makes it efficient to compute $$D$$.
2. The share size $$e$$ is as small as practical.
3. Some suitable security criteria is met, perhaps this CPA-like experiment:
• attacker chooses $$k,n,d,D_0,D_1$$ with $$D_0\ne D_1$$, and a set of $$k-1$$ share indexes
• referee chooses $$b\in\{0,1\}$$ uniformly at random, computes shares for $$D=D_b$$, reveals the designated shares
• attacker outputs their guess of $$b$$, and has vanishing advantage over a random choice.

How small can the share size $$e$$ be? Is it helpful to use a Memory-Hard Key Derivation Function like Argon2?

If we further assume that the secret $$D$$ was chosen uniformly at random (e.g. an ECC private key, with the public key known to all), can we further reduce $$e$$, and what's an appropriate security experiment?

1 Adi Shamir: How to share a secret, in CACM, 1979

2 Using a binary field $$\mathbb F_{2^d}$$ for $$d$$-bit secret yields $$e=d+\bigl\lceil\log_2 n\bigr\rceil$$

• Something simplified to the max improving over Shamir secret sharing: for $k=n=4,d=256$, it reaches $e=194$ with 128-bit security plus what Argon2 stretching adds, say 24 bits. Draw 4 random 128-bit keys $K_i$. Concatenate them in order into $K$. Use $K$ to encrypt $D$ into $C$ per a $d=256$-bit block cipher (e.g. 6 rounds of Feistel with Argon2 for the round functions). Split $C$ into 4 segments $C_i$ each 64-bit. A share $D_i$ is $K_i\mathbin\|C_i\mathbin\|\underline i$ where $\underline i$ encodes $i$ on 2 bits. To recover $D$, rebuild $K$ and $C$ from the shares, and decipher into $D$.
– fgrieu
Commented Feb 17 at 6:47
• Inspired by the first answer, and more appropriate for sharing a secret chosen by the scheme: We have $n$ parties expanding a short seed with a PRG, then engage in a Distributed Key Generation scheme like Pedersen's DKG to basically convert additive shares into threshold ones. Would this also fit the scope of the question? Or is there a requirement that the threshold scheme takes the secret to be shared as an input? Commented Feb 20 at 16:25
• @MarcIlunga: the problem statement asks that the shared secret is an input. I settled for that because it seems to me that otherwise we can share a seed of size as required for computational security (e.g. 128-bit) by Shamir's method, then expand it to $d$ with a PRG or KDF (perhaps a purposely slow MHKDF to gain some bits of security, because we can).
– fgrieu
Commented Feb 20 at 16:31
• Thanks for the clarifications. Yeah, this is an interesting scope in and of itself. One last comment on the out-of-scope option, it seems the distributed option seems to still have the advantage that for the same size of a share, there's "more to guess". Whereas an SSS split of a short seed, might still have a high guessing advantage in the computational like security notion outlined in the question. This might be wrong, tho, as I haven't sat down for formalize all this. Commented Feb 20 at 16:48
• Actually, my suggestion doesn't even work for the general case… It only works if $k=n$ which isn't probably interesting. Commented Feb 20 at 17:31

I will describe the classical (and simple) approach proposed by Krawczyk in:

Hugo Krawczyk, Secret Sharing Made Short, CRYPTO 1993

It is a $$t$$-out-of-$$n$$ threshold scheme. When the secret has $$\ell$$ bits, the shares have $$\ell/t + \lambda$$ bits, where $$\lambda$$ is the computational security parameter. (Compared to $$\ell$$ bits necessary for information-theoretic secret sharing.) The scheme has the following structure:

1. First divide the secret into $$n$$ pieces such that any $$t$$ pieces can reconstruct the entire secret. This is similar to secret sharing, but it doesn't include the requirement that $$t-1$$ pieces reveal nothing about the secret. As such, the pieces can be only $$\ell/t$$ bits long. This step is called information dispersal -- I will use the term "pieces" when referring to information dispersal and "shares" when referring to secret sharing.

2. Secret share an symmetric encryption key $$K$$ in an $$t$$-out-of-$$n$$ threshold scheme. Each user gets one share.

3. Encrypt each piece under $$K$$, and give each user one encrypted piece.

More detail follows:

• Let $$M \in \{0,1\}^\ell$$ be the value we wish to share. Split it into blocks $$M = M_0 \| \cdots \| M_{t-1}$$, so each block is $$\ell/t$$ bits.

• Define the polynomial $$P$$ as $$P(x) = M_0 + M_1 x + M_2 x^2 + \cdots + M_{t-1} x^{t-1}$$. The $$i$$'th "piece" is $$P(i)$$. Note that this polynomial is over $$GF(2^{\ell/t})$$. The difference between Shamir secret sharing is that the target value is not encoded as $$P(0)$$, but rather as the entire $$P$$. Clearly any $$t$$ pieces are enough to reconstruct $$M$$ in its entirety.

• Sample a symmetric encryption key $$K \gets \{0,1\}^\lambda$$.

• Secret share $$K$$ in a $$t$$-out-of-$$n$$ scheme (say, Shamir), and let $$S_i$$ be the $$i$$'th share.

• Encrypt each piece: $$C_i \gets \textsf{Enc}\bigl(K, P(i)\bigr)$$. If $$\textsf{Enc}$$ is a deterministic nonce-based encryption scheme,, then we can use each user's id ($$i$$) as nonce and avoid any ciphertext expansion -- i.e., $$C_i$$ can be exactly $$\ell/t$$ bits.

• Give to user $$i$$ the values $$S_i$$ and $$C_i$$, a total of $$\ell/t + \lambda$$ bits.

Now, any $$t$$ users can reconstruct $$M$$ by (1) reconstructing $$K$$ with the usual Shamir method, (2) using $$K$$ to decrypt their "pieces" of $$M$$, (3) reconstructing $$M$$ through polynomial interpolation.

To answer your other questions: I don't see how something like Argon2 is useful here. And your security definition for computationally secure secret sharing seems like the right one to me.

If you allow the shared secret to be random (i.e., let the secret sharing scheme itself "choose" the secret), then you can just let the first $$t$$ users' shares be short $$\lambda$$-bit seeds. Imagine each one of these users expanding their seed under a PRG to the full length, and then solve for the other $$n-t$$ users' shares. This is a fairly standard trick. I don't know of an obvious way to make all users' shares shorter, though.

• Great description and spot-on reference! We need to number the shares somehow, adding like $\log_2n$ bits in practice. I still think that Argon2 would allow to reduce $λ$, thus each share's size, by using key stretching on $K$. In practice we can gain 24 bits per share with tolerable delay on a PC, right? Note: the answer's last paragraph is about using the secret sharing to generate the secret, not taking advantage of the secret to share being uniformly random secret bits (but still an arbitrary input), as I have in mind with "If we further assume that the secret…"
– fgrieu
Commented Feb 20 at 16:45
• In my experience, optimizing something for "random inputs only" means "letting the construction choose the value". For example KEMs are a specialized PKE scheme that can only encrypt random payloads; as a result, the "encryption" (encapsulation) algorithm doesn't take the plaintext as input but gives it as output. Commented Feb 20 at 17:02
• The PRG idea is cool. I was wondering whether one could use that as part of a kind of DKG with inputs shares expanded by the PRG. But, that doesn't work since, the linear to threshold conversion would make the shares larger. Maybe it would be possible if there's such a thing as a “homomorphic” PRG? I am not even sure how this would work… Anyway, nice paper from Krawczyk that I should give a read :) Commented Feb 20 at 17:36
• Just to illustrate that we can make good use of a uniformaly random secret that's an input of the scheme: consider a 2 out of 2 sharing of a 256-bit ECC private key. We can apply a public 256-bit PRP to that (made slow using a MHKDF), then split the outcome in two 128-bit halves (+1 bit to recognize them). This seems to have 128-bit computational security plus what the MHKDF gives, and a better attack is the DLP against the ECC public key. The PRP is indispensable, otherwise there's a feasible attack knowing 1 share and the public key, using BS/GS or Pollard's rho.
– fgrieu
Commented Feb 21 at 9:58
• About @fgrieu's last remark: if you model the PRP as an ideal random permutation, this strategy can in fact be proven secure in the generic group model (however, no proof is known to the best of my knowledge without using idealized models on both sides) Commented Feb 25 at 22:13