Skip to main content
Cryptography

Return to Answer

added 2 characters in body
Source Link
poncho
poncho
  • 150.6k
  • 11
  • 230
  • 369

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^x$$p^k$ (where $GF(p^x)$$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 random;randomly; however it makes no other assumptions.

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^x$ (where $GF(p^x)$ 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 random; however it makes no other assumptions.

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.

Source Link
poncho
poncho
  • 150.6k
  • 11
  • 230
  • 369

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^x$ (where $GF(p^x)$ 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 random; however it makes no other assumptions.