2
$\begingroup$

Shamir secret sharing techniques rely on polynomials for splitting and reconstructing. It's security properties are very good, i.e. it is impossible to reconstruct the secret when $t-1$ shares are given.

The coefficient for the highest term of a polynomial should be non-zero. But is it mandatory for other co-efficients of polynomials to be non-zero ?

Is there an impact to security guarantees when few co-efficients (other than the highest term) are zero ?

$\endgroup$
2
$\begingroup$

The coefficients must be uniformly chosen. If you do not choose your coefficients uniformly, then by Kerckhoff's principle, the attacker knows this, and that makes it easier than normal to reconstruct the polynomial, and thus to obtain the secret.

$\endgroup$
  • $\begingroup$ can you explain a bit more ? you mean an attacker is guessing the co-efficients to reconstruct the polynomial ? $\endgroup$ – sashank Oct 20 '15 at 12:17
1
$\begingroup$

For a polynomial f of degree n and randomly chosen coefficients, you need n+1 values of f to uniquely determine the coefficients. If you know m coefficients, you need only n-m+1 values of f to calculate the coefficients. For the secret sharing, this implies that fewer shares will suffice to caclulate the secret.

$\endgroup$
  • $\begingroup$ So does this mean , if few co-efficients are zeros , then attacker has lesser work in guessing them so less securre ? $\endgroup$ – sashank Oct 20 '15 at 13:05
  • $\begingroup$ This means the following: if you have a secret sharing system, which needs t shares to reconstruct the secret and it is known that s coefficients are zero, then t-s shares are sufficient to reconstruct the secret. $\endgroup$ – user27950 Oct 20 '15 at 14:22
0
$\begingroup$

The coefficient for the highest term in a polynomial should not actually be non zero as this results in an imperfect Shamir scheme.

This is because this assumption means that any attacker will know that the polynomial is definitely of a size t-1. Now if said attacker gained t-1 shares it is actually possible for him to compute a number S' that is not equal to S (the secret)

now although this doesn't seem like much it actually means that the scheme is not secure as the attacker definitely knows that S' is not the secret (as S' is not equal to S). Hence all coefficients should be chosen randomly and uniformly as even if the attacker has t-1 shares of a Shamir scheme in which the highest polynomial's coefficient is 0 there is now way (in an information theoretical security perspective) for him to know that he has computed the secret.

this is explained and proved in more detail on page 4 of the following paper: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.44.6353&rep=rep1&type=pdf

In relation to your question i do not believe that some of the coefficients being equal to 0 will result in any more or less work for an attacker as hwo are they going to know which coefficients are non zero or zero?

hope this helps :)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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