2
$\begingroup$

In standard Shamir's Secret Sharing schemes the shares are generated from randomly generated polynomials. I was wandering if it would be possible to create some predefined shares that a user would be able to use. e.g. in a threshold of 5, 2 shares are predefined by the user and the 3 others are generated like normal.

My thinking was that a user could have a few short memorable shares that are hashed to a length equal to or greater than the length of the secret and then that these could be used as shares. Is this possible and would this still be secure?

$\endgroup$
2
  • $\begingroup$ You should give the metrics of a few short memorable shares together with the SSS settings. $\endgroup$
    – kelalaka
    Commented Feb 19 at 18:24
  • 1
    $\begingroup$ Of course, if your secret is memorable, it might also be possible for others to guess it, thereby cutting you out of the share. $\endgroup$ Commented Feb 20 at 1:31

2 Answers 2

2
$\begingroup$

As Daniel S notes this is certainly possible, in the sense that the math behind Shamir's secret sharing allows you to arbitrarily choose up to $k$ of the field points that the polynomial will be interpolated through (i.e. the secret and up to $k-1$ shares, or up to $k$ shares if you don't care what the secret will be), where $k$ is the threshold for reconstructing the secret.

The real question, however, is whether choosing these points (other than the secret) non-randomly is secure. And my answer would be "no, it's not."

In particular, choosing any of the $k-1$ "arbitrary" shares by any method other than independently and uniformly at random destroys the perfect secrecy property of Shamir's secret sharing. In other words, if the probability distribution from which the arbitrary shares are chosen is not uniform, an attacker may be able to derive some (probabilistic) information about the secret from observing less than $k$ shares, basically because they may have a better-than-random chance of correctly guessing the remaining shares that they have not seen.

In particular:

  • If we choose $1 < j ≤ k$ shares non-randomly and the remaining $k - j$ "arbitrary" shares uniformly at random, an attacker who has access to the $k - j$ random shares and can guess the $j$ non-random shares can obviously recover the secret.

  • Furthermore, if we generate $n > k$ shares, the attacker who correctly guesses the $j$ non-random shares only needs to gain access to any $k - j$ of the remaining $n$ shares in order to recover the secret.

  • If the attacker knows (or suspects) that the $j$ non-random shares belong to a restricted subset of the field elements (e.g. that their numeric value encodes a date, or that their representation in base 256 encodes ASCII text), and has access to at least $k - j$ other shares, they may use this knowledge to narrow down the possible values that the secret may have (since some secret values would correspond to impossible values for the non-random shares).

  • If both the secret and at least one of the shares have low entropy (as an "easily memorable" share likely has), an attacker with access to enough other shares may be able to apply techniques from classical cryptanalysis to efficiently guess both the secret and the low-entropy share, similar to e.g. exploiting one-time-pad key reuse.

I'd really like to add a practical "toy example" of cracking a secret shared with a non-random share here, but I don't really have time to work one out right now. I may amend this answer later.

I'll just generally note that e.g. if the attacker knows $k-1$ shares, the secret $s$ and the remaining share $y$ (which can be any of the remaining shares!) are related via a bijective affine map $s = ay + b$, where the coefficients $a$ and $b$ are determined by the other shares and addition and multiplication are done in the finite field used for the sharing scheme. This suggests that techniques for breaking affine ciphers ought to be generally applicable, although details may vary depending on e.g. the size of the field used.

$\endgroup$
1
  • $\begingroup$ Sorry for the delay, this was an excellent answer! I was going to comment a few follow up questions but got locked out so instead I asked the questions here. I would love your insight if possible, thanks! $\endgroup$
    – euandeas
    Commented Mar 24 at 13:43
5
$\begingroup$

This is certainly possible. Given a threshold of $k$, we can set $k-1$ shares to be arbitrary and then determine the remaining shares. This is a natural consequence of all possible secrets being possible given $k-1$ shares.

To make this constructive, we assume the canonical Shamir set up where our secret is encoded as $f(0)$ and shares are $(i,f(i))$ for $i=1,\ldots,n$. If we specify any $k-1$ of the shares then we can construct unique $f(x)$ using Lagrange interpolation. Given $f(x)$ we can then construct the remaining $n-k$ shares.

How secure this is depends on how the pre-specified shares are constructed. If they are uniform random elements of the underlying finite field then the perfect privacy is preserved. If there is less entropy in the choice of shares then there is a corresponding drop in the entropy of the threshold. For a mix of different entropies the entropy of the shared secret will vary for different compromises of unrelated shares.

$\endgroup$
1
  • 1
    $\begingroup$ We can set $k-1$ shares to arbitrary if we have a specific preshared secret in mind; $k$ shares if any arbitrary secret will do (e.g. it's the seed to generate a private key, for example). Not saying that doing 'pot-luck' is necessarily a wise thing to do, though... $\endgroup$
    – poncho
    Commented Feb 19 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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