Shamir secret sharing: calculate rest of shares when you know secret and one share

Question

Using Shamir secret sharing, one is starting with a secret and end up with a number of shares based on a polynomial.

---

For example:

INPUT: secret: 123456 Shares:4 Threshhold:2

OUTPUT (4 shares calculated):

8017f1267477aa02cf0e6c6b36c29
802fd24948eab5d04fd84912dd801
8038336c5c9e4fd1c0d5157acb419
804e4486f0114ba54e7403f0cad51

---

My question is whether one can start with both a secret and a string - representing ultimately a share in the end state - and work his way into finding the rest of the shares?

For example:

INPUT: secret: 123456 Shares:4 Threshhold:2 Future Share: 8017f1267477aa02cf0e6c6b36c29

OUTPUT (Shares Calculated):

802fd24948eab5d04fd84912dd801
8038336c5c9e4fd1c0d5157acb419
804e4486f0114ba54e7403f0cad51

---

At the end you can express safely a secret in the form of shares as before - only this time you provided one of the shares as input to the process?

The benefit I see in the above process is in sharing secrets with a structure and very low entropy i.e. a Credit card number or a username. Splitting the secret in shares and sending them encrypted will still leave them vulnerable to brute force attack due to the inherent structure of the secret.

---

If though you:

1. use Diffie–Hellman key exchange for sharing 1 secret and use it as one of the future shares
2. produce the rest $t - 1$ shares
3. send the $t - 1$ shares encrypted

might this make the process more secure?

Answer 1

My question is whether one can start with both a secret and a string - representing ultimately a share in the end state - and work his way into finding the rest of the shares?

With $t-1$ shares and the secret, you can uniquely reconstruct the polynomial (and with that, generate all the rest of the shares, assuming you know their $x$ coordinates). With fewer shares than that, we can't reconstruct the polynomial (even with the secret), as there'll be at least $p^k$ (where $GF(p^k)$ is the field you're working in) possible polynomials.

In essence, the secret is just another share (with $x$ coordinate 0).

However...

Splitting the secret in shares and sending them encrypted will still leave them vulnerable to brute force attack due to the inherent structure of the secret

Nope. You appear to be speculating that an attacker with $t-1$ shares might guess the secret, and reconstruct the other shares based on that guess. They can certainly do that; however they have no way of determining whether that guess is correct (because all possible guesses will yield plausible looking shares).

In turns out that Shamir Secret Sharing is Informationally Secure; that is, with $t-1$ shares, you get no information about the shared secret, even if you have unbounded computation at your disposal. This statement assumes that the polynomial was generated truly randomly; however it makes no other assumptions.